基于R2指标的拟态物理学约束多目标优化算法

孙 宝,郭 娜,李占龙,张丽静

(1.太原科技大学 应用科学学院， 太原 030024； 2.太原科技大学 机械工程学院， 太原 030024)

1 引言

在实际问题中，绝大多数优化问题由多个子目标所组成，并且这些子目标之间相互矛盾，相互冲突，一个子目标性能的改善可能会引起其余子目标性能的降低，这种在优化过程中要求多个子目标同时在指定区域内达到最优值的问题即为多目标优化问题。针对多目标优化问题及其研究，越来越多的群体智能进化算法在自然行为的启发下得到发展，如多目标粒子群优化算法(MOPSO)、非支配排序遗传算法(NSGAII)、多目标分布估计算法(MOEDA)等。

APO算法是一种新的基于群体智能的随机优化算法。通过牛顿第二定律的启发，建立个体之间的虚拟力规则，更新个体的速度和位置，使个体移动到最优目标，并围绕全局最优收敛。APO算法已成功应用于无约束多目标优化问题。Wang Y等针对APO算法自身的性能，从多目标优化问题出发，以虚拟力的角度分析多目标算法中个体-优劣，提出一种基于虚拟力排序的约束多目标拟态物理学优化算法。Sun B等在MOAPO算法的基础上结合约束违反度的判断准则，提出一种基于序值和拥挤度的拟态物理学多目标算法(improved constrained rank multi-objective artificial physics optimization,ICRMOAPO)，但在解的筛选过程中将新的个体与archive解集中的个体进行比较，容易将优质解丢失，使其无法得到一组均匀且广泛的最优解。

近年来，对于多目标优化算法的选解机制，国内外学者做了大量的研究。Sedighizadeh D等提出了一种连续空间粒子群优化算法，通过在速度更新方程中引入新的项，使得在搜索空间中更好地进行搜索。Cai D等将目标空间分解为多个子空间，并在每个子空间上保留最优解以保持解集的分布性。Kohler M等将多样性插入到群体中，扩大搜索空间的覆盖率，提高了算法的效率和收敛速度。Garcia I C等提出了一种基于超体积指标的多目标粒子群算法，利用外部存档来存储进化过程中发现的全局非支配解，为求解多目标问题提出了一种新的思考方向。Li F团队针对HV指标难以有效权衡计算时间复杂度和计算精度之间的矛盾进行研究，发现R2指标可以替代HV指标求解多目标问题，将R2指标和PBI分解策略结合求解多目标优化问题,提出了R2-MOPSO算法。

针对ICRMOAPO算法的不足，为了得到收敛于Pareto前沿且均匀分布的解，利用R2指标综合评价解集的特质，提出一种基于R2指标的拟态物理学约束多目标优化算法(R2-ICRMOAPO)。算法将非支配排序和R2指标结合，并根据R2指标的贡献值对外部存储集进行更新和维护，保留分布均匀的精英解。

2 约束多目标优化问题

一般地,约束多目标优化问题的数学模型可以被描述为：

min()=[(),(),…,()]

s.t.()=((),()…,())<0

()=((),()…,())=0

(1)

式中，=[,,…,]∈为决策变量，决策空间∈，

满足边界约束条件：≤≤,1≤≤，,分别为的上界和下界；()为目标函数；()<0为不等式约束条件，()=0为等式约束条件，约束条件决定可行域的范围。

1pareto支配

Pareto支配，记为<，其中为支配解，为非支配解，当且仅当∀∈{1,2,…,},()≤()，∃∈{1,2,…,},s.t.()<()。

2Pareto最优解集

对于一个约束多目标优化问题，它的可行决策空间中所有最优解的集合称为Pareto最优解集，令其为。

(2)

3Pareto前沿

Pareto最优解集中每个解对应的目标值向量组成的集合称为Pareto前沿。

约束多目标优化问题就是要得到一组解集，使之逼近Pareto前沿。在目标空间中则表示为，非支配解集覆盖的目标空间区域尽可能大，且与真实前沿的距离尽可能小。

3 拟态物理学算法

拟态物理学是由美国怀俄名州立大学的Spear等人以自然物理力量为动力所提出来的，受启发于物理力学定律，故称之为“拟态”，最初被应用于机器人群体的分布式控制研究。

