双子群自适应变异多目标粒子群算法

摘 要：多目标粒子群优化算法因其强大的搜索能力和简单的实现方式受到广泛关注，然而它在收敛性和多样性之间常常存在不平衡的问题。为了解决这一问题，作者提出了一种双子群自适应变异多目标粒子群算法（BAMOPSO），旨在更好地平衡收敛性和多样性。首先，采用一种新颖的双子群初始化方法，使粒子在目标空间中分布更均匀，从而提高算法的多样性。其次，设计了一种新的自适应变异策略，依据进化过程中目标函数值的变化来提升收敛性。最后，通过将BAMOPSO算法与六个经典多目标优化算法在十五个基准测试函数上进行比较实验，验证了该算法在平衡收敛性和多样性方面的显著提升。

关键词：多目标粒子群优化算法；双子群；自适应变异；

中图分类号：TP18" " " " " " " " " " " " " " " " " " " " " " " " " " " 文献标识码：A文章编号：1009-3583（2024）-0086-08

Binary Group Adaptive Variation Multi-objective Particle Swarm Optimization Algorithm

CHEN Jian-jie1， LIU Yan-min2*， LUO Yi3

（1. College of Data Science and Information Engineering， Guizhou Minzu University， Guiyang 550025， China; 2. School of Mathematics， Zunyi Normal University， Zunyi 563006， China; 3. School of Mathematics and Statistics， Guizhou University， Guiyang 550025， China）’

Abstract： Multi-objective particle swarm optimization has been widely concerned because of its powerful search ability and simple implementation， but it often has an imbalance between convergence and diversity. To solve this problem， a binary group adaptive variation multi-objective particle swarm optimization （BAMOPSO） algorithm is proposed to better balance convergence and diversity. Firstly， a novel binary group initialization method is used to make the particles more evenly distributed in the target space， thus improving the diversity of the algorithm. Secondly， a new adaptive variation strategy is designed to improve the convergence according to the change of the objective function value during evolution. Finally， by comparing BAMOPSO algorithm with six classical multi-objective optimization algorithms on 15 benchmark functions， it is verified that the algorithm has a significant improvement in balance convergence and diversity.

Keywords： multi-objective particle swarm optimization algorithm; binary group; adaptive variation

粒子群优化（Particle swarm optimization， PSO）[1]最早由Eberhart和Kennedy于1995年提出。PSO是一种基于群体智能的优化算法，它通过模仿鸟类等生物的社会行为来寻找最优解。与鸟一样，PSO中的候选解（也称为粒子）通常由两个关键部分组成：飞行速度和当前位置，它们根据自身的飞行历史信息和整个社会群体在进化过程中的飞行经验进行动态调整。由于其结构和实现的简单性，粒子群算法具有许多优点，不仅在目标函数优化、神经网络训练等各种数学优化领域表现出良好的性能，而且在工程优化中的制造控制、云计算中的多源调度等诸多实际优化问题中得到广泛应用。然而，与其他经典群智能优化算法一样，粒子群优化算法也存在收敛性和多样性不平衡的问题，特别是在处理大规模复杂优化问题时。

现实生活中存在的问题往往和理想状态下设想的问题相差很大，实际工程优化中的制造控制、云计算中的多源调度等诸多实际优化问题，多数都存在多个难以平衡相互冲突的目标，即多目标优化问题（Multi-objective Optimization Problems，MOPs）[2，3]。为了更好处理现实生活中遇到的诸多多目标问题，Coell和Lechuga等将原先的单目标优化问题（Particle swarm optimization， PSO）改进拓展为多目标粒子群算法（Multi-objective Particle Swarm Optimization ， MOPSO）[4]。从单目标到多目标的扩展虽然在很多方面大大优化了求解中的很多问题，然而这种扩展也不可避免地引出了新的MOPSO问题，即算法的解在收敛性和多样性方面很容易失衡。为了得到更好的多目标优化算法，研究者们设计了很多不同的策略来解决收敛性和多样性不平衡的问题，这也为多目标粒子群优化算法提供了新的研究方向。

