【机器学习】基于目标空间分解和连续变异的多目标粒子群算法

团购合买资源类别：文库，文档格式：PDF，文档页数：7，文件大小：1.07MB

第14卷第3期智能系统学报 Vol.14 No.3 2019年5月 CAAI Transactions on Intelligent Systems May 2019 D0:10.11992/tis.201711015 网络出版地址：http:/kns.cnki.net/cms/detail/23.1538.TP.20180426.1712.011.html 基于目标空间分解和连续变异的多目标粒子群算法钱小宇2，葛洪伟2，蔡明3 (1.江南大学轻工过程先进控制教育部重点实验室，江苏无锡214122；2.江南大学物联网工程学院，江苏无锡214122：3.江南大学信息化建设与管理中心，江苏无锡214122) 摘要：针对当前多目标粒子群优化算法收敛性和多样性不佳等问题，提出了一种基于目标空间分解和连续变异的多目标粒子群优化算法。利用目标空间分解方法将粒子群分配到预先设定好的子区域中，在该过程中，通过一种新适应值公式来对每个子区域中的粒子进行择优筛选，该适应值公式融入了支配强度因素：在全局搜索过程中，使用差分变异、高斯变异和柯西变异对全局引导粒子的位置进行连续变异操作。将该算法与当前主流的一些多目标优化算法进行对比实验，结果表明，本文提出的算法在提高粒子收敛性的同时，多样性也得到了提升。关键词：多目标优化：粒子群优化算法：分解：子区域：变异；差分；高斯变异：柯西变异中图分类号：TP391.4文献标志码：A 文章编号：1673-4785(2019)03-0464-07 中文引用格式：钱小宇，葛洪伟，蔡明.基于目标空间分解和连续变异的多目标粒子群算法.智能系统学报，2019,14(3)： 464-470. 英文引用格式：QIAN Xiaoyu,,GE Hongwei,,CAI Ming..Decomposition and continuous mutation-based multi--objective particle swarm optimizationJ CAAI transactions on intelligent systems,2019,14(3):464-470. Decomposition and continuous mutation-based multi-objective particle swarm optimization QIAN Xiaoyu2,GE Hongwei,CAI Ming' (1.Ministry of Education Key Laboratory of Advanced Process Control for Light Industry,Jiangnan University,Wuxi 214122, China;2.School of Internet of Things Engineering.Jiangnan University,Wuxi 214122,China;3.Information Construction and Man- agement Center,Jiangnan University,Wuxi 214122,China) Abstract:In light of the poor convergence problems and the diversity of current multi-objective optimization al- gorithms,in this paper,we propose an objective-space decomposition and continuous mutation-based multi-objective particle-swarm-optimization algorithm.Its innovations are as follows:we use a space decomposition method to distrib- ute the particle swarm into a predefined sub-region.During this process,we apply a new adaptive value formula to se- lect and filter the particles in each sub-region and incorporate a fitness formula into the dominance factor.In the global search process,we apply differential,Gaussian,and Cauchy mutations to continuously mutate the position of the global guide particle.We compare the performance of this algorithm with those of current multi-objective optimization al- gorithms,and the results show that the proposed algorithm improves the convergence and diversity of the particles. Keywords:multi-objective optimization;particle swarm optimization algorithm;decomposition;sub-region,mutation; differential;Gaussian mutation;Cauchy mutation 粒子群算法自1995年被Kennedy和Eberhart 收稿日期：2017-11-13.网络出版日期：2018-04-27. 基金项目：江苏省普通高校研究生科研创新计划项目提出后山，由于其简单高效，收敛速度快，逐渐在 (KYLX16_0781,KYLX16_0782):江苏高校优势学科优化算法中脱颖而出。随之粒子群算法被Col. 建设工程资助项目(PAPD). 通信作者：葛洪伟.E-mail:ghw8601@163.com. loran应用到多目标优化问题上)，得到了各界的

DOI: 10.11992/tis.201711015 网络出版地址: http://kns.cnki.net/kcms/detail/23.1538.TP.20180426.1712.011.html 基于目标空间分解和连续变异的多目标粒子群算法钱小宇1,2，葛洪伟1,2，蔡明3 （1. 江南大学轻工过程先进控制教育部重点实验室，江苏无锡 214122; 2. 江南大学物联网工程学院，江苏无锡 214122; 3. 江南大学信息化建设与管理中心，江苏无锡 214122）摘要：针对当前多目标粒子群优化算法收敛性和多样性不佳等问题，提出了一种基于目标空间分解和连续变异的多目标粒子群优化算法。利用目标空间分解方法将粒子群分配到预先设定好的子区域中，在该过程中，通过一种新适应值公式来对每个子区域中的粒子进行择优筛选，该适应值公式融入了支配强度因素；在全局搜索过程中，使用差分变异、高斯变异和柯西变异对全局引导粒子的位置进行连续变异操作。将该算法与当前主流的一些多目标优化算法进行对比实验，结果表明，本文提出的算法在提高粒子收敛性的同时，多样性也得到了提升。关键词：多目标优化；粒子群优化算法；分解；子区域；变异；差分；高斯变异；柯西变异中图分类号：TP391.4 文献标志码：A 文章编号：1673−4785(2019)03−0464−07 中文引用格式：钱小宇, 葛洪伟, 蔡明. 基于目标空间分解和连续变异的多目标粒子群算法[J]. 智能系统学报, 2019, 14(3): 464–470. 英文引用格式：QIAN Xiaoyu, GE Hongwei, CAI Ming. Decomposition and continuous mutation-based multi-objective particle swarm optimization[J]. CAAI transactions on intelligent systems, 2019, 14(3): 464–470. Decomposition and continuous mutation-based multi-objective particle swarm optimization QIAN Xiaoyu1,2 ，GE Hongwei1,2 ，CAI Ming3 (1. Ministry of Education Key Laboratory of Advanced Process Control for Light Industry, Jiangnan University, Wuxi 214122, China; 2. School of Internet of Things Engineering, Jiangnan University, Wuxi 214122, China; 3. Information Construction and Management Center, Jiangnan University, Wuxi 214122, China) Abstract: In light of the poor convergence problems and the diversity of current multi-objective optimization algorithms, in this paper, we propose an objective-space decomposition and continuous mutation-based multi-objective particle-swarm-optimization algorithm. Its innovations are as follows : we use a space decomposition method to distribute the particle swarm into a predefined sub-region. During this process, we apply a new adaptive value formula to select and filter the particles in each sub-region and incorporate a fitness formula into the dominance factor. In the global search process, we apply differential, Gaussian, and Cauchy mutations to continuously mutate the position of the global guide particle. We compare the performance of this algorithm with those of current multi-objective optimization algorithms, and the results show that the proposed algorithm improves the convergence and diversity of the particles. Keywords: multi-objective optimization; particle swarm optimization algorithm; decomposition; sub-region; mutation; differential; Gaussian mutation; Cauchy mutation 粒子群算法自 1995 年被 Kennedy 和 Eberhart 提出后[1] ，由于其简单高效，收敛速度快，逐渐在优化算法中脱颖而出。随之粒子群算法被 Coelloran 应用到多目标优化问题上[2-3] ，得到了各界的收稿日期：2017−11−13. 网络出版日期：2018−04−27. 基金项目：江苏省普通高校研究生科研创新计划项目 (KYLX16_0781，KYLX16_0782)；江苏高校优势学科建设工程资助项目 (PAPD). 通信作者：葛洪伟. E-mail：ghw8601@163.com. 第 14 卷第 3 期智能系统学报 Vol.14 No.3 2019 年 5 月 CAAI Transactions on Intelligent Systems May 2019

