A brief introduction of backpack problem

1 [Knapsack problem] Knapsack problem is a NP complete combinatorial optimization problem. The problem is described as follows: given a group of items, each item has its own weight and price value. Within the limited total weight, how can we choose to make the total price of the item the highest? 2 [0-1 backpack problem] There are only two cases of loading/not loading a backpack for each item I. We have n items. Item J has a weight of Wj and a price of Pj. We assume that the weight and price of all goods are non-negative. The maximum weight a backpack can carry is W. If you limit the selection to zero or one of each item, the problem is called the 0-1 backpack problem. Let V(I,j) represent the maximum value of the first I items that can be loaded into the backpack with capacity J, then the dynamic programming function can be obtained: V(I,0) = V(0,j)=0; V(I,j) = V(i-1,j) j

j, Then the maximum value obtained by loading the first I items is the same as that obtained by loading the first I-1 items, that is, item I is not loaded into the backpack V(I,j) = Max {V(i-1,j), V(i-1, J-WI)+vi} j>wi // 1. If the i-th item is loaded into the backpack, then the value of the item in the backpack = the value of the former I-1 item into the j-WI backpack plus the value of the i-th item vi; 2. If the i-th item is not loaded into the backpack, then the value in the backpack = the value of the former i-1 item loaded into the backpack of capacity J. Take the greater value of the two. Step 1: Only load the first 1 item to determine the maximum value of the backpack under various circumstances; Step 2: Only pack the first two items to determine the maximum value of the backpack under various circumstances. Step n:… Finally, V(n,C) is the maximum value of n items in a backpack of capacity C. To get V(n,C), you have to push forward to V(n minus 1,C). If V(n,C)>V(n-1,C), the NTH item is packed into the backpack, and the first n-1 item is packed into the backpack with capacity C-WN; Otherwise, the NTH item is not loaded into the backpack and the first n-1 item is loaded into the backpack of capacity C. Make sure the first item is loaded into the backpack. When V(I,j)= V(i-1,j), xi = 0; When V(I,j) > V(i-1,j), xi = 1,j = j-wi;

2. Introduction of Firefly Optimization Algorithm (FA)

1 Introduction There are many kinds of firefly, mainly distributed in tropical areas. Most fireflies produce rhythmic flashes for a short time. This flash is due to a chemical reaction called bioluminescence, and the pattern of fireflies’ flashes varies from species to species. Firefly Algorithm (FA) is based on firefly flash behavior. It is an intelligent random algorithm for global optimization problems proposed by Yang Xin-She (2009) [1]. Fireflies glow through bioluminescence, a chemical reaction in their underbelly. This bioluminescence is an important part of firefly courtship rituals and is the main medium for male and female communication. The glow can also be used to lure a mate or prey. The flash also helps protect the firefly’s territory and warns predators to stay away from the habitat. In FA, it is thought that all fireflies are hermaphrodite and are attracted to each other regardless of sex. The algorithm is based on two key concepts: the intensity of the light emitted and the degree of attraction between the two fireflies.

Natural firefly behavior Natural firefly displays amazing flashing behavior when it comes to finding prey, attracting mates, and protecting territory. Fireflies mostly live in tropical environments. Generally, they produce cold light, such as green, yellow or reddish. The attraction of a firefly depends on its light intensity, and for any pair, the brighter firefly will attract the other. So, the less bright individual moves toward the brighter one, and the brightness of the light decreases with increasing distance. Firefly flash patterns can vary from species to species, and in some species, females use the phenomenon to prey on other species; Some fireflies exhibit synchronized flashing behavior in a large group to attract prey. Females observe the flashes of males from a stationary position. When they find an interesting flash, they respond by flashing, and the courtship ritual begins. Some females produce the flash patterns of other species to trap males and eat them.

