Initialize the particle position: Generate binary code according to a certain policy;

Speed update formula: speed x inertia weight + (individual optimal position – current position) x learning factor 1 x random number + (global optimal position – current position) x learning factor 2 x random number.



Position updating formula: Probability mapping. Sigmoid function is used to map the velocity to the interval [0, 1] as the probability, which is the probability that the next value of the particle is 1.



The absolute probability of change in position: The change from 0 to 1 and the change from 1 to 0 are called absolute changes; The probability is expressed as:

[Backpack 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?

[0-1 backpack problem]

For each item I, there are only two cases of loading or not loading the backpack.

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; // Put the first I items into the backpack with capacity 0 and the first 0 items into the backpack with capacity j, both of value 0

V(I,j) = V(i-1,j) j<wi // If the weight of the ith item is greater than the capacity of the backpack wi>j, then the maximum value of the item I before loading is the same as that of the item I-1 before loading, 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.

Get:

When V(I,j)= V(I -1,j), xi = 0;

When V(I,j) > V(i-1,j), xi = 1,j = j-wi;

Backpack problem: For n items with volume AJ and value Cj, how to fit them into a backpack with total volume B to maximize the total value of the selected items? %n = 10% AJ =[95, 4, 60, 32, 23, 72, 80, 62, 65, 46] % Cj =[55, 10, 47, 5, 4, 50, 8, 61, 85, 87] %b=269 % % a=[95 4 60 32 23 72 80 62 65 46]; % item volume c=[55 10 47 5 4 50 8 61 85 87]; % Item value b=269; % Backpack weight limit % % % initializer: Dim=10; % Particle dimension xSize=20; % population MaxIt=30; % Maximum number of iterations C1 =0.7; C2 = 0.7; % define acceleration factor w=0.8; Inertia factor % % % define web browser http://www.ilovematlab.cn/thread-12680-1-1.html - A = repmat (A, xSize, 1); % extend a to a 30*10 matrix C=repmat(C,xSize,1); % extend c to a 30*10 matrix x=round(rand(xSize,Dim)); % Randomly select a 30*10 0/1 matrix as the initial particle position v=rand(xSize,Dim); % Particle initial speed xbest=zeros(xSize,Dim); % Initial best position for a single particle fxBest =zeros(xSize,1); %xbest fitness gbest= Zeros (1,Dim); % initial optimal position of particle swarm FGBest =0; % gBest fitness % % % % selection of particle swarm optimal position and single particle optimal position % iterative loop algorithm: iter=0; while iter<MaxIt iter=iter+1; fx=sum((C.*x)'); Sx =sum((A.*x)'); sx=sum(A.*x)'); % limit function, volume of items in backpack for I =1:xSize if sx(I)>269 fx(I)=0; End end for I =1:xSize if FXBest (I)<fx(I) fxBest (I)=fx(I); xbest(i,:)=x(i,:); % If fgBest < Max (fxBest) [FGBest,g]= Max (fxBest); end end if FGBest < Max (fxBest) [FGBest,g]= Max (fxBest); gbest=xbest(g,:); % End for I =1:xSize if x(I,:)==gbest x(I,:)=round(rand(1,Dim)); End end R1=rand(xSize,Dim); end end R1=rand(xSize,Dim); R2=rand(xSize,Dim); v=v*w+c1*R1.*(xbest-x)+c2*R2.*(repmat(gbest,xSize,1)-x); % Use velocity iteration formula to generate new velocity x=x+v; For I =1:xSize for j=1:Dim if x(I,j)<0.5 x(I,j)=0; else x(i,j)=1; End % % fgBest sgBest =sum((a.*gbest)') gbestCopy the code