第3期钱小宇，等：基于目标空间分解和连续变异的多目标粒子群算法 ·465· 广泛认可。后来更多学者对多目标粒子群算法 PS={x∈2-3ze2:z>x刘 (3) (MOPSO)进行了更深入的研究：Raquel等使用定义4 Pareto前沿(PF): 了拥挤距离作为适应值对粒子进行排序：Lⅰ等 PF={F(x)x∈PSI (4) 通过整合粒子的GMR(global margin ranking)和粒 1.2粒子群优化子密度信息的方法来对粒子进行排序，能高效快粒子群算法中的粒子由速度信息和位置信息速地选择出Pest和gbet粒子；除了对排序选择的组成，更新公式为方法进行优化外，有的利用聚合函数来对多个目 Vi=WKi+CiR(P-X)+C2R2(G-X) (5) 标函数进行处理：有的使用了目标空间分解的方 X=V+X (6) 法来保障粒子最优解的多样性m:以及将MOPSO 式中：k指粒子群中第k个粒子；1为当前迭代次和其他优化算法进行交叉使用，如教与学方法圆、数；W为权衡局部搜索和全局搜索的参数，差分方法等，通过一定的比例调用MOPSO。 W∈0.1,0.9：C,和C2为学习因子，其大小都为2；上述的这些方法不断地对MOPSO的多样性 R和R都是[O,1]之间的随机数；P指当前粒子最和全局收敛进行改进和优化，虽然取得了较好的好位置Ppesti;G指引导粒子Sbest的位置；V?指在研究成果，但是这些方法的改进策略只对MOPSO 第1次迭代中第k个粒子的速度；X指在第1次迭某一性能效果进行改进，其他的性能指标并没有代中第k个粒子的位置。同时得到很好的改进。例如：文献[]中，多样性 2 MOPSO/DC算法方面得到很大的提升，但是其收敛性方面仍有很大不足。所以，本文借鉴Pareto支配强度uo和连 2.1目标空间分解续变异的方法对基于目标空间分解方法的多目把目标空间Y分成M个子区域Y,Y2,…, 标粒子群算法进行优化，在给每个子区域分配 YM。令je{1,2,…,M,对任一给定的第j个子区粒子时，删除没有归属的粒子，给没分到粒子的域，每个目标函数在所有目标函数中所占有的权区域初始化新的粒子，增加获得较优粒子的可能重a,(=1,2.…,m,且4=1)所组成的向量性。这样既从整体和局部两方面提升了粒子的收敛性，同时多样性也得到了一定的优化提升，这 (a1,a2,…,am)定义为该子区域的中心向量A。当种新的算法被称为基于目标空间分解和连续变异目标函数个数m=2时，则第j子区域的中心向的多目标粒子群优化算法(multi-.objective particle 量A,表示 [品1-当m=3时，进行 swarm optimization based on decomposition and con- 两层循环，令k为第1层（外层）循环变量，2为 tinuous mutation,MOPSO/DC). 第2层（内层）循环变量，k1从0取到h,从0取 1多目标优化问题到h-,每次循环令u=+1+乃+2-，其 k,=1 1.1基本概念中h和M满足：当C2≥M时h取最小值，则第 miny F(x)=(fi(x),f(x),...fin(x)) stg(x)≤0，i=01,2,…,q (1) “个子区镜的中心向量为伤会1-会-当 Γh-h h,(x)=0,j=1,2,…,p m>3时，进行m-1层循环，k1为第一层循环变量式中：x=(,x2,…,x)为n维决策变量；m为目标 (最外层)，依次由外向内，令k为第层循环变量，函数的个数；g(:)函数为目标函数的q个不等式 km1为第m-1层（最内层）循环变量，k1从0取到约束；h()为目标函数的p个等式约束。所有这 h,k2从0取到h-k,k从0取到(h-k1-k2-…k), 些满足条件的决策变量用集合2表示，Y={F(x)x∈2 最里层循环变量km1从0取到(h-k1-k2-…km-2), 为目标空间。接下来介绍4个关于多目标问题的每次循环令重要定义。 u=的定义1 Pareto支配。解d,ee2,d支配e,记 4=02=0 为d>e,满足下面的两个关系式： ∫i∈(,2,…,ml,fd≤f(e) 3ie{1,2,…,m以，f(dx成立。定义3 Pareto最优解集(PS): 向量为 …1-小当m≥3时，一共产 hh h台

广泛认可。后来更多学者对多目标粒子群算法 (MOPSO) 进行了更深入的研究：Raquel 等 [4]使用了拥挤距离作为适应值对粒子进行排序；Li 等 [5] 通过整合粒子的 GMR(global margin ranking) 和粒子密度信息的方法来对粒子进行排序，能高效快速地选择出 pbest 和 gbest 粒子；除了对排序选择的方法进行优化外，有的利用聚合函数来对多个目标函数进行处理[6] ；有的使用了目标空间分解的方法来保障粒子最优解的多样性[7] ；以及将 MOPSO 和其他优化算法进行交叉使用，如教与学方法[8] 、差分方法[9]等, 通过一定的比例调用 MOPSO。上述的这些方法不断地对 MOPSO 的多样性和全局收敛进行改进和优化，虽然取得了较好的研究成果，但是这些方法的改进策略只对 MOPSO 某一性能效果进行改进，其他的性能指标并没有同时得到很好的改进。例如：文献[7]中，多样性方面得到很大的提升，但是其收敛性方面仍有很大不足。所以，本文借鉴 Pareto 支配强度[10]和连续变异的方法[11]对基于目标空间分解方法的多目标粒子群算法[7]进行优化，在给每个子区域分配粒子时，删除没有归属的粒子，给没分到粒子的区域初始化新的粒子，增加获得较优粒子的可能性。这样既从整体和局部两方面提升了粒子的收敛性，同时多样性也得到了一定的优化提升，这种新的算法被称为基于目标空间分解和连续变异的多目标粒子群优化算法 (multi-objective particle swarm optimization based on decomposition and continuous mutation ，MOPSO/DC)。 1 多目标优化问题 1.1 基本概念    miny = F(x) = (f1(x), f2(x),··· , fm(x)) s.t.gi(x) ⩽ 0, i = 0,1,2,··· ,q hj(x) = 0, j = 1,2,··· , p (1) x = (x1, x2,··· , xn) n m g(x) q h(x) p Ω Y = {F(x)|x ∈ Ω} 式中：为维决策变量；为目标函数的个数；函数为目标函数的个不等式约束；为目标函数的个等式约束。所有这些满足条件的决策变量用集合表示，为目标空间。接下来介绍 4 个关于多目标问题的重要定义。 d, e ∈ Ω d e d ≻ e 定义 1 Pareto 支配。解，支配，记为，满足下面的两个关系式： { ∀i ∈ {1,2,··· ,m}, fi(d) ⩽ fi(e) ∃i ∈ {1,2,··· ,m}, fi(d) 3 m−1 k1 ki m−1 k1 h−k1 ki (h−k1 −k2 − ··· ki) (h−k1 −k2 − ··· km−2) 把目标空间 Y 分成 M 个子区域 Y1，Y2，···， YM。令，对任一给定的第 j 个子区域，每个目标函数在所有目标函数中所占有的权重且所组成的向量定义为该子区域的中心向量。当目标函数个数时，则第子区域的中心向量表示为；当时，进行两层循环，令为第 1 层 (外层) 循环变量，为第 2 层 (内层) 循环变量，从 0 取到 h，从 0 取到，每次循环令，其中 h 和 M 满足：当时 h 取最小值，则第 u 个子区域的中心向量为；当时，进行层循环，为第一层循环变量 (最外层)，依次由外向内，令为第 i 层循环变量， km-1 为第层 (最内层) 循环变量，从 0 取到 h，k2 从 0 取到，从 0 取到，最里层循环变量 km-1 从 0 取到，每次循环令 u = ∑h k1=0 ∑h−k1 k2=0 ··· h−k1∑−···−ki−1 ki=0 ··· h−k1∑−···−km−4 km−3=0   h−k1∑−···−km−3 km−2=1 (h+2− ∑m−2 l=1 kl)+km−1 +1   C m−1 h+m−1 ⩾ M   k1 h k2 h ··· 1− 1 h ∑m−1 l=1 kl   m ⩾ 3 其中参数 h、m 和子区数 M 满足关系：h 取满足时的最小值，则第 u 个子区域的中心向量为。当时，一共产第 3 期钱小宇，等：基于目标空间分解和连续变异的多目标粒子群算法 ·465·

·466· 智能系统学报第14卷生C1个中心向量，这些向量的下标为子中选择离所在子区域中心向量最近的Vol个粒 u=1,2,…Cl1。若C1>M,则从下标u=2开子，多余的劣质粒子删除。始，以M二己为步长依次酬除C-M个下 2)当子区域粒子数少于该子区域容量标对应的中心向量，然后将剩下的M个中心向量 Vol时，由于情况1)中已经对劣质的粒子进行删除，为了尽可能保证整体的优越性，所以重新初依次作为A,=1,2,…,M。通过每个子区域的中始化该子区域所缺数目的粒子作为该区域的粒心向量找出该子区域的T个相邻的子区域，参考指标为两个中心向量的余弦值。子，增加获得较优粒子的可能性，增加粒子多样性。然后计算新粒子的目标函数值。 2.2粒子的分类与更新 2.3连续变异操作在对粒子进行分配时，通过参考点确定每个粒子的方向向量。令参考点为R(1,2,…,rm),其当只采用一种方法进行变异时，不能兼顾全局粒子和局部粒子的特性。在MOPSO/DC中提中r=min(f(xx∈2，i=1,2…,m,m为目标函数出差分+柯西+高斯连续的变异策略，公式为个数。例如：如图1所示，无和方表示两个目标 Xm=X+0.5(X1-X2) 函数，m=2,则图中粒子C的方向向量为从点 XCauchy= c)2 R(,2)指向点C的向量XX=C-R。通过比较粒子 π(X2+c(t)) (8) 方向向量和所有子区域中心向量的余弦值，确定 1 该粒子属于最大余弦值所对应的中心，向量子区域。 w g()V2元式中：X为当前引导粒子get的位置；X,和X,是从EPOP中随机选出的两个不同粒子的位置。这样在变异时可保留全局粒子的一部分性质，起到定信息交流的作用，增加了多样性。1为当前迭代的次数，gmax为最大迭代次数，g(1)=2,gt+1)= 80-1 ;c=1,ct+1)=c0-;Xt、Xey和 XGus分别是对get的位置进行变异操作之后产生的新粒子。每次变异后让产生的新粒子和当前 0 的ge进行比较，选择支配权优先的作为ge,然图1粒子的方向向量后进行后续变异操作，直到3次变异结束，最终确 Fig.1 Direction vector of the particle 定引导粒子g0 高斯变异步长较短，能很好地吸取局部粒子在对粒子进行分配时会有以下两种特殊情况： 1)有的子区域粒子数大于子区域的容量性质，柯西变异具有相对大的步长，能进行较大范围的变异，具有全局范围变异的特性，这样能 Vol时，通过适应值进行取舍，适应值公式为 f=aT+CD (7) 很好地产生全新的粒子。式中：T是Pareto支配强度，其数值为当前粒子支下面对标准柯西分布。和标准高斯分布配的粒子数，在适应值计算中加入了Pareto支配 y。进行对比分析，根据y和y。的单调性和对强度T,增强每个子区域中的粒子趋向真实P℉的称性，对其第一象限进行分析：人= π(x2+1) 能力；参数α表示支配强度对适应值的影响程度， 2 ，M指目标空间子区域数；CD为拥挤距离， p-,求反函数=衣-1和 V2π Iye x=-2n(V2y),求两反函数之差(x-x),并用y 通过每个目标函数值对粒子进行排序，序列两端粒子在当前目标函数中的拥挤距离设为5，其他同时替代和，即T=-1+21n(V2:对T求粒子在当前目标函数中的拥挤距离为在序列中该关于y的导数，即T=示+子T在@安上单 12 粒子前后两粒子的目标函数值之差的绝对值，最后将求出的该粒子在每个目标函数中计算的拥挤减，在会上单增，所以70>T家>1会距离之和作为当前该粒子的拥挤距离CD。又因为T(灵>0，所以T0)>0:所以在，和同计算该子区域包含的粒子的适应值，从大到时趋向于0时，x足>，即x>x,所以柯西分布在小排序，选择序列中前30%的粒子，再从这些粒 x轴上覆盖的面积比高斯分布大。从图2中可直

C m−1 h+m−1 u = 1,2,···C m−1 h+m−1 C m−1 h+m−1 > M u = 2 M −2 C m−1 h+m−1 − M C m−1 h+m−1 − M Aj 生个中心向量，这些向量的下标为。若，则从下标开始，以为步长依次删除个下标对应的中心向量，然后将剩下的 M 个中心向量依次作为，j=1, 2, ···, M。通过每个子区域的中心向量找出该子区域的 T 个相邻的子区域, 参考指标为两个中心向量的余弦值。 2.2 粒子的分类与更新 R(r1,r2,··· ,rm) ri = min{fi(x)|x ∈ Ω},i = 1,2,··· ,m f1 f2 R(r1,r2) 在对粒子进行分配时，通过参考点确定每个粒子的方向向量[7]。令参考点为，其中，m 为目标函数个数。例如：如图 1 所示，和表示两个目标函数， m=2，则图中粒子 C 的方向向量为从点指向点 C 的向量 X，X=C−R。通过比较粒子方向向量和所有子区域中心向量的余弦值，确定该粒子属于最大余弦值所对应的中心，向量子区域。在对粒子进行分配时会有以下两种特殊情况： 1 ) 有的子区域粒子数大于子区域的容量 Vol 时，通过适应值进行取舍，适应值公式为 f = aT +CD (7) a = 2 M 式中：T 是 Pareto 支配强度，其数值为当前粒子支配的粒子数，在适应值计算中加入了 Pareto 支配强度 T，增强每个子区域中的粒子趋向真实 PF 的能力；参数 a 表示支配强度对适应值的影响程度，，M 指目标空间子区域数；CD 为拥挤距离，通过每个目标函数值对粒子进行排序，序列两端粒子在当前目标函数中的拥挤距离设为 5，其他粒子在当前目标函数中的拥挤距离为在序列中该粒子前后两粒子的目标函数值之差的绝对值，最后将求出的该粒子在每个目标函数中计算的拥挤距离之和作为当前该粒子的拥挤距离 CD。计算该子区域包含的粒子的适应值，从大到小排序，选择序列中前 30% 的粒子，再从这些粒子中选择离所在子区域中心向量最近的 Vol 个粒子，多余的劣质粒子删除。 2 ) 当子区域粒子数少于该子区域容量 Vol 时，由于情况 1) 中已经对劣质的粒子进行删除，为了尽可能保证整体的优越性，所以重新初始化该子区域所缺数目的粒子作为该区域的粒子，增加获得较优粒子的可能性，增加粒子多样性。然后计算新粒子的目标函数值。 2.3 连续变异操作当只采用一种方法进行变异时，不能兼顾全局粒子和局部粒子的特性。在 MOPSO/DC 中提出差分+柯西[12] +高斯[13]连续的变异策略，公式为    Xdiff = X +0.5(X1 − X2) XCauchy = c(t) 2 π(X2 +c(t) 2 ) XGauss = 1 g(t) √ 2π exp( −X 2 2 ) (8) g(1) = 2 g(t+1) = g(t)−1 gmax c(1) = 1 c(t+1) = c(t)−1 gmax Xdiff XCauchy XGauss 式中：X 为当前引导粒子 gbest 的位置；X1 和 X2 是从 EPOP 中随机选出的两个不同粒子的位置。这样在变异时可保留全局粒子的一部分性质，起到一定信息交流的作用，增加了多样性。t 为当前迭代的次数，gmax 为最大迭代次数，，；，；、和分别是对 gbest 的位置进行变异操作之后产生的新粒子。每次变异后让产生的新粒子和当前的 gbest 进行比较，选择支配权优先的作为 gbest，然后进行后续变异操作，直到 3 次变异结束，最终确定引导粒子 gbest。高斯变异步长较短，能很好地吸取局部粒子性质，柯西变异具有相对大的步长，能进行较大范围的变异，具有全局范围变异的特性，这样能很好地产生全新的粒子。 yc yg yc yg yc = 1 π(x 2 +1) yg = 1 √ 2π exp(− x 2 2 ) x 2 c = 1 πyc −1 x 2 g = −2ln( √ 2πyg) (x 2 c − x 2 g ) y yc yg T = 1 πy −1+2ln( √ 2πy) y T ′ = − 1 πy 2 + 2 y (0, 1 2π ) ( 1 2π ,+∞) T(0) > T( 1 5π ) > T( 1 2π ) T( 1 5π ) > 0 T(0) > 0 yc yg x 2 c > x 2 g xc > xg 下面对标准柯西分布和标准高斯分布进行对比分析，根据和的单调性和对称性，对其第一象限进行分析： , ，求反函数和，求两反函数之差，并用同时替代和，即；对 T 求关于的导数，即 , T 在上单减，在上单增，所以；又因为 , 所以；所以在和同时趋向于 0 时, , 即 , 所以柯西分布在 x 轴上覆盖的面积比高斯分布大。从图 2 中可直 f2 f O 1 C X R 图 1 粒子的方向向量 Fig. 1 Direction vector of the particle ·466· 智能系统学报第 14 卷

第3期钱小宇，等：基于目标空间分解和连续变异的多日标粒子群算法 ·467· 观地看出，柯西分布具有较宽的变异范围，粒子从该粒子的所在区域的邻域中随机选择一个粒具有较大范围的变异。子。让当前粒子和这个随机选出的粒子进行比 0.40 一高斯分布较，选出支配权优先的作为当前粒子的Pm。 0.35 一…柯西分布 T)通过上述选出的goet和pe,以及粒子速度 0.30 更新式(5)和位置更新式(6)产生下一代新的粒 0.25 =0.20 子群体，这些新粒子位置集合记为NPOP,下一代 0.15 新的速度集合重新覆盖集合V。 0.10 8)如果当前迭代次数1大于最大迭代次数 0.05 ga,则循环结束，输出EPOP作为最优解集，否则 4之寸0124 把NPOP和EPOP合并放入POP中，然后跳转至 3),继续循环。图2标准高斯和分布柯西分布对比 Fig.2 Comparison of standard Gaussian and Cauchy dis- 3实验分析 tributions 用这3种方法进行变异操作，既增强了为了测试所提出的MOPSO/DC算法的性能， ge的引导能力，同时ges吸取局部或全局粒子的将其与目前较流行的MOPSO/Dm、MOPSOTL例性质，促进了粒子之间信息交流共享，增加了多 MOPSODE和NNIAUA算法进行对比，实验中同样性。样选择了文献[]中的6个测试函数，依次为F1, 2.4 MOSPO/DC步骤 F2…F6。为了定量比较5种算法的性能，采用以 1)初始化2N个粒子的位置，这些粒子的位置下3种广泛使用的性能指标：HV1,测量了粒子集合记为POP,初始化N个速度，这些速度集合收敛于真实P℉的效果以及最优解集的多样性，记为V,设目标函数的个数为m,当前迭代次数为1，所获得值越大越好；GD,指算法获得的P℉到真初始化最大迭代次数gmax、每个子区域容量实P℉的距离，数值越小越接近真实PF,效果越 Vol∈[1,3]、邻域个数T以及子区域数目M。好；IGD,显示真实PF到算法所得到PF的距 2)进行目标空间分解操作。离，值越小越能说明算法得到的P℉上的点可以 3)计算粒子群POP目标函数值，选出每个目分散地均匀地收敛于真实P℉上。标函数的最小值作为参考点R用于计算每个粒子 MOPSO/DC参数设置：当目标函数个数m=2 的方向向量，方向向量的计算参考图1。时，M=500。当m=3时，M=1035。Vo1=1, 4)进行粒子的分类与更新操作，接着将当前 W=MVol,T=0.1M,粒子维度n=10,最大循环次所有子区域粒子的位置信息存入集合EPOP中，数gma=1000,一共进行了30次实验求各性能指最后更新参考点R,并重新计算每个粒子的方向标的均值和标准差。其他算法参数请参考文向量，清空POP备用。献[7。 5)gbet的选择：产生[0,1]之间的随机数r,当 MOPSO/DC与其他算法关于这6个测试函数 r>0.8时，随机从EPOP集合中选择一个粒子作为的3种性能指标对比结果见表1，表中给出了通当前粒子的ge;否则，在该粒子所在区域的邻域过MOPSO/DC和其他4个算法获得关于这6个内操作。首先计算该粒子邻域中每个子区域的中问题的IGD、GD和HV的平均值和标准差。从心向量和该子区域中粒子方向向量的余弦值，然表1中可以看出：1)MOPSO/DC获得的IGD平均后选出余弦值最大的子区域中的粒子作为当前粒值远小于其他4种算法；2)MOPSO/DC获得的子的g。过多地使用变异会让算法变得更加随 GD平均值都是最佳的，除F3函数外，不过关于机，降低了算法的效率，所以产生[0,1]之间的随机 F3的GD均值，本算法也优于MOPSO/D算法：数r2,当r20.8时，随机从EPOP中选择一个粒子；否则，算法，对MOPSO/D算法进行了很好的改进