3 Firefly AlgorithmThe firefly algorithm simulates the natural phenomena of fireflies. Real fireflies naturally exhibit a discrete flickering pattern, and firefly algorithms assume that they are always glowing. In order to simulate this flashing behavior of fireflies, Yang Xin-she proposed three rules (Yang, 2009) : (1) Assume that all fireflies are hermaphroditic, so a firefly may be attracted to any other firefly. (2) The brightness of fireflies determines their attractiveness, with brighter fireflies attracting darker ones. If no firefly is brighter than the firefly in question, it will move randomly. (3) The optimal value of the function is directly proportional to the brightness of fireflies. The light intensity (I) and the distance from the light source (r) obey the inverse square law. Therefore, due to the absorption of air, the light intensity (I) decreases with the increase of the distance from the light source. This phenomenon limits the visibility of fireflies to a very limited radius:The main implementation steps of firefly algorithm are as follows:Where I0 is the light intensity (brightest) at distance r=0, that is, its own brightness, which is related to the value of the objective function. The better the target value is, the brighter the brightness is. γ is the absorption coefficient, because fluorescence will gradually weaken with the increase of distance and the absorption of the transmission media, so the light intensity absorption coefficient is set to reflect this characteristic, which can be set as a constant. R is the distance between the two fireflies. Monotonically decreasing functions are sometimes used, as shown in the following formula.The second step is population initialization:Where t represents algebra, xt represents the current position of the individual, β0exp(-γ R2) is the attraction, and αε is the random term. The next step is to calculate the attraction between fireflies:β0 represents the maximum attraction at r=0. Next, the low-brightness firefly moves toward the brighter firefly:In the final stage, the light intensity is updated and all fireflies are ranked to determine the best solution for the moment. The main steps of firefly algorithm are as follows.

Begin Initialization algorithm basic parameters: set the number of fireflies n and the maximum attraction β0, light intensity absorption coefficient γ, step size factor α, maximum iteration times MaxGeneration or search accuracy ε; Initialization: Randomly initialize firefly positions and calculate firefly objective function values as their maximum fluorescence brightness I0; t=1
	whilePrecision (t < = MaxGeneration | | > epsilon) the calculation of relative brightness of fireflies in group I (type2) and attractiveness β (eq5), determine the movement direction of fireflies according to relative brightness; Update the spatial position of fireflies, and move the fireflies in the best position randomly (equation6); According to the updated firefly position, the brightness of firefly I0 was recalculated. t=t+1
	end whileOutput global extremum and optimal individual values. endCopy the code

Firefly algorithm has some similarities with particle swarm optimization (PSO) and bacterial foraging algorithm (BFA). In the position update equation, both FA and PSO have two main components: one is deterministic and the other is random. In FA, attractiveness is determined by two components: objective function and distance, while in BFA, attractiveness between bacteria also has two components: fitness and distance. When firefly algorithm is implemented, the whole population (such as N) needs two inner cycles, and a specific iteration needs one outer cycle (such as I), so the computational complexity of FA is O(n2I) in the worst case.

Three, some source code

% to solve0- 1Improved Firefly swarm algorithm for knapsack problem (WGFA) % Setting parameter: step size factor alpha=0.5, attraction beta0=1, medium absorption factor GAMA =1CLC clear All close all %% % alpha=0.2; % step size factor Randomness0-- 1
gamma=1.0; % medium absorption factor beta0=1.0; % Maximum attraction wmax=1; wmin=0.05; % weight, used to calculate the linearly decreasing inertia weight Pm=0.1; Function [xn]=f_GA(xn,M,n,V,P,W) [fn,index]=sort(P./W,'ascend');
coresV=sum((W.*xn)'); For I =1:M if coresV(I)>V for j=1:n if xn(I,index(j))==1 coresV(I)=coresV(I) -w (index(j)); if coresV(i)>V xn(i,index(j)) = 0; else xn(i,index(j)) = 0; break end end end end rest=[]; index2=[]; for k=1:n if xn(i,index(k))==0 rest(end+1)=fn(index(k)); index2(end+1)=index(k); end end rest=fliplr(rest); index2=fliplr(index2); for j=1:size(rest,2) coresV(i)=coresV(i)+W(index2(j)); if coresV(i)Copy the code

4. Operation results

Matlab version and references

1 matlab version 2014A

[1] Yang Baoyang, YU Jizhou, Yang Shan. Intelligent Optimization Algorithm and Its MATLAB Example (2nd Edition) [M]. Publishing House of Electronics Industry, 2016. [2] ZHANG Yan, WU Shuigen. MATLAB Optimization Algorithm source code [M]. Tsinghua University Press, 2017.