文献[5]中利用拟态物理学的思想处理全局优化问题，提出一种新的优化算法APO。该方法本质上是通过对牛顿第二定律的模拟，将问题可行域中采样的个体粒子看作是物理中的质点，在粒子之间虚构一种相互作用力，给出该作用力的计算规则，结合个体的速度和位移更新粒子的运动，实现对整个种群的控制。

在APO算法中，种群规模为，个体在维上的速度表示为,，个体在维上位置表示为,。第个个体的质量为(=1,2,…,)，且个体的质量随着适应值的改变而改变，适应值小的个体质量大，适应值大的个体质量反而小。此外个体质量还受到种群中适应度值最优和最差个体的影响，进而影响个体所受的力。所以，计算个体质量函数定义为：

(3)

式中：、分别表示最优、最差适应值的位置。

由每个个体质量，仿照万有引力公式，计算出各个个体所受作用力的大小，故个体在第维上所受的第个(≠)个体的虚拟力为,：

(4)

个体在第维上所受作用力合力的计算公式为：

(5)

式中，为引力因子。

个体的速度和位置更新公式为：

,(+1)=,()+,, ∀≠

(6)

,(+1)=,()+,(+1), ∀≠

(7)

式中：∈(0,1)为惯性权重；为分布在区间[0，1]上的一个随机数；∈[,]；∈[,]。

4 R2-ICRMOAPO算法

随着约束多目标问题的广泛应用，相应的约束多目标优化算法也层出不穷。非支配解的选取是解决约束多目标问题的重要技术之一，直接影响算法的性能。ICRMOAPO 算法通过比较新的非支配个体和archive集中的个体来获得新的外部存储集，在一定程度上对问题进行了求解，但由于没有严格地对解集进行筛选，可能会使一些优质个体缺失。R2指标可以很好地解决这一问题，利用个体的R2指标贡献值，对个体进行筛选，可以得到一组性能较好的解集。

4.1 R2指标

R2指标是基于效用函数，区分候选解的优劣，从而选择效用较大的候选解，最初被用于评价2组个体的相对质量。利用具有特定参考点的标准加权切比雪夫函数，可以用该指标相对于参考点来评估单个个体集合的质量。因R2指标可以综合评价种群的收敛性和多样性,并可以通过快速计算获得均匀分布的解集,已被应用于求解多目标优化问题。

在此利用加权切比雪夫函数作为R2指标的效用函数，通过一组个体(集合)和参考点对个体的质量进行评价：

(8)

式中：为一组均匀的权重向量，每个权重向量=(，，…，)∈，均匀的分布在目标空间中，1||代表每个权重向量被选择的概率。

如果效用函数集中每个函数由于不同的权重向量而确定,则个体的R2指标的贡献值被定义为：

CR2(,,,)=R2(,,)-R2({},,)

(9)

通过R2指标的贡献值可以对种群中的个体进行全排序,R2指标的贡献值越大说明解集的分布性能越好，解的质量越高，将其保留到下一代种群的概率就越大。

4.2 R2-ICRMOAPO算法基本思想

外部存储集非支配个体的选取对算法的收敛性和分布性具有直接的影响，在算法的迭代进化过程中，非支配解的数量也在同步增加，并且可能会超过预先设定的解集规模，因此外部存储集的更新和维护对于解集的质量起着非常重要的作用。本研究在ICRMOAPO算法的基础上，将非支配排序和R2指标结合，首先利用Pareto支配关系得到一组非支配解集，计算出非支配解集中个体的R2指标贡献值，然后将R2指标贡献值作为外部存储集的更新机制，通过删减R2指标贡献值较小的个体，实现对整个种群的控制，从而选择出效用更好的候选解。针对上述思想构造出一种R2-ICRMOAPO算法，为求解约束多目标优化问题提供一种新的思路。算法的关键要素如下：

1) 个体序值

设在第代生成的种群()由个个体所组成，()表示种群()中支配个体的所有个体数量，则个体在第代的序值定义为：

()=1+()

(10)

依据个体序值的定义，为种群中所有的支配个体，分配相对应的序值。但若在某一代中出现具有相同序值的个体，则需要从其他角度对此问题进行解决。

2) 邻域半径

针对序值相同的个体，下面引入邻域半径的定义。