观地看出，柯西分布具有较宽的变异范围，粒子具有较大范围的变异。用这 3 种方法进行变异操作，既增强了 gbest 的引导能力，同时 gbest 吸取局部或全局粒子的性质，促进了粒子之间信息交流共享，增加了多样性。 2.4 MOSPO/DC 步骤 Vol ∈ [1,3] 1) 初始化 2N 个粒子的位置，这些粒子的位置集合记为 POP，初始化 N 个速度，这些速度集合记为 V，设目标函数的个数为 m，当前迭代次数为 t，初始化最大迭代次数 g max、每个子区域容量、邻域个数 T 以及子区域数目 M。 2) 进行目标空间分解操作。 3) 计算粒子群 POP 目标函数值，选出每个目标函数的最小值作为参考点 R 用于计算每个粒子的方向向量，方向向量的计算参考图 1。 4) 进行粒子的分类与更新操作，接着将当前所有子区域粒子的位置信息存入集合 EPOP 中，最后更新参考点 R，并重新计算每个粒子的方向向量，清空 POP 备用。 5)gbest 的选择：产生[0，1]之间的随机数 r1 ,当 r1>0.8 时，随机从 EPOP 集合中选择一个粒子作为当前粒子的 gbest；否则，在该粒子所在区域的邻域内操作。首先计算该粒子邻域中每个子区域的中心向量和该子区域中粒子方向向量的余弦值，然后选出余弦值最大的子区域中的粒子作为当前粒子的 gbest。过多地使用变异会让算法变得更加随机，降低了算法的效率，所以产生[0,1]之间的随机数 r2 ,当 r20.8 时，随机从 EPOP 中选择一个粒子；否则，从该粒子的所在区域的邻域中随机选择一个粒子。让当前粒子和这个随机选出的粒子进行比较，选出支配权优先的作为当前粒子的 pbest。 7) 通过上述选出的 gbest 和 pbest，以及粒子速度更新式 (5) 和位置更新式 (6) 产生下一代新的粒子群体，这些新粒子位置集合记为 NPOP，下一代新的速度集合重新覆盖集合 V。 8) 如果当前迭代次数 t 大于最大迭代次数 gmax，则循环结束，输出 EPOP 作为最优解集，否则把 NPOP 和 EPOP 合并放入 POP 中，然后跳转至 3)，继续循环。 3 实验分析为了测试所提出的 MOPSO/DC 算法的性能，将其与目前较流行的 MOPSO/D[7] 、MOPSOTL[8] 、 MOPSODE[9]和 NNIA[14]算法进行对比，实验中同样选择了文献[7]中的 6 个测试函数，依次为 F1， F2···F6。为了定量比较 5 种算法的性能，采用以下 3 种广泛使用的性能指标：HV[15] ，测量了粒子收敛于真实 PF 的效果以及最优解集的多样性，所获得值越大越好；GD[16] ，指算法获得的 PF 到真实 PF 的距离，数值越小越接近真实 PF，效果越好；IGD[15] ，显示真实 PF 到算法所得到 PF 的距离，值越小越能说明算法得到的 PF 上的点可以分散地均匀地收敛于真实 PF 上。 m = 2 M = 500 m = 3 M = 1 035 N = MVol T = [0.1N] MOPSO/DC 参数设置：当目标函数个数时，。当时，。 Vol=1 ，，，粒子维度 n=10，最大循环次数 gmax=1 000，一共进行了 30 次实验求各性能指标的均值和标准差。其他算法参数请参考文献[7]。 MOPSO/DC 与其他算法关于这 6 个测试函数的 3 种性能指标对比结果见表 1，表中给出了通过 MOPSO/DC 和其他 4 个算法获得关于这 6 个问题的 IGD、GD 和 HV 的平均值和标准差。从表 1 中可以看出：1)MOPSO/DC 获得的 IGD 平均值远小于其他 4 种算法；2)MOPSO/DC 获得的 GD 平均值都是最佳的，除 F3 函数外，不过关于 F3 的 GD 均值，本算法也优于 MOPSO/D 算法[7] ； 3) 通过 MOPSO/DC 获得的 HV 值总体来说比其他算法获得的 HV 值好 (除 F1 函数)，说明 MOPSO/ DC 的收敛性以及解的多样性也相当好。整体来说，MOPSO/DC 的这 3 个性能指标优于其他 4 个算法，对 MOPSO/D 算法进行了很好的改进。 0.40 0.35 0.30 0.25 0.20 0.15 0.10 0.05 0 高斯分布柯西分布 −5 −4 −3 −2 −1 0 1 2 3 4 5 x y 图 2 标准高斯和分布柯西分布对比 Fig. 2 Comparison of standard Gaussian and Cauchy distributions 第 3 期钱小宇，等：基于目标空间分解和连续变异的多目标粒子群算法 ·467·