为了更好平衡收敛性和多样性，提高粒子群算法的性能，人们提出了多种策略。最近兴起了一种通过修改原始随机初始化种群而选择自定义初始化种群的方法来增加种群多样性，研究者通过特定的方法产生一个或多个种群来达到增加种群多样性的目的。Chao Wang[5]等提出了一种基于双种群的进化算法，其中一个种群用于位置优化，另一个种群用于半径优化。这两个种群在进化过程中迭代交换从精英解中获得的信息，协同搜索问题的最优解。Bui[6]等在所提算法DPP2中，试图让种群达到这两个标准，但为这些标准设定的优先级有所不同。一个种群的重点是实现更好的收敛性（通过使用基于帕累托的排序方案），另一个种群的重点是确保种群的多样性（通过使用基于分解的方法）。之后，通过合作机制将两个种群进行融合，形成一个新的组合种群，希望使种群同时具有收敛和多样性的特征。Li[7]等提出了一种基于双种群的大规模多目标优化算法LSTPA。在该算法中，将解分为两个子种群：收敛子种群（CP）和多样性子种群（DP），分别以提高种群收敛和多样性为目标。

可以看出，为了丰富和提升种群多样性和收敛性，学者们对种群进行了不同的划分和改进，通过这些操作很大程度上丰富和增强了种群的多样性和收敛性。此外，另一批学者选择另辟蹊径，企图通过操作变异手段来提升种群的多样性和收敛性平衡。Tao[8]等提出了一种基于多尺度自适应协同突变策略的粒子群优化算法（MSCPSO）。在该方法中，采用不同标准差的多尺度高斯突变，以提高充分搜索整个解空间的能力。在采用的多尺度突变策略中，大尺度突变可以使种群在早期探索全局解空间，快速找到较优解区域，从而避免过早收敛，同时加快收敛速度，而小尺度突变可以使种群在后期更准确地挖掘局部最优解区域，从而提高最终解的准确性。Yang[9]等在改进的粒子群优化算法中引入自适应变异，提高了粒子群优化算法的收敛性和多样性平衡。突变概率根据种群适应度的方差进行调整。采用非线性递减策略调整惯性权值，增强搜索能力，使其能够放弃局部最优解而找到全局最优解。

综合前述改进策略，本文提出了一种双子群自适应变异多目标粒子群算法（BAMOPSO），旨在提高种群的平衡收敛性和多样性。首先，利用均匀采样和拉丁超立方体采样方法生成两个子群。其次，根据种群进化中目标函数值标准差的变化情况，设计了一种自适应突变策略。最后，将提出算法BAMOPSO与六个经典多目标优化算法在十五个基准测试函数上进行实验结果比较，验证了所提出的算法对平衡收敛性和多样性有明显提升。

1" "基本概念

1.1" 多目标优化问题

通常多目标优化问题都是以最小化问题为例，对于最大化问题通过取相反数的形式化为最小化问题进行求解。由于多目标优化问题的多准则性质，解的“最优性”必须重新定义，从而产生了帕累托最优性的概念。与单目标优化情况相反，多目标优化问题的特点是权衡，因此，有大量的帕累托最优解。

1.2" 粒子群优化

2" "算法设计

2.1" 双子群初始化

现有的大多数MOPS算法基本上初始化种群都采用随机初始化，这会导致搜索空间中的粒子分散不均匀从而陷入局部最优。本文利用均匀采样（Uniform Sampling，缩写US）和拉丁超立方采样（Latin Hypercube Sampling，缩写为LHS）来分别生成两个子群，然后将两个子群合并为一个主种群来增加种群多样性。

均匀采样（US）能够确保粒子在搜索空间的均匀覆盖，避免了某些区域的过度集中，其实现简单，易于操作和理解。通过均匀覆盖整个搜索空间，减少陷入局部最优的可能性。假设有N个样本，每个样本有M个维度，则均匀采样（US）公式为：xi，j～U（0，1），其中xi，j为样本在目标空间中的每个维度j∈{1，2，…，M}上均匀分布生成的，i∈{1，2，…，M}为每个样本的索引。将生成的样本从单位区间[0，1]映射到目标空间的实际范围[targetmin，targetmax]产生目标粒子：

