MATLAB 粒子群算法

MATLAB 粒子群算法

本文学习自：Particle Swarm Optimization in MATLAB - Yarpiz Video Tutorial 与《精通MATLAB智能算法》

1. 简介：

Particle Swarm Optimization ，粒子群优化算法，常用来找到方程的最优解。

2. 算法概述：

每次搜寻都会根据自身经验（自身历史搜寻的最优地点）和种群交流（种群历史搜寻的最优地点）调整自身搜寻方向和速度。

3. 算法优势：

• 相较于传统算法计算速度非常快，全局搜索能力也很强；
• PSO对于种群大小不十分敏感，所以初始种群设为500-1000，速度影响也不大；
• 粒子群算法适用于连续函数极值问题，对于非线性、多峰问题均有较强的全局搜索能力。

4. 算法基本原理：

示例：

A与B初始时在河的两侧，他们想要找到河最深处。如果A某时刻所在位置的深度比B的浅，A就会像B的方向走，反之亦然。 当A到达Global Minimum时，B会一直向着A前进，直到在optimum solution处汇合。

粒子群算法类似于这种搜索机制（search mechanism）

从上面的示例中我们得到两个准则

• Communication : 彼此互相通知

• Learning : 不停地学习以达最优解

  Learning the concept of better is the main problem that an optimizer should solve. Then an optimizer learns the concept of better, it is able to solve any kind of optimuzation.Because the solution of optimization problem is to find the best one . So if we know what is the better, we actually can discover the concept of best.

粒子群Swarm of particles : all particle –>optimization

• any particle is a candidate solution to the optimization problem we are going to solve it.
• any particle has a position in the search space of the optimization problem.
• The synthesis (合成) space is the set of all possible solutions to the optimization problem .
• We would like to find the best solution among these possible solutions in the searcher space

每个particle包含两个基本信息，Position & Velocity , 每个信息都是一个vector：

• we denote the position of particle i in time step T by Xi(t)→$\overrightarrow{X_i(t)}$ ，记录位置
• denote the velocity by Vi(t)→$\overrightarrow{V_i(t)}$ , 记录方向与速度

仅有上述两个信息还不够，我们之前提到过，每一个particle是会学习的。 每个particle还拥有下面两个信息（每个信息都是一个vector）：

• 每一个particle有它自己的记忆，会记住自己的best position , best experience. This is denoted by personal best, Pi(t)→$\overrightarrow{P_i(t)}$

• 当前时刻全局的最优解 Common best experience among the members ,denoted by gi(t)→$\overrightarrow{g_i(t)}$

  小结：PSO初始化位一群随机粒子，然后通过迭代找到最优解。在每一次迭代过程中，粒子通过跟踪两个极值来更新自己，一个事粒子本身所找到的最优解，这个解称为个体极值Pi(t)→$\overrightarrow{P_i(t)}$；另一个极值是整个种群目前找到的最优解，这个极值是全局极值 gi(t)→$\overrightarrow{g_i(t)}$ 。

  On every iteration of PSO , position and velocity of every particle updated.

find new position

根据平行四边形法则，已知个体极值与整体极值，有了新时刻的速度Vi→(t+1)$\overrightarrow{V_i}(t+1)$ ,会得到新的位置Xi→(t+1)$\overrightarrow{X_i}(t+1)$

状态转移方程：

vij→(t+1)=wvij→(t)+c1r1(pij(t)−xij→(t))+c2r2(gj(t)−xij→(t))(4-1)$$\begin{array}{}\text{(4-1)}& \overrightarrow{v_{ij}}(t+1)=w\overrightarrow{v_{ij}}(t)+c_1{r}_1(p_{ij}(t)-\overrightarrow{x_{ij}}(t))+c_2{r}_2(g_j(t)-\overrightarrow{x_{ij}}(t))\end{array}$$

xij→(t+1)=xij→(t)+vij→(t+1)(4-2)$$\begin{array}{}\text{(4-2)}& \overrightarrow{x_{ij}}(t+1)=\overrightarrow{x_{ij}}(t)+\overrightarrow{v_{ij}}(t+1)\end{array}$$

其中，c1,c2$c_1,c_2$为学习因子，也称加速常数（acceleration constant）;

r1,r2$r_1,r_2$，[0,1]范围内的均匀随机数。

式(1)右边由三部分组成：