MOPSO/DC 算法的仿真图如图 3，结果显示该算法得到的 PF 和真实 PF 完全重合。通过这些对比实验得出结论：MOPSO/DC 对原算法[7]的收敛性和多样性进行了很好地优化，增强了粒子趋向真实 PF 的效果，并且具有很好的稳定性。表 1 各算法效果指标对比 Table 1 Comparison of the effect of each algorithm 函数算法 IGD GD HV 平均值标准差平均值标准差平均值标准差 F1 MOPSO/DC 0.000 0 0.000 0 0.000 1 0.000 0 0.332 4 0.000 0 MOPSO/D 0.004 5 0.000 1 0.001 8 0.000 1 0.659 8 0.000 2 MOPSOTL 0.143 3 0.137 5 0.001 4 0.002 0 0.274 1 0.116 5 MOPSODE 0.119 0 0.076 9 0.002 1 0.001 8 0.264 1 0.057 6 NNIA 0.383 0 0.014 9 0.061 5 0.134 7 0.125 1 0.026 5 F2 MOPSO/DC 0.000 0 0.000 0 0.000 0 0.000 0 0.665 7 0.000 0 MOPSO/D 0.005 9 0.000 4 0.002 2 0.000 2 0.325 2 0.000 3 MOPSOTL 0.321 4 0.297 7 0.000 4 0.000 6 0.374 3 0.227 7 MOPSODE 0.309 2 0.226 2 0.000 7 0.001 2 0.370 9 0.170 5 NNIA 0.354 6 0.000 0 0.000 0 0.000 0 0 0 F3 MOPSO/DC 0.000 0 0.000 0 0.000 2 0.000 0 0.784 5 0.000 0 MOPSO/D 0.005 3 0.000 2 0.001 5 0.000 2 0.202 7 0.000 4 MOPSOTL 0.422 0 0.329 7 0.000 5 0.000 6 0.468 0 0.245 9 MOPSODE 0.369 6 0.321 4 0.001 0 0.002 0 0.501 4 0.232 9 NNIA 0.387 3 0.000 0 0.000 0 0.000 0 0 0 F4 MOPSO/DC 0.000 0 0.000 0 0.000 2 0.000 1 0.596 1 0.014 5 MOPSO/D 0.004 7 0.000 1 0.001 7 0.000 2 0.513 1 0.000 6 MOPSOTL 0.327 8 0.253 9 0.000 7 0.000 7 0.147 1 0.168 0 MOPSODE 0.224 8 0.190 0 0.002 6 0.003 8 0.334 5 0.217 6 NNIA 0.356 2 0.003 9 0.007 5 0.001 6 0.018 7 0.008 4 F5 MOPSO/DC 0.000 1 0.000 0 0.000 7 0.000 0 0.809 9 0.001 2 MOPSO/D 0.041 0 0.000 6 0.021 9 0.000 6 0.764 5 0.003 7 MOPSOTL 0.038 9 0.024 9 0.004 3 0.000 8 0.737 4 0.024 7 MOPSODE 0.296 2 0.249 7 0.005 0 0.000 9 0.572 5 0.059 NNIA 0.299 4 0.000 0 0.017 2 0.000 3 0.494 0 0.000 3 F6 MOPSO/DC 0.000 2 0.000 0 0.000 7 0.000 0 0.459 8 0.001 5 MOPSO/D 0.062 7 0.003 4 0.026 9 0.001 8 0.391 2 0.005 7 MOPSOTL 0.078 7 0.006 6 0.006 9 0.001 3 0.334 6 0.010 3 MOPSODE 0.322 2 0.049 5 0.012 4 0.003 7 0.216 8 0.035 3 NNIA 0.369 4 0.000 1 0.018 7 0.000 4 0.210 2 0.000 1 ·468· 智能系统学报第 14 卷

