针对目前多目标粒子群优化算法的收敛性能和非劣解的多样性不能同时得到满足等缺陷，提出一种基于多策略的多目标粒子群优化算法（Multi-Objective Particle Swarm Optimization algorithm for Multi-Strategy，MS-MOPSO）。采用非支配排序和拥挤距离排序相结合策略，重新划分外部种群和进化种群；采用小生境选择策略，在外部种群中选择最佳粒子作为领导粒子，用于领导进化种群中粒子的进化；在进化种群中利用多尺度高斯变异策略，平衡算法的全局搜索和局部精确搜索；采用邻域认知个体极值更新策略，不断更新个体极值。将该算法应用到典型的多目标测试函数，并与其他多目标优化算法进行对比分析，测试结果表明该算法中四个策略的有效性和互补性，同时验证了该算法不但具有较好的收敛性和收敛速度，而且该算法最优解的分布具有良好的均匀性和多样性。
雷瑞龙,侯立刚,曹江涛:基于多策略的多目标粒子群优化算法 2016,52(8 21 分布的随机数;c,和c为学习因子;和x分别是 小,由∑(x:"-x4)确定。f(pn)是当前种群屮适应 粒子在第k次迭代时的速度和位置,在进行速度和位置 更新的过程中,其速度必须满足速度向量的约束条件,度最差的粒子。 RFER表示粒子与粒子j的参考 即 a,其位置向量也必须满足:x2∈,u,因子。 1<iN,l和u1是位置向量第维坐标的下限和上限。4.2.2确定小生境 在上述搜索策略中,每个粒子都会向离自已最近而 4基于多策略的多目标粒子群优化算法 且适应度比较好的粒子移动.使得粒子探索多个局部最 41非支配排序和拥挤距离排序相结合构造外优解并将其存储起来,进而建立小生境。建立小生境的 部集的策略 原则为:如果一个粒子作为其他粒子的局部最优粒子 (1),这些粒了和局部最优粒了的欧氏距离的平均值作 使用外部种群保存所求非劣解,不仅可以作为粒子 为一个潜在的小生境半径 radius,和l粒子的欧氏距 群的领导集合,引导整个种群的进化;而且可以作为算 法的输出,保证输出解的有效性,构成最终的 Paret前离小于半径的粒子就与这个粒子组成为一个小生境。 沿。因此,外部集存档策略非常关键 如果在下一轮迭代中这个粒子与其他粒子的参考因子 非支配排序的具体过程:首先从当前种群中寻找E值仍然是该粒子自已最大那么这个粒子就会不 出最优解并分配等级1;然后从该种群中将这些个体移除, 再以自己作为局部最优解,而是以参考因子RFER值第 二大的粒子作为局部最优解。图2为该小生境选择策 在剩余个体中寻找新的最优解并分配等级2;重复上述 过程,直到该种群中所有个体都被设定了相应的等级。 略下的粒子最终分布示意图。 拥挤距离排序:群体中一个解周围其他解的疏密 程度可以通过个体间的拥挤距离来进行判断。拥挤距 离越大,则说明解分布得越稀疏,多样性越大;反之,则 说明解分布得越密集,多样性越小。拥挤距离的排序方 法:首先根据待优化标函数的大小对外部集中的解进 行排序,然后计算每个解相邻两个粒子所构成的立方体 图2粒了分布示意图 的平均边长,图1为该解的拥挤距离示意图;最后根据4.3多尺度高斯变异策略 计算所得拥挤距离的大小对粒子重新进行降序排列 多尺度高斯变异机制可以保证算法具有全局解 日标 搜索能力的同时,进一步提高最优解的精度。该机制描 述为:设尺度个数为M,首先初始化多尺度高斯变异算 子的初始方差为: (8 2+1 日标f 在刚开始的时候,方差一般设定为优化变量的取值 图1拥挤距离示意图 范围,随着迭代次数的增加,多尺度高斯变异算子的方差 会随之进行调整,调整方式为:首先根据适应值的大小对 4.2小生境选择策略 种群屮的粒了进行由小到大的排序;然后对其进行组合, 4.2.1搜索策略 生成M个子群,每一个子群的粒子个数为P=MM 本文设计的小生境选择策略改变了原始粒子群N为粒子个数,每一个子样的适应度为: 算法的採索策略,使得算法可以存储多个局部枚值点。 Fim=∑f(x")P,m=1 M 该策略确定粒子局部最优解的原则是通过计算粒子的 参考因子RFER找到适应度在种群中占有比例较大而其中,k是当前迭代次数,f是非劣解的适应值计算函 且与这个粒子欧氏距离较小的粒子,其公式为: 数,第m个变异算子的标准差为 RFER=ax f(p)if(p) (7) M·.Fit p-p exp(- Fix Fit 其中,f(p)表示粒子i的适应度;f(p)表示种群中所 mix 有粒子的适应度和;a=~|l‖ FitX_=max(Fitx ) Fix ) .. FitY( 表示尺度因子,以 f(p)if(p) Fitr min=min(Fitr, Fitr,,,,, FitYy) 保适应度和欧氏距离的平衡。‖是搜索空间的大 变异算了的进化是一个递归过程,排在后面的变异 016,52(8) Computer Engineering and Applications计算机工程与应用 算子可能很大,因此对变异算子的标准差做如下规范 ⑧)根据邻域认知的个体极值更新策略,快速更新 若n>W/4,则 个体极值(P=) W/4 (11) (9)判断是否满足终止条件,如果满足,则将A集中 其中W为待优化变量空间的宽度,重复使用式(11),直的粒子作为 Parcto最优解集输出,否则返回步骤(3) 到满足o>H4。通过该多尺度变异算子能实现整个 算法相关参数初始化 搜索空间的覆盖,其中大尺度变异算子具有振荡性质, 有利于实现解空间的全局粗略搜索,可以快速定位到最 陌机初始化进化种群和外部种群 优解区域,逐渐减小的小尺度变异算子能在进化后期实 现局部精确解的搜索。图3为M=5个不同尺度下变异 外部种群A进化种群P 算子的方差随迭代次数的变化 基于非支配排序和拥挤距离排序 100 结合构造外部集簽略 外部种群A 根据小生境选择策 咯确定领导粒子→进化种群 10 对粒子的速度进行更新 迭代次数N 图35种不同尺度变异算子的方差随 对粒子的位置进行更新 迭代次数变化的示意图 多尺度高斯变异策略 4.4个体极值更新策略 本文采用基于邻域认知的个体极值吏新策略,具 根据个体极值选择簧略 体思路为:随机选择几个粒子作为该粒子的邻域粒子, 更新个体极值 在该邻域范围内选择非劣个体极值和原极值进行比较, 完成更新策略,其更新方程为 是否满足终止条件少 (k) =w·v+c1:r1( (12) 算法结束 图4MS- MOPSO算法的流程图 其中,1n为邻域最优个体极值 该个体极值更新策略能更好地提高算法性能,进一5仿真分析 步增强其抗早熟能力,增加种样多样性,有利于粒子的5.1测试函数 局部寻优。 本文采用以下典型测试函数对本文算法和基于多 4.5算法实现的步骤及流程图 子样的多目标算法,基于拥挤距离的多目标算法"进 图4为本算法的流程图,其具体实现步骤如下: 行测试,测试函数F(x)如下: (1)对算法的相关公数进行初始化,包括外部种样 minf,(r 大小MA,进化种群大小MP,参数c1、C2和w,t=0,最 F(x) min/(x)-=g(1-√x/ (13) 大迭代次数,高斯变异概率等。 g=1+9∑x(n-1 (2)对进化种群P和外部种群A进行初始化 (3)令t=t+1,迭代计算,开始循环。 x.∈ (4)将P和A结合后根据非支配排序和拥挤距离5.2性能评价指标 排序重新划分P和A。 为了对算法的性能进行更加准确、全面的评价,本 (5)在外部种群A集中根据小生境选择策略选择领文采用以下三个评价指标对算法进行评价。 导粒子(G)。 (1)准确性指标 (6)更新粒子的速度和位置 (⑦)根捃多尺度变异策略,对进化种群P集中的粒 zQ=∑d 子进行变异操作。 (2)多样性和均匀性指标 雷瑞龙,侯立刚,曹江涛:基于多策略的多目标粒子群优化算法 2016,52(8 23 算法进行比较分析。参数设置:进化种群和外部种群大 SP= (15) 小都为100,迭代次数的最大值为800,c,和c,均取值2, P1=min(1(x)-/1(x)+12(x)-/2(x) (16)惯性权重w从0.9线性减小到0.1,其公式为:w=wm P (17) X(Tms-y,运行50次。其中,vm、m分别为 (3)计算时间T 的最大值和最小值,t为当前迭代步数,t为最大迭代 a为算法所得非劣解的个数,d为第;个解到 Pareto步数。测试结果如下:表1为 MS-MOPSO算法、MM 最优解集的最小距离,T为优化计算所需要的时间。指 MOPSO算法和 DC-MOPSO算法关于测试函数的zQ 标ZQ反映了算法所得优化解集与 Pareto最优解集的逼均值和SP均值的对比;表2为三种算法的计算时间。 近程度,即如果zQ=0,则说明所得非劣解均属于 Pareto 图5为三种算法关于典型测试函数的收敛速度及生成 最优解集;如果ZQ≠0,则说明所求非劣解与 Pareto最优 Parcto前沿的对比。 值有一定的偏离。因此,ZQ值越小,其逼近程度越 表1测试函数F(x)的2均值和SP均佰 好。如果SP一0,则说明非劣解前端上所有解呈均匀分 测试函数F(x) 算法 布,因此,SP值越小,非劣解前端分布越均匀,其多样性 ZQ均值SP均值 越好。如果T越小.则说明算法的复杂程度越小;反之 MS-MOPSO 00257 0387 DC-MOPSO 0.032 0.0865 则说明算法的复杂程度越大。 MM-MOPSO 800 0.0269 0.0458 53仿頁测试 苌23种算法的计算时间 为了验证本文所提出的 MS-MOPSO算法的有效性 算法 测试函数迭代100次迭代400次迭代800次 采用上述典型测试函数对 MS-MOPSO算法 MM-MOPSO MS-MOPSO F(x)21.3016779.23541158.01653 算法和 DC-MOPSO算法进行测试,并将本文算法和文献(7 F(x) 15.7145256.3204 提出的 MM-MOPSO算法和文献[8]提出的 DC-MOPSO MM-MOPSO F(x)18834716364523135.51031 2 12 16 (a)MSMⅥOPSO迭代100次 (b)DC- MOPSO迭代100次 (c)MM- MOPSO迭代100次 0.8 l.0 0.5 0.5 0.40.60.81.0 0. fo f1(x) fc (d) MS-MOPSO迭代400次 (c)DC- MOPSO迭代400次 (fMM- MOPSO迭代400次 1.2 0.8 0.8 0.4 40.60.81.0 040.60.81.0 040.60.81 f1(x) ( g)MS-MOPSO迭代800次 (h) DC-MOPSO迭代800次 (i) MM-MOPSO迭代800次 图5三种算法关于测试函数F(x)的 Pareto曲线 24 016,52(8) Computer Engineering and4 pplications计算机工程与应用 54测试结果分析 本文算法具有非常好的性能。 由表1可知:无论是Q值还是SP值,本文算法都 要好于文献[刀]提出的 MM-MOPSO算法和文献8提出参考文献: 的DC- MOPSO算法ε这主要是由于本文算法采用小生「1]于繁华,杨威,张利彪基于模糊的多目标粒子群优化算法 境选择策略从外部种群中选出最优粒子作为领导粒子, 及应用[J计算机仿真,2007,24(2):153-156 从而很奷地领导了群体的进化,使得最优解更加接近最[2]赵志刚,李陶深,杨林峰求多日标优化问题的粒子群优化 优前沿,ZQ值也就会比较小;由于本文算法采取多尺 算法[J计算机工程与应用,2009,45(29):37-40 度高斯变异策略从而避免变异的盲目性,使得最优解分31阳春华,莫志勋,李勇刚基于改进粒子群优化算法的约束 布得更加均匀,从而SP值也就会比较小。由表2可知: 多目标优化计算机工程,2010,36(20):203-206 在相同计算代数下,本文算法的计算时间比其他两个算4劫成玉,姚宏颜雪松基于多粒子群协同的动态多日标优 法的计算时间长,这是由于本文算法在构造外部集和进 化算法及应用[计算机研究与展,2012,50(6):1313-1323 5 Santana R A, Pontes M R. Bastos-Filho C J A. A multiple ob 行有选择性变异的时候,都需要进行排序,这就增加了相 应的计算量进而增加了计算时间。然而,本文算法的收 jective particle swarm optimization approach using crowding distance and roulette wheel[C]9th International Conference 敛速度很快,在400代时就已经收敛了,而其他两个算法 on Intelligent Systems Design and Applications, 2009 都需要800代左右才能收敛收敛时间比本文算法吋间 长因此,本文算法在一定程度上也减少了计算时间。[6]罗辞勇,卢斌陈民轴,等组合粒子群优化和分布估计的 由图5可知: DC-MOPSO算法的收敛速度比MM 多日标优化算法!重庆大学学报,2010,334):31-36. MOPSO算法快,但是 MM-MOPSO算法最优解的分布7]张利彪,周春光,刘小华,等求解多月标优化问题的一种多 性比DC- MOPSO算法好,这两种算法都不能同时达到 了群休进化算法[J控制与决策,2007,22(11):1313-1316. 收敛速度快和最优解分布性好的要求。然而从图5中[8]王辉,钱锋基于拥挤度与变异的动态微粒样多目标优化 可以看出本文算法在这两方面表现得非常好,既能保证 算法[J控制与决箦,2008,23(11):1238-1242 粒子快速收敛,又能保证最优解的多样性。 [9]黄树运,赵志刚,王伟倩基于随机惯性权重的简化粒子群 优化算法[计算机应用研究,2013,31(2):361-363. 6结论 [10]潘峰,李位星,高琪,等粒子群优化算法亐多目标优化[M] 本文提出了一种基于多策略的多目标粒子群优化 北京:北京理工大学出版社,2013:9-13 算法,即在基本粒子样算法中引进四种改进策略:采用t11hk, grana,PpA, ala fast elitist non -domin 非支配排序和拥挤距离排序结合的构造外部集策咯,这 sorting genetic algorithn for multiobjective optimization c NSGA-II Lecture Notes in Computer Science, 2000,1917 样不仅可以保证算法最后输出解的有效性,还可以促进 849-858 种群的多样性;采用小生塇比较选择策略,此策略既可 [12]李屮凯,谭建荣,冯毅雄,等基于拥挤距离排序的多目标 以保证算法的收敛速度,又有利于算法跳出局部最优; 粒了群优化算法及其应用[J计算机集成制造系统,2008, 采用多尺度高斯变异策珞,该机制可以平衡算法的全局 14(7):1329-1336 搜索和局部楮确搜索,这样不但加快了算法的收敛速13]业宁,董逸生小生境排挤聚类算法[]计算机科学,00 度,而且提高了算法的准确度;采用邻域认知的个体极 30(7):149-151 值更新策略,该策略增加了种群多样性,有利于粒子进141陶新民,刘福荣,刘压,等定向多尺度变异克隆选择优化 行局部寻优。这四种策略相互配合,共同提高算法的收 算法[J控制与决策,2011,26(2):175-181. 敛性和多样性。将其应用于典型的测试函数,并与DC-15]胡广浩,毛志忠,何大阔基于两阶段领导的多目标粒子 MOPSO和MM- MOPSO进行比较分析,最终结果表明 群优化算汯[控制与决策,2010,25(3):404-410.