• 第一部分为“惯性(inertia)”或“动量（MOMENTUM）”部分，反映了粒子的运动习惯，代表粒子有维持自己先前速度的趋势。
• 第二部分为“认知（cognition）”部分，反映了粒子对自身历史经验的记忆，代表粒子由向自身历史最佳位置逼近的趋势。
• 第三部分为“社会(social)”部分，反映了粒子间协同合作与知识共享的群体历史经验，代表粒子有向群体或领域历史最佳位置逼近的趋势。

5. 算法的运行参数

PSO算法一个最大的优点是不需要调节太多的参数，但是算法中少数几个参数却直接影响着算法的性能和收敛性。

基本粒子群算法有下述7个运行参数需要提前设定：

1. r：粒子群算法的种子数，对粒子群算法中种子数值可以随机生成也可以固定位一个初始的数值，要求能涵盖目标函数的范围内。
2. m：粒子群群体大小，即群体中所含个体的数量，一般取为20~40。在变两年比较多的时候可以取100以上较大的数。
3. max_d：一般为最大迭代次数以最小误差的要求满足的。粒子群算法的最大迭代次数，也是终止条件数。
4. r1,r2：两个在[0,1]之间变化的加速度权重系数随机产生。
5. c1,c2：加速常数，取随机2左右的值。
6. w：惯性权重产生的。
7. vk,xk：一个粒子的速度和位移数值，用粒子群算法迭代出每一组的数值。

6. 算法的基本流程

1. 初始化粒子群，包括群体规模N，每个粒子的位置xi$x_i$和速度vi$v_i$。
2. 计算吗每一个粒子的适应度值Fit[i]$Fit[i]$。
3. 计算每个粒子，用它的适应度值Fit[i]$Fit[i]$和个体极值pbest(i)$p_{best}(i)$比较，如果Fit[i]>pbest(i)$Fit[i]>p_{best}(i)$,则用Fit[i]$Fit[i]$替换掉pbest(i)$p_{best}(i)$。
4. 计算每个粒子，用它的适应度值Fit[i]$Fit[i]$和全局极值gbest(i)$g_{best}(i)$比较，如果Fit[i]>gbest(i)$Fit[i]>g_{best}(i)$,则用Fit[i]$Fit[i]$替换掉gbest(i)$g_{best}(i)$。
5. 根据式（4-1）和式（4-2）更新粒子的位置xi$x_i$和速度vi$v_i$。
6. 如果满足结束条件（误差足够好或到达最大循环次数）退出，否则返回步骤2.

7. 手动实现PSO

function[xm,fv] = PSO(fitness,N,c1,c2,w,M,D)
% c1,c2：学习因子
% w：惯性权重
% M：最大迭代次数
% D：搜索空间维数
% N：初始化群体个体数目


% 初始化种群的个体（可以在这里限定位置和速度的范围）
format long;
for i = 1:N
    for j=1:D
        x(i,j) = randn; % 随机初始化位置
        v(i,j) = randn; % 随即初始化速度
    end
end


% 先计算各个粒子的适应度，并初始化pi和pg
for i=1:N
    p(i) = fitness(x(i,:));
    y(i,:) = x(i,:);
end 
pg = x(N,:);  % pg为全局最优
for i=1:(N-1)
    if(fitness(x(i,:))<fitness(pg))
        pg = x(i,:);
    end
end


% 进入主要循环，按照公式依次迭代，直到满足精度要求
for t=1:M
    for i=1:N  % 更新速度、位移
        v(i,:)=w*v(i,:)+c1*rand*(y(i,:)-x(i,:))+c2*rand*(pg-x(i,:));
        x(i,:)=x(i,:)+v(i,:);
        if fitness(x(i,:)) < p(i)
            p(i)=fitness(x(i,:));
            y(i,:)=x(i,:);
        end
        if p(i) < fitness(pg)
            pg=y(i,:);
        end
    end
    Pbest(t)=fitness(pg);
end


% 输出结果
disp('目标函数取最小值时的自变量：')
xm=pg';
disp('目标函数的最小值为：')
fv=fitness(pg);

例1:求解下列函数的最小值：

f(x)=∑i=130x2i+xi−6$$f(x)=\sum _{i=1}^{30}{x}_i^2+x_i-6$$

function F=fitness(x)
F = 0;
for i = 1:30
    F = F+x(i)^2+x(i)-6;
end

输入：

x = zeros(1,30);
[xm1,fv1] = PSO(@fitness,50,1.5,2.5,0.5,100,30);

9. 自适应权重法

