粒子群优化（PSO）技术由电气工程师Russell C. Eberhart和社会心理学家James Kennedy提出并最初开发。这一方法在两篇由他们两位作者共同撰写的论文中被描述，并于1995年发表，其中一篇论文的标题正是他们提出的技术名称。
这种技术与一些社会关系、概念和行为有着深刻的联系，这些关系、概念和行为来源于这些作者对一群鸟类寻找食物的简化社会模型进行计算研究和模拟时所发现的。这一技术属于所谓的群体智能，这是自然计算中的一个重要且广泛的研究领域。
PSO方法基于这样一个前提：知识不仅存在于代与代之间的信息社会共享中，也存在于同一代元素之间的信息共享中。尽管PSO在某种程度上具有一些与其他基于群体的计算模型（如遗传算法（GA）和其他进化计算技术）相似的特征，但它具有相对简单的优势，其算法相对容易描述和实现。
实际上，由于其简单性和在复杂搜索空间中找到最优解的明显能力，PSO算法在科学界变得广为人知，这促进了对其的研究和改进。因此，许多方法被提出，并且在过去十年中，使用PSO进行了各种应用测试。
自2006年以来，三种连续的标准PSO版本已在Particle Swarm Central线上发布，分别是SPSO 2006、2007和2011。这些版本的基本原理大致相同，但由于设计时利用了当时最新的理论分析，其具体公式略有不同。
PSO 的计算过程主要是在迭代的过程中逐步优化问题的解 — 以一簇粒子群为初始步骤, 逐步迭代, 群中的每个粒子都知道截至当前迭代步的解空间中, 群内的 全局最佳位置 和 个体最佳位置, 故而 PSO 中的 群 和 个体 是有记忆的.
在每一步的迭代中, 群中的每个粒子 位置 和 速度 受所在群中全局和个体的 记忆最优解 影响, 通过重复 “变动” 的过程来, 比对解空间的 “适应度” 函数, 来渐进逼近问题的真实最优解;
算法的描述:
[SPSO2007]
[SPSO2011]
粒子群中的每个粒子在搜索空间内随机初始化位置和速度
[SPSO2006]
[SPSO2007]
[SPSO2011]
#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;
}
\(\omega_1\),和 \(\omega_2\) 为 加速系数, 来控制全局和个体最佳位置对粒子的 移动速度 和 移动方向 的影响程度
\(R_1\) 和 \(R_2\) 是符合均匀随机分布的单位向量, 用于来维护群体的各异性
\(\vec{p}_t^i\)是群中 \(粒子_i\) 在 \(t\)代迭代的个体最优位置
\(\vec{g}_t^i\)是群中 \(粒子_i\) 在 \(t\)代迭代的全局最优位置
记 \(\vec{x}_0^i\) 和 \(\vec{V}_0^i\) 是符合均匀随机分布的初始量, 其中,个体最优位置的初始化与它的初始位置相同: \(\vec{p}_0^i = \vec{x}_0^i\)
因此它有非常广泛的应用场景，因为运行算法所需的唯一信息是适应度评估每个候选解决方案(有时候会增加问题的约束集)
全局最优模型的PSO中,一般定义为:
y作为目标粒子, 表示d维搜索空间中整个群或其邻域中最佳粒子的位置;
在 局部最优模型中, 如下定义一个粒子的符合线性排序邻居粒子:
则 lbest模型公式如下
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 会影响整个优化过程中的速度和效率, 同时在一次"迭代"过程中, 一个粒子是否应该多次修改自己的位置也是一个问题
Note: 减低性能可能不会对结果有太大改善.(做了更多的尝试)
Note: 减低性能可能不会对结果有太大改善(做了更多的尝试)
Note: 在极少数情况下，如果停止标准是最大评估次数，则不限制位置可能会导致无 限运行
额外的, 在随机数的计算上提供了一些其他的方法
从逻辑上来讲, 在随机生成初始位置和初始速度后, 增加了一步 量化(Quantisation), 用于将连续问题的解空间进行离散化, 通常可以用于一下问题的处理
离散优化问题: 当优化问题的解空间是离散的, 而粒子群算法通常处理的是连续空间. 在这种情况下, 通过量化技术可以将连续粒子的位置转换为离散的可行解, 以适应离散优化问题
编码和解码: 在某些应用中, PSO 算法的粒子可能需要通过编码和解码机制与离散决策变量进行交互. 例如，优化过程中使用浮点数表示解决方案，但最终解需要在离散的参数空间中被实现。量化就是将这些浮点数转换为离散的值。
精度控制：量化也可以用于控制粒子位置的精度，以避免计算中的浮点数误差或过度复杂的计算。通过将粒子的位置量化为有限精度的值，可以简化计算，并提高算法的稳定性。
速度调整：在某些变体中，量化用于调整粒子的速度或位置，使得搜索过程在离散的步长或区间内进行，从而控制算法的步伐和收敛速度。
在项目结构上, 在不着重考虑性能的情况下, 对算法的逻辑进行了更详细的结构化, 将算 法中涉及到的数据进行了封装, 分为:
#define D_max 114 //搜索空间的最大维度数
#define R_max 500 //最大运行次数
#define S_max 910 //最大群容量
#define fMax 6 //最大约束数+1
#define zero 0 //1.0e-30//避免数值不稳定
定义粒子群中包含
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
};
其中:
struct Position
{
double f;
int improved; // *** add improved to SPSO2006
int size;
double x[D_max];
};
struct Velocity
{
int size;
double v[D_max];
};
一种粒子群算法的通用控制参数:
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
};
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
};
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
};
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];
};
相较于 SPSO2006, 该版本增加了量化的步骤, 用于处理离散问题的优化
相较于 SPSO2006, 该版本定义了两种筛选方法
相较于 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;
单目标问题是指在优化过程中只有一个目标函数需要优化. 这个目标函数可以是需要最大化或最小化的.
单目标优化问题具有以下特点
所以在 PSO 的计算过程中, 每个粒子根据自身的历史最好位置和群体的最好位置来调整自己的位置和速度, 最终只使得所有的粒子都趋近于某一个非常优秀的粒子
多目标问题是指在优化过程中存在多个目标函数, 且这些目标函数通常是相互冲突的(有相关性)
多目标优化问题具有以下特点:
故而在多目标PSO(MOPSO)中扩展了标准PSO(SPSO)以处理多个目标:
简而言之, 单目标的 PSO 是群求单一最优解, 多目标 PSO 寻求 Pareto 最优解集
多目标PSO（MOPSO）的关键之一确实是如何构建和维护Pareto结构。然而，这只是多目标优化中的一个方面。为了全面理解MOPSO，还需要考虑其他一些关键要素。以下是多目标PSO的几个重要组成部分：
Pareto 前沿：这是多目标优化中的一组非支配解。这些解在一个目标上不能被另一个解改进而不在其他目标上变差。
非支配解：在群体中找到所有非支配解，并将其存储在一个外部存档（Pareto 存档）中。
更新机制：每当有新的解产生时，更新Pareto存档，确保存档中始终保持最优和多样化的非支配解。
多目标适应度：使用适应度函数来综合评估多个目标函数。这通常涉及将多个目标函数值结合成一个适应度值。
支配关系：基于支配关系来评估粒子的适应度。一个解支配另一个解如果它在所有目标上都不差于另一个解，并且在至少一个目标上更好。
拥挤距离: 通过计算拥挤距离来维护粒子群体的多样性, 防止所有粒子收敛到局部最优解
多样化操作: 引入某些机制, 如变异操作或者随机重新初始化部分粒子位置, 来增加解的多样性
速度和位置更新: MOPSO 仍然保留了标准PSO的速度和位置更新机制, 但在多目标环境中, 粒子的位置更新要综合考虑多个目标
引导粒子: 选择合适的粒子(如存档中的非支配解)作为其他粒子的引导, 确保搜索朝向 Petro 前沿移动
目标权重: 根据决策者的偏好, 为不同的目标分配不同的权重, 有时使用加权和法来结合多个目标
动态调整: 在优化过程中动态调整粒子对不同目标的关注程度, 使得搜索过程更加灵活.
我们先简单看一段代码, 这是 SPSO 中的一个测试函数
#include "structs.h"
double ParabolaShpere(struct position xs, double p)
{
int D = xs.size; // 粒子群的 d-dimension
double f = 0, xd;
p = 0; // Shift
for (int d = 0; d < D; d++)
{
xd = xs.x[d] - p;
f = f + xd * xd;
}
return f;
}
如果我们有一个 点 \(x = (x_1, x_2, \cdots, x_D)\), 则这段代码的输出为: \(f = \sum_{d=0}^{D-1}(x_d - p)^2\), 这就是点 \(x\) 到 \(P = (p, p, \cdots, p)_D\) 的欧几里得范数的平方;
# Convergence Improvements
## New parameters
### Inertia weight ($\omega$)
### Constriction factor($K$)
### Guaranteed Convergence PSO (GCPSO)
### Near Neighbour Ineractions
## Cooperative PSO (CPSO)
## Stretched PSO (STPSO)
## Fully Informed Particle Swarm (FIPS)
## Hybrid approaches
### Evolutionary operators
#### Selection
#### Mutation
#### Evolutionary PSO (EPSO)
### Other algorithms
#### Genetic Algorithms(GA)
#### Differential Evolutionary PSO (DEEPSO)
#### Simulated Annealing(SA)
#### Ant Colony Optimisation(ACO)