这是本节的多页打印视图。 点击此处打印.

返回本页常规视图.

标准粒子群算法

Maurice.Clerc于Standard PSO Descriptions中提出了 StandardPSO 的概念

0.介绍

自2006年以来，三种连续的标准PSO版本已在Particle Swarm Central线上发布，分别是SPSO 2006、2007和2011。这些版本的基本原理大致相同，但由于设计时利用了当时最新的理论分析，其具体公式略有不同。

1. 基本概念

  • 解空间: 粒子的特性所处的问题的边界
  • 适应函数: 每个粒子的位置有一个对应的适应度值, 用于衡量该位置的优劣
  • 粒子群(群): 对问题描述的的解的集合
  • 粒子: 组成粒子群的单位
  • 位置: 对粒子的特性的描述,一般用一个 n 维向量表示
  • 速度: 位置的变化率

2.Particle Swarm Optimisation

PSO 的计算过程主要是在迭代的过程中逐步优化问题的解 — 以一簇粒子群为初始步骤, 逐步迭代, 群中的每个粒子都知道截至当前迭代步的解空间中, 群内的 全局最佳位置 和 个体最佳位置, 故而 PSO 中的 群 和 个体 是有记忆的.

在每一步的迭代中, 群中的每个粒子 位置 和 速度 受所在群中全局和个体的 记忆最优解 影响, 通过重复 “变动” 的过程来, 比对解空间的 “适应度” 函数, 来渐进逼近问题的真实最优解;

算法的描述:

2.0 环境条件(全局变量)

  • S: 粒子群容量
  • K: 指定个体的最大通知数
  • T: 信息链路的拓扑结构
  • w: 第一置信系数(first cognitive/confident coefficient)
  • c: 第二置信系数(second cognitive/confidence coefficient)
  • R: random distribution of c
  • B: 边界条件

SPSO2006

[SPSO2007]

[SPSO2011]

2.1 群体的初始化

粒子群中的每个粒子在搜索空间内随机初始化位置和速度

[SPSO2006]

[SPSO2007]

[SPSO2011]

2.2 迭代过程

  • 更新粒子的速度和位置
  • 速度更新公式的各个版本的定义
  • 更新位置信息
  • 计算新位置的适应度值并更新粒子的最佳位置

2.3 停止条件

  • 对目标函数结果的收敛

代码框架

 #include <stdio.h>
 #include <stdlib.h>
 int main(void)
 {
    puts("Hello World!");
    return EXIT_SUCCESS;
 }
 

 #include <stdio.h>
 #include <stdlib.h>
 int main(void)
 {
    puts("Hello World!");
    return EXIT_SUCCESS;
 }
 
 using namespace math
 int main(void)
 {
    puts("Hello World!");
    return EXIT_SUCCESS;
 }

速度的公式表示

$$\vec{V}_{t+1}^{i} = \vec{V}_{t}^{i} + \varphi_{1} R_{1t}^{i} (\vec{p}_{t}^{i} - \vec{x}_{t}^{i}) + \varphi_{2} R_{2t}^{i} (\vec{g}_{t} - \vec{x}_{t}^{i})$$

\(\omega_1\),和 \(\omega_2\) 为 加速系数, 来控制全局和个体最佳位置对粒子的 移动速度 和 移动方向 的影响程度

\(R_1\) 和 \(R_2\) 是符合均匀随机分布的单位向量, 用于来维护群体的各异性

\(\vec{p}_t^i\)是群中 \(粒子_i\) 在 \(t\)代迭代的个体最优位置

\(\vec{g}_t^i\)是群中 \(粒子_i\) 在 \(t\)代迭代的全局最优位置

位置变化公式

$$\vec{x}_{t+1}^i = \vec{x}_{t}^i + \vec{V}_{t+1}^i$$

记 \(\vec{x}_0^i\) 和 \(\vec{V}_0^i\) 是符合均匀随机分布的初始量, 其中,个体最优位置的初始化与它的初始位置相同: \(\vec{p}_0^i = \vec{x}_0^i\)

PSO 是一种独立于问题的算法

因此它有非常广泛的应用场景，因为运行算法所需的唯一信息是适应度评估每个候选解决方案(有时候会增加问题的约束集)

1 - PSO gbest and lbest

在粒子群优化（Particle Swarm Optimization，PSO）算法中，lbest模型和gbest模型是两种不同的策略，用于更新粒子的位置和速度。

gbest 模型(全局最优模型)

全局最优模型的PSO中,一般定义为:

$$\hat{y}_t \in \left\{ \vec{p}_t^1, \vec{p}_t^2, \ldots, \vec{p}_t^s \right\} \mid f(\hat{y}_t) = \min \left( \left\{ f(\vec{p}_t^1), f(\vec{p}_t^2), \ldots, f(\vec{p}_t^s) \right\} \right)$$

y作为目标粒子, 表示d维搜索空间中整个群或其邻域中最佳粒子的位置;

  • 在 gbest 模型中，所有粒子都参考全局最优位置（全局最佳解）来更新自己的位置和速度。
  • 全局最优位置是整个粒子群中所找到的最好的位置。
  • 这种模型通常收敛速度较快，但容易陷入局部最优，因为所有粒子都朝向相同的目标移动。

lbest 模型(局部最优模型)

在 局部最优模型中, 如下定义一个粒子的符合线性排序邻居粒子:

$$N_i = \left\{ \vec{p}_t^{i-l}, \vec{p}_t^{i-l+1}, \ldots, \vec{p}_t^{i-1}, \vec{p}_t^i, \vec{p}_t^{i+1}, \ldots, \vec{p}_t^{i+l-1}, \vec{p}_t^{i+l} \right\}$$

则 lbest模型公式如下

$$\hat{y}_t \in N_i \mid f(\hat{y}_t) = \min \left( \left\{ f(\vec{a}) \right\} \right), \forall \vec{a} \in N_i$$
  • 在 lbest 模型中，每个粒子仅参考其邻域内的最优位置来更新自己的位置和速度。
  • 邻域的定义可以是粒子群中的一小部分粒子，通常是该粒子周围的某个固定数量的邻居粒子。
  • 这种模型能够更好地保持多样性，减少陷入局部最优的风险，但收敛速度可能较慢

2 - PSO 的控制参数

3 - PSO 性能描述

描述 PSO 的运行性能的参数

  • 迭代次数 (在一次初始化后, 循环移动的次数)
  • 失败次数 (在一次初始化后, 迭代至上限时, 没有得到结果, 算一次失败)
  • 运行次数 (失败后重新初始化, 算一次运行)
  • 成功率 (在一次迭代中, 得到收敛结果后, 不退出, 重新初始化, 至总运行次数上限, 其中成功次数的占比)
  • 失败率 ( not 成功率)

4 - Standard PSO Version 2006

非常接近 1995 版本的算法, 所以一般说 SPSO2006 版本指(w=0.8)

定义 位置&速度 结构体

struct position
{
  int size;
  double* x;
  float f;
}

struct velocity
{
  int size;   // d-dimension
  double* v; // value of velocity
}

环境数据

int D = 2; // 设置问题的搜索空间维度为 2;

// 设置搜索空间的边界
for(d = 0; d< D; d++)
{
  xmin[d] = -100;
  xmax[d] = 100;
}
int S = 10+( int )(2*sqrt(D)); if (S>S_max) S=S_max;
int K = 3;
double w = 1 / ( 2 * log( 2 ) ); double c = 0.5 + log( 2 );

int best_index; // 从 P[] 中找到全局最佳的位置;
struct position *P; // P[] 最佳位置, 和 X 有数据对齐的关系;

初始化粒子群

// init: 粒子群初始化
init:
X = (struct position_06*)malloc(S * sizeof(struct position_06));
V = (struct velocity_06*)malloc(S * sizeof(struct velocity_06));
if (X == NULL || V == NULL)
{
  return -1;
}

for (int s = 0; s < S; s++)
{
  X[s].size = D;
  V[s].size = D;
  double* d_array = (double*)malloc(D* sizeof(double));
  double* v_array = (double*)malloc(D * sizeof(double));
  if (d_array == NULL || v_array == NULL)
  {
    return -1;
  }
  for (int d = 0; d < D; d++)
  {
    d_array[d] = alea_06(xmin[d], xmax[d]);
    v_array[d] = (alea_06(xmin[d], xmax[d]) - d_array[d]) / 2;
  }
  X[s].x = d_array;
  V[s].v = v_array;
  free(d_array);
  free(v_array);
}

筛选当前最优解

// 初始化 局部最佳位置&全局最佳位置
for (int s = 0; s < S; s++)
{
  X[s].f = fabs(0 - 0); //TODO: 定义适应度函数
  P[s] = X[s];// Best Position = current one
}

// Find the best
best_index = 0;
for (int s = 1; s < S; s++)
  if (P[s].f < P[best_index].f)
    best_index = s;

迭代移动