function[xm,fv] = PSO_adaptation(fitness,N,c1,c2,wmax,wmin,M,D)
% c1,c2：学习因子
% wmax：惯性权重最大值
% wmin：惯性权重最小值
% M：最大迭代次数
% D：搜索空间维数
% N：初始化群体个体数目


% 初始化种群的个体（可以在这里限定位置和速度的范围）
for i = 1:N
    for j=1:D
        x(i,j) = randn; % 随机初始化位置
        v(i,j) = randn; % 随即初始化速度
    end
end


%先计算各个粒子的适应度，并初始化个体最优解pi和整体最优解pg %
%初始化pi %
for i = 1:N
    p(i) = fitness(x(i,:)) ;
    y(i,:) = x(i,:) ;
end
%初始化pg %
pg = x(N,:) ;
%得到初始的全局最优pg %
for i = 1:(N-1)
    if fitness(x(i,:)) < fitness(pg)
        pg = x(i,:) ;
    end
end

%主循环函数，进行迭代，直到达到精度的要求 %
for t = 1:M
    for j = 1:N
        fv(j) = fitness(x(j,:)) ;
    end
    fvag = sum(fv)/N ;
    fmin = min(fv);
    for i = 1:N    %更新函数,其中v是速度向量，x为位置,i为迭代特征
        if fv(i) <= fvag
            w = wmin+(fv(i)-fmin)*(wmax-wmin)/(fvag-fmin) ;   %依据早熟收敛程度和适应度值进行调整
        else
            w = wmax ;
        end
        v(i,:) = w*v(i,:)+c1*rand*(y(i,:)-x(i,:))+c2*rand*(pg-x(i,:)) ;
        x(i,:) = x(i,:)+v(i,:) ;
        if fitness(x(i,:)) < p(i)
            p(i) = fitness(x(i,:)) ;
            y(i,:) = x(i,:) ;
        end
        if p(i) < fitness(pg)
            pg = y(i,:) ;
        end
    end
     Pbest(t) = fitness(pg) ;
end

%给出最后的计算结果 %
xm = pg' ;
fv = fitness(pg) ;

plot(Pbest)
xlabel('进化次数') ;
ylabel('适应度值') ;

例2：用自适应权重法求解函数

y=((sin(x21+x22))2−cos(x21+x22)+1)((1+0.1×(x21+x22))2)−0.7$$y=\frac{((sin(x_1^2+x_2^2){)}^2-cos(x_1^2+x_2^2)+1)}{((1+0.1\times (x_1^2+x_2^2){)}^2)-0.7}$$

其中，粒子数为50，学习因子均为2，惯性权重取值[0.6,0.8]，迭代步数为100.

建立目标函数：

function y = AdaptFunc(x)
    y = ((sin(x(1)^2+x(2)^2))^2-cos(x(1)^2+x(2)^2)+1)/((1+0.1*(x(1)^2+x(2)^2))^2)-0.7;
end

运行：

[xm,fv] = PSO_adaptation(@AdaptFunc,50,2,2,0.8,0.6,100,2)

10.线性递减权重法

 function [ xm,fv ] = PSO_lin(fitness,N,c1,c2,wmax,wmin,M,D)
format long ;
%给定初始化条件
% fitness：适应度函数
% N:       初始化种群数目
% c1:      个体最优化学习因子
% c2:      整体最优化学习因子
% wmax:    惯性权重最大值
% wmin:    惯性权重最小值
% M:       最大迭代次数      
% D:       搜索空间的维数
% xm:      最佳个体
% fv:      适应度值

%初始化种群个体%
for i = 1:N
    for j = 1:D
        x(i,j) = randn ;  %随机初始化位置
        v(i,j) = randn ;  %随机初始化速度
    end
end

%先计算各个粒子的适应度，并初始化个体最优解pi和整体最优解pg %
%初始化pi %
for i = 1:N
    p(i) = fitness(x(i,:)) ;
    y(i,:) = x(i,:) ;
end
%初始化pg %
pg = x(N,:) ;
%得到初始的全局最优pg %
for i = 1:(N-1)
    if fitness(x(i,:)) < fitness(pg)
        pg = x(i,:) ;
    end
end

