基于聚类和高斯变异的多目标粒子群算法.pdf

为了解决工程中遇到的多目标优化问题，提出一种改进的多目标粒子群算法。首先，加人动态非线性余弦变化惯性参数，提升了算法的寻优能力；然后，提出一种改进的Pareto支配关系更新粒子的个体最优解，并根据拥挤距离对外部存档进行维护，提高了解集分布的均匀性；最后，将K-means聚类算法和高斯变异算法融合到多目标粒子群算法的迭代过程中，避免算法陷人局部最优解。在5个测试函数上进行仿真实验，结果表明，在保持解的均匀性和多样性的同时，改进算法使得Pareto解集具有更好的收敛性。关键词：多目标优化；粒子群算法；K-means聚类；高斯变异中图分类号：TN823文献标志码：A文章编号：10 0 1-9146（2 0 2 3)0 3-0 0 0 1-0 80引言粒子群算法(ParticleSwarmOptimization，PSO)是一种群聚智能优化算法，源于对鸟类捕食行为的研究1。鸟类捕食时，找到食物最简单有效的策略就是搜寻距离食物最近的区域，基于该思想衍生的多目标粒子群算法广泛应用于工程实践。例如，Sannigrahi等2 将多目标粒子群算法应用于配电系统规划；邢小红等3 运用多目标优化算法解决水库洪水调度问题；张玉平等4 将多目标粒子群算法应用于斜拉桥索拉力优化分析。PSO具有结构简单、收敛速度快等特点5，但由于多目标问题本身的复杂性，运用该算法解决多目标问题时，很难确定多目标优化问题中的局部最优个体和全局最优个体，搜索精度不高，容易陷人局部最优解6 。为此，本文提出一种改进的多目标粒子群算法，将K-means聚类算法7 和高斯变异算法融合到多目标粒子群算法的迭代过程中，避免算法陷人局部最优解的同时还提高了算法的局部搜索能力和精度。1基础理论1.1多目标优化问题在科学研究和工程实践中遇到的问题大多是多目标优化问题，不仅涉及多个目标函数的优化，各优化目标之间也存在复杂的约束关系8 。在优化部分目标的同时，往往出现其他目标遭受损失的情况，很难得到同时使每个目标达到最优的结果。所以，多目标问题并不存在一个可以满足全部目标的全局最优解，只能对所有目标进行权衡，得到相对较优的解，这些解组成了多目标优化问题的解集。一个包含m个目标函数，n个决策变量，p个不等式约束和q个等式约束的多目标优化问题，表示如下：minimize F(x)=(fi(x),f2(x),.,fm(x)g;(x)0i=1,2,3,pS.t.(h,(x)=0j=1,2,3,q收稿日期：2 0 2 2-0 6-2 7基金项目：浙江省高校基本科研业务费专项资金项目（GK219909299001-024）作者简介：程兵（1997 一），男，研究方向：天线设计智能优化算法。E-mail：h y c j 0 7 10 h d u.e d u.c n。通信作者：项铁铭，副教授，研究方向：天线设计与智能优化算法。E-mail:。(1)2式中,x=(,，,z )ER,是一个n维决策变量,F(x)=(fi(x),f2(x),fm(x)为m维目标向量，g;(x)为第i个不等式约束,h,（x)为第i个等式约束，p和q值分别为2 种约束条件的个数。多目标优化问题最终得到一个解的集合，即Pareto前沿 。多目标优化算法的目的就是寻找这一解集。1.2标准粒子群算法PSO中的每个粒子都代表问题的一个潜在解，粒子的适应度值用来衡量位置的好坏，粒子的速度决定了该粒子的运动方向和距离，并且速度随着个体最优值（pbest）和全局粒子的历史最优值（gbest)进行动态调整，从而实现优化。粒子群算法的迭代公式如下：v;(t+1)=ww;(t)+ciri(xpbest,-x;(t)+c2r2(gbet,-x;(t)式中，v(t)和x;(t)分别表示第i个粒子在t时刻的速度和位置，为惯性权重，用于平衡局部搜索和全局搜索，C1和c2分别表示个体最优和历史最优的学习因子，决定粒子在进化过程中向个体最优和群体最优学习的权重大小，ri和r为加速因子，是介于0，1 之间的随机数。2基于聚类和高斯变异的多目标粒子群算法针对PSO算法的局部搜索能力不足、收敛精度不高、算法易陷人局部最优解等缺陷，本文分别从惯性参数动态变化方式、个体最优和全局最优的选取、解的多样性维护、种群的变异等方面进行改进，提出一种融合多种改进策略的多目标粒子群算法。2.1权重非线性变化策略在PSO中，惯性权重w通常随着当前迭代次数T动态变化。一些改进的粒子算法采用惯性权重线性下降策略来加强算法的寻优能力，权重变化公式如下：Tmax式中Wmax和Wmin分别为惯性参数的最大值和最小值，Tmax为最大迭代次数。但是，线性下降策略的搜索精度不高，在优化过程中，最好是一开始就着重于全局搜索，后期逐渐收敛后再着重于局部搜索，这样不仅可以提升算法的收敛速度，而且还可以提高算法的搜索精度。为此，本文提出一种惯性权重余弦递减策略，权重变化公式如下：元T(Wmax一Wmin)cos(Tmax2由式（4)和式（5)得到惯性权重随迭代次数T的变化趋势如图1所示。杭州电子科技大学学报（自然科学版）x;(t+1)=x,(t)+v;(t+1)Wmx-WminXTw=Wmax一余弦.线性2023年(2)(3)(4)Wmin(5)Tmax/2图12 种权重变化策略下，惯性权重随选代次数T的变化曲线Tmax第3期从图1可以看出，和线性下降策略相比，余弦递减策略下的惯性权重在算法搜索过程的前期和后期的下降速率更为缓慢，说明该策略下，算法在前期具有较强的全局搜索能力，在后期具有较高的局部搜索精度。2.2个体最优值的选取在个体最优值选取过程中，以往的做法是将个体的当前位置与其历史最优位置进行比较，选出一个非支配解作为个体最优值。但是，在算法后期，要优化的目标数较多时，个体的当前位置与其历史最优位置往往不存在支配关系，无法直接比较，如果随机选择其中一个解作为个体最优值，反而会降低算法的性能。为此，本文在Pareto支配原则的基础上，提出更为精细的比较方法。依据Pareto支配原则进行比较，如果两者存在相互支配关系，则将其中的非支配解直接作为个体最优值，如果互相不支配，则进一步比较两者所在每一个目标函数上适应度值的大小，分别统计两者适应度值较小的次数，选择较小次数多的解作为个体最优值，避免在2 个解互不支配情况下盲目选取个体最优值。2.3全局最优值的选取多目标粒子群算法需要解决的一个重要问题是全局最优值的选取。本文采用拥挤距离排序的方法来确定每个粒子的全局最优解。首先，按照拥挤距离的定义，计算外部存档中每个粒子的拥挤距离，并从大到小排序；然后，将前2 0%的粒子单独取出，按轮盘赌法为每个粒子选取全局最优值，处在稀疏区域的粒子拥挤距离大，被选中成为粒子全局最优解的概率就大，不仅有利于算法的快速收敛，还可以保证解集分布的均匀性。2.4基于聚类算法的高斯变异策略标准多目标粒子群算法很容易陷人局部最优解，导致算法早熟，收敛精度差。为了提高算法的性能，本文将K-means聚类算法和高斯变异算法融合到标准粒子群算法中。从非支配解集中随机选取k个解作为初始聚类中心(Ci，C 2，C），再计算每个粒子到每个聚类中心的距离，(6)t=1式中，x；表示第i个粒子，表示第i个粒子的第t维的值，C,表示第i个聚类中心，C表示第个聚类中心的第t维的值。依次比较每个粒子到每个聚类中心的距离，将粒子划分到距离其最近的聚类中心所在的类中，得到k个类簇(Si，S2，,S）。每次分类完成之后，重新计算聚类中心，将本类中所有粒子在各个维度上的均值作为下次分类的聚类中心，以此循环计算，直至满足算法要求。聚类中心更新计算公式如下：(7)式中，Ci表示第1个类中心，S|表示第1个类簇中包含解的个数，x,表示第1个类簇中的第i个粒子。最终将解集分为k类，并且满足误差平方和达到最小。误差平方和（Sumof SquaresforError,SSE）的定义如下：(8)式中，dist(xi,C）表示类S,中的第i个解到该类中心C,的距离。所有非支配解均经过K-means聚类后，再计算得到每个类中所有粒子的每一维度上的方差，以该方差为依据，为该类中的每个粒子进行变异，具体变异公式如下：(9)P Q(T)72Q(T)=1 e式中，表示第i个粒子在第维度上的值，c表示i变异之后的值，Gaussian(O，）表示一个服从均值程兵，等：基于聚类和高斯变异的多目标粒子群算法dist(x;,C,)=C,=Ese=22dist(x.,C.)*i+Gaussian(O,o）P Q(T)=3(-C.)2(10)4为0,方差为的高斯分布的随机数，方差为该粒子所在的类中所有粒子的方差，对粒子的每一维进行概率为Q(T）的变异操作，T为算法的当前迭代次数，Tmax为最大迭代次数，P为一个服从O，1区间均匀分布的随机数。与传统变异策略相比较,结合聚类算法的高斯变异后，每个类中的个体都有极高的相似性，避免了种群变异的盲目性和随机性，使得变异的结果更为理想并且范围可控，相当于在原先解的基础上对每一维度进行微量扰动，有利于算法在原先解的邻域空间内找到更为优质的解，有效提高了算法的局部搜索能力和精度。3仿真实验与分析在Windows 10 Intel(R）Co r e(T M)i 7-7 50 0 U M A T LA B2 0 2 0 a 的环境下，选用ZDT2-ZDT4101和DTLZ1-DTLZ211测试函数，分别对标准多目标粒子群算法MOPSO、基于精英策略的快速非支配排序遗传算法（NSGA-II）12 、基于2 个局部最佳的多目标粒子群算法（2 LBMOPSO)131、使用拥挤距离机制和突变操作保持非支配解多样性的多目标粒子群算法（MOPSO-CD)141、基于精英学习策略的粒子群算法（MOPSO-ELS)15和本文改进的多目标粒子群算法进行仿真实验。6 种算法均采用相同设置，种群和外部存档规模N=100，送代次数T=1000，惯性权重Wmax和min分别取2.0 和0.4。分别统计每种算法在30 次独立运行下求得的反转世代距离（Inverted GenerationalDistance，IG D)16 、超体积（H y p e r v o l u me，H V)17 、多样性（Diversity,DIV)18、空间性（Spacing，SP)19 的均值（Mean）和标准差(Std),本文选取（1,1)和(1,1,1)两点分别作为二目标和三目标测试函数HV指标计算的参考点，其中“表示数据超出有效范围，实验结果如表1所示。性能算法类别指标NSGA-IIMOPSO2LBMOPSOIGDMOPSO-CDMOPSO-ELS本文算法NSGA-IIMOPSO2LBMOPSOHVMOPSO-CDMOPSO-ELS本文算法NSGA-IIMOPSO2LBMOPSODIVMOPSO-CDMOPSO-ELS本文算法NSGA-IIMOPSO2LBMOPSOSPMOPSO-CDMOPSO-ELS本文算法杭州电子科技大学学报（自然科学版）表1不同算法的性能指标ZDT2ZDT3MeanStd5.60e-34.89e-44.90e-12.40e-15.10e-32.27e-44.19e-11.61e-27.80e-39.21e-43.90e-32.39e-53.27e-11.36e-21.14e-11.22e-13.28e-19.60e-34.19e-26.90e-33.28e-11.42e-23.34e-11,39e-24.63e-13.26e-29.30e-11.41e-14.14e-12.47e-29.25e-11.09e-22.97e-15.55e-26.98e-28.60e-36.70e-39.81e-42.10e-34.30e-37.30e-36.27e-41.55e-24.78e-46.02e-38.97e-44.20e-34.68e-52023年ZDT4DTLZ1MeanStd5.90e-3 4.85e-41.45e-17.44e-26.00e-33.70e-43.20e-16.25e-25.40 e-33.41e-44.30e-3 2.19e-57.79e-11.53e-27.60e-1 5.95e-28.00e-11.04e-25.46e-19.79e-27.99e-11.08e-28.04e-19.40e-36.99e-12.35e-28.23e-14.08e-26.93e-12.06e-28.09e-17.03e-26.78e-12.26e-21.73e-11.11e-28.40e-38.28e-46.10e-3 1.50e-37.90e-3 7.49e-47.30e-36.30e-38.20e-31.90e-34.02e-31.79e-4DTLZ2MeanStd1.26e-0 8.16e-11.34e-01.66e-11.71e-07.27e-11.87e-01.65e-14.60e-33.82e-43.60e-35.96e-57.38e-2 1.67e-15.02e-41.00e-36.57e-11.70e-26.65e-11.01e-27.74e-19.28e-28.96e-13.08e-27.89e-19.58e-28.66e-11.49e-23.22e-13.06e-27.39e-21.39e-29.70e-3 1.70e-31.54e-23.10e-31.44e-21.70e-25.90e-34.40e-36.20e-3 6.07e-44.10e-34.44e-5Mean14.22e-04.57e-04.54e-01.93e-06.76e-01.92e-04.16e-01.58e-03.07e-21.80e-32.53e-22.30e-3一9.66e-16.70e-39.69e-13.50e-37.82e-16.23e-28.14e-11.25e-17.88e-13.66e-28.96e-11.06e-18.34e-12.36e-27.72e-12.12 e-21.26e-04.82e-12.56e-0 1.12e-02.35e-04.77e-110.57e-06.06e-02.17e-22.40e-31.97e-22.30e-3StdMean7.72e-23.00e-33.11e-13.32e-29.23e-24.90e-38.68e-16.10e-36.56e-21.50e-36.50e-23.10e-33.69e-11.60e-22.23e-12.21e-23.07e-11.82e-23.02e-11.63e-23.57e-11.71e-23.80e-11.12e-27.06e-13.91e-26.50e-13.35e-26.22e-1 2.34e-27.07e-12.90e-26.29e-13.67e-26.14e-11.84e-25.75e-25.10e-34.44e-25.30e-36.12 e-28.30e-36.62e-21.62e-25.74e-25.10e-35.03e-21.90e-3Std第3期从表1可以看出，本文算法的IGD,HV和DIV的均值比其他5种算法小，同时SP指标的均值也取得3个较好的结果，说明本文算法得到的近似Pareto前沿更收敛于真实Pareto前沿，分布也更均匀。为了更加直观地观察非支配解集在目标空间的分布情况，分别画出6 种算法得到的非支配解在目标空间的分布和真实Pareto前沿的分布。在二目标测试函数中，星形点和圆形点分别为算法得到的近似Pareto前沿和真实Pareto前沿，在三目标测试函数中算法得到的近似Pareto前沿和真实Pareto前沿分别用圆形点和透明的阴影平面或曲面表示。具体分布情况如图2 一图6 所示。1.2真实Pareto前沿1.0近似Pareto前沿0.80.60.40.20.00.0 0.20.40.60.81.0(a)NSGA-II1.00.80.60.40.2真实Pareto前沿近似Pareto前沿0.00.00.20.4 0.60.8 1.0(d)MOPSO-CD图2ZDT2真实Pareto前沿和近似Pareto前沿的分布1.01.0真实Pareto前沿0.5近似Pareto前沿0.0-0.5-1.00.00.20.4 0.6 0.8 1.0(a)NSGA-II1.0。真实Pareto前沿0.5近似Pareto前沿0.0-0.5-1.00.00.20.40.60.81.0(d)MOPSO-CD图3ZDT3真实Pareto前沿和近似Pareto前沿的分布程兵，等：基于聚类和高斯变异的多目标粒子群算法1.21.00.8S0.60.40.20.00.00.20.40.60.81.0(b)MOPSO1.00.80.60.40.2真实Pareto前沿近似Pareto前沿0.00.00.20.40.60.81.0(e)MOPSO-ELS真实Pareto前沿0.5近似Pareto前沿0.0-0.5-1.00.00.2 0.40.60.8 1.0(b)MOPSO1.0真实Pareto前沿0.5近似Pareto前沿0.0-0.5-1.00.00.2 0.40.60.81.0(e)MOPSO-ELS51.0真实Pareto前沿近似Pareto前沿0.80.60.40.20.00.0 0.20.40.60.81.0(c)2LBMOPSO1.00.80.60.40.2真实Pareto前沿近似Pareto前沿0.00.00.2 0.40.60.81.0(f)KGMOPSO1.0真实Pareto前沿0.5近似Pareto前沿0.0-0.5-1.00.00.2 0.4 0.60.81.0(c)2LBMOPSO1.0真实Pareto前沿0.5近似Pareto前沿0.0-0.5-1.00.00.20.40.60.81.0(f)KGMOPSO真实Pareto前沿近似Pareto前沿6杭州电子科技大学学报（自然科学版）2023年2.01.5S1.00.50.00.00.20.40.6 0.81.0(a)NSGA-II3.53.02.52.01.51.00.50.00.00.20.40.6 0.8 1.0(d)MOPSO-CD图4ZDT4真实Pareto前沿和近似Pareto前沿的分布3.5真实Pareto前沿3.0近似Pareto前沿2.52.01.51.00.50.00.00.20.40.60.81.0(b)MOPSO1.0真实Pareto前沿0.8近似Pareto前沿0.60.40.20.00.00.2 0.40.60.81.0(e)MOPSO-ELS3.5真实Pareto前沿3.0近似Pareto前沿2.52.01.51.00.50.00.00.20.40.6 0.81.0(c)2LBMOPSO1.0真实Pareto前沿0.8近似Pareto前沿0.60.40.20.00.00.20.40.60.81.0(f)KGMOPSO真实Pareto前沿近似Pareto前沿真实Pareto前沿近似Pareto前沿15105102020(a)NSGA-II100500204060(d)MOPSO-CD图5DTLZ1真实Pareto前沿和近似Pareto前沿的分布从图2 一图4可以看出，在所有的ZDT系列测试函数中，本文算法得到的解集更收敛于真实的Pareto前沿，两者几乎重合。从图5一图6 可以看出，在DTLZ1和DTLZ2测试函数上，其他5种算法得到的解要么完全不收敛，要么在某个区域内有大量的解聚集，解的分布较差，而本文算法得到的解的分布更均匀。从解的分布图还可以看出，NSGA-II，M O PSO,2 LBM O PSO,M O PSO-CD 这4种算法在ZDT4与DTLZ1测试函数上并不收敛，将迭代次数增加到150 0 次时，得到的解仍然不收敛，和送代1000次得到的解的收敛程度相比，没有明显变化，说明这4种算法跳出局部最优解的能力较差。4丝结束语针对多目标优化遇到的问题，本文对标准多目标粒子群算法进行改进，提出了惯性参数余弦递减策略和基于K-means聚类算法的高斯变异策略，提升了算法的搜索精度和避免陷入局部最优解，并对201510501002060404030201000-1020204040(b)MOPSO1.0,0.80.60.40.20.010.00.51.01.0(e)MOPSO-ELS0204040(c)2LBMOPSO1.00.80.60.40.20.00.50.00200.00.51.01.0(f)KGMOPSO0.50.0第3期程兵，等：基于聚类和高斯变异的多目标粒子群算法702.01.51.00.50.002.01.54S1.00.50.0J22(d)MOPSO-CD图6DTLZ2真实Pareto前沿和近似Pareto前沿的分布Pareto支配关系进行改进，在保证良好的全局搜索能力的同时，增强了算法的局部搜索能力和搜索精度。虽然，改进算法在所有测试函数上都得到分布更收敛、更均匀的解集，但仿真实验只是针对一些特定的测试函数进行优化，目标数较少，说服力还不够，后续将进一步改进算法，以解决更多目标的优化问题。参考文献1J KENNEDY J,EBERHART R.Particle swarm optimizationCJ/Proceedings of International Conference on NeuralNetworks.IEEE,Perth,WA,Australia,1995:1942-1948.2J SANNIGRAHI S,GHATAK S R,ACHARJEE P.Point estimate method based distribution system planning usingMOPSO techniqueCJ/2020 IEEE International Conference on Power Electronics,Smart Grid and RenewableEnergy(PESGRE2020),2020:1-6.3邢小红，罗军刚，解建仓.基于改进多目标粒子群算法的水库防洪调度J.计算机工程与应用，2 0 12，48（30）：33-39.4张玉平，刘雪松，李传习.基于MOPSO算法的斜拉桥索力优化分析J.土木与环境工程学报（中英文），2 0 2 0，42（2)：107-114.5J XIE X F,ZHANG W J,YANG Z L.Overview of particle swarm optimizationLJJ.Control and Decision,2003,18(2):129-134.6 冯茜，李擎，全威，等.多目标粒子群优化算法研究综述J.工程科学学报，2 0 2 1，43（6）：7 45-7 53.7J CHOUHAN R,PUROHIT A.An approach for document clustering using PSO and K-means algorithmCJ/20182nd International Conference on Inventive Systems and Control(ICISC),Coimbatore,India,2018:1380-1384.8J XU G,LUO K,JING G X,et al.On convergence analysis of multi-objective particle swarm optimization algorithmEJ.European Journal of Operational Research,Elsevier,vol.2020,286(1):32-38.9 HUSSAIN MM,FUJIMOTO N.Parallel multi-objective particle swarm optimization for large swarm and highdimensional problemsCJ/2018 IEEE Congress on Evolutionary Computation(CEC),Rio de Janeiro,Brazil,2018:1-10.10 刘子怡，王宇嘉，孙福禄，等.结合特征扰动与分配策略的集成辅助多目标优化算法J.计算机工程，2 0 2 2，48（6）：115-123.11巩敦卫，刘益萍，孙晓燕，等.基于目标分解的高维多目标并行进化优化方法J.自动化学报，2 0 15，41（8）：1438-1451.12J DEBK,PRATAP A,AGARWAL S,et al.A fast and elitist multiobjective genetic algorithm:NSGA-II JJ.IEEE Transactions on Evolutionary Computation,2002,6(2):182-197.2.01.51.00.50.0101122(a)NSGA-II12.01.51.00.50.001122(b)MOPSO2.01.5S1.00.500.011(c)2LBMOPSO2.01.5S1.00.500.0%1122(e)MOPSO-ELS22122(f)KGMOPSO1813J ZHAO S Z,SUGANTHAN P N.Two-lbests based multi-objective particle swarm optimizerJ.EngineeringOptimization，,2 0 11,43(1):1-17.14J RAQUEL C R,JR PC N.An effective use of crowding distance in multiobjective particle swarm optimizationCJ/Genetic and Evolutionary Computation Conference.Proceedings,2005:25-29.15J DING S X,CHEN C,XIN B,et al.A bi-objective load balancing model in a distributed simulation system usingNSGA-II and MOPSO approachesLJJ.Applied Soft Computing,2018,63:249-267.16J ISHIBUCHI H,IMADA R,SETOGUCHI Y,et al.Reference Point Specification in Inverted GenerationalDistance for Triangular Linear Pareto FrontJJ.IEEE Transactions on Evolutionary Computation,2018,22(6):961-975.17J PAN A Q,WANG L,GUO W A,et al.A diversity enhanced multiobjective particle swarm optimizationJJ.Information Sciences:An International Journal,2018,436-437:441-465.18 王丽萍，任宇，邱启仓，等.多目标进化算法性能评价指标研究综述J.计算机学报，2 0 2 1，44（8）：1590-16 19.19J WANG Y J,YANG Y P.Particle swarm optimization with preference order ranking for multi-objective optimizationJJ.Information Sciences,2009,179(12):1944-1959.杭州电子科技大学学报（自然科学版）2023年Multi-objective particle swarm optimization basedon clustering and gaussian mutationCHENG Bing,XIANG Tieming,ZHENG Binhao(School of Electronic Information,Hangzhou Dianzi University,Hangzhou Zhejiang 310018,China)Abstract:In order to solve the multi-objective optimization problems encountered in engineering,animproved multi-objective particle swarm optimization algorithm is proposed.Firstly,the dynamicnonlinear cosine variation inertia parameter is proposed,which improves the optimization ability of thealgorithm.Then,an improved Pareto dominance relation is proposed to update the individual optimalsolution of the particle,and the external archive is maintained according to the crowding distance,soas to improve the uniformity of solution set distribution.Finally,the K-means clustering algorithmand the Gaussian mutation algorithm are applied to the iterative process of the multi-objective particleswarm optimization algorithm to avoid the algorithm falling into the local optimal solution.Experimental results on five testing functions show that the improved multi-objective particle swarmoptimization algorithm can keep the Pareto solution set with excellent convergence,and also maintainthe uniformity and diversity of the solutions.Key words:multi-objective optimization;particle swarm algorithm;K-means clustering;Gaussian mutation