我们利用均匀采样（US）生成的第一个子群PA和拉丁超立方体采样（LHS）生成的第二个子群PB合并后得到主种群P，种群P综合两子群的优点，均匀采样提供了广泛且均匀的搜索空间覆盖，而拉丁超立方体采样确保每个维度的样本分布均匀。这种组合方法提高了搜索的全面性，增强全局探索能力，减少局部最优的影响，从而提升优化算法的性能。

2.2" 自适应变异策略

目前普遍使用的变异方式大多是无规律随机变异，这种变异无法根据搜索环境控制变异程度，往往会把一个优的粒子变异为一个劣的粒子导致算法性能变差。本文提出了一种根据粒子群在搜索过程中的目标函数值标准差变化情况自适应改变变异率，从而提升了算法的收敛性。

如图 1函数值对应图中我们可以看出虽然函数值均值最贴合收敛距离，但由于迭代后期均值基本保持不变这违背我们需要的变异期望（我们希望迭代后期对粒子进行扰动）。因此，函数值的标准差是最优反映了收敛到真实帕累托前沿变化情况，我们可以利用函数值的标准差来动态调整变异过程的变异率。

当检测到当前代种群位于优的位置时，下一次迭代就减小这个粒子的变异率。反之，当种群在当前代位于劣的位置则在下一次迭代中增加变异率。而判断种群位置的优劣则通过计算目标函数值的标准差衡量，将当前代目标函数的标准差与上一代目标函数标准差进行比较来调节适合的变异率。首先，将第一次种群初始化后的目标函数值计算其标准差记为S0，再把种群第一次迭代的目标函数值记为S1，计算绝对值标准差：€%]=€HLS1-S0€HL。其次，根据€%]的变化情况设置相应的变异率，计算公式如下：

2.3 算法步骤

3" "仿真实验与结果分析

3.1" 性能指标

3.2" 实验设计

本文将五个ZDT[13]基准测试函数和十个UF[14]基准测试函数用于评估本文提出的BAMOPSO算法的性能。这些测试问题都具有不同的复杂特征和形状，能够更为全面评估算法的性能。为了验证提出算法的性能，使用了拥有较强竞争力的NMPSO[15]、MPSOD[16]、MOEADD[17]、NSGAIII[18]、SPEAR[19]、MOPSO[4]六个经典的多目标优化算法进行比较。

3.3" 实验参数设置

本文使用了双目标测试函数ZDT系列、UF系列以及三目标测试函数UF8-UF-10来验证算法的综合性能，本文通过将所有对比算法的参数都与原算法保持一致来保证各个算法之间更具有可比性和公平性。设置种群规模为200，外部存档的阈值也为200，最大评估次数设置为10000，每个算法在每个测试函数上独立运行30次。此外所有算法实验数据都是在AMD Ryzen 7 4800U with Radeon Graphics 1.80 GHz、windows 11系统，MATLAB R2022b条件下实现的。对比算法的原代码均由 PlatEMO[20]提供。

3.4" 实验结果与分析

为了更好地验证改进算法的综合性能，本次实验选择了ZDT 系列和 UF 系列中的 15个基准测试函数进行测试。这些函数用于评估算法在不同条件下的表现，并通过表1、表2详细分析实验结果，以全面了解改进算法的实际效果和优越性。表1和表2显示了算法NMOPSO、MPSOD、MOEADD、NSGAIII、SPEA、MOPSO和BAMOPSO在 ZDT和UF系列基准问题上独立运行 30 次的IGD和HV的平均值及标准差结果。这些结果作为算法评估的标准，以平均值（mean）和标准差（std）形式表示，并且在IGD和HV上的最佳结果已加粗标出。