定义个体的邻域为该个体半径内所包含的区域。为了避免算法中邻域半径过小，故将邻域半径定义为：

(11)

式中，max||为初始化时第维上个体间的最大欧式距离。

3) 邻域拥挤度

邻域拥挤度是指在个体间支配与被支配的作用下所计算出某个个体在对应邻域半径区域内所包含个体数量的大小。

当出现序值大小相同，邻域拥挤度也相同的个体时，将邻域半径重新调整。若调整后，具有相同序值的个体在相应邻域半径内还包含相同的个体数量，将这些个体随机进行排列，分配编号即可。

4) 质量函数

为了考虑个体间的支配关系和个体所处邻域半径内的拥挤程度，并充分体现多目标优化问题本身的特点，将质量函数定义为：

(12)

5) 引力因子

引力因子是影响算法性能的重要因素之一，在一定程度上会决定种群做收敛运动的个体数量。在标准APO算法中，将引力因子规定为10。R2-ICRMOAPO算法为了使引力因子随种群的进化而产生动态的变化，将其进行改进，令为：

(13)

式中：和为引力因子的初始值和终值，由经验可知，算法中=70，迭代到最后，的终取值为=1；为迭代次数；为最大迭代次数。

6) 惯性权重

惯性权重的选取影响算法的性能和效率，迭代初期较大的惯性权重使算法保持较强的全局搜索能力，迭代后期较小的惯性权重有利于算法进行更精确的局部搜索。

在R2-ICRMOAPO算法中采用线性递减的惯性权重，使惯性权重随着迭代的进行而动态减小：

(14)

式中：为初始值，算法中取09；为终值，算法中取04。

7) 不可行度

不可行度可以作为一种准则来判断更新个体是否落入可行域中。

R2-ICRMOAPO算法中定义不可行度为：

(15)

式中:、分别为多目标优化问题的不等式约束和等式约束。当为可行解时，不可行度为0。

4.3 R2-ICRMOAPO算法流程

R2-ICRMOAPO算法流程如图1所示。

图1 R2-ICRMOAPO算法流程框图Fig.1 R2-ICRMOAPO algorithm flowchart

R2-ICRMOAPO算法的主要步骤如下：

Step 1：初始化种群：种群规模，外部存储集规模archivesize，权重向量，最大迭代次数，随机产生所有个体的初始速度和位置，初始化参考点。

Step 2：计算所有个体在每个目标下的适应度值，确定非支配个体，存储于archive集。对非支配个体的序值定义为1，其余个体的序值定义为+1。

Step 3：对archive集中的非支配个体计算R2指标贡献值，按降序原则进行排序。

Step 4：根据个体序值的定义，对种群中所有个体按照升序原则进行排序。

Step 5：利用欧式距离计算邻域半径，若出现序值相等的个体，重新确定个体邻域拥挤度，按升序原则对全部个体重新进行排序。

Step 6：出现邻域半径内包含相同个体数量的同序值个体时，将该个体标记为()=1。

Step 7：()=1时，对邻域半径进行调整并重新排序，对于调整后序值大小和拥挤度相等的个体，进行随机排序。对所有个体赋予1～的自然数，作为每个个体序号，记作()。

Step 8：计算每个个体的质量，个体在第维上所受的第个(≠)个体的虚拟力,，在第维上所受作用力的合力,。

Step 9：根据式(6)、式(7)更新个体的速度和位置。

Step 10：利用不可行度的判断准则来确定所更新的个体是否落在可行域内，将未落入可行域内的个体用最优迭代更新的方法重新更新其位置。

Step 11：确定新的非支配个体，更新archive集，当archive集中都是非支配个体时，对所有个体计算CR2值，按照降序原则进行排序，若个体数量超过archive集规模时，将archive集中R2指标贡献值较小的个体删除，直到个体数量满足设定的规模，获得新的archive集。

Step 12：若达到最大迭代次数则退出，否则返回步骤5。

5 实验结果与分析