loop:
    // The swarm MOVES
    for (s = 0; s < S; s++) // For each particle ...
    {
        // .. find the best informant
        g = s;
        for (m = 0; m < S; m++)
        {
            if (LINKS[m][s] == 1 && P[m].f < P[g].f) g = m;
        }

        // ... compute the new velocity, and move
        for (d = 0; d < D; d++)
        {
            V[s].v[d] = w * V[s].v[d] + alea_06(0, c) * (P[s].x[d] - X[s].x[d]);
            V[s].v[d] = V[s].v[d] + alea_06(0, c) * (P[g].x[d] - X[s].x[d]);
            X[s].x[d] = X[s].x[d] + V[s].v[d];
        }

        // ... interval confinement (keep in the box)
        for (d = 0; d < D; d++)
        {
            if (X[s].x[d] < xmin[d])
            {
                X[s].x[d] = xmin[d]; V[s].v[d] = 0;
            }
            if (X[s].x[d] > xmax[d])
            {
                X[s].x[d] = xmax[d]; V[s].v[d] = 0;
            }
        }


        // ... evaluate the new position
        X[s].f = fabs(perf_06(s, function) - f_min);


        // ... update the best previous position
        if (X[s].f < P[s].f)
        {
            P[s] = X[s];
            // ... update the best of the bests
            if (P[s].f < P[best].f) best = s;
        }
    }

环境判断条件(退出的时机)

// Check if finished
// If no improvementd, information links will be reinitialized
error = P[best_index].f;
if (error >= error_prev) init_links = 1;
else init_links = 0;
error_prev = error;

if (error > eps && nb_eval < eval_max) goto loop;
if (error > eps) n_failure = n_failure + 1;

关于这个话题已经做了很多工作。主要结果是没有 “最佳”拓扑。因此，SPSO2006 版本使用了随机方法。

K=3 这并不意味着每个粒子都由K个粒子通知：通知给定粒子的粒子数量可以是1（对于每个粒子通知自己）和S之间的任何值。

if (init_links == 1)
{
    // Who informs who, at random
    for (s = 0; s < S; s++)
    {
        for (m = 0; m < S; m++) LINKS[m][s] = 0; // Init to "no link"
        LINKS[s][s] = 1; // Each particle informs itself
    }

    for (m = 0; m < S; m++) // Other links
    {
        for (i = 0; i < K; i++)
        {
            s = alea_integer_06(0, S - 1);
            LINKS[m][s] = 1;
        }
    }
}

直观来说, LINKS 会影响整个优化过程中的速度和效率, 同时在一次"迭代"过程中, 一个粒子是否应该多次修改自己的位置也是一个问题

5 - Standard PSO Version 2007

这与原始版本（1995）非常接近，基于最近的一些工作，只做了一些改进。

与 SPSO2006 之间的主要区别

  1. 增加控制项: “使算法对搜索空间的旋转变换不敏感”

    Note: 减低性能可能不会对结果有太大改善.(做了更多的尝试)

  2. 增加控制项 “是否每次迭代随机前置换粒子的位置”

    Note: 减低性能可能不会对结果有太大改善(做了更多的尝试)

  3. 增加控制项 “是否约束粒子边界”

    Note: 在极少数情况下，如果停止标准是最大评估次数，则不限制位置可能会导致无 限运行

  4. 一个特定粒子是另一个粒子的通知者的概率 p。在 SPSO-06 中，它是隐式的（通过构建 随机信息网络）。在这里，默认值直接作为（S，K）的函数计算，因此信息网络与 SPSO-07 中的完全相同。然而，现在它可以被“操纵”（即可以分配任何值）
  5. 搜索空间可以量化,但该算法不适用于组合问题

额外的, 在随机数的计算上提供了一些其他的方法

SPSO2007 的初始化

从逻辑上来讲, 在随机生成初始位置和初始速度后, 增加了一步 量化(Quantisation), 用于将连续问题的解空间进行离散化, 通常可以用于一下问题的处理

  • 离散优化问题: 当优化问题的解空间是离散的, 而粒子群算法通常处理的是连续空间. 在这种情况下, 通过量化技术可以将连续粒子的位置转换为离散的可行解, 以适应离散优化问题

  • 编码和解码: 在某些应用中, PSO 算法的粒子可能需要通过编码和解码机制与离散决策变量进行交互. 例如，优化过程中使用浮点数表示解决方案，但最终解需要在离散的参数空间中被实现。量化就是将这些浮点数转换为离散的值。

  • 精度控制：量化也可以用于控制粒子位置的精度，以避免计算中的浮点数误差或过度复杂的计算。通过将粒子的位置量化为有限精度的值，可以简化计算，并提高算法的稳定性。

  • 速度调整：在某些变体中，量化用于调整粒子的速度或位置，使得搜索过程在离散的步长或区间内进行，从而控制算法的步伐和收敛速度。