第3期钱小宇，等：基于目标空间分解和连续变异的多目标粒子群算法。469· 1.0 1.0 0.9 0.9 0.8 鑫 0.8 真实PF 0.7 ·当前PF 0.7 0.6 c0.6 0.5 0.4 0.3 0.3 02 0.2 0.1 0.1 0 0.2 0.40.6 0.8 1.0 0 0.2 0406 0.8 Function I Function 1 (a)函数F1 (b)函数F2 1.0 1.0 0.9 0.9 。其实PF 真实PF 0.8 0.8 ·当前PF ·当前PF 0.7 0.7 0.6 05 03 03 0 01 0.1 02 0 0.6 0.8 0 02 0.40.6 Function 1 Function 1 (c)函数F3 (d函数F4 1.0 真P℉ 1.4 真实PF 当前PF 当前PF 0.8 810 0.6 0.6 0.4 0.2 0.2 0 0 02 0.5 05 0.4 0.6 Function 1 0.5 0.81.0 1.0 Function 1 1.0 Function 2 Function 2 1.5 e)函数F5 函数F6 图3测试函数的仿真图 Fig.3 Test function's simulations 4结束语 tion[C]//Proceedings of ICNN'95-International Confer- ence on Neural Networks.Perth,WA,Australia,Australia: 本文提出的算法采用目标空间分解与子区 IEEE,1995:1942-1948 域粒子更新和对引导粒子ge的位置进行连续变 [2]COELLO C A C,LECHUGA M S.MOPSO:a proposal 异的方法来提高粒子多样性和收敛性，对原算法 for multiple objective particle swarm optimization 的不足之处进行了很好地弥补和优化。通过和 [C]//Proceedings of the 2002 Congress on Evolutionary 4个不同种类的优化算法对不同种测试函数进行 Computation.Honolulu,HI,USA:IEEE,2002: 多种性能的测试对比实验证明，MOPSO/DC整体 1051-1056 效果最好，具有很高收敛性，多样性方面也有提 [3]COELLO C A C.PULIDO GT.LECHUGA M S.Hand- 升。总之，MOPSO/DC对多目标优化问题的多个 ling multiple objectives with particle swarm 性能指标同时进行了很好的优化。未来的研究重 optimization[J].IEEE transactions on evolutionary compu- 点是，将该算法更好地适应更多目标的优化问 tation,2004,8(3):256-279. 题，增强其通用性，用于解决实际问题。 [4]RAQUEL C R.NAVAL P C JR.An effective use of 参考文献： crowding distance in multiobjective particle swarm optim- ization[Cl//Proceedings of the 7th Annual Conference Ge- [1]KENNEDY J,EBERHART R.Particle swarm optimiza- netic and Evolutionary Computation Washington,DC

