基于全局边际排序和自适应参数调节的多目标粒子群算法

Multi-Objective Particle Swarm Optimization Based on Global Marginal Ranking and Adaptive Parameter Adjustment

摘要: 多目标粒子群优化算法作为一种强大的优化技术，在各个领域得到了广泛的应用。然而，对于大多数现有的算法来说，同时在收敛性和多样性方面表现良好仍然是一项具有挑战性的任务。针对上述挑战，本文提出了一种基于全局边际排序和自适应参数调节的多目标粒子群优化算法(GGRAW)。在多目标粒子群算法中，飞行参数、惯性权重ω、加速度系数c₁和c₂对于实现种群开发和勘探之间的平衡非常重要。该策略利用个体在客观空间中的位置信息，以获得整个种群的优势边际。该方法不仅考虑了种群的分布，还考虑了个体的相关信息。通过自适应参数的调节更加促使种群中的粒子向真实的Pareto前沿移动；将GGRAW算法与3种经典的多目标粒子群算法在ZDT、DTLZ和WFG系列的部分测试函数上进行仿真实验；试验结果表明：相对于其他的几种经典算法，GGRAW算法表现出较好的收敛性和多样性，因此，GGRAW算法可以作为求解多目标优化问题的有效算法。

Abstract: As a powerful optimization technology, multi-objective particle swarm optimization algorithm has been widely used in various fields. However, performing well in both convergence and diversity remains a challenging task for most existing algorithms. To address these challenges, this paper proposes a multi-objective particle swarm optimization algorithm (GGRAW) based on global marginal sorting with adaptive parameter adjustment. In multi-objective particle swarm optimi-zation, flight parameters, inertia weight ω, acceleration coefficients c₁ and c₂ are very important to achieve a balance between population exploitation and exploration. This strategy uses the position information of individuals in objective space to obtain the dominant margin of the whole population. This method not only considers the distribution of the population, but also considers the relevant information of the individual. By adjusting the adaptive parameters, the particles in the population can move towards the real Pareto frontier. The GGRAW algorithm and three classical multi-objective particle swarm optimization algorithms were simulated on some test functions of ZDT, DTLZ and WFG series. The experimental results show that compared with other classical algorithms, GGRAW algorithm shows better convergence and diversity. Therefore, GGRAW algorithm can be used as an effective algorithm for solving multi-objective optimization problems.

1. 引言

在过去的十几年中，多目标优化受到了越来越多的关注，比如基于差分进化(DE) [1]、粒子群优化(PSO) [2] 等遗传算法的自然启发元启发式算法。值得一提的是，基于种群的元启发式算法由于能够处理非线性、多模态和不连续的问题，已被广泛应用于求解真实的MOPs。其中，PSO是一种很有前途的群体智能技术，其灵感来自于鸟类和鱼类寻找食物的行为。由于其易于实现和快速收敛到全局最优，引起了研究者的极大兴趣，并广泛应用于许多单目标工程应用。

多目标优化问题(MOPs)的特点是多个目标同时优化 [1]。由于MOP中的目标之间的冲突，几乎没有一个单一的解决方案能够同时满足所有的目标。因此，解决一个MOP的目标是找到一组帕累托非支配的解决方案，这需要在不同的目标之间进行权衡 [3]。所有帕累托非支配解的集合称为帕累托最优集(PS)，PS在目标空间中的映射称为帕累托前部(PF) [4]。当求解一个MOP时，在PS中得到的解不仅要尽可能地收敛于优化后的MOP的真实PF，而且要尽可能均匀地分布在PF上。一般来说，收敛性和多样性是评价最终解质量的两个关键标准。

为了应用PSO来解决MOP问题，我们必须解决以下两个基本问题。首先，如何选择全球最佳的解决方案(领导者)来指导群体搜索。由于没有单一存在所有目标中优于所有其他解决方案，因此许多非主导的解决方案可以被视为被选为领导者的候选方案。为了完成这项任务，人们必须采用一种合适的选择技术，同时考虑到解决方案的多样性和收敛速度。然而在多目标优化过程中往往会忽略参数的设置，这可能会导致在优化过程中使得一些粒子陷入局部最优解。例如文献 [5] 中，对于参数的设置考虑欠妥，导致一些非劣解陷入局部最优，虽然在收敛性方面有所提高，但对于收敛性与多样性综合来看还是存在很大的不足。因此本文提出了基于全局边际排序和自适应参数调节的多目标粒子群算法(GGRAW)来进一步提高非劣解的多样性和收敛性。GGRAW算法中加入了自适应参数的调节机制，更加有效地避免了种群陷入局部最优，大大提高了种群的收敛性和多样性。

