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

返回本页常规视图.

适用于粒子群优化算法的问题

PSO 中的单目标问题

单目标问题是指在优化过程中只有一个目标函数需要优化. 这个目标函数可以是需要最大化或最小化的.

单目标优化问题具有以下特点

  1. 只需要一个目标函数(适应度评估函数)
  2. 优化的目标是找到使目标函数达到全局最优的解
  3. 很多现实的问题可以简化为单目标优化问题

所以在 PSO 的计算过程中, 每个粒子根据自身的历史最好位置和群体的最好位置来调整自己的位置和速度, 最终只使得所有的粒子都趋近于某一个非常优秀的粒子

PSO 中的多目标问题

多目标问题是指在优化过程中存在多个目标函数, 且这些目标函数通常是相互冲突的(有相关性)

多目标优化问题具有以下特点:

  1. 需要计算多个目标函数
  2. Pareto最优, 在多目标优化中, 通常是不存在一个全局最优解, 而是一个 Pareto 前沿. 处于 Pareto 前沿上的解是相互不可优的, 即无法在不损失另一个目标的情况下改进另一个目标.
  3. 需要在不同的目标之间找到一个平衡点, 具体取决于决策这的偏好

故而在多目标PSO(MOPSO)中扩展了标准PSO(SPSO)以处理多个目标:

  • Pareto 存档: 维护一个 Pareto 前沿存档, 记录非支配解
  • 多目标适应度: 通过适应度函数结合多个目标函数, 帮助粒子在搜索空间中寻找到平衡解
  • 多样性维护: 通过机制如拥挤距离来维护粒子群体的多样性, 防止过早收敛

结论

简而言之, 单目标的 PSO 是群求单一最优解, 多目标 PSO 寻求 Pareto 最优解集

1 - MOPSO 中的关键可能性

介绍

多目标PSO（MOPSO）的关键之一确实是如何构建和维护Pareto结构。然而，这只是多目标优化中的一个方面。为了全面理解MOPSO，还需要考虑其他一些关键要素。以下是多目标PSO的几个重要组成部分：

1. Pareto 前沿构建和维护

Pareto 前沿：这是多目标优化中的一组非支配解。这些解在一个目标上不能被另一个解改进而不在其他目标上变差。

非支配解：在群体中找到所有非支配解，并将其存储在一个外部存档（Pareto 存档）中。

更新机制：每当有新的解产生时，更新Pareto存档，确保存档中始终保持最优和多样化的非支配解。

2. 适应度函数设计

多目标适应度：使用适应度函数来综合评估多个目标函数。这通常涉及将多个目标函数值结合成一个适应度值。

支配关系：基于支配关系来评估粒子的适应度。一个解支配另一个解如果它在所有目标上都不差于另一个解，并且在至少一个目标上更好。

3. 多样性维护

拥挤距离: 通过计算拥挤距离来维护粒子群体的多样性, 防止所有粒子收敛到局部最优解

多样化操作: 引入某些机制, 如变异操作或者随机重新初始化部分粒子位置, 来增加解的多样性

4. 粒子更新机制

速度和位置更新: MOPSO 仍然保留了标准PSO的速度和位置更新机制, 但在多目标环境中, 粒子的位置更新要综合考虑多个目标

引导粒子: 选择合适的粒子(如存档中的非支配解)作为其他粒子的引导, 确保搜索朝向 Petro 前沿移动

5. 权衡处理

目标权重: 根据决策者的偏好, 为不同的目标分配不同的权重, 有时使用加权和法来结合多个目标

动态调整: 在优化过程中动态调整粒子对不同目标的关注程度, 使得搜索过程更加灵活.

2 - 典型的单目标问题

2.1 - Parabola(Sphere) Formula

Code

我们先简单看一段代码, 这是 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\) 的欧几里得范数的平方;

应用场景

  • 抛物面: 在计算抛物面上的某个点到原点的距离平方时使用
  • 球面: 在计算球面上某个点到球心的距离平方时使用

3 - 典型的多目标问题