4 结束语本文提出的算法采用目标空间分解与子区域粒子更新和对引导粒子 gbest 的位置进行连续变异的方法来提高粒子多样性和收敛性，对原算法的不足之处进行了很好地弥补和优化。通过和 4 个不同种类的优化算法对不同种测试函数进行多种性能的测试对比实验证明，MOPSO/DC 整体效果最好，具有很高收敛性，多样性方面也有提升。总之，MOPSO/DC 对多目标优化问题的多个性能指标同时进行了很好的优化。未来的研究重点是，将该算法更好地适应更多目标的优化问题，增强其通用性，用于解决实际问题。参考文献： [1] KENNEDY J, EBERHART R. Particle swarm optimization[C]//Proceedings of ICNN’95-International Conference on Neural Networks. Perth, WA, Australia, Australia: IEEE, 1995: 1942–1948. COELLO C A C, LECHUGA M S. MOPSO: a proposal for multiple objective particle swarm optimization [C]//Proceedings of the 2002 Congress on Evolutionary Computation. Honolulu, HI, USA: IEEE, 2002: 1051–1056. [2] COELLO C A C, PULIDO G T, LECHUGA M S. Handling multiple objectives with particle swarm optimization[J]. IEEE transactions on evolutionary computation, 2004, 8(3): 256–279. [3] RAQUEL C R, NAVAL P C JR. An effective use of crowding distance in multiobjective particle swarm optimization[C]//Proceedings of the 7th Annual Conference Genetic and Evolutionary Computation Washington, DC, [4] (a) 函数 F1 0 0.2 0.4 0.6 0.8 1.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 Function 1 Function 2 真实 PF 当前 PF (b) 函数 F2 0 0.2 0.4 0.6 0.8 1.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 Function 1 Function 2 真实 PF 当前 PF (c) 函数 F3 0 0.2 0.4 0.6 0.8 1.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 Function 1 Function 2 真实 PF 当前 PF (d) 函数 F4 0.2 0.4 0.6 0.8 1.0 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 Function 1 Function 2 真实 PF 当前 PF (e) 函数 F5 0 0.5 0 0.2 0.4 0.6 0.8 1.0 0.2 0.4 0.6 0.8 1.0 Function 1 Function 2 Function 3 真实 PF 当前 PF (f) 函数 F6 0 0.5 1.0 0 0.5 1.0 1.5 0.2 0.4 0.6 0.8 1.0 1.2 1.4 Function 1 Function 2 Function 3 真实 PF 当前 PF 图 3 测试函数的仿真图 Fig. 3 Test function’s simulations 第 3 期钱小宇，等：基于目标空间分解和连续变异的多目标粒子群算法 ·469·