2. 相关概念

2.1. 多目标优化问题

一般来说，多目标优化问题可以用数学方法描述为 [6]

$\underset{x\in \Omega }{\min }F\left(x\right)=\left\{f_1\left(x\right),f_2\left(x\right),\cdots ,f_D\left(x\right)\right\}$

s.t. $g_j\left(x\right)\le 0,0\le j\le k$

其中 $x={\left(x_1,x_2,\cdots ,x_D\right)}^{\text{T}}$ 是决策空间Ω中的d维决策向量， $g_j\left(x\right)\le 0$ 表示k个等不等式约束，映射函数 $f_i\left(x\right)$ 表示第i个目标函数，m是目标函数的个数。

2.2. 粒子群优化算法

粒子群优化(PSO)是一种用于处理非线性优化问题的元启发式 [6]。首先，初始化一组解决方案。然后，将种群经过多代人进行更新，以找到最优解。在演化过程中，每个粒子的位置通过两个学习算子 [7] 进行更新。一个是粒子在速度上的更新，另外一个是位置上的更新。设 $x_i\left(t\right)=\left(x_{i,1}\left(t\right),x_{i,2}\left(t\right),\cdots ,x_{i,D}\left(t\right)\right)$， $v_i\left(t\right)=\left(v_{i,1}\left(t\right),v_{i,2}\left(t\right),\cdots ,v_{i,D}\left(t\right)\right)$ 分别为第i次迭代时粒子的位置和速度。然后，就可以用以下公式来更新该位置的每个维度：

$v_{i,j}\left(t+1\right)=\omega v_{i,j}\left(t\right)+c_1{r}_1\left(p{b}_{i,j}\left(t\right)-x_{i,j}\left(t\right)\right)+c_2{r}_2\left(g{b}_{i,j}\left(t\right)-x_{i,j}\left(t\right)\right)$ (1)

$x_{i,j}\left(t+1\right)=x_{i,j}\left(t\right)+v_{i,j}\left(t+1\right)$ (2)

其中， $P{b}_i\left(t\right)=\left(p{b}_{i,1}\left(t\right),p{b}_{i,2}\left(t\right),\cdots ,p{b}_{i,D}\left(t\right)\right)$ 和 $G{b}_i\left(t\right)=\left(g{b}_{i,1}\left(t\right),g{b}_{i,2}\left(t\right),\cdots ,g{b}_{i,D}\left(t\right)\right)$ 分别代表第i个粒子的个人最佳和全局最佳的位置。另外， $c_1$ 和 $c_2$ 是两个学习因子，是惯性权值，这两个随机数 $r_1$ 和 $r_2$ 在区间[0, 1]中生成。其中， $c_1$ 、 $c_2$ 和 $\omega$ 是控制种群不同进化状态的关键参数 [8]，即全球勘探和局部开发。例如，如果 $c_1$ 和 $\omega$ 较大，而 $c_2$ 较小，则种群倾向于扩大搜索范围，以改善全球探索。相反，当 $c_1$ 和 $\omega$ 较小时， $c_2$ 较大时，该算法将具有更好的局部搜索能力。这样，就可以通过调整飞行参数来实现相应的进化能力。

3. 基于全局边际排序和自适应参数的改进算法(GGRAW)的介绍

3.1. 外部存档集的维护

多目标优化算法中提取非劣势个体的方法主要包括基于Pareto的优势策略 [9]，大部分算法都使用的是非Pareto的方法。然而，对于非Pareto的方法有些常见的缺点，比如极端点的排序值可能太靠近边缘，但是这些极端点的值对于后期的更新有着很重要的作用，还有在排序的过程中被选择的非支配解重复值太多，然而全局一般排序更好的解决了这一点。下面给出全局边际排序的定义。

定义1. 全局边际排序

将个体的全局边际排序定义为所有目标值的差值之和，如等式中所述(3)

$\text{GMR}\left(x_i\right)={\displaystyle {\sum }_{x_i\ne x_j}\max \left(\left({\displaystyle {\prod }_{m=1}^M{f}_m\left(x_i\right)}-{\displaystyle {\prod }_{m=1}^M{f}_m\left(x_j\right)}\right),0\right)}$ (3)

