多目标优化算法NSGA_II的改进

就多目标优化算法NSGA_II的改进

多目标优化算法!"#$%&&的改进

刘旭红

刘玉树

张国英

阎光伟

（北京理工大学计算机科学与工程系，北京%"""J%）

摘

要

该文提出了./01233算法的一种改进算法—3./01。在引入算术交叉算子的同时，提出并引入累积排序适应度

赋值策略。实验表明，3./01具有更高的收敛速度和更好的种群多样性。关键词

多目标进化算法

&’()*+前端./01233算法

文献标识码1

中图分类号K&<"%

（!""#）文章编号%""!2J<<%2%#2""G<2"<

&’()*+,’,-.*/012.3%*45,6.3+,7(.3’389.3*-$2:*)3.;’!"#$%&&

<31=1;*-:<31>1?;1@;9-:#1*A3-:>9-#19-:B,3

（L)E*$+MB+6E@*)(/97)49)’45N4874))(748，>)7O74834C*7*@*)+MK)9;4+:+8A，>)7O748%"""J%）

$4?.)96.：1476E(+D)5D)(C7+4+M./01233，3./01，7CE(+E+C)5$3./01’5+E*C’(7*;6)*799(+CC+D)(+E)(’*+($P)’4Q;7:)，’4)Q’99@6@:’*)5(’4RM7*4)CC’CC7846)4*C*(’*)8A7CE(+E+C)5$1C)SE)(76)4*C5)6+4C*(’*)*;)()C@:*C+M3./01;’D);78;)(9+4D)(8)49)CE))5’45T)**)(E+E@:’*7+457D)(C7*A*;’4*;+C)+M./01$C,AB*)D?：6@:*72+TO)9*7D)+E*767U’*7+4，&’()*+M(+4*，./01233

%引言

由于多目标进化算法可以在一次运行中得到多个&’()*+

域覆盖!#和!$的所有邻域，且二者之间的区域搜索几率较大。显然，该算术交叉算子比/>?具有更好的全局搜索能力，能更好地保持种群的多样性。

""

优化解，近年来，在多目标优化领域已经成为一个研究热点，出现了许多优秀的算法，取得了较好的效果。其中非支配排序算法./01233（.+425+674’*)5/+(*7480)4)*791:8+(7*;633）是具

<-有代表性的算法,!，。./01233是./01,=-算法的改进，在./01

,%-

!$!累积排序适应度赋值策略

的基础上加上了精英策略、密度值估计策略和快速非支配排序策略，在很大程度上改善了./01的缺点。实验证明./01233的结果优于有代表性的其他几种算法,!-。但./01233采用的

,#-（/76@:’*)5>74’(AB(+CC+D)(）交叉算子搜索性能相对较/>?弱，所使用的个体&’()*+排序值方法有时不能很好地反映个体

当前群体中不被任何./01233采用的&’()*+排序策略是：

其他个体支配的个体是非支配个体，其&’()*+排序值赋为%，全部非支配个体的集合是第一级非支配个体集；从当前群体中将这些个体去掉，新产生的非支配个体的&’()*+排序值为!，组成的集合为第二级非支配个体集。依次类推，直到所有的个表示的"代中的个体)体的&’()*+排序值确定为止。以（()，"）的&’()*+排序值。

这种赋值方法的一个缺点是，个体的&’()*+排序值有时不尽管个体%周能很好反映个体周围的密度信息，如图%所示，但它们的&’()*+排围种群的密度大于个体’周围的种群密度，

序值都为!。尽管./01233算法中有密度信息估计的部分，但对于所采用的密度信息的估计仅限于同一级非支配个体集中,!-，图%中的个体%和’仍然具有同样的机会繁殖后代。

周围的密度信息，从而在一定程度上限制了算法的搜索性能，使得./01233在种群的多样性保持和收敛速度方面尚不能令人满意。

在./01233算法的基础上，针对./01233存在的问题，该文提出一种改进的./01233算法———3./01算法（36E(+D)5，在引入算术交叉算.+425+674’*)5/+(*7480)4)*791:8+(7*;6）

子的同时，提出并引入累积排序适应度赋值策略。最后，在收敛速度和种群多样性保持方面进行了实验验证。

!3./01算法

!$%交叉算子

./01233中采用/>?交叉算子。/>?算子模拟二进制交

叉算子的过程，对实数编码的父个体进行交叉操作，即对于给定的随机交叉点，交换两个父个体位于交叉点两侧的部分。

G-该文将算术交叉算子,F，引入./01233。设!#和!$分别为

"

"

图%个体周围种群密度的影响

该文提出的累积排序适应度赋值策略同时考虑个体的类似于./01233对所有的个&’()*+排序值和密度信息。首先，

得到每一个个体的&’()*+排序值。设在第"体进行&’()*+排序，

代种群中支配个体)的个体集为：…，则个体)累积排)%，)!，)*，序值定义为支配个体)的所有个体的&’()*+排序值的和，如式所示：（!）