·470· 智能系统学报第14卷 USA:ACM,2005:257-264 ary programming[C]//Proceedings Volume 3165,Applic- [5]LILi,WANG Wanliang,XU Xinli.Multi-objective ations of Soft Computing.San Diego,CA,United States: Particle swarm optimization based on global margin rank- SPIE,1997:260-269. ing[J].Information sciences,2017,375:30-47. [14]GONG Maoguo,JIAO Licheng,DU Haifeng,et al.Mul- [6]LIN Qiuzhen,LI Jiangqiang,DU Zhihua,et al.A novel tiobjective immune algorithm with nondominated neigh- multi-objective particle swarm optimization with multiple bor-based selection[J].Evolutionary computation,2008. search strategies[J].European journal of operational re- 16(2:225-255. search,2015,247(3:732-744. [15]STORN R.PRICE K.Differential evolution-a simple [7]DAI Cai,WANG Yuping,YE Miao.A new multi-object- and efficient heuristic for global optimization over con- ive particle swarm optimization algorithm based on decom- tinuous spaces[J].Journal of global optimization,1997, position[J].Information sciences,2015,325:541-557. 11(4:341-359 [8]CHENG Tingli,CHEN Minyou,FLEMING P J,et al.A [16]ZITZLER E,THIELE L,LAUMANNS M,et al.Perform- novel hybrid teaching learning based multi-objective particle swarm optimization[J].Neurocomputing,2017, ance assessment of multiobjective optimizers:an analysis 222:11-25. and review[J].IEEE transactions on evolutionary compu- [9]SU Yixin,CHI Rui.Multi-objective particle swarm-differ- tation,2003,72):117-132. ential evolution algorithm[J].Neural Computing and ap- 作者简介： plications,.2017,28(2):407-418. 钱小宇，男，1992年生，硕士研究 [10]ZITZLER E,LAUMANNS M,THIELE L.SPEA2:Im- 生，主要研究方向为人工智能与模式 proving the strength Pareto evolutionary algorithm for 识别。 multiobjective optimization[M]//GIANNAKOGLOU K C,TSAHALIS D T,PERIAUX J,et al.Evolutionary Methods for Design,Optimisation and Control with Ap- plications to Industrial Problems.Athens,Greece:Interna- tional Center for Numerical Methods in Engineering, 葛洪伟，男，1967年生，教授，博 2002:95-100. 士，博士生导师，主要研究方向为人工 [11]JORDEHI A R.Enhanced leader PSO (ELPSO):a new 智能与模式识别、机器学习、图像处理与分析等。 PSO variant for solving global optimisation problems[J]. Applied Soft Computing,2015,26:401-417. [12]陈明杰，黄佰川，张旻.混合改进蚁群算法的函数优化 [).智能系统学报，2012,74)：370-376. CHEN Mingjie,HUANG Baichuan,ZHANG Min.Func- 蔡明，男，1962年生，高级工程师，主要研究方向为计算机软件、网络 tion optimization based on an improved hybrid ACO[J]. 应用的研究。 CAAI transactions on intelligent systems,2012,7(4): 370-376. [13]CHELLAPILLA K,FOGEL D B.Two new mutation op- erators for enhanced search and optimization in evolution-