%主循环函数，进行迭代，直到达到精度的要求 %
for t = 1:M
    for i = 1:N    %更新函数,其中v是速度向量，x为位置,i为迭代特征
        w = wmax-(t-1)*(wmax-wmin)/(M-1)
        v(i,:) = w*v(i,:)+c1*rand*(y(i,:)-x(i,:))+c2*rand*(pg-x(i,:)) ;
        x(i,:) = x(i,:)+v(i,:) ;
        if fitness(x(i,:)) < p(i)
            p(i) = fitness(x(i,:)) ;
            y(i,:) = x(i,:) ;
        end
        if p(i) < fitness(pg)
            pg = y(i,:) ;
        end
    end
    Pbest(t) = fitness(pg) ;
end

%给出最后的计算结果 %
xm = pg' ;
fv = fitness(pg) ;

11. 基于杂交（遗传算法）的算法

 function [ xm,fv ] = PSO_breed(fitness,N,c1,c2,w,bc,bs,M,D)
format long ;
%给定初始化条件
% fitness：适应度函数
% N:       初始化种群数目
% c1:      个体最优化学习因子
% c2:      整体最优化学习因子
% w:       惯性权重
% bc:      杂交概率
% bs:      杂交池的大小比率
% M:       最大迭代次数      
% D:       搜索空间的维数
% xm:      最佳个体
% fv:      适应度值

%初始化种群个体%
for i = 1:N
    for j = 1:D
        x(i,j) = randn ;  %随机初始化位置
        v(i,j) = randn ;  %随机初始化速度
    end
end

%先计算各个粒子的适应度，并初始化个体最优解pi和整体最优解pg %
%初始化pi %
for i = 1:N
    p(i) = fitness(x(i,:)) ;
    y(i,:) = x(i,:) ;
end
%初始化pg %
pg = x(N,:) ;
%得到初始的全局最优pg %
for i = 1:(N-1)
    if fitness(x(i,:)) < fitness(pg)
        pg = x(i,:) ;
    end
end

%主循环函数，进行迭代，直到达到精度的要求 %
for t = 1:M
    for i = 1:N    %更新函数,其中v是速度向量，x为位置,i为迭代特征
        v(i,:) = w*v(i,:)+c1*rand*(y(i,:)-x(i,:))+c2*rand*(pg-x(i,:)) ;
        x(i,:) = x(i,:)+v(i,:) ;
        if fitness(x(i,:)) < p(i)
            p(i) = fitness(x(i,:)) ;
            y(i,:) = x(i,:) ;
        end
        if p(i) < fitness(pg)
            pg = y(i,:) ;
        end
        r1 = rand() ;
        if r1 < bc
            numPool = round(bs*N) ;    %杂交池中随机选取numPool个种群%
            PoolX = x(1:numPool,:) ;   %杂交池中的初始杂交父辈位置%
            PoolVX = v(1:numPool,:) ;  %杂交池中的初始杂交父辈速度%
            for i = 1:numPool
                seed1 = floor(rand()*(numPool-1))+1 ;   %得到速度和位置的初始种子%
                seed2 = floor(rand()*(numPool-1))+1 ;
                pb = rand() ;
                childxl(i,:) = pb*PoolX(seed1,:)+(1-pb)*PoolX(seed2,:) ;   %子代的速度和位置计算
                childvl(i,:) = (pb*PoolVX(seed1,:)+pb*PoolVX(seed2,:))*norm(pb*PoolVX(seed1,:))/norm(pb*PoolVX(seed1,:)+pb*PoolVX(seed2,:)) ;
            end
            x(1:numPool,:) = childxl ;
            v(1:numPool,:) = childvl ;
        end
    end
end

%给出最后的计算结果 %
xm = pg' ;
fv = fitness(pg) ;

12. 基于自然选择

 function [xm,fv]=PSO_nature(fitness,N,c1,c2,w,M,D)
% fitness：待优化的目标函数;
% N：粒子数目;
% c1：学习因子1;
% c2：学习因子2;
% w：惯性权重;
% M：最大迭代次数;
% D：自变量的个数;
% xm：目标函数取最小值时的自变量值;
% fv：目标函数的最小值。
format long;
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,:);    %pg为全局最优
for i=1:(N-1)
    if fitness(x(i,:))
        pg=x(i,:);
    end
