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

返回本页常规视图.

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 介绍

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

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];
};

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;