（)，(%*+"）,%&!（()#，"）

#,%*

第"代两个体交叉点处对应的决策变量的真实值编码，则交叉后两个体的相应的决策变量值为：

"H%

"

"

!#I%!#&’!$

（%）

且%&’I%。

其中%和’为,2"$#，%$#-上均匀分布的随机数，和’,"，%-（!）

计算机工程与应用!""#$%#G<

就多目标优化算法NSGA_II的改进

由此，对于图%中的个体!和"的累积排序值分别为&和采用累积排序适应度赋值策略并没有增加算法的复杂度，只!。

如需对’()*+,,中的快速非支配排序算法做少许改动即可，下所示，其中黑体对应的两行是改进后的算法。

（#）-./0+121+32451.063+/270

其中%&+&/->#4,%>；#4,%:#4,%#*+，

（#4,%）；04,%:9!.:-&:<-$7$

4(4>%，+(+>%；

几点说明：

子程序872?351C+35/0.186+.//5C14610和/270分别对某（%）

一个非支配个体集进行拥挤距离赋值和拥挤距离排序，具体过程可以参考文献D!E，在此不再赘述；

子程序4.F6+16?+G2G中的选择算子使用联赛选择，（!）

个体的优劣主要由个体的累积排序适应度值确定，累积排序适应度值小的个体优。对于具有相同累积排序适应度值的个体，再进行拥挤距离的比较，拥挤距离小的个体优。

-276.89$!#%$:!；&$:"；!"#$%:!；-276.89’!#

5-（$"’）0961%$(%$#;’<；6=/65-’"$0961&$(&$>%；5-&$:"0961$):%；*%:*%#;$<；+:%；?95=6*+$!*+,%:!；-276.89$!*+

-276.89’!%$

&’(&’-%；&"#$%:&"#$%>!"；5-&’:"0961’)(+>%；*+,%:*+,%#;’<；

+(+>%；

@实验结果

该文采用,’()*对文献D!E所列举的两个典型的测试函数

进行了计算，并与由’()*+,,计算得到的结果进行比较（两个测试函数均为最小化问题）。

#

（?++%5%:%+6HGD+!%+:%"*%：$@

%（?+>%5!:%+6HGD+!

+:%&"其中，+&&?%，?!，?@&&。

@

）E）E

!

!

其中，每一个个体$对应四个数据结构：（%）个体集%$记录$支配的所有个体；（!）（@）&$记录优于$的个体数目；$)记录$的A.7602排序值；（&）$)!&.记录$的累积排序值。

*%的最优解为?%:?!:?@!D+%%E。

""#

（-"$!"?+>?+,%）5（?）:!D+%"6HGE%%+:%

*!：’&

"$I@

%?）（?+）E5（?:>#/51!+!

+:%&

&+%

*+记录第+级非支配个体集。

首先，找到群体中所有&+:"的个体，将其存入第一级非支配个体集*%，这些个体的A.7602排序值和累积排序值都为%。（中的每个个体$，考察它所支配的个体集然后，对于*++%%）将%$中的每个个体’的支配它的个体数量&’减%，并计算%$，

个体’的累积排序值’)!&.，如果支配’的个体数量&’:"，则将’存入下一级非支配集*+>%。直到所有的个体排序完毕，算法中止。

其中+#&?%，?!，?@&#。

对于两个测试问题，两种算法所采用的相同的设置为：实联赛选择，联赛规模为J，交叉概数编码方式，种群规模为%""，率为"$I，进化代数为#"代。

图!是实验结果。（.）是’()*+,,对于函数*%的运行结果，是,’()*对于*%的运行结果，（8）是’()*+,,对于函数*!（K）

的运行结果，（3）是,’()*对于*!的运行结果。由实验可以看出，采用,’()*得到的A.7602曲线分布更加均匀，且解的精确度更高。

!$@,’()*算法过程

随机产生一个规模为/的初始种群#"，将种群中的所有个体快速非支配排序。采用选择、交叉遗传算子产生一个规模选择算子主要根据累积排序值评价为/的子代种群0"。其中，

个体的优劣，选择累积排序值小的个体参与繁殖。将#"和0"合并为一个规模为!/的种群1"，对1"进行非支配排序得到非支配个体集（*%，，选择前（（@））个非支配集和*!$$$）++满足式

+

*+>%的前/-!*2个个体组成#%。

2(%

2(%

!

+

*2&/，且!*+3/

2(%

+,%

（@）

（.）

（K）

再由#%经选择、交叉产生0%，将#%和0%合并为1%。重复上面的循环，直到满足停止条件。从第一代开始主流程如下：

14(#4#04；

（14）；（*%，*!，$$$）:5!64-&7&-879+&!4:8-67)4

#4,%:!，+(%?95=6B#4>%B>B*+B&/

（*+）；;)7<8+&=-8+6!&;:-!66+=&9:&4

#4,%:#4,%#*+；+(+>%；

（*+；&图（8）

（3）

和L&!""#$%#计算机工程与应用

就多目标优化算法NSGA_II的改进

R结论

该文使用算术交叉算子代替V.-(ILL算法中的.1_交叉

V.-(ILLE0G$L===H?7+57@,2A+5A+=CA3<IABc*@,2C*)*+*,2@73)A?2,84：

（!）：,2A+7?OMA4><,7,2A+，!""!；W%K!S%&J

算子，提高了算法的搜索性能；同时，提出了累积排序适应度赋值策略，更好地维持了种群的多样性。在两个典型的多目标优化测试函数上进行了实验，对照结果可以证明LV.-(比V.b

/$‘73O7+4AOX*B$T<3,2IABc*@,2C*A>,242]7,2A+<52+)*CA3<,2A+7?O73)AI?2,845ETG$V*U^A?P：0A+8:23*Od.A+5Q?*55，!""%：!%"S/"!R$X*B‘，()?7U73F1$.24<37,*9B2+7?O@?A55AC*?DA?@A+,2+<A<55*7?@8%&&#；&：%%#5>7@*E0G$MA4>3*e.O5,*45，

#$V.?2+2C75，‘X*B，T<3,2ABc*@,2C*D<+@,2A+A>,242]7,2A+<52+)+A+9AI（/）：%&&#；!!!%S!RK42+7,*95A?,2+))*+*,2@73)A?2,845E0G$=CA3MA4><,，

陈彤，薛量等$多个体参与交叉的Q7?*,A多目标遗传算法E0G$W$朱学军，

电子学报，（%）：!""%；!&%"WS%"&

康立山$基于多父体杂交的多目标演化优化算法E0G$计算机工J$陈文平，

程与应用，（%"）：!""/；/&J&SK!

-(ILL具有更快的收敛速度和更好的种群多样性。

（收稿日期：!""R年K月）

参考文献

陈火旺，康立山$多目标优化的演化算法E0G$计算机学报，%$谢涛，!""/；（K）：!W&&JS%""/

!$‘73O7+4AOX*B，(4?2,Q?7,7>，HT*O7?2C7+$(D75,7+9*32,25,4<3,2I

（上接%&页）

较好地解决加速收敛和停滞早熟的矛盾，对算法性能的改善比较明显。算法的时间复杂度分析如下：算法初始化的复杂度为（"#）；（%）（!），其复杂!’"层包含$个蚂蚁构造解和计算公式（$!"#%）；（!&"#%）；度为!’%层局部搜索的复杂度为!’!层信息素更新的复杂度为!（"#）。因此，在最坏情况下整个算法的复杂度为!（’(%)*+,*$"#%），’(%)*+,*是达到收敛条件的演化代数。可以看到，算法的时间复杂度受收敛情况影响很大，且随问题规模的扩大，算法的复杂度呈线性上升。

*95$Q?A@**92+)5AD,8*Y2?5,L+,*?+7,2A+73MA+D*?*+@*A+.24<37,2A+Y?A4(+24735,A(+247,*5，M74B?29)*，T(：TLHAD(97>,2C*1*87C2A?：Q?*55，%&&%：/#WS/W/

W$=’<4B*?，1Y72*,7$X2C*?52,O7+9797>,2A+2+>A><37,2A+5AD@3<5,*?I0I(T*O*?，.::235A+*95$Q?A@**92+)AD,8*H82?92+)7+,5EMG$L+：

L+,*?+7,2A+73MA+D*?*+@*A+.24<37,2A+AD(97>,2C*1*87C2A?：Y?A4(+24735,A7+247,*5，M74B?29)*，T(：TLHQ?*55Z1?79DA?91AAP5，%&&R；/：#"%S#"K

J$VTA+47?@8[$\+97,7@3<5,*?2+)U2,87?,2D2@2737+,5EMG$L+：(Y?*2,75*9$X7,7T2+2+)U2,8=CA3<,2A+7?O(3)A?2,845，F*5*7?@8X2?*@,2A+5I>7>*?5D?A4,8*(((L:A?P58A>，T*+3AQ7?P，M(：(((L>?*55，%&&&：!/S!W

郑毅，傅伟鹏等$一种基于群体智能的客户行为分析算法E0G$计K$吴斌，

算机学报，（K）：!""/；!W&%/S&%K

傅伟鹏，郑毅等$一种基于群体智能的:*B文档聚类算法E0G$计&$吴斌，

算机研究与发展，（%%）：!""!；/&%R!&S%R/#

#总结

该文在分析蚁群优化算法的多()*+,结构的基础上，提出

了一种自适应蚁群优化聚类算法。该算法分为三个层次，每一层均由多个()*+,（即蚂蚁）组成。’"层是解构造层，’%层是可行解改进层（算法采用局部搜索），’!层是信息素更新层。更新后的信息素矩阵作为蚂蚁一次演化结果的反馈，为下一轮搜索提供启发信息。算法选取解构造过程中的变异概率-以及信息素残留度!作为自适应参数，在蚁群演化过程中自动调节其值，达到加快收敛和全局搜索的最佳效果。

实验结果及分析验证了该算法的有效性。与-(和.(聚类算法相比较，该算法确实表现出更好的性能，聚类效果和运行效率均优于上述两种方法。与成熟的聚类算法相比较，在运行效率和处理大规模聚类问题上有待进一步提高。（收稿日期：!""#年/月）

%"$XA?2)AT，T7+2*]]A6，MA3A?+2($(+,.O5,*4：\>,242]7,2A+BO7MA3A+OADMAA>*?7,2+)()*+,5E0G$L===H?7+5A+.O5,*4，T7+，7+9MOI（%）：B*?+*,2@5，%&&W；!W!&SR%

%%$XA?2)AT，1A+7B*7<=，H8*?7<37]-$(+,73)A?2,847+95,2)4*?)OE0G$Y<,<?*-*+*?7,2A+MA4><,*?.O5,*45，!"""；%W：K#%SKJ%

%!$^7+)_2+I12+，.<+02+)I-7A，;<7+)X7A$(+*U@3<5,*?2+)4*,8A9B75*9A+7+,@A3A+O73)A?2,84EMG$L+：Q?A@**92+)ADR,8:A?39MA+)?*55.87+)872，QFM82+7，!""!：A+L+,*332)*+,MA+,?A37+9(<,A47,2A+，!!!!S!!!W

%/$.8*3AP7?Q.，07O7?747+6‘，‘<3P7?+21X$(+7+,@A3A+O7>>?A7@8（#"&）：DA?@3<5,*?2+)E0G$(+73O,2@7M8242@7(@,7，!""R；%KJS%&#

参考文献

%$01234*5，(67897,，:;5<$=4>2?2@73AB5*?C7,2A+5AD>?AB7B2325,2@8*<?25,2@5DA?,8*@3<5,*?2+)>?AB3*4EFG$H*@8+2@73F*>A?,HFI&JI"%K，L+,*?+7,2A+73MA4><,*?.@2*+@*L+5,2,<,*，N+2C*?52,OADM732DA?+27，1*?P*3*O，M(，%&&J

!$.<+)M.，02+;:$(,7B<I5*7?@8IB75*98*<?25,2@DA?@3<5,*?2+)E0G$!"""；//：&R&SK#KQ7,,*?+F*@A)+2,2A+，

/$T<?,8OM(，M8AU98<?OV$L+5*7?@8ADA>,2473@3<5,*?5<52+))*+*,2@（%J）：73)A?2,845E0G$Q7,,*?+F*@A)+2,2A+’*,,*?5，%&&W；K!#SK/!

%R$V2@A375’7B?A@8*，V2@A375TA+47?@8a*，-233*56*+,<?2+2$(+,M3<5,：(+,@3<5,*?2+)7+9U*B<57)*42+2+)EMG$L+：-=MM\!""/，’VM.!J!/，1*?32+;*29*3B*?)：.>?2+)*?I6*?37)，!""/：!#S/W

%#$;(]]7)，VTA+47?@8a*，T.3247+**,73$(@3<5,*?2+)73)A?2,84B75*9A+,8*7+,55*3DI755*4B3OB*87C2A?EMG$L+：=M(’!""/，’V(L!K"%，1*?32+;*29*3B*?)：.>?2+)*?I6*?37)，!""/：#WRS#J%

%W$TT237+A，(FA32$T(-T(：(T<3,27)*+,(?@82,*@,<?*DA?T*,78*<I（!）：?25,2@E0G$L===H?7+5A+.O5,*4，T7+，7+9MOB*?+*,2@5，!""R；//

&!#S&R%

%J$.*?)2A5H8*A9A?2925，‘A+5,7+,2+A5‘A<,?A<4B75$Q7,,*?+F*@A)+2,2A+ETG$.*@A+9=92,2A+，=35*C2*?.@2*+@*，(@79*42@Q?*55，N.(，!""/杨志军$基于变异和动态信息素更新的蚁群优化算法E0G$软%K$朱庆保，

件学报，（!）：!""R；%#%K#S%&!

R$1?AU+X=，;<+,3*OM’$(>?7@,2@737>>32@7,2A+AD524<37,*97++*73I（R）：2+)E0G$Q7,,*?+F*@A)+2,2A+，%&&!；!#R"%SR%!

#$0’X*+*<BA<?)，.-A55，VY?7+P5*,73$H8*9O+742@5AD@A33*@,2C*5A?,2+)：FABA,I32P*7+,57+97+,I32P*?ABA,5EMG$L+：0(T*O*?，.:235A+

计算机工程与应用!""#$%#J#

本文来源：https://www.bwwdw.com/article/u98e.html