其中， $x_i$ 和 $x_j$ 是两种不同的解决方案，M是目标的数量。随着帕累托主导地位的概念， $\text{GMR}\left(x_i\right)$ 越小，越多的解决方案将占主导地位。根据等式(3)，对于空间中的任何两个个体，当且仅当 $\text{GMR}\left(x_i\right)<\text{GMR}\left(x_j\right)$ 时， $x_i$ 都优于 $x_j$。如果 $\text{GMR}\left(x_i\right)=0$， $x_i$ 将不会在种群空间中被任何其他个体所主导。下面通过一个实列来说明它的优势性

定义2. 全局密度(密度估计器)

$\text{GD}\left(x_i\right)={\displaystyle {\sum }_{j=1}^{pop}{d}_{i,j}}\left(i\ne j\right)$ (4)

这里， $\text{GD}\left(x_i\right)$ 表示粒子 $x_i$ 的整体密度， $d_{i,j}$ 是 $x_i$ 和 $x_j$ 之间的欧氏距离。 $\text{GD}\left(x_i\right)$ 值越大， $x_i$ 周围的粒子越少，个体间差异越大，分布越好。

定义3. 全局一般排序

$\text{GGR}\left(x_i\right)\triangleq \frac{\text{GMR}\left(x_i\right)}{\text{GD}\left(x_i\right)}$ (5)

这里的 $\text{GGR}\left(x_i\right)$ 表示 $x_i$ 的全局一般排名。 $\text{GGR}\left(x_i\right)$ 越小， $x_i$ 的优势就越大，这也表明 $x_i$ 的GD分布越好。根据等式(5)获得的全局一般排名，我们采取一种策略，将前一半放入外部档案，消除后半部分，以获得人口的最优前沿。这个过程一直持续到算法终止。

3.2. 自适应参数

在MOPSO中，飞行参数、惯性权重 $\omega$ 、加速度系数 $c_1$ 和 $c_2$ 对于实现种群开发和勘探之间的平衡非常重要。而全局搜索和局部细化与收敛性和多样性性能直接相关。现有的模型采用线性或非线性迭代递减策略动态调整飞行参数 [10]。然而，为了正确管理算法的性能，根据进化信息调整这些参数是非常必要的。在GGRAW中，根据 [11]，设计了 $\omega$ 、 $c_1$ 和 $c_2$ 的独立自适应调整策略。为了自适应地调整飞行参数，需要对种群进行综合评估，以获得其进化信息。本文计算的进化信息包括种群进化能力，每个粒子的进化能力和进化效率。

$U_i^{gb}\left(t\right)=\sqrt{\underset{j=1}{\overset{m}{{\displaystyle \sum }}}{\left(f_{i,j}^{gb}\left(t\right)-f_{i,j}^{gb}\left(t-1\right)\right)}^2}$

$U_i\left(t\right)=\sqrt{\underset{j=1}{\overset{m}{{\displaystyle \sum }}}{\left(f_{w,j}\left(t\right)-f_{i,j}\left(t\right)\right)}^2/\underset{j=1}{\overset{m}{{\displaystyle \sum }}}{\left(f_{w,j}\left(t\right)-f_{b,j}\left(t\right)\right)}^2}$

${\phi }_i\left(t+1\right)=\sqrt{{\left(U_i^{gb}\left(t\right)\right)}^2+{\left(U_i\left(t\right)\right)}^2}$

这里 $U^{gb}\left(t\right)=\left(U_1^{gb}\left(t\right),U_2^{gb}\left(t\right),\cdots ,U_n^{gb}\left(t\right)\right)$ 表示种群的进化能力， $U_i\left(t\right)$ 表示第i个粒子的进化能力。进化能力描述了种群或单个粒子找到比当前粒子更好的解决方案的能力。 ${\phi }_i\left(t+1\right)$ 是进化效率，它是结合种群进化来评价粒子进化能力的综合指标。对于所涉及的目标值， $f_{i,j}\left(t\right)$ 表示第i个粒子的第j个目标值， $f_{i,j}^{gb}\left(t\right)$ 表示全局领先者的第j个目标值。而 $f_{w,j}\left(t\right)$， $f_{b,j}\left(t\right)$ 分别是总体中第二差解和第二优解的第j个目标值。需要注意的是，所涉及的客观值都在[0, 1]的范围内标准化了。

根据上述计算的演化信息，可以通过( $\epsilon$ 为常数)得到第i个粒子的自适应参数

$R_i\left(t+1\right)=1/\sqrt{{\left({\phi }_i\left(t+1\right)\right)}^2+\epsilon }$ (6)