end
for t=1:M
    for i=1:N   %速度、位移更新
        v(i,:)=w*v(i,:)+c1*rand*(y(i,:)-x(i,:))+c2*rand*(pg-x(i,:));
        x(i,:)=x(i,:)+v(i,:);
        fx(i)=fitness(x(i,:));
        if fx(i)
            p(i)=fx(i);
            y(i,:)=x(i,:);
        end
        if p(i)
            pg=y(i,:);
        end
    end
    [sortf,sortx]=sort(fx);     %将所有的粒子按适应值排序
    exIndex=round((N-1)/2);
    x(sortx((N-exIndex+1):N))=x(sortx(1:exIndex));%将最好的一半粒子的位置替换掉最差的一半
    v(sortx((N-exIndex+1):N))=v(sortx(1:exIndex));%将最好的一半粒子的速度替换掉最差的一半
end
xm=pg';
fv=fitness(pg);

13.基于模拟退火

function [xm,fv]=PSO_lamda(fitness,N,c1,c2,lamda,M,D)
% fitness：待优化的目标函数;
% N：粒子数目;
% c1：学习因子1;
% c2：学习因子2;
% lamda:退火常数;
% M：最大迭代次数;
% D：自变量的个数;
% xm：目标函数取最小值时的自变量值;
% fv：目标函数的最小值。
format long;
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,:);    %pg为全局最优
for i=1:(N-1)
    if fitness(x(i,:))
        pg=x(i,:);
    end
end
T=-fitness(pg)/log(0.2);    %初始温度
for t=1:M
    groupFit=fitness(pg);
    for i=1:N           %当前温度下各个pi的适应值
        Tfit(i)=exp(-(p(i)-groupFit)/T);
    end
    SumTfit=sum(Tfit);
    Tfit=Tfit/SumTfit;
    pBet=rand();
    for i=1:N   %用轮盘赌策略确定全局最优的某个替代值
        ComFit(i)=sum(Tfit(1:i));
        if pBet<=ComFit(i)
            pg_plus=x(i,:);
            break;
        end
    end
    C=c1+c2;
   ksi=2/abs(2-C-sqrt(C^2-4*C));  %速度压缩因子
   for i=1:N
       v(i,:)=ksi*(v(i,:)+c1*rand*(y(i,:)-x(i,:))+c2*rand*(pg_plus-x(i,:)));
       x(i,:)=x(i,:)+v(i,:);
       if fitness(x(i,:))
           p(i)=fitness(x(i,:));
           y(i,:)=x(i,:);
       end
       if p(i)
           pg=y(i,:);
       end
   end
   T=T*lamda;
   Pbest(t) = fitness(pg) ;
end   
xm=pg';
fv=fitness(pg);

14. MATLAB粒子群工具箱

添加工具箱的具体步骤就不在这里说了，网上有很多。

例3:计算如下函数的最小值：

z=0.4∗(x−2)2+0.3∗(y−4)2−0.7,x∈[−40,40],y∈[−40,40]$$z=0.4\ast (x-2{)}^2+0.3\ast (y-4{)}^2-0.7,x\in [-40,40],y\in [-40,40]$$

• 定义待优化的MATLAB代码：

  function z = pso_func(in)
  n = size(in);
  x = in(:,1);
  y = in(:,2);
  nx = n(1);
  for i=1:nx
      temp = 0.4*(x(i)-2)^2+0.3*(y(i)-4)^2-0.7;
      z(i,:) = temp;
  end

• 调用PSO算法的核心函数：pso_Trelea_vectorized

  clear
  clc
  x_range = [-40,40];
  y_range = [-40,40];
  range = [x_range;y_range];
  Max_V = 0.2*(range(:,2)-range(:,1));
  n = 2;
  pso_Trelea_vectorized('pso_func',n,Max_V,range)

执行即可得到答案。

在PSO算法函数pso_Trelea_vectorized173行中，PSO参数设置如下：

Pdef = [100 2000 24 2 2 0.9 0.4 1500 1e-25 250 NaN 0 1];

• 100：MATLAB命令窗口进行显示的间隔数
• 2000：最大迭代次数
• 24：初始化种子数，种子数越多，越有可能收敛到全局最优值，但算法收敛速度慢
• 2：算法的加速度参数，分别影响局部最优值和全局最优值，一般不需要修改
• 0.9和0.4为初始时刻和收敛时刻的加权值，一般不需要修改
• 1500：迭代次数超过此值时，加权值取其最小
• 1e-25：算法终止条件之一，当两次迭代中对应的种群最优值小于此阈值时，算法停止
• 250：算法终止条件之一，取NaN时表示为非约束下的优化问题（即没有附加约束方程）
• 0：制定采用何种PSO类型，0表示通常的PSO算法
• 1：说明是否指定种子，0表示随机产生种子，1表示用户自行产生种子