粒子群算法

 

粒子群算法是基于鸟群觅食的行为提出来的，每一个单一个体鸟视为搜索空间的一个粒子，都被视为问题的可能解，每个粒子都有一个由待优化函数决定的适应度函数，通过适应度值迭代更新粒子的位置和速度

粒子速度和位置的维度由问题的未知量决定，例如，求sin(∑_{i=1 to k}x_i-4)的最小值，如果k=2,那么速度V和位置X就是二维的，如果k=20，那么V和X都是20维的

设粒子i的历史最优位置为p,种群粒子的历史最优位置为pg,粒子按照下式来更新位置和速度：

v=w*v+c₁r₁(p-x)+c₂r₂(pg-x) c1和c2是加速常数，r1和r2是[0,1]之间的随机数

x=x+v

w*x表示粒子有维持自身速度的趋势，c₁r₁(p-x）表示粒子有向粒子历史最优位置移动的趋势，c₂r₂(pg-x)表示粒子有想群体最优位置逼近的趋势

算法流程：

1，初始化粒子群体，包括粒子种群数，每个粒子的速度和位置

2，计算各个粒子的适应度值

3，对于每个粒子，用它的适应度值与个体极值比较，如果fit>p,就p=fit

4,比较p和pg如果，p>pg，那么pg=p

5,根据上面的两式更新x和v

6，直到满足条件，否则返回2

下面的例子是由matlab实现的

function pso()
c1=2;
N=50;
D=30;
M=500;
c2=2;
w=0.7;
xx=zeros(1,D);
F=fitnessfunction(xx);
[x,y]=tso(@fitnessfunction,c1,c2,w,N,D,M);
end
%适应度函数
function F=fitnessfunction(x)
F=0;
for i=1:30
    F=F+x(i)^2+x(i)-6;
end
end

function [x,y]=tso(fitness,c1,c2,w,N,D,M)
%初始化位置和速度
for i=1:N
    for j=1:D
        x(i,j)=randn;
        v(i,j)=randn;
    end
end
%计算粒子的适应度值
for i=1:N
    p(i)=fitness(x(i,:));
    y(i,:)=x(i,:);
end
%找出当前种群最优位置
pg=x(N,:)
for i=1:(N-1)
    if fitness(x(i,:))<fitness(pg)
        pg=x(i,:);
    end
end
%更新速度和位置,相应地,随着迭代的进行,个体极值和全局极致也在变化
for i=1:M
    for j=1:N
        v(j,:)=w*v(j,:)+c1*rand*(y(j,:)-x(j,:))+c2*rand*(pg-x(j,:));
        x(j,:)=x(j,:)+v(j,:);
        if fitness(x(j,:))<p(j)
            p(j)=fitness(x(j,:));
            y(j,:)=x(j,:);
        end
        if p(j)<fitness(pg)
            pg=y(j,:)
        end
    end
end
disp('the position is:')
x=pg'
disp('the value is')
y=fitness(pg)
end