在优化过程的早期阶段，全局搜索对种群进化很重要，而也需要开发在后期阶段，细化解决方案 [5]。相应的， $\omega$ 和 $c_1$ 越大， $c_2$ 越小的条件有利于全局勘探，而 $\omega$ 和 $c_1$ 越小， $c_2$ 越大的条件促进局部开发。因此，我们设计了独立的自适应调整策略来调整每个粒子的 $\omega$ 、 $c_1$ 和 $c_2$。

${\omega }_i\left(t+1\right)={\omega }_{\max }-\left({\omega }_{\max }-{\omega }_{\min }\right)\times \sin \left(R_i\left(t+1\right)\pi /2\right)\times \frac{t}{T}$ (7)

$c_{1i}\left(t+1\right)=c_{1\max }-c_{1\max }\times \sin \left(R_i\left(t+1\right)\pi /2\right)\times \frac{t}{T}$ (8)

$c_{2i}\left(t+1\right)=c_{2\min }+c_{2\min }\times \sin \left(R_i\left(t+1\right)\pi /2\right)\times \frac{t}{T}$ (9)

其中 ${\omega }_{\max }$， ${\omega }_{\min }$ 为 $\omega$ 的最大值和最小值， $c_{1\max }$ 为 $c_1$ 的最大值， $c_{2\min }$ 为 $c_2$ 的最小值，T为预先设定的最大总体迭代次数。这样， $\omega$ 和 $c_1$ 的值就会很大，而 $c_2$ 的值在早期进化中就会很小。因此，将促进全球勘探，以扩大搜索范围。而在后期的进化过程中， $\omega$ 和 $c_1$ 会很小，而 $c_2$ 会很大。相应地，可以促进局部开发的种群收敛。这种参数调整不仅推动了近似PF向前发展，而且确保了更多样化的解。

3.3. 个体最优解和全局最优解的选取

在多目标粒子群优化算法中个体最优解的选取(Pbest)和全局最优解(Gbest)的选取是决定算法是否有效的关键性因素，因此对于选取个体最优解和全局最有解至关重要。对于个体最优解的选取通过由公式(3)计算出来的值与当前由公式(3)计算出来的值进行比较，如果当前粒子的值小于前一代粒子的值，则选取当前粒子的值作为Pbest，否则把前一代的粒子的值作为Pbest。然而对于全局最优解用外部存档集即可，算法的框架为图1。

Figure 1. Flow chart of GGRAW algorithm

图1. GGRAW算法流程图

具体步骤如下：

1) 初始化种群P且Pbest = P

2) 通过全局一般排序建立外部存档集

3) 随机生成Gbest(N)

4) 随机生成自适应参数 $\omega$ 、 $c_1$ 和 $c_2$ 个数为N

5) 设置终止条件

6) 更新种群P

7) 通过全局一般排序更新外部存档集

8) 更新Pbest，Gbest

9) for i=1:N

10) 通过种群P和Gbest更新 $R_i$

11) 更新参数 $\omega$ 、 $c_1$ 和 $c_2$

12) 结束for

13) 判断是否满足终止条件，若满足则迭代结束，否则返回第5步

14) 输出外部存档集

4. 实验结果与分析

4.1. 评价指标

在本文中，我们采用了两个综合的指标，超体积(HV)和逆代距(IGD)来量化测试算法。虽然这两个指标都能表达关于收敛性和多样性的综合信息，但一个指标不能充分评价实验算法。IGD指标主要通过计算测试算法得到的近似PF上沿真帕累托前沿的均匀分布解到其最近解的平均距离来评估算法 [11]。IGD的公式如(18)，其中Ω表示在真PF上均匀采样的一组点，Θ是通过测试算法得到的一组最优解。此外， $\left|\Omega \right|$ 表示采样点的数量， $dis\left(x,\Theta \right)$ 是Θ中 $x$ 与最近点之间的最小欧氏距离。在计算IGD时，参考采样点是由Das和Dennis在 [12] 中提出的系统方法生成的。高压指示器计算所有超立方体的并集体积，以评估算法 [13]。由所得到的解集中的解和一个参考点a形成了超立方体。HV的计算公式如(19)，其中， $\delta$ 表示勒贝格测度，用于计算超立方体的体积。 ${\theta }_i$ 为第i个解及对应参考点形成的超立方体。在计算HV时，参考 [14] 中的建议，首先使用理想点和最低点对得到的非支配解的目标值进行归一化。 $z_{\text{ideal}}$ 和 $z_{\text{nadir}}$ 分别是真PF的理想点和最低点。然后将参考点指定为(1.1、1.1、…、1.1)