表1展示了包括经典算法MOPSO、MPSOD、NSGAIII、MOEADD 、SPEAR、NMPSO以及提出算法BAEMOPSO在ZDT和UF系列测试函数上的IGD指标的平均值和标准差。通过对这些数据的分析，可以看出改进算法BAEMOPSO在大多数测试函数中都取得了最佳的结果。尽管BAEMOPSO在ZDT6和UF1、2、4、5、6上的表现并不是绝对最优，但其最优结果个数依然多于其他六种经典算法。此外，BAEMOPSO在ZDT系列的测试函数中表现出显著的优势，得益于其使用了双子群初始化种群和自适应变异策略。这两种策略有效地提高了算法的收敛性和种群多样性，从而在整体性能上取得了提升。结合表 1中的数据，我们可以得出结论：改进算法BAEMOPSO在所有15个测试函数中表现最为出色，相较于其他经典算法，具有明显的优势。这一结果不仅证明了BAEMOPSO算法的有效性，也展示了其在多目标优化问题中的良好性能。

表2展示了六种经典算法MOPSO、MPSOD、NSGAIII、MOEADD 、SPEAR、NMPSO，以及提出算法BAEMOPS在ZDT和UF系列测试函数（包括ZDT和UF系列）上的HV指标的平均值和标准差。从表2中可以直观看出与其他六种经典算法相比，BAEMOPSO在十五个测试函数中有超过一半多的测试函数结果比其他算法优。总体而言， BAEMOPSO在所有15个测试函数上表现最佳，验证了提出算法的优越性能，展示了其在多目标优化问题中的强大优化性能。

为了更直观地展示算法性能差异，图3展示了七个算法在ZDT1测试问题中收敛情况结果。这些图表明了Pareto最优解在理想解附近的分布情况。具体来看，在ZDT1问题中，NMPSO 算法的Pareto最优解虽然接近理想解，但分布较为集中在中间区域，表现出多样性较差的分布特征。与其相比，BAMOPSO算法的Pareto最优解不仅接近理想解，而且在理想解附近的分布较为均匀，明显多样性更好。相比于其他六个算法BAMOPSO的收敛性远远优于它们，这直观展示了提出的算法具有较强竞争力。

图4 展示了七个算法在ZDT3测试问题上的PF图，与在ZDT1测试函数上情况一样，虽然NMPSO在收敛到真实Pareto时表现很好，但也显示了它的收敛都是局部最优的缺点，与之相比，本文所提出的算法BAMOPSO不仅能收敛到真实Pareto前沿而且分布更加均匀。此外，相比其他六种算法所提出的算法无论收敛性还是多样性都表现出更优，这说明BAMOPSO算法的收敛性能和多样性能都有更好的竞争力。

图5展示了对比算法与提出的BAMOPSO算法在ZDT1和ZDT3问题上的IGD值收敛轨迹。通过图中的信息，可以观察到所有算法IGD值的变化趋势，同时明显可以看出，BAMOPSO算法的收敛速度相比对比算法更为迅速。

图6展示了七种算法在ZDT系列问题上的IGD值箱型图，其中1至7分别代表算法MOPSO、MPSOD、NSGAIII、MOEADD、SPEAR、NMPSO和BAMOPSO。从图中可以观察到各算法数据的离散分布情况，可以看出BAMOPSO算法的数据波动相对较小。

4" "结语

本文提出了一种新型的双子群自适应变异算法，简称BAMOPSO算法，该算法采用不同的种群初始化方法和自适应变异技术。具体来说，BAMOPSO算法通过两种特定的初始化方法来生成两个不同的子种群，从而有效增加了整体种群的多样性。另外，根据目标函数值的变化情况动态调整变异率，以提升算法的收敛性。为了验证算法的有效性，将BAMOPSO与其他六种现有算法进行了标准测试基准问题的对比实验。实验结果表明，相较于其他算法，BAMOPSO在解决ZDT和UF系列测试问题时展现出了显著的优势，显示出其在处理多目标优化问题方面的强大竞争力。

参考文献：

[1]Kennedy J， Eberhart R. Particle swarm optimization[C]Pro- ceedings of the 1995 IEEE international conference on neural networks. ieee， 1995（4）： 1942-1948.

[2]Ali S， Ullah K， Hafeez G， et al. Solving day-ahead scheduling problem with multi-objective energy optimization for demand side management in smart grid[J]. Engineering Science and Technology， an International Journal， 2022（36）： 101135.

