粒子群算法(particleswarm optimization,PSO)由Kennedy和Eberhart在1995年提出,该算法对于Hepper的模拟鸟群(鱼群)的模型进行修正,以使粒子能够飞向解空间,并在最好解除降落,从而得到了粒子群优化算法

粒子群算法,也称粒子群优化算法或鸟群觅食算法(Particle Swarm Optimization),缩写为 PSO, 是近年来由J. Kennedy和R. C. Eberhart等开发的一种新的进化算法(Evolutionary Algorithm - EA)。PSO 算法属于进化算法的一种,和模拟退火算法相似,它也是从随机解出发,通过迭代寻找最优解,它也是通过适应度来评价解的品质,但它比遗传算法规则更为简单,它没有遗传算法的“交叉”(Crossover) 和“变异”(Mutation) 操作,它通过追随当前搜索到的最优值来寻找全局最优。这种算法以其实现容易、精度高、收敛快等优点引起了学术界的重视,并且在解决实际问题中展示了其优越性。粒子群算法是一种并行算法 

11.png 粒子群算法 人工智能算法大全_AI算法 第1张

标准粒子群算法(PSO) 

PSO从这种模型中得到启示并用于解决优化问题。PSO 中,每个优化问题的潜在解都是搜索空间中的一只鸟,称之为粒子。所有的粒子都有一个由被优化的函数决定的适值( fitness value) ,每个粒子还有一个速度决定它们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索。

PSO初始化为一群随机粒子(随机解),然后通过迭代找到最优解。在每一次迭代中,粒子通过跟踪两个极值来更新自己;第一个就是粒子本身所找到的最优解,这个解称为个体极值;另一个极值是整个种群目前找到的最优解,这个极值是全局极值。另外也可以不用整个种群而只是用其中一部分作为粒子的邻居,那么在所有邻居中的极值就是局部极值。

    假设在一个clip_image002 粒子群算法 人工智能算法大全_AI算法 第2张维的目标搜索空间中,有clip_image004 粒子群算法 人工智能算法大全_AI算法 第3张个粒子组成一个群落,其中第clip_image006 粒子群算法 人工智能算法大全_AI算法 第4张个粒子表示为一个clip_image002[1] 粒子群算法 人工智能算法大全_AI算法 第5张维的向量

clip_image009 粒子群算法 人工智能算法大全_AI算法 第6张clip_image011 粒子群算法 人工智能算法大全_AI算法 第7张

     第clip_image006[1] 粒子群算法 人工智能算法大全_AI算法 第8张个粒子的“飞行 ”速度也是一个clip_image002[2] 粒子群算法 人工智能算法大全_AI算法 第9张维的向量,记为

clip_image013 粒子群算法 人工智能算法大全_AI算法 第10张clip_image015 粒子群算法 人工智能算法大全_AI算法 第11张

     第clip_image006[2] 粒子群算法 人工智能算法大全_AI算法 第12张个粒子迄今为止搜索到的最优位置称为个体极值,记为

clip_image018 粒子群算法 人工智能算法大全_AI算法 第13张clip_image011[1] 粒子群算法 人工智能算法大全_AI算法 第14张

     整个粒子群迄今为止搜索到的最优位置为全局极值,记为

clip_image021 粒子群算法 人工智能算法大全_AI算法 第15张

      在找到这两个最优值时,粒子根据如下的公式(2-1)和( 2-2)来更新自己的速度和位置:

clip_image023 粒子群算法 人工智能算法大全_AI算法 第16张 (2-1)