1. SPSO2007 介绍

在项目结构上, 在不着重考虑性能的情况下, 对算法的逻辑进行了更详细的结构化, 将算 法中涉及到的数据进行了封装, 分为:

5.1 - 参数结构体

全局变量

#define D_max 114 //搜索空间的最大维度数
#define R_max 500 //最大运行次数
#define S_max 910 //最大群容量
#define fMax 6 //最大约束数+1
#define zero  0 //1.0e-30//避免数值不稳定

粒子群(Swarm)

定义粒子群中包含

  • P: 粒子局部最优位置队列(上一代)
  • X: 当前每个粒子的位置特征
  • V: 当前每个粒子的迭代速度
  • best: 全局最优位置
struct swarm
{
 int best;                  // rank of the best particle
 int S;                     // Swarm size
 struct Position P[S_max];  // Previous best positions found by each particle
 struct Velocity V[S_max];  // Velocities
 struct Position X[S_max];  // Positions
};

其中:

位置(Position)

  • f: 当前位置的评估误差
  • improved: 增加了判断参数
  • x: 解数组
struct Position
{
 double f;
 int improved;  // *** add improved to SPSO2006
 int size;
 double x[D_max];
};

速度(Velocity)

  • v: 速度数组
struct Velocity
{
 int size;
 double v[D_max];
};

控制(环境)参数(Param)

一种粒子群算法的通用控制参数:

  • S: 粒子群容量
  • K: 每次移动的通知数
  • w: 关于速度生成公式的第一变量
  • c: 关于速度生成公式的第二变量
struct Param
{
 int clamping;  // Position clamping or not
 double p;      // Probability threshold for random topology
                // (is actually computed as p(S,K) )
 int randOrder; // Random choice of particles or not
 int rand;      // 0 => use KISS. Any other value: use the standard C RNG
 int initLink;  // How to re-init links
 int rotation;  // Sensitive to rotation or not
 int S;         // Swarm size
 int K;         // Max number of particles informed by a given one
 int stop;      // Flag for stop criterion
 double w;      // Confidence coefficient
 double c;      // Confidence coefficient
};

问题描述(Problem)

  • SearchSpace 问题的解空间
  • objective 通常一个优化问题是有一个目标值的
  • epsilon 允许误差(对目标值)
  • function 适应度函数
struct Problem
{
 double epsilon;            // Admissible error
 int evalMax;               // Maximum number of fitness evaluations
 int function;              // Function code
 double objective;          // Objective value
 struct Position solution;  // Solution position (if known, just for tests)
 struct SearchSpace SS;     // Search space
};

解空间描述(SearchSpace)

  • D 问题的维度
  • max 上边界
  • min 下边界
  • maxInit 初始化上边界
  • minInit 初始化下边界
struct SearchSpace
{
 int D;
 double max[D_max];
 double maxInit[D_max];
 double min[D_max];
 double minInit[D_max];
 struct quantum q;  // Quantisation step size. 0 => continuous problem
};

结果(Result)

struct result
{
 struct swarm SW; // Final swarm
 double nEval;   // Number of evaluations
 double error;  // Numerical result of the run
};

子数据

struct quantum
{
 double q[D_max];
 int size;
};

struct fitness
{
 int size;
 double f[fMax];
};

struct matrix  // Useful for "non rotation sensitive" option
{
 int size;
 double v[D_max][D_max];
};

5.2 - 主逻辑

初始化

相较于 SPSO2006, 该版本增加了量化的步骤, 用于处理离散问题的优化

筛选最优解

相较于 SPSO2006, 该版本定义了两种筛选方法

  1. 比较评价函数的值与目标值的误差
  2. 比较当前位置(解)与目标位置(目标解)的误差

更新拓扑通知

迭代移动

相较于 SPSO2006, 该版本在移动过程中增加了如下步骤

  • 在每次开始移动前对粒子群中的粒子进行随机排序
  • 更新了一种新的速度生成策略

速度生成逻辑

环境判断条件(退出的时机)

相较于 SPSO2006, 该版本增加了更多推出条件, 防止陷入死循环

// Check if finished
// If no improvementd, information links will be reinitialized
error = P[best_index].f;
if (error >= error_prev) init_links = 1;
else init_links = 0;
error_prev = error;

if (error > eps && nb_eval < eval_max) goto loop;
if (error > eps) n_failure = n_failure + 1;

6 - Standard PSO Version 2011

介绍

在 SPSO2011 中探讨了更多的速度生成方式和策略