为了评估R2-ICRMOAPO算法在解决约束多目标问题时的性能，通过R2-ICRMOAPO算法和其他四种优化算法：基于序值与拥挤度的拟态物理学多目标算法(improved constrained rank multi-objective artificial physics optimization，ICRMOAPO)、带精英策略的非支配排序的遗传算法 (non-dominated sorting genetic algorithm，NSGAII)、基于R2指标的多目标粒子群算法(multi-objective particle swarm optimization on R2 indicator,R2MOPSO)、ε多目标进化算法(epsilon multi-objective evolutionary algorithm,ε-MOEA)在标准约束多目标测试函数上进行实验对比，并将超体积(Hypervolume,HV)和反转世代距离(inverted generational distance，IGD)作为算法的性能评价指标，从收敛性和分布性对算法进行综合评价，全面说明算法的有效性。

本文选定的测试函数如表1所示。

表1 约束多目标标准测试函数Table 1 Constrained multi-objective standard test functions

实验中，设定种群规模和外部存储集规模均为100，进化代数为50。图2～图4表示算法R2-ICRMOAPO、ICRMOAPO、R2MOPSO、NSGAII、和ε-MOEA对测试函数生成的Pareto前沿和真实Pareto前沿曲线。

图2 Binh(2)的Pareto前沿曲线Fig.2 The Pareto Frontier of Binh (2)

图3 SRN的Pareto前沿曲线Fig.3 The Pareto Frontier of SRN

图4 DEB的Pareto前沿曲线Fig.4 The Pareto Frontier of DEB

图5～图7显示了R2-ICRMOAPO算法所求得Pareto 解集中更新个体的位置。

图5 Binh(2)的Pareto解集中更新个体位置曲线Fig.5 The updated position of Binh(2)

图6 SRN的Pareto解集中更新个体位置曲线Fig.6 The updated position of SRN

图7 DEB的Pareto解集中更新个体位置曲线Fig.7 The updated position of DEB

大多数研究使用逼近实际解决方案的程度和设置解决方案的分布情况来测量多目标优化算法的性能。本文采用HV和IGD算法性能指标对5种算法进行对比。

HV指标是一种能够同时衡量算法的收敛性和分布性的综合性能指标，表示非支配解集覆盖的目标空间区域大小。HV函数的定义为：

(16)

式中：为Lebesgue测度,用来测量体积；||为非支配解的数目；为参照点与解集中第个解所构成的超体积。算法求得的HV值越大则意味着解集收敛性和分布性越好。

IGD指标是一种综合评价解集质量的指标，衡量的是真实前沿的个体到所求得的近似解集之间最小距离的平均值。IGD的函数定义为：

(17)

对测试函数进行了100次独立实验后，表2～表3分别展示了5种算法关于HV和IGD性能指标的平均值、最优值和方差。此外，还采用统计学Wilcoxon秩和检验来表明结果的显著性水平，显著性差异水平为0.05，如果值大于0.05，则表示2种算法之间没有明显差异。

表2 测试函数的HV指标值Table 2 HV performance indicators on test functions

表3 测试函数的IGD指标值Table 3 IGD performance indicators on test functions

从表2和表3可以看出，R2-ICRMOAPO算法的HV值高于ICRMOAPO算法，且IGD值低于ICRMOAPO算法。数据表明，利用R2指标贡献值对个体进行筛选，提高了算法的收敛性和分布性。

从图2～图4和表2～表3可知，R2-ICRMOAPO算法在测试函数Binh(2)和SRN上对Pareto前沿产生了更好的近似，得到的解大部分够收敛于真实的Pareto前沿上，在DEB函数上略差于NSGAII算法。以上数据和图表表明，R2-ICRMOAPO算法在大多数测试问题上优于对比算法，说明R2-ICRMOAPO算法在解决约束多目标问题方面具有很大的潜力，可进一步推广应用于实际问题中。

6 结论

在APO算法的基础上，针对约束多目标优化算法，构造基于R2指标的多目标约束优化算法，将非支配排序和R2指标结合，利用R2指标贡献值区分候选解的优劣，更新最优个体，维护外部存储集；将其与4种算法在HV和IGD指标下进行对比实验。主要得到以下结论：

1) 算法利用个体间的支配关系，考虑个体的拥挤度，对搜索空间中个体适应值合理排序，增强了Pareto 解集的多样性。

2) 设计R2指标贡献值选择个体，对外部存储集进行维护和更新，增强了种群的分布，在处理约束多目标问题中取得较好的效果。

3) 该算法在求解约束多目标的问题中收敛性和分布性均得到提高，但对于提高收敛速度还需进行研究。