clip_image025 粒子群算法 人工智能算法大全_AI算法 第17张 (2-2)

     其中:clip_image027 粒子群算法 人工智能算法大全_AI算法 第18张clip_image029 粒子群算法 人工智能算法大全_AI算法 第19张为学习因子,也称加速常数(acceleration constant),w为惯性因子,clip_image031 粒子群算法 人工智能算法大全_AI算法 第20张clip_image033 粒子群算法 人工智能算法大全_AI算法 第21张为[0,1]范围内的均匀随机数。式(2-1)右边由三部分组成,第一部分为“惯性(inertia)”或“动量(momentum)”部分,反映了粒子的运动“习惯(habit)”,代表粒子有维持自己先前速度的趋势;第二部分为“认知(cognition)”部分,反映了粒子对自身历史经验的记忆(memory)或回忆(remembrance),代表粒子有向自身历史最佳位置逼近的趋势;第三部分为“社会(social)”部分,反映了粒子间协同合作与知识共享的群体历史经验,代表粒子有向群体或邻域历史最佳位置逼近的趋势, clip_image035 粒子群算法 人工智能算法大全_AI算法 第22张,clip_image037 粒子群算法 人工智能算法大全_AI算法 第23张是粒子的速度,clip_image039 粒子群算法 人工智能算法大全_AI算法 第24张clip_image041 粒子群算法 人工智能算法大全_AI算法 第25张是常数,由用户设定用来限制粒子的速度。clip_image031[1] 粒子群算法 人工智能算法大全_AI算法 第26张clip_image033[1] 粒子群算法 人工智能算法大全_AI算法 第27张是介于clip_image045 粒子群算法 人工智能算法大全_AI算法 第28张之间的随机数

22.png 粒子群算法 人工智能算法大全_AI算法 第29张

自话粒子群算法(超简单实例)

我们需要一个pbest来记录个体搜索到的最优解,用gbest来记录整个群体在一次迭代中搜索到的最优解。速度和粒子位置的更新公式如下:

          v[i] = w * v[i] + c1 * rand() * (pbest[i] - present[i]) + c2 * rand() * (gbest - present[i])    

          present[i] = present[i] + v[i]                                                                                                          

    其中v[i]代表第i个粒子的速度,w代表惯性权值,c1c2表示学习参数,rand()表示在0-1之间的随机数,pbest[i]代表第i个粒子搜索到的最优值,gbest代表整个集群搜索到的最优值,present[i]代表第i个粒子的当前位置。

    我这里打了一个求解y=-x*(x-1) [-2,2]上最大值的粒子群算法,选用这个简单的例子主要是能让大家清楚的看到效果和粒子的运动方向,也方便理解我想说的一些观点。代码如下:

 

