PSO 粒子群算法

二维动态演示视频

1 什么是粒子群算法？

​ 粒子群算法源于复杂适应系统（Complex Adaptive System,CAS）。CAS理论于1994年正式提出，CAS中的成员称为主体。比如研究鸟群系统，每个鸟在这个系统中就称为主体。主体有适应性，它能够与环境及其他的主体进行交流，并且根据交流的过程“学习”或“积累经验”改变自身结构与行为。整个系统的演变或进化包括：新层次的产生（小鸟的出生）；分化和多样性的出现（鸟群中的鸟分成许多小的群）；新的主题的出现（鸟寻找食物过程中，不断发现新的食物）。

首先，主体是主动的、活动的。

主体与环境及其他主体是相互影响、相互作用的，这种影响是系统发展变化的主要动力。

环境的影响是宏观的，主体之间的影响是微观的，宏观与微观要有机结合。

最后，整个系统可能还要受一些随机因素的影响。

粒子群算法就是对一个CAS系统——鸟群社会系统的研究得出的。

粒子群算法（ Particle Swarm Optimization, PSO）最早是由Eberhart和Kennedy于1995年提出，它的基本概念源于对鸟群觅食行为的研究。设想这样一个场景:一群鸟在随机搜寻食物，在这个区域里只有一块食物，所有的鸟都不知道食物在哪里，但是它们知道当前的位置离食物还有多远。那么找到食物的最优策略是什么呢?最简单有效的就是搜寻目前离食物最近的鸟的周围区域。

PSO算法就从这种生物种群行为特性中得到启发并用于求解优化问题。在PSO中，每个优化问题的潜在解都可以想象成d维搜索空间上的一个点，我们称之为“粒子”（Particle），所有的粒子都有一个被目标函数决定的适应值(Fitness Value )，每个粒子还有一个速度决定他们飞翔的方向和距离，然后粒子们就追随当前的最优粒子在解空间中搜索。Reynolds对鸟群飞行的研究发现。鸟仅仅是追踪它有限数量的邻居但最终的整体结果是整个鸟群好像在一个中心的控制之下.即复杂的全局行为是由简单规则的相互作用引起的。

2.粒子群算法通俗描述

​ PSO模拟的是鸟群的捕食行为。设想场景：一群鸟在随机搜索食物。在这个区域里只有一块食物。所有鸟都不知道食物在哪里。但是他们知道当前的位置距离食物还有多远。那么找到食物的最优策略是什么？最简单有效的就是搜寻目前离食物最近的鸟的周围区域。鸟群在整个搜寻过程中，通过相互传递各自的信息，让其他鸟知道自己当前的位置，通过这样的协作来判断自己找到的是不是最优解，同时也将最优解的信息传递给整个鸟群，最终整个鸟群都能聚集在食物源的周围，即找到了最优解。

​ PSO中，每个优化问题的解都是搜索空间的一只鸟，我们称之为“粒子”。所有的粒子都有一个被优化的函数决定的适应值，每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索。

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

3. 粒子抽象

关于速度和位置
粒子群算法统领给设计一种无质量的粒子来模拟鸟群中的鸟，粒子仅有两个属性：速度和位置，速度代表移动的快慢，粒子代表移动的方向。

鸟被抽象为没有质量和体积的微粒（点），并延伸到N维空间，粒子i在N维空间的位置表示为矢量Xi = （x1，x2，…，xn），飞行速度表示为矢量Vi=（v1，v2，…，vn）。

每个粒子都有一个由目标函数决定的适应值，并且知道自己到目前为止发现的最好位置（pbest）和现在的位置Xi。这个可以看作是粒子自己的飞行经验。除此之外，每个粒子还知道到目前为止整个群体中所有粒子发现的最好的位置（gbest），这个可以看作是粒子同伴的经验。粒子就是通过自己的经验和同伴中最好的经验来决定下一步运动。

速度和位置的更新

PSO初始化为一群随机粒子（随机解）。然后通过迭代找到最优解。在每一次迭代中，粒子通过跟踪两个“极值（pbest和gbest）”来更新自己。在找到这两个最优值后，粒子通过下面的公式来更新自己的速度和位置。

对于公式（1）：

• 公式（1）中的第一部分称为记忆项，表示上次速度大小和方向的影响；
• 公式（1）中的第二部分称为自身认知项，是从当前点指向粒子自身最好点的一个矢量，表示粒子的动作来源于自己经验的部分；
• 公式（1）中的第三部分称为群体认知项，是一个从当前点指向种群最好点的矢量，反映了粒子间的协调合作和知识共享。粒子就是通过自己的经验和同伴中最好的经验来决定下一步的运动。

边界处理

标准PSO算法流程

代码

main.m

%% 粒子群算法求解x1^2 + x2^2的最小值
clc;clear all;close all;
%粒子群参数设定
pop = 100;%种群数量
dim = 2;%变量维度
ub = [10,10];%粒子上边界信息
lb = [-10,-10];%粒子下边界信息
vmax = [2,2];%粒子的速度上边界
vmin = [-2,-2];%粒子的速度下边界
maxIter = 100;%最大迭代次数
fobj = @(x) fun(x);%设置适应度函数为fun(x); 
%粒子群求解问题
[Best_Pos,Best_fitness,IterCurve,HistoryPosition,HistoryBest] = pso(pop,dim,ub,lb,fobj,vmax,vmin,maxIter);


%% 绘制每一代粒子群分布
for i = 1:maxIter
   Position = HistoryPosition{i};%获取当前代位置
   BestPosition = HistoryBest{i};%获取当前代最佳位置
   
   
   
   
   figure(1)
   plot(Position(:,1),Position(:,2),'g*','linewidth',0.5); 
   hold on;
   plot(BestPosition(1),BestPosition(2),'ro','linewidth',0.5); 
   hold on;
   plot(0,0,'bp','linewidth',1); 
   grid on;
   axis([-10 10,-10,10])
   legend('粒子','最佳粒子','最值点');
   title(['第',num2str(i),'次迭代']);
   hold off
end

%绘制迭代曲线
figure(2);
plot(IterCurve,'r-','linewidth',1.5);
grid on;%网格开
title('粒子群迭代曲线')
xlabel('迭代次数')
ylabel('适应度值')

disp(['求解得到的x1，x2为',num2str(Best_Pos(1)),'   ',num2str(Best_Pos(2))]);
disp(['最优解对应的函数值为：',num2str(Best_fitness)]);

initialization.m

%% 粒子群初始化函数
function X = initialization(pop,ub,lb,dim)
    %pop:为种群数量
    %dim:每个粒子群的维度
    %ub:为每个维度的变量上边界，维度为[1,dim];
    %lb:为每个维度的变量下边界，维度为[1,dim];
    %X:为输出的种群，维度[pop,dim];
    X = zeros(pop,dim); %为X事先分配空间
    for i = 1:pop
       for j = 1:dim
           X(i,j) = (ub(j) - lb(j))*rand() + lb(j);  %生成[lb,ub]之间的随机数
       end
    end
end

完整代码链接