USA: ACM, 2005: 257–264. LI Li, WANG Wanliang, XU Xinli. Multi-objective Particle swarm optimization based on global margin ranking[J]. Information sciences, 2017, 375: 30–47. [5] LIN Qiuzhen, LI Jiangqiang, DU Zhihua, et al. A novel multi-objective particle swarm optimization with multiple search strategies[J]. European journal of operational research, 2015, 247(3): 732–744. [6] DAI Cai, WANG Yuping, YE Miao. A new multi-objective particle swarm optimization algorithm based on decomposition[J]. Information sciences, 2015, 325: 541–557. [7] CHENG Tingli, CHEN Minyou, FLEMING P J, et al. A novel hybrid teaching learning based multi-objective particle swarm optimization[J]. Neurocomputing, 2017, 222: 11–25. [8] SU Yixin, CHI Rui. Multi-objective particle swarm-differential evolution algorithm[J]. Neural Computing and applications, 2017, 28(2): 407–418. [9] ZITZLER E, LAUMANNS M, THIELE L. SPEA2: Improving the strength Pareto evolutionary algorithm for multiobjective optimization[M]//GIANNAKOGLOU K C, TSAHALIS D T, PÉRIAUX J, et al. Evolutionary Methods for Design, Optimisation and Control with Applications to Industrial Problems. Athens, Greece: International Center for Numerical Methods in Engineering, 2002: 95–100. [10] JORDEHI A R. Enhanced leader PSO (ELPSO): a new PSO variant for solving global optimisation problems[J]. Applied Soft Computing, 2015, 26: 401–417. [11] 陈明杰, 黄佰川, 张旻. 混合改进蚁群算法的函数优化 [J]. 智能系统学报, 2012, 7(4): 370–376. CHEN Mingjie, HUANG Baichuan, ZHANG Min. Function optimization based on an improved hybrid ACO[J]. CAAI transactions on intelligent systems, 2012, 7(4): 370–376. [12] CHELLAPILLA K, FOGEL D B. Two new mutation operators for enhanced search and optimization in evolution- [13] ary programming[C]//Proceedings Volume 3165, Applications of Soft Computing. San Diego, CA, United States: SPIE, 1997: 260–269. GONG Maoguo, JIAO Licheng, DU Haifeng, et al. Multiobjective immune algorithm with nondominated neighbor-based selection[J]. Evolutionary computation, 2008, 16(2): 225–255. [14] STORN R, PRICE K. Differential evolution – a simple and efficient heuristic for global optimization over continuous spaces[J]. Journal of global optimization, 1997, 11(4): 341–359. [15] ZITZLER E, THIELE L, LAUMANNS M, et al. Performance assessment of multiobjective optimizers: an analysis and review[J]. IEEE transactions on evolutionary computation, 2003, 7(2): 117–132. [16] 作者简介：钱小宇，男，1992 年生，硕士研究生，主要研究方向为人工智能与模式识别。葛洪伟，男，1967 年生，教授，博士，博士生导师，主要研究方向为人工智能与模式识别、机器学习、图像处理与分析等。蔡明，男，1962 年生，高级工程师，主要研究方向为计算机软件、网络应用的研究。 ·470· 智能系统学报第 14 卷

点击进入文档下载页（PDF格式）

已到末页，全文结束

点击下载（PDF格式）

浏览记录