1 /*** 2  *  计算y=-x(x-1)的最大值 3  *  取值范围x--[-2,2] 4  * @author BreezeDust 5  * 6  */ 7 public class PSOTest { 8     int n=2; //粒子个数,这里为了方便演示,我们只取两个,观察其运动方向 9     double[] y;10     double[] x;11     double[] v;12     double c1=2;13     double c2=2;14     double pbest[];15     double gbest;16     double vmax=0.1;17     public void fitnessFunction(){//适应函数18         for(int i=0;i<n;i++){19             y[i]=-1*x[i]*(x[i]-2);20         }21     }22     public void init(){ //初始化23         x=new double[n];24         v=new double[n];25         y=new double[n];26         pbest=new double[n];27         /***28          * 本来是应该随机产生的,为了方便演示,我这里手动随机落两个点,分别落在最大值两边29          */30         x[0]=-0.5;31         x[1]=2.6;32         v[0]=0.01;33         v[1]=0.02;34         fitnessFunction();35         //初始化当前个体极值,并找到群体极值36         for(int i=0;i<n;i++){37             pbest[i]=y[i];38             if(y[i]>gbest) gbest=y[i];39         }40         System.out.println("start gbest:"+gbest);41     }42     public double getMAX(double a,double b){43         return a>b?a:b;44     }45     //粒子群算法46     public void PSO(int max){47         for(int i=0;i<max;i++){48             double w=0.4;49             for(int j=0;j<n;j++){50                 //更新位置和速度51                 v[j]=w*v[j]+c1*Math.random()*(pbest[j]-x[j])+c2*Math.random()*(gbest-x[j]);52                 if(v[j]>vmax) v[j]=vmax;53                 x[j]+=v[j];54                 //越界判断55                 if(x[j]>2) x[j]=2;56                 if(x[j]<-2) x[j]=-2;57                 58             }59             fitnessFunction();60             //更新个体极值和群体极值61             for(int j=0;j<n;j++){62                 pbest[j]=getMAX(y[j],pbest[j]);63                 if(pbest[j]>gbest) gbest=pbest[j];64                 System.out.println(x[j]+"  "+v[j]);65             }66             System.out.println("======"+(i+1)+"======gbest:"+gbest);67         }68         69         70     }71     public static void main(String[] args){72         PSOTest ts=new PSOTest();73         ts.init();74         ts.PSO(100);75     }76 77     78 79 }

    我们可以从打印的数据看出来,刚开始x[0]和x[1]分散在最大值两边,然后x[0]和x[1]逐渐聚集到1的周围,这里,我们已经收敛到x=1这个地方了,这正是我们要求的最大值,其最大值为1,下面是图解过程。

    1.初始状态

 粒子群算法 人工智能算法大全_AI算法 第30张

编辑


    2.第二次x[1]向左边移动了

 粒子群算法 人工智能算法大全_AI算法 第31张

编辑


   3.最后,两点聚集在1上,上面多个圈是他们聚集的过程,可以看出来,聚集过程是个越来越密集的过程。

 粒子群算法 人工智能算法大全_AI算法 第32张

编辑


粒子群算法的matlab实现

粒子群算法是一门新兴算法,此算法与遗传算法有很多相似之处,其收敛于全局最优解的概率很大。

①相较于传统算法计算速度非常快,全局搜索能力也很强;

②PSO对于种群大小不十分敏感,所以初始种群设为500-1000,速度影响也不大;

③粒子群算法适用于连续函数极值问题,对于非线性、多峰问题均有较强的全局搜索能力。


Step1:确定一个粒子的运动状态是利用位置和速度两个参数描述的,因此初始化的也是这两个参数;

Step2:每次搜寻的结果(函数值)即为粒子适应度,然后记录每个粒子的个体历史最优位置和群体的历史最优位置;

Step3:个体历史最优位置和群体的历史最优位置相当于产生了两个力,结合粒子本身的惯性共同影响粒子的运动状态,由此来更新粒子的位置和速度。


    粒子群算法中所涉及到的参数有:

       种群数量:粒子群算法的最大特点就是速度快,因此初始种群取50-1000都是可以的,虽然初始种群越大收敛性会更好,不过太大了也会影响速度;

       迭代次数:一般取100~4000,太少解不稳定,太多浪费时间。对于复杂问题,进化代数可以相应地提高;

       惯性权重:该参数反映了个体历史成绩对现在的影响,一般取0.5~1;

       学习因子:一般取0~4,此处要根据自变量的取值范围来定,并且学习因子分为个体和群体两种;

       空间维数:粒子搜索的空间维数即为自变量的个数。

       位置限制:限制粒子搜索的空间,即自变量的取值范围,对于无约束问题此处可以省略。

       速度限制:如果粒子飞行速度过快,很可能直接飞过最优解位置,但是如果飞行速度过慢,会使得收敛速度变慢,因此设置合理的速度限制就很有必要了。


      不同于遗传算法,粒子群算法不需要编码,直接利用粒子的位置来表示自变量,每个粒子的位置都由自变量的个数和取值范围决定,而速度由自变量的个数和速度限制决定,形式如下,其中d代表空间维数(自变量数):


        下面我们用一个例子来帮助理解,对于函数 f=x*sin(x)*cos(2*x)-2*x*sin(3*x) ,求其在区间[0,20]上该函数的最大值。首先我们需要画出函数的图像,如下图:


       多峰问题对于算法的检验效果最佳,而上图显然是一个简单的非等距、非等高的多峰一元函数。

初始化种群

        已知位置限制[0,20],由于一维问题较为简单,因此可以取初始种群N 为50,迭代次数为100,当然空间维数d 也就是1。

        位置和速度的初始化即在位置和速度限制内随机生成一个N x d 的矩阵,对于此题,位置初始化也就是在0~20内随机生成一个50x1的数据矩阵,而对于速度则不用考虑约束,一般直接在0~1内随机生成一个50x1的数据矩阵。

        此处的位置约束也可以理解为位置限制,而速度限制是保证粒子步长不超限制的,一般设置速度限制为[-1,1]。

        粒子群的另一个特点就是记录每个个体的历史最优和种群的历史最优,因此而二者对应的最优位置和最优值也需要初始化。其中每个个体的历史最优位置可以先初始化为当前位置,而种群的历史最优位置则可初始化为原点。对于最优值,如果求最大值则初始化为负无穷,相反地初始化为正无穷。

       每次搜寻都需要将当前的适应度和最优解同历史的记录值进行对比,如果超过历史最优值,则更新个体和种群的历史最优位置和最优解。

       通过之前的参数设定可以得到如下的初始分布图:


速度与位置的更新

        速度和位置更新是粒子群算法的核心,其原理表达式和更新方式如下:

       每次更新完速度和位置都需要考虑速度和位置的限制,需要将其限制在规定范围内,此处仅举出一个常规方法,即将超约束的数据约束到边界(当位置或者速度超出初始化限制时,将其拉回靠近的边界处)。当然,你不用担心他会停住不动,因为每个粒子还有惯性和其他两个参数的影响。


代码如下:

clc;clear;close all;

%% 初始化种群

f= @(x)x .* sin(x) .* cos(2 * x) - 2 * x .* sin(3 * x); % 函数表达式

figure(1);ezplot(f,[0,0.01,20]);

N = 50;                         % 初始种群个数

d = 1;                          % 空间维数

ger = 100;                      % 最大迭代次数     

limit = [0, 20];                % 设置位置参数限制

vlimit = [-1, 1];               % 设置速度限制

w = 0.8;                        % 惯性权重

c1 = 0.5;                       % 自我学习因子

c2 = 0.5;                       % 群体学习因子 

for i = 1:d

    x = limit(i, 1) + (limit(i, 2) - limit(i, 1)) * rand(N, d);%初始种群的位置

end

v = rand(N, d);                  % 初始种群的速度

xm = x;                          % 每个个体的历史最佳位置

ym = zeros(1, d);                % 种群的历史最佳位置

fxm = zeros(N, 1);               % 每个个体的历史最佳适应度

fym = -inf;                      % 种群历史最佳适应度

hold on

plot(xm, f(xm), 'ro');title('初始状态图');

figure(2)

%% 群体更新

iter = 1;

record = zeros(ger, 1);          % 记录器

while iter <= ger

     fx = f(x) ; % 个体当前适应度   

     for i = 1:N      

        if fxm(i) < fx(i)

            fxm(i) = fx(i);     % 更新个体历史最佳适应度

            xm(i,:) = x(i,:);   % 更新个体历史最佳位置

        end 

     end

if fym < max(fxm)

        [fym, nmax] = max(fxm);   % 更新群体历史最佳适应度

        ym = xm(nmax, :);      % 更新群体历史最佳位置

 end

    v = v * w + c1 * rand * (xm - x) + c2 * rand * (repmat(ym, N, 1) - x);% 速度更新

    % 边界速度处理

    v(v > vlimit(2)) = vlimit(2);

    v(v < vlimit(1)) = vlimit(1);

    x = x + v;% 位置更新

    % 边界位置处理

    x(x > limit(2)) = limit(2);

    x(x < limit(1)) = limit(1);

    record(iter) = fym;%最大值记录

%     x0 = 0 : 0.01 : 20;

%     plot(x0, f(x0), 'b-', x, f(x), 'ro');title('状态位置变化')

%     pause(0.1)

    iter = iter+1;

end

figure(3);plot(record);title('收敛过程')

x0 = 0 : 0.01 : 20;

figure(4);plot(x0, f(x0), 'b-', x, f(x), 'ro');title('最终状态位置')

disp(['最大值:',num2str(fym)]);

disp(['变量取值:',num2str(ym)]);