[3]XIONG G， SHUAI M， HU X. Combined heat and power economic emission dispatch using improved bare-bone multi- objective particle swarm optimization[J]. Energy， 2022， 244 （1）： 123108.

[4]COELLO C， LECHUGA S. MOPSO： a proposal for multiple objective particle swarm optimization [C].Proceedings of the 2002 Congress on Evolutionary Computation. CEC'02 （Cat. No. 02TH8600）. IEEE， 2002（ 2）： 1051-1056.

[5]Wang C， Wang Z， Tian Y， et al. A dual-population based evol- utionary algorithm for multi-objective location problem under uncertainty of facilities[J]. IEEE Transactions on Intelligent Transportation Systems， 2021， 23（7）： 7692-7707.

[6]Bui L T， Nguyen T T. A modified dual-population approach for solving multi-objective problems[C]. 21st Asia Pacific Symposium on Intelligent and Evolutionary Systems（IES）. IEEE， 2017： 89-94.

[7]Li B， Zhang Y， Yang P， et al. A two-population algorithm for large-scale multi-objective optimization based on fitness- aware operator and adaptive environmental selection[J]. IEEE Transactions on Evolutionary Computation， 2023.

[8]Tao X， Guo W， Li Q， et al. Multiple scale self-adaptive coop- eration mutation strategy-based particle swarm optimization[J]. Applied Soft Computing， 2020， 89： 106124.

[9]Yang H， Yang Z， Tian A， et al. Particle swarm optimization based on adaptive mutation and diminishing inerita weights[C]. 2013 Ninth International Conference on Natural Computa- tion （ICNC）. IEEE， 2013： 549-553.

[10]HAN H， LU W，QIAO J. An adaptive multiobjective particle " "swarm optimization based on multiple adaptive methods[J]. " IEEE Transactions on Cybernetics， 2017， 47（9）： 2754-2767.

[11]COELLO C A C， CORTES N C. Solving multiobjective op " "timization problems using an artificial immune system[J]. " Genetic Programming and Evolvable Machines，2005，6（2）： " "163-190.

[12]ZITZLER E， THIELE L. Multiobjective evolutionary algor- " ithms： a comparative case study and the strength Pareto ap- " proach[J]. IEEE Transactions on Evolutionary Computation， " 1999， 3（4）： 257-271.

[13]ZITZLER E， DEB K， THIELE L. Comparison of multi ob- " jective evolutionary algorithms： Empirical results[J]. Evol- " utionary Computation， 2000， 8（2）： 173-195.

[14]ZHANG Q， ZHOU A， ZHAO S， et al. Multiobjective optimi- " zation test instances for the CEC 2009 special session and " competition[J]. Mechanical engineering， 2008（264）： 1-30.

[15]LIN Q， LIU S， ZHU Q， et al. Particle swarm optimization " with a balanceable fitness estimation for many-objective op- " timization problems[J]. IEEE Transactions on Evolutionary " Computation， 2016， 22（1）： 32-46.

[16]DAI C， WANG Y， YE M. A new multi-objective particle " swarm optimization algorithm based on decomposition[J]. " Information Sciences， 2015（325）： 541-557.

[17]LI K， DEB K， ZHANG Q， et al. An evolutionary many-ob- " jective optimization algorithm based on dominance and de- " composition[J]. IEEE Transactions on Evolutionary Compu- " tation， 2014， 19（5）： 694-716.

[18]DEB K， JAIN H. An evolutionary many-objective optimiza- " tion algorithm using reference-point-based nondominated " sorting approach， part I： solving problems with box constra- " ints[J]. IEEE Transactions on Evolutionary Computation， " 2013， 18（4）： 577-601.

[19]JIANG，YANG S. A strength Pareto evolutionary algorithm " based on reference direction for multiobjective and many-ob- " jective optimization[J]. IEEE Transactions on Evolutionary " Computation， 2017， 21（3）： 329-346.

[20]TIAN Y， CHENG R， ZHANG X， et al. PlatEMO： A MATLAB " "platform for evolutionary multi-objective optimization [edu- " cational forum][J]. IEEE Computational Intelligence Maga- " zine， 2017， 12（4）： 73-87.

（责任编辑：罗东升）