$\text{IGD}\left(\Theta ,\Omega \right)\frac{{\displaystyle {\sum }_{x\in \Omega }dis\left(x,\Theta \right)}}{\left|\Omega \right|}$ (18)

$\text{HV}=\delta \left({\displaystyle {\cup }_{i=1}^{\left|Q\right|}{\theta }_i}\right)$ (19)

4.2. 实验条件及参数设置

为了更加有效的验证GGRAW算法的性能，本文选取了3个二维的测试函数(ZDT1, ZDT2, ZDT3) [15] 和两个三维的测试函数(DTLZ2 [16]，WFG4 [17])对这4种算法(MOPSO, dMOPSO, SMPSO)进行了对比测试。关于GGRAW的算法设置参数如下：种群规模100，外部存档规模为100，迭代次数为1000代， ${\omega }_{\max }=0.5$， ${\omega }_{\min }=0.42$， $c_{1\max }=2.33$， $c_{2\min }=1.21$，其他的算法参数与它被提出时的参数保持一致。

4.3. 算法的仿真分析结果

图2~6分别展示了dMOPSO, MOPSO, SMPSO, GGRAW四种算法在4.2中所提到的测试函数上的仿真结果图。从图2~6中可以看出对于算法GGRAW所获得的非劣解的收敛性除了SMPSO在测试函数ZDT2的收敛性与GGRAW算法的收敛性相差不大外，其余的情况明显好于其余三算法。从图5，图6可以很好的看出，GGRAW算法在分布性上也明显好于其余三个算法。

Figure 2. Simulation results of algorithm on test function ZDT1

图2. 算法在测试函数ZDT1上的仿真结果

Figure 3. Simulation results of algorithm on test function ZDT2

图3. 算法在测试函数ZDT2上的仿真结果

Figure 4. Simulation results of algorithm on test function ZDT3

图4. 算法在测试函数ZDT3上的仿真结果

Figure 5. Simulation results of algorithm on test function WFG4

图5. 算法在测试函数WFG4上的仿真结果

Figure 6. Simulation results of algorithm on test function DTLZ2

图6. 算法在测试函数DTLZ2上的仿真结果

4.4. 算法的收敛性与多样性的综合分析

表1和表2分别展示了dMOPSO，MOPSO，SMPSO和GGRAW四种算法在测试函数ZDT，DTLZ，WFG上独立运行50次所获得的综合指标IGD和HV的标准差和平均值。需要注意的是，表中的符号“+”表示其他MOPSOs的结果明显优于GGRAW的结果，而“−”表示结果明显差于GGRAW。而“=”表示比较算法的结果，结果与GGRAW相似。下面将根据者四种算法所获得的IGD和HV指标，对四种算法的收敛性和多样性进行综合分析。

Table 1. Indexes of various algorithms on IGD

表1. 各种算法在IGD上的指标

Table 2. Indexes of various algorithms on HV

表2. 各种算法在HV上的指标

通过表1和表2不难看出，GGRAW算法所获得的IGD和HV指标整体上是明显优于算dMOPSO，SMPSO，MOPSO，说明了GGRAW算法有较好的综合性能，从表1看可以看出GGRAW算法在表中的测试函数所获得IGD的值都是优于其余三个算法的，从表2中来看，在测试函数ZDT2中算法SMPSO与GGRAW算法在HV相差不大，在ZDT3上对于指标HV来说算法dMOPSO是优与GGRAW，但是从总体来看GGRAW算法综合性能是好于与之相比的3种算法。

5. 结论

为了更加有效地提高种群的多样性和收敛性，本文提出了基于全局边际排序和自适应参数调节的多目标粒子群算法(GGRAW)。该算法通过全局边际排序的优势性对外部存档的规模进行了有效的维护，并且在自适应参数的加持下更加使得在种群中的优秀的粒子在随后的更新迭代中得以保存和发展，有效提升了种群的多样性，同时也提高了粒子收敛到真实的Pareto的前沿的概率。将GGRAW算法在dMOPSO, MMOPSO和SMPSO三种算法在同一个环境下进行了仿真实验，实验的结果表明：GGRAW算法与其余3种算法相比较，在收敛性和综合性能上明显的改善，这就意味着GGRAW算法可以作为求解多目标优化问题的有效算法。