Zephus 发表于 2023-3-2 14:10

粒子群优化算法(Particle Swarm Optimization, PSO ...

一、背景简介

粒子群算法(Particle Swarm Optimization,简称PSO)是1995年Eberhart博士和Kennedy博士一起提出的。粒子群算法是通过模拟鸟群捕食行为设计的一种群智能算法。区域内有大小不同的食物源，鸟群的任务是找到最大的食物源（全局最优解），鸟群的任务是找到这个食物源。
鸟群在整个搜寻的过程中，每只鸟沿着自己判定的方向进行搜索，并在搜索的过程中记录自己曾经找到过食物且量最多的位置，同时所有的鸟都共享自己每一次发现食物的位置以及食物的量，通过相互传递各自的信息，鸟群就知道当前在哪个位置食物的量最多。在搜索的过程中每只鸟都会根据自己记忆中食物量最多的位置和当前鸟群记录的食物量最多的位置调整自己接下来搜索的方向。最终，整个鸟群都能聚集在食物源周围。即我们所说的找到了最优解，问题收敛。
粒子群算法属于进化算法的一种。和模拟退火算法相似，它也是从随机解出发，通过迭代寻找最优解，它也是通过适应度来评价解的品质；和遗传算法相比，规则更为简单，没有遗传算法的“交叉”(Crossover) 和“变异”(Mutation) 操作，它通过追随当前搜索到的最优值来寻找全局最优。这种算法具有实现容易、精度高、收敛快等优点。是一种并行算法。
二、算法讲解

粒子群算法中，我们将鸟抽象成一个个粒子，粒子群算法初始化一群随机粒子(随机解)，然后通过迭代找到最优解。
粒子是每个优化问题的候选解。粒子由位置和速度两个参数进行描述，分别表示候选解所在的位置和移动的速度。
所有的粒子都有一个由被优化的函数决定的适应值(fitness value)，用于评价粒子优劣的值，一般设置为目标函数值。
在每一次迭代中，粒子通过跟踪两个"极值"来更新自己。一个就是粒子本身所找到的最优解，这个解叫做个体极值pBest。另一个极值是整个种群目前找到的最优解，这个极值是全局极值gBest。

1.标准PSO算法的流程：


[*]随机初始化粒子群的位置和速度(种群规模N)；
[*]计算每个粒子的适应值；
[*]对每个粒子，将其适应值与其经过的最好位置pbest作比较，如果当前值更好，更新pbest（历史最优）；
[*]对每个粒子，将其适应值与其经过的最好位置gbest作比较，如果当前值更好，更新gbest（全局最优）；
[*]调整粒子速度和位置；
[*]满足结束条件，结束；否则，转到第2）步。




2.各个参数与表达式含义

初始的参数：


[*]n ：粒子个数
一个正整数，可行解的规模，推荐取值范围：，简单问题一般取20~40，较难或特定类别的问题可以取100~200。较小的种群规模容易陷入局部最优；较大的种群规模可以提高收敛性，更快找到全局最优解，但是相应地每次迭代的计算量也会增大；当种群规模增大至一定水平时，再增大将不再有显著的作用。

[*]D ：粒子维度
粒子搜索的空间维数即为自变量的个数。

[*]K ：迭代次数
推荐取值范围：，典型取值：60、70、100；这需要在优化的过程中根据实际情况进行调整，迭代次数太小的话解不稳定，太大的话非常耗时，没有必要。

[*]f\left( x \right)：在位置x时的适应度值(一般取目标函数值)，搜索到的最优位置的适应值（优化目标函数的值）

速度公式：

粒子第 d 步的速度=上一步自身的速度惯性+自我认知部分+社会认知部分
v_{i}^{d}=wv_{i}^{d-1}+c_1r_1(pbest_{i}^{d}-x_{i}^{d})+c_2r_2(gbest^d-x_{i}^{d})\tag{1}
第一项：惯性部分
由惯性权重和粒子自身速度构成，表示粒子对先前自身运动状态的信任。 第二项：认知部分
表示粒子本身的思考，即粒子自己经验的部分，可理解为粒子当前位置与自身历史最优位置之间的距离和方向。第三项：社会部分
表示粒子之间的信息共享与合作，即来源于群体中其他优秀粒子的经验，可理解为粒子当前位置与群体历史最优位置之间的距离和方向。

[*]c_1 ：粒子的个体学习因子，也称为个体加速因子
表示粒子下一步动作来源于自己经验部分所占的权重；若为0，则是无私型粒子群算法，“只有社会，没有自我”，迅速丧失群体多样性，易陷入局部最优而无法跳出。

[*]c_2 ：粒子的社会学习因子，也称为社会加速因子
表示粒子下一步动作来源于其它粒子经验部分所占的权重；若为0，则是自我认知型粒子群算法，“只有自我，没有社会”，完全没有信息的社会共享，导致算法收敛速度缓慢 。

[*]r_1,r_2：上的随机数。
[*]w ：速度的惯性权重
w 值较大，全局寻优能力强，局部寻优能力弱；反之，则局部寻优能力强。当问题空间较大时，为了在搜索速度和搜索精度之间达到平衡，通常做法是使算法在前期有较高的全局搜索能力以得到合适的种子，而在后期有较高的局部搜索能力以提高收敛精度。
在解决实际优化问题时，往往希望先采用全局搜索，使搜索空间快速收敛于某一区域，然后采用局部精细搜索以获得高精度的解。因此提出了自适应调整的策略，即随着迭代的进行，线性地减小 \[\omega\] 的值。
这里提供一个简单常用的方法——线性变化策略：随着迭代次数的增加，惯性权重\[\omega\]不断减小，从而使得粒子群算法在初期具有较强的全局收敛能力，在后期具有较强的局部收敛能力。
\[\omega ={{\omega }_{\max }}-\left( {{\omega }_{\max }}-{{\omega }_{\min }} \right)\frac{\text{iter}}{\text{ite}{{\text{r}}_{\max }}}\\\]
{{\omega }_{\max }} ——最大惯性权重； {{\omega }_{\min }}——最小惯性权重；{\text{iter}} ——当前迭代次数； {\text{ite}{{\text{r}}_{\max }}} ——最大迭代次数。


[*]pbest_{i}^{d} ：到第d次迭代为止，第 i 个粒子搜索到的最优位置（个体最优解）
[*]gbest^d ：到第d次迭代为止，群体搜索到的最优位置（群体最优解）
位置公式：

粒子第 d+1 步所在的位置=第 d 步所在的位置+第 d 步所在的位置*运动的时间(每一步运动的时间t一般取1)
x_{i}^{d+1}=x_{i}^{d}+v_{i}^{d}\tag{2}

[*]v_{i}^{d} ：第d次迭代时，第i个粒子的速度
[*]x_{i}^{d} ：第d次迭代时，第i个粒子所在的位置

三、优化中注意的条件

位置限制：限制粒子搜索的空间，即自变量的取值范围，对于无约束问题此处可以省略。
速度限制：为了平衡算法探索能力与开发能力，需要设定一个合理的速度范围，限制粒子的最大速度。
V_m 较大时，粒子飞行速度快，探索能力强，但粒子容易飞过最优解；
V_m较小时，飞行速度慢，开发能力强，但是收敛速度慢，且容易陷入局部最优解；
V_m一般设为每维变量变化范围的10％~20％。
优化停止准则：一般有两种

[*]最大迭代步数
[*]可接受的满意解：上一次迭代后最优解的适应值与本次迭代后最优解的适应值之差小于某个值后停止优化
初始化：如果粒子的初始化范围选择得好的话可以缩短优化的收敛时间，我们需要根据具体的问题进行分析。如果根据我们的经验判断出最优解一定在某个范围内，则就在这个范围内初始化粒子；如果无法确定，则以粒子的取值边界作为初始化范围。

四、代码实现

1.main.cpp

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <time.h>
#include "particle.h"

using namespace std;


int main()
{
    Coordinate gBest;
    Particle* p;    //对于简单问题取40个粒子
    Particle* tmp;
    float w;
    float randx, randy;
    float bestP;
    int bestIndex = 0;

    //随机生成40个粒子
    srand((int)time(NULL));
    for (int i = 0; i < 40; i++)      
    {
      randx = (rand() / (float)RAND_MAX) * 30.0;
      randy = (rand() / (float)RAND_MAX) * 30.0;

      p = new Particle(randx, randy);   
      cout << "The temp info is X: " << p->getX() << ", Y: " << p->getY() << endl;
    }

    //将P的值带入适应值函数，通过迭代找到初始的gBest
    bestP = p->getP();
    gBest = p->getPBest();
    for (int i = 1; i < 40; i++)
    {
      if (p->getP() < bestP)
      {
            bestP = p->getP();
            gBest = p->getPBest();
            bestIndex = i;
      }
    }
    cout << "Now the initial gBest is X: " << gBest.x << ", Y: " << gBest.y << endl;


    for (int k = 0; k < 90; k++)   //K为迭代次数，为算法的结束条件
    {
      w = 0.9 - (0.9 - 0.4) * k / 99.0;       //w的线性变化策略
      
      for (int i = 0; i < 40; i++)    //在每次迭代时对粒子的速度和位置进行更新
      {
            tmp = p;

            tmp->setV(gBest, w);
            tmp->setCoordinate();
            tmp->setP();
      }

      //将P的值带入适应值函数，通过迭代找到最终的gBest
      bestP = p->getP();
      gBest = p->getPBest();
      bestIndex = 0;
      for (int i = 1; i < 40; i++)
      {
            if (p->getP() < bestP)
            {
                bestP = p->getP();
                gBest = p->getPBest();
                bestIndex = i;
            }
      }
      cout << "Now the gBest is X: " << gBest.x << ", Y: " << gBest.y << endl;
    }
    system("pause");
    return 0;
}

2.Particle.cpp

#include <fstream>
#include <cstdio>
#include <cstdlib>
#include <time.h>
#include "particle.h"

using namespace std;

float Particle::Xmax = 30.0;
float Particle::Xmin = 0.0;
float Particle::Ymax = 30.0;
float Particle::Ymin = 0.0;
float Particle::Vxmax = Xmax - Xmin;
float Particle::Vxmin = 0.0 - Vxmax;
float Particle::Vymax = Ymax - Ymin;
float Particle::Vymin = 0.0 - Vymax;

float Particle::c1 = 2.0;
float Particle::c2 = 2.0;

Coordinate::Coordinate()
{
    x = 0.0;
    y = 0.0;
}

Coordinate::Coordinate(float x, float y)
{
    this->x = x;
    this->y = y;
}


Particle::Particle(float x, float y)
{
    //初始位置
    c.x = x;
    c.y = y;

    //初始适应值
    p = pow(c.x - 10.0, 2) + pow(c.y - 20.0, 2);

    //初始速度
    Vx = (Xmax - Xmin) / 8.0;
    Vy = (Ymax - Ymin) / 8.0;

    //初始的pBest;
    pBest.x = x;
    pBest.y = y;
}


void Particle::setP()
{
    float tmp = pow(c.x - 10.0, 2) + pow(c.y - 20.0, 2);

    if (tmp < p)
    {
      p = tmp;
      pBest = c;
    }
}

float Particle::getP()
{
    return p;
}

Coordinate Particle::getPBest() const
{
    return pBest;
}

//设置粒子的速度，本例子中要求解两个值，维度为2，所以有两个粒子速度
void Particle::setV(Coordinate gBest, float w)   
{
    float r1, r2;

    r1 = rand() / (float)RAND_MAX;    //上的随机数
    r2 = rand() / (float)RAND_MAX;

    Vx = w * Vx + c1 * r1 * (pBest.x - c.x) + c2 * r2 * (gBest.x - c.x);

    if (Vx > Vxmax)
    {
      Vx = Vxmax;
    }
    else if (Vx < Vxmin)
    {
      Vx = Vxmin;
    }

    Vy = w * Vy + c1 * r1 * (pBest.y - c.y) + c2 * r2 * (gBest.y - c.y);

    if (Vy > Vymax)
    {
      Vy = Vymax;
    }
    else if (Vy < Vymin)
    {
      Vy = Vymin;
    }
}

float Particle::getVx()
{
    return Vx;
}

float Particle::getVy()
{
    return Vy;
}

//设置粒子的位置
void Particle::setCoordinate()
{
    c.x = c.x + Vx;

    if (c.x > Xmax)
    {
      c.x = Xmax;
    }
    else if (c.x < Xmin)
    {
      c.x = Xmin;
    }

    c.y = c.y + Vy;

    if (c.y > Ymax)
    {
      c.y = Ymax;
    }
    else if (c.y < Ymin)
    {
      c.y = Ymin;
    }
}

float Particle::getX() const
{
    return c.x;
}

float Particle::getY() const
{
    return c.y;
}

void Particle::outputFile(char Dir[])
{
    cout << this->getX() << " " << this->getY() << " " << pBest.x << " " << pBest.y << endl;
}

3.Particle.h

#include <iostream>
#include <math.h>


class Coordinate {
public:
    float x;
    float y;
    Coordinate();
    Coordinate(float x, float y);
    ~Coordinate() {}
};



class Particle {
   // friend std::ostream& operator<<(std::ostream& output, const Particle& right);

public:
    Particle(float x, float y);
    void setP();
    float getP();

    Coordinate getPBest() const;

    void setV(Coordinate gBest, float w);//w为惯性因子
    float getVx();
    float getVy();

    void setCoordinate();
    float getX() const;
    float getY() const;

    void outputFile(char Dir[]);

private:
    Coordinate c;//求解的系数
    float p;   //p为适应度
    Coordinate pBest;
    float Vx;
    float Vy;

    static float Xmax, Xmin;
    static float Ymax, Ymin;
    static float Vxmax, Vxmin;
    static float Vymax, Vymin;
   
    static float c1, c2;//c1和c2为学习因子
};

五、算法优化

1.合理的设置基本参数


[*]种群规模amout的设置：根据模型复杂度定义
[*]惯性权重w，加速系数c1、c2的设置：w范围在0.7-0.9，c1=c2=（1-w）/2
[*]最大速度系数V_scale：范围在0.05-0.15之间
[*]退火思想（学习率渐渐减小）：种群规模N、Vmax、w前期设置较大，后期渐渐变小，前期偏重全局搜索避免遗漏最优解，后期偏重局部搜索以提高收敛速度。
2.使用拓扑结构


[*]全局拓扑：全连接（标准粒子群算法）
[*]局部拓扑：环形拓扑、冯诺依曼、四簇结构
优缺点：全局拓扑结构速度快，但易早熟，陷入局部最优；局部拓扑结构收敛速度慢一点，全局搜索的能力强；通常情况下，冯诺依曼、四簇结构的综合性能比较好。
3. 与其他智能优化算法联用


[*]粒子群算法与禁忌搜索联用：可以过早避免陷入局部 （仿真速度和优化结构与四簇结构相似）；
[*]粒子群算法与PCA主成分分析联用：可以大大提高收敛速度（参数之间有较强相关性时使用有较好效果）；
[*]粒子群与梯度下降联用：可以提高收敛速度；
[*]将基因算法的变异因子引入粒子群：在所有粒子陷入局部并停滞后，可以通过变异因子跳出局部继续仿真

参考：


[*]运筹OR帷幄：优化 | 粒子群算法介绍
[*]追梦小公子：粒子群优化算法(Particle Swarm Optimization, PSO)的详细解读
[*]（C++源码,详细注解）pso粒子群算法的调参技巧及改进方法_远上寒山的博客-CSDN博客
[*]【算法】粒子群算法Particle Swarm Optimization超详细解析+代码实例讲解
[*]小季不是咸鱼：数学建模：非常通俗易懂的粒子群算法（PSO）入门
[*]粒子群算法原理及C++代码实例_BUAA海海的博客-CSDN博客_粒子群算法的原理
[*]c++实现粒子群算法
[*]Kennedy J , Eberhart R . Particle Swarm Optimization// Icnn95-international Conference on Neural Networks. IEEE, 1995.
[*]Shi Y . A Modified Particle Swarm Optimizer// Proc of IEEE Icec Conference. 1998.

c0d3n4m 发表于 2023-3-2 14:19

[赞][赞][赞]

zt3ff3n 发表于 2023-3-2 14:28

利用粒子群对神经网络权重进行搜索有优势吗？[好奇]

ChuanXin 发表于 2023-3-2 14:33

不好意思，这个方面我还没有考虑过，不过PSO作为一个优化算法，应该会有帮助吧，你可以试试[好奇]
页: [1]
查看完整版本: 粒子群优化算法(Particle Swarm Optimization, PSO ...