基于环形拓扑结构和动态邻域的多模态多目标粒子群优化算法.pdf

第2 6 卷第4期2023年8 月扬州大学学报（自然科学版）Journal of Yangzhou University(Natural Science Edition)Vol.26No.4Aug.2023基于环形拓扑结构和动态邻域的多模态多目标粒子群优化算法章恩泽，赵哲萱，韦静月，葛，蒋超*（扬州大学信息工程学院，江苏扬州2 2 512 7）摘要：传统多目标优化算法在求解多模态多目标优化问题时未充分考虑解集在决策空间中的分布特性，导致种群早熟收敛且所得Pareto解集不完整.针对该问题，提出一种基于环形拓扑结构和动态邻域的多模态多目标粒子群优化算法.为更好地平衡探索与开发，将进化过程分为2 个阶段：1）整个种群被划分为多个小型子种群和一个劣势子种群.采用基于空间距离的无重叠环形拓扑结构提升小型子种群的多样性，使得算法能搜索到更多Pareto最优解，并利用全局最优位置更新劣势子种群，提高搜索效率；2）所有粒子都跟随全局最优位置进行搜索，提高算法的搜索精度.同时，引入周期重组和一种新的全局最优位置更新策略，避免算法早熟收敛.仿真结果表明，所提算法可以有效解决多模态多目标优化问题.关键词：粒子群算法；多目标优化；多模态；环形拓扑；动态邻域中图分类号：TP301.6D0I:10.19411/j.1007-824x.2023.04.004文献标志码：A文章编号：10 0 7-8 2 4X(2023)04-0019-06在工程实际中广泛存在着一类具有多模态特性的多目标优化问题，其决策空间存在2 个或以上Pareto最优解集对应于目标空间同一Pareto前沿，该类问题被称为多模态多目标优化问题（multi-modal multi-objective optimizationproblems，M M O Ps），如路径规划问题1、建筑选址问题2 或结构优化设计3等.由于大多数已有的多目标优化算法鲜少关注解在决策空间中的多样性，所以在求解MMOPs时通常难以得到分布性良好的Pareto最优解集.近年来，一些改进的MMOPs求解算法被相继提出.Yue等11提出基于环形拓扑和特殊拥挤距离的多目标粒子群优化算法（multi-objectiveparticle swarm optimization algorithm with ring topology and special crowding distance,MO_Ring-PSO_SCD)，通过环形拓扑结构限制种群内的信息传递速度，使得种群在搜索过程中逐渐形成稳定的小生境，从而找到更多的Pareto最优解；Hu等在多模态多目标鸽群算法（multimodalmulti-objective pigeon-inspired optimization，M M O PIO)中采用映射方法将原始决策空间转化到映射空间，并根据粒子在映射空间的分布确定其邻域关系，使得种群在映射空间邻域内进化；Zhang 等51通过决策空间聚类方法将整个种群分为多个子种群，子种群内的粒子根据全局最优位置更新位置和速度，不同种群之间采用环形拓扑结构进行信息传递；Qu等6 采用自组织方法将种群划分为多个子种群进行并行搜索，提出了自组织多目标粒子群优化算法（self-organized speciation based multi-objective particle swarm optimizer，SS-M O PSO)；Zo u 等7 采用改进的差分进化策略扩大搜索范围，并利用近邻移动策略使粒子向最优解逼近且在局部范围内进行优化.上述MMOPs求解算法均难以获得完整的Pareto最优解集，且种群多样性仍有待提高.为更有效地求解MMOPs，本文基于无重叠环形拓扑结构构造粒子邻域，采用邻域最优位置替代种群的全局最优位置进行粒子更新，并引人收稿日期：2 0 2 3-0 1-10.*联系人，E-mail:.基金项目：国家自然科学基金资助项目（6 2 2 0 338 1)。引文格式：章恩泽，赵哲萱，韦静月，等基于环形拓扑结构和动态邻域的多模态多目标粒子群优化算法扬州大学学报（自然科学版），2 0 2 3，2 6（4）：19-2 4.20周期重组（periodic recombination，PR）和一种全局最优位置更新（global best positionupdating，GBPU)策略，拟提出一种新的多模态多目标粒子群优化算法（ring topologyanddynamic neighbor-hood based multi-objective particle swarm optimizer using periodic recombination and global bestposition updating,RDNMOPSO-PR-GBPU).1FRDNMOPSO-PR-GBPU算法1.1买采用邻域最优位置的粒子群算法粒子群优化（particleswarmoptimization，PSO)算法是最常用的群集智能算法之一在PSO中，种群中的每个个体根据各粒子的个体最优位置Pbest和整个种群的全局最优位置gbest来调整方向和步长，向更好的位置搜索.令x，v 分别为第t代第i个粒子的位置和速度，进行PSO更新：(1)x:+1=x;+v/+1,(2)其中为惯性权重，Ci和c为学习因子，ri和r2为o,1上服从均匀分布的随机数，pbesti为第t代第i个粒子的个体最优位置.PSO算法的收敛性虽较强，但容易陷入局部最优，故将式（1)中的全局最优位置替换为邻域最优位置nbest，进行PSO更新8 ：(3)其中nbesti为第t代第i个粒子的邻域最优位置.相较于传统PSO算法，采用邻域最优位置的PSO算法可以收敛到多个最优解附近，提高了解集的多样性，更适用于求解多模态优化问题。1.2基于空间距离的无重叠环形拓扑结构粒子群的拓扑结构决定了种群中粒子间的信息交换方式，从而直接影响算法的收敛速度.在环形拓扑结构中，粒子仅与其相邻的两个粒子共享信息，并根据各自邻域最优位置进行更新，因而能够发现更多最优解8 1.常见的环形拓扑结构一般根据粒子的索引构建邻域，如图1所示，其中1号、2 号粒子编号虽相邻，但在决策空间中距离却较远，因此该类邻域关系并不能反映粒子在决策空间中的真实分布，导致搜索效率下降.为更好地体现粒子在决策空间中的分布，本文充分考虑粒子在决策空间和目标空间的多样性，提出一种基于空间距离的无重叠环形拓扑结构，如图2 所示.对种群中所有粒子按照非支配关系和特殊拥挤距离1进行优劣排序，将排名前Ndms个粒子归类为小型子种群，其余Ndisad个粒子归人劣势子种群.由于各子种群相互独立且进行并行搜索，所以种群的多样性可进一步得以提升.以图2 中种群规模为10 的粒子群为例，根据基于特殊拥挤扬州大学学报（自然科学版）v/+1=wi+Ciri(pet i-xi)+c2 r2(gbestx),v+1=wvi+ciri(pbest i-xi)+c2 r2(nbesti-x),10Daiad9第2 6 卷6图1基于索引的环形拓扑结构Fig.1An index-based ring topology structureDssI368Ds25距离的非支配排序方法1对粒子进行排序，将编号为1、4、3的粒子置于第一个小型子种群Dss1，将编号为2、6、5的粒子置于第二个小型子种群Dss2，D s s 1和Dss2分别追随拓扑结构中粒子的邻域最优位置进行并行搜索.剩余编号为7、8、9、10 的粒子在决策空间中分布较松散且距离邻域最优解较远，为了提升搜索效率，将此类粒子并人劣势子种群Ndisad，利用全局最优位图2 基于空间距离的无重叠环形拓扑结构Fig.2A non-overlapping ring topologybased on the distance structure第4期置引导其向更好的区域进行搜索.1.3全局最优位置更新策略对于PSO算法，全局最优位置的选择直接影响整个种群的搜索方向和最终解集的质量，因而在利用PSO算法求解多目标优化问题时，为每个粒子选择合适的全局最优位置成为算法设计的关键 .针对多模态多目标优化问题，本文通过在已有邻域最优位置的周围进行局部搜索，以获得潜在的分布性更优的全局最优位置，从而在引导种群逼近Pareto最优解集的同时维护其多样性.本文设计的全局最优位置更新策略的步骤如下：1）对种群中所有粒子按照基于特殊拥挤距离的非支配排序方法进行排序，选择第一个粒子作为当前全局最优位置ghbest；2）在所有小型子种群的邻域最优位置附近生成一个新的粒子，并计算其目标函数值；3）将所有新生成的粒子和gbest合并为一个待选种群；4）对待选种群中的所有粒子按照基于特殊拥挤距离的非支配排序方法进行排序，选择第一个粒子作为下一代的全局最优位置g。1.4周期重组小型子种群采用无重叠环形拓扑结构，增加了搜寻到最优解的可能性，但由于粒子间信息流动过于单一，粒子可能表现出“趋同性”，即一旦某一粒子陷入局部最优，则可能导致与之处于同一邻域的其他粒子处于停滞状态.为引导粒子跳出局部最优，现引入周期重组策略，以增强算法的探索力度和开拓搜索范围.周期重组策略的具体步骤如下：1）对于第i个小型子种群Dssi，若其当前邻域最优位置nbesti与前3代邻域最优相同，则执行步骤2），否则跳转至步骤4）；2）保存Dss;中所有粒子的个体最优档案（personalbestarchive，PBA）和邻域最优档案（neigh-borhood best archive,NBA);3）对Dssi中粒子重新进行初始化操作，将随机新生成的粒子加人下一代种群中；4）根据式（2)（3)更新Ds中粒子，并将更新后的粒子加人到下一代种群中。2仿真结果与分析为验证本文算法的有效性，现设置3组对比实验进行仿真分析：比较参数Ndms和Ndisad取值对算法优化结果的影响；对比引入周期重组和全局最优位置更新策略前后算法性能的有效性；对比本文算法与5种已有多目标优化算法的性能.所有实验均通过MATLAB2020b编程实现，计算机配置为Intel(R）C o r e（T M）i5-9 40 0 F 2.9 0 G H z，16 G BR A M.采用8 个多模态多目标优化测试函数MMF1M M F8 1综合测试算法的性能.2.1性能评价指标选择决策空间反世代距离（the inverted generational distance in the decision space，IG D X)10 和Pareto解集逼近度（Pareto setsproximity，PSP)作为评价指标，评价算法的性能.IGDX可衡量获得的解集与真实Pareto解集的近似程度.对于解集X，有2ex-minex(D(x.),1IGDX(X)=IX*其中D(x,y)为解x和解y的欧氏距离，X*为真实Pareto解集中的均匀采样，X*为集合X*中解的总个数.IGDX的值越小，表明解集的收敛性和多样性越好.PSP既能衡量算法求得解集的收敛性和多样性，又能衡量其对真实Pareto解集的覆盖率（coverIG，CR 越大说明解集覆盖真实 Pareto 解集的比例越高.PSP 值越大表明算法CRrate,CR),PSP=章恩泽等：基于环形拓扑结构和动态邻域的多模态多目标粒子群优化算法2122综合性能越好.2.2参数取值的影响设置种群规模为6 0 0，当小型子种群Ndms与劣势子种群Nadisad之比r分别为2，4，6,8,10，12 时，参数Ndms和Naisad的取值如表1所示.图3给出了不同r值下算法运行30 次所得PSP均值.由图3可见：当r=8时，在除MMF5和MMF6外的其余6 个测试函数上PSP均值都最大，表明该取值下小型子种群和劣势子种群的数目使算法在探索和开发之间实现了更好的权衡，从dSd10080而获得更好的综合性能.602.3周期重组和全局最优位置更新策略40的有效性200MMF1对比引人周期重组和全局最优位置MMF2MMF3MMF4MMF5MMF6MMF7MMF8测试函数更新策略前后算法的有效性，PSP均值如图3不同参数取值下算法所得PSP均值表2 所示.由表2 可见：本文算法在8 个Fig.3PSP mean values obtained by the algorithm测试函数上都获得了最优结果，且在全局under different values of parameter和局部Pareto解集共存的测试函数MMF2和MMF3上优势较明显，说明周期重组和全局最优位置更新策略有助于算法跳出局部最优.表2 引入周期重组和全局最优位置更新策略前后算法的PSP均值Tab.2 PSP mean values of proposed algorithm with and without periodic recombination andglobal best position updating strategy测试函数RDNMOPSOMMF160.3683MMF2114.3737MMF3128.4308MMF4101.8074MMF531.5889MMF631.9798MMF794.6271MMF848.17962.4几种算法的性能对比为进一步验证本文算法的有效性，现与基于分解的多目标进化算法（multi-objective evolution-ary algorithm based on decomposition，M O EA/D)1I、多目标粒子群优化算法(multi-objective parti-cle swarm optimization algorithm，M O PSO)12 、决策空间小生境多目标遗传优化算法（decisionspace based niching nondominated sorting genetic algorithm II,DN-NSGA II)13、M O _ R i n g _ PSO _ SCD 11和SS-MOPSOL61等5种算法在8 个测试函数上进行对比.所有算法均设置最大评价次数为6 0 0 0 0，种群规模为6 0 0，每种算法在各测试函数上独立运行30 次，所得IGDX和PSP均值分别如表34所示.由表34可见：1）本文算法虽在MMF3和MMF7测试函数上的IGDX结果略逊于SS-MOPSO和DN-NSGAII，但在其他6 个测试函数上获得了IGDX的最小值；2）本文算法在除MMF5外的7个测试函数上PSP值均最大，表明所提算法在大多数测试函数上获得了更加逼近真实Pareto解集且分布性更好的最优解集.其可能原因是，作为传统的多目标优化算法，MOEA/D和MOPSO未针扬州大学学报（自然科学版）表1不同r值下Ndms和Ndisad的取值Tab.1Values of Nams and Naisad under different r valuesNdmsNdisad240244806516200r180F160140120FRDNMOPSO-GBPU66.073.5110.6607134.8231105.232432.387731.466995.906348.8525第2 6 卷NdisadNams1988120108412口r=2r=4r=6r=8日r=10r=12RDNMOPSO-PR65.9087113.4077138.0338106.034731.747532.747798.196948.4513531546555本文算法67.288 4127.299 2162.1087107.874 234.554533.120599.612 449.4338695445第4期对多模态情形进行特殊处理；相较于DN-NSGAII和SS-MOPSO，M O _ R i n g _ PSO _ SCD 和本文算法在信息传递时采用环形拓扑结构，在环境选择中采用特殊拥挤度距离，大大提高了解集在决策空间的分布性；本文算法和MO_Ring_PSO_SCD虽然都采用基于拥挤距离的非支配排序方式，但本文算法因引人周期重组和一种新的全局最优位置更新策略，故能帮助算法跳出局部最优，找到更接近真实Pareto最优解的解集.综上，本文算法在求解多模态多目标优化问题时更有效.测试函数MOEA/DMMF10.1403MMF20.2543MMF30.1391MMF40.4478MMF50.2956MMF60.2035MMF70.151 4MMF80.7235测试函数MOEA/DMMF17.3232MMF24.4552MMF37.2335MMF41.4646MMF53.4535MMF64.257 1MMF77.458 2MMF80.183 7参考文献：1YUE Caitong,QU Boyang,LIANG Jing.A multiobjective particle swarm optimizer using ring topology for sol-ving multimodal multiobjective problems JJ.IEEE Trans Evol Comput,2018,22(5):805-817.2LIAO Pinchao,SUN Xinlu,ZHANG Dan.A multimodal study to measure the cognitive demands of hazard rec-ognition in construction workplaces JJ.Saf Sci,2021,133:105010.3RAMACHANDRAM D,LISICKI M,SHIELDS T J,et al.Bayesian optimization on graph-structured searchspaces:optimizing deep multimodal fusion architectures JJ.Neurocomputing,2018,298:80-89.4HU Yi,WANG Jie,LIANG Jing,et al.A self-organizing multimodal multi-objective pigeon-inspired optimiza-tion algorithm JJ.Sci China Inf Sci,2019,62(7):070206.5ZHANG Weizheng,LI Guoqing,ZHANG Weiwei,et al.A cluster based PSO with leader updating mechanismand ring-topology for multimodal multi-objective optimization JJ.Swarm Evol Comput,2019,50:100569.6QU Boyang,LI Chao,LIANG Jing,et al.A self-organized speciation based multi-objective particle swarm opti-mizer for multimodal multi-objective problems JJ.Appl Soft Comput,2020,86:105886.7ZOU Juan,DENG Qi,ZHENG Jinhua,et al.A close neighbor mobility method using particle swarm optimizerfor solving multimodal optimization problems JJ.Inf Sci,2020,519(6):332-347.8许胜才，蔡军，程昀，等.基于拓扑结构与粒子变异改进的粒子群优化算法J控制与决策，2 0 19，34（2）：419-428.9XU Zhen,ZHANG Enze,CHEN Qingwei.Rotary unmanned aerial vehicles path planning in rough terrain basedon multi-objective particle swarm optimization JJ.J Syst Eng Electron,2020,31(1):130-141.10李文桦，明梦君，张涛，等，考虑全局和局部帕累托前沿的多模态多目标优化算法J自动化学报，2 0 2 3，章恩泽等：基于环形拓扑结构和动态邻域的多模态多目标粒子群优化算法Tab.3IGDX mean values of different algorithmsMOPSODN-NSGAII0.29380.02460.18460.02280.13580.01560.27640.03740.40790.06710.34800.05520.17450.010 40.647 10.0546表4不同算法的PSP均值Tab.4PSP mean values of different algorithmsMOPSODN-NSGAII2.676442.68154.562761.52625.774875.117 13.185738.42482.354 614.57592.780418.24063.596095.785 81.332 618.009023表3不同算法的IGDX均值MO_Ring_PSO_SCD0.01880.01480.00760.011 10.03560.03240.01120.0242MO_Ring_PSO_SCD53.089564.4995119.080990.177828.004230.734 888.585741.2796SS-MOPSO0.01720.01010.00620.00990.03980.03070.01160.0257SS-MOPSO55.557899.3541155.8697101.723 833.554 932.541 585.608338.8163本文算法0.016 20.007 60.00830.009 30.030 90.030 10.01230.020 2本文算法62.384 2127.2894162.1293107.456 732.246733.246 799.623 449.345 62449(1):148-160.11ZHANG Qingfu,HUI Li.MOEA/D:a multiobjective evolutionary algorithm based on decomposition LJJ.IEEE Trans Evol Comput,2007,11(6):712-731.12MOHD ZAIN M Z B,KANESAN J,CHUAH J H,et al.A multi-objective particle swarm optimization algo-rithm based on dynamic boundary search for constrained optimization J.Appl Soft Comput,2018,70:680-700.13 LIANG Jing,YUE Caitong,QU Boyang.Multimodal multi-objective optimization:a preliminary study CJ/Proceedings of the 2016 IEEE Congress on Evolutionary Computation.Vancouver,BC:IEEE,2016:2454-2461.扬州大学学报（自然科学版）第2 6 卷Multimodal multi-objective particle swarm optimization algorithmbased on ring topology and dynamic neighborhoodZHANG Enze,ZHAO Zhexuan,WEI Jingyue,GE Rui,JIANG Chao*(School of Information Engineering,Yangzhou University,Yangzhou 225127,China)Abstract:The traditional multi-objective optimization algorithm does not fully consider the distribu-tion of solutions in the decision space when solving multimodal multi-objective optimization prob-lems,resulting in premature convergence and incomplete Pareto solution sets.To solve the aboveproblem,a multimodal multi-objective particle swarm optimization algorithm based on ring topologyand dynamic neighborhood is proposed.In order to better balance exploration and exploitation,theentire evolutionary process is divided into two stages.In the first stage,the population is dividedinto several smal sub-swarms and one disadvantage sub-swarm.The non-overlapping ring topologybased on spatial distance is used to improve the diversity of small subpopulations,so that the algo-rithm can search more Pareto optimal solutions,and use the global optimal location to update theinferior subpopulations to improve the search efficiency.In the second stage,all the particles followthe global optimal position to search and improve the search accuracy.At the same time,periodicrecombination and a new global optimal position update strategy are introduced to avoid prematureconvergence.Simulation results show that the proposed algorithm can effectively solve multimodalmulti-objective optimization problems.Keywords:particle swarm optimization;multi-objective optimization;multimodal;ring topology;dynamic neighborhood(责任编辑林子)