论文研究-NSGA-II算法的改进策略研究.pdf

所需积分/C币:18 2019-09-11 07:01:36 572KB .PDF

带精英策略的非支配排序遗传算法(NSGA-II)在多目标优化领域具有广泛的应用,但该算法种群收敛分布不均匀,全局搜索能力较弱,算法运行速度较慢。针对这些局限性提出了改进的排序适应度策略、算术交叉算子策略、按需分层策略和设定阈值选择策略。在典型的测试函数集上的数值实验结果表明,根据这些策略改进的算法得到的非劣解集具有较好的分布性,同时收敛速度更快。
44 2011,47(19) Computer Engineering and Applications计算机工程与应用 适应度策略。该策略在NSGA算法基础上,不仅考虑了个择拥挤距髙大于阈值个体参与赌轮盘选择,小于阈值个体被 体的 Pareto非支配排序值,而且结合了个体周围的密度信息,淘汰,然后重新选择一个满足条件个体参与轮盘赌选择操作。 如图1所示,个体a、b和c的 Pareto非支配排序赋值为2,但a25算法流程 个体周围密度明显大于b个体周围密度,b个体周围密度明显 步骤1初始化种群P,种群大小为N; 大于c个体周围密度。改进排序适应度策略是将同一层非支 步骤2计算每个个体的非劣级别值、拥挤距离和改进排 配排序级别中个体的适应度赋值重新定义为该个体的非支配序适应度值; 排序赋值与支配该个体所有个体数日之和,这样不仅考虑了 步骤3进入循环迭代2; 个体的非支配排序,又结合了个体周围密度信息。即个体a 步骤4对每个」种群依据每个个体的非劣级别值、拥挤 被个体2、3和4支配,其新适应度赋值为3+2=5,同理,个体b距离和改进排序适应度值,运用轮盘赌方法进行设定阈值选 被体4、5支配,其新适应度值为2+2=4,c被个体6支配,其新择操作; 适应度赋值为2+1=3。测试函数结果表明此策略不仪没有增 步骤5使用算术交叉算子进行变异操作,得到N个后代; 加算法的复杂度,同时结合个体周围密度信息进行适应度赋 步骤6对变异操作之后的每个个体计算适应度值; 值,保证了种群分布多样性。 步骤7收集第i代和第计1代所有个体,得到规模为2N的 22算术交义算子设计 种群Q; 基于上述14节中SBX交叉算子局限性分析,使用算术交 步骤8计算种群Ω内每个个体的非劣级别值、拥挤距离 叉算子替代SBX交叉算子,该算术交叉算子结合了种群个体和改进排序适应度值,使用按需分层策略选择较好的N个个 Pareto非支配排序级别信息,其定义如下: 体作为种群P; Brank 步骤9如果满足停机条件则停机;否则,=计1,转步骤4: Drank+ brank 其中A,ank代表个体A的非支配排序赋值,B.mnk代表个体 步骤10输出结果,并画图。 B的非支配排序赋值,该交叉算子系数α与每个个体在种群中 Pareto非支配排序级别相关联。由定义可知,在算法运算前3数值实验 期,a变化较大, Pareto非支型排序值小的个体在后代个体中31测试函数 占据比较大的数量。但随着演化发展,群体中个体都趋于同 本文采用 zitzler和Deb在文献[9]列举的几个典型的测试 Pareto前沿上,a趋于常数0.5。 函数(ZDT1、ZDT2、ZDT5和ZDT6)进行了数值实验,并与经 423按需分层策略 典算法NSGA-Ⅱ的计算结果进行比较。 基于述1.6节中 Pareto排序策略时间复杂度局限性分 ZDT1:具有凸的 Pareto最优前沿。 析,提出按需分层策略:在NSGA-Ⅱ算法中需要将规模为2N的 f(r=x 父代与子代混合种群进行 Pareto排序,得到一系列非支配集 f2(x)=g(x)[1 合F=F1UF,∪…∪Fn,n为非支配集合层数。首先利用构造 (x) 非支配集的方法求出F1至Fn,当NSGAⅡ算法分层结束后, g(x)=1+ 进行选择截断,如图2所示,取规模为2N的非支配集中一半个 体,保留其上半部分规樸N的个体集演化到下一代,删除F x2∈[O,1i=1,2 下半部分规模N的个体集。这种分层方法有其不足之处,当 ZDT2:具有非凸的 Pareto最优前沿。 F3分层完毕后,如果前面三层F1、F2和F3中的所有个体累计 f(=x 数已经超出了一个种群规模N,那么接下来再对后面F4F5 12(x)=g(x)-(-1 和F6分层是没有必要的,这样操作增加了算法运行时间。按 需分层策略是在分层的过程,当已分层的非支配集中的累 g(x)=1+-9 x 计个体数大于或等于种群规模N时便停止分层,不对种群规 x1∈[0,1 模为2N的所有个体进行分层操作。该策略的优点在于提高 ZDT5:具有单式幺正的骗问题。 算法运行效率,如图2所示,当前三层F1、F2和F3非支配集构 f1(x)=1+(x 造完毕后,它们个体累计数目已经超过了种群规模N,便停止 f,(x)=g/fi 分层。测试函数表明,按需分层策略比原有算法具有更高的 运行效率,更少的非支配集层数。 g(x)=∑((x) 24设定阈值选择策略 m=1,0≤x1≤1;如果(x)<5,则y(x)=2+(x); 基于上述1.2节中选择截断策略局限性分析,提岀设定阈 如果l(x)=5则v(x)= 值选择策略,该策略思想如下:对图2中非支配序列F至F ZDT6:具有非幺正特性。 先进行拥挤度排序,然后根据实际问题选取一个阈值,当进行 f()=1-exp(4x )sin (6x) 选择截断操作时,从规模为2N种群中首先选择大丁阈值个体 进入下一代演化群体,小于國值个体被淘汰。同理,将该策略 f2(x)=g(1-(-)) 思想运用到赌轮盘选择策略中去,在勾次对两个个体进行比 较选择之前,首先判断个体拥挤度。通过预先没一个國值,选 g(x)=1+9 陈婕,熊盛武,林婉如:NSGA-II算法的改进策略研究 2011,47(19) 1.1 nsgaz-vI. I/best popout a sga2-vl. 1/best pop out 10 nga/ best pop out”*/ 0.9 nsga2/best pop out 0.8 0.8 0.7 0.6 0.4 0.4 0.3 0.2 0.1 00.10.20.3040.50.60.70.80.91.0 00.10.20.30.40.50.60.70.80.91.0 图5两种算法在ZDI上的实验结果比较图6两种算法在ZDT2上的实验结果比较 18 “nsga2/ best pop.our”·/ ga2-v1. 1/best popout 0.8 nsga2-v1. 1/best popout ¨nsga2 best pop.out 14 0.6 0.5 0.4 0.3 上aaag目目B上日B和+ 0.1 05101520253035 30.40.50.60.70.80.910 图7两种算法在ZDT5上的实验结果比较 图8两种算法在ZDT6上的实验结果比较 m=10,0≤x1≤1 用在一个算法中,而应该根据具体情况具体分析。此外,算法 这4个测试函数的 Pareto最优前沿都是由g(x)=1确定在处理具有离散特性和多峰特性问题上还有待进一步研究和 的,且 Pareto最优解满足0≤x1≤1,x=0,=1,2,…,n。 探索。 32实验结果 图5~图8分别是ZD、ZD12、ZDs和ZD6的实验结参考文献 果:nga2vl. 1/best popout”三角形曲线是改进后的实验结[1 J Deb K, Agrawal S, Pratap A, et al. a fast elitist non-dominated 果,nsga2/ best pop.out”交叉曲线是原始算法结果。 sorting genetic algorithm for multi-objective optimization 33实验结果分析 Nsga-il[Ebol].http://citeseerx.ist.psuedu/viewdoc/summary?doi 10.1.1.18.4257 实验结果表明,本文提出的改进NSGAⅡ算法能够非常(2郑强带槽英築略的非支配排序遗传算法的研究与应用D杭州 有效地处理 Pareto最优前沿为凸的和非凸的以及骗问题多目 浙江大学,2006 标测试函数,其收敛性能优于NsGA算法。所得的非劣解(3]李中凯,谭建荣,冯毅雄,等基于拥挤距离排序的多目标粒子群优 在目标空间上有较好的多样性和均匀性,比原有的 NSGA-II 化算法及其应用[门计算机集成制造系统,2008,14(7):1329-1336 方法具有更好的种群收敛性,更少的非支配集层数,更高的运[4]冯上刚,艾芊带精英策略的快速非支配排序遗传算法在多目标无 行效率。但是改进NSGA-I算法在处理具有离散特性的 功优化中的应用[J电子技术学报,2007,22(12):146-151 ZDT3测试函数和具有多峰特性的ZDT4测试函数上效果不[S]唐云岚,赵青松,高妍方,等 Pareto最优概念的多目标进化算法综 佳,算法在处理高维问题ZDT4函数时,由于此函数具有219 述[计算机科学,2008,35(10):25-27 个局部最优前治,导致算法很难收敛到仝局 Pareto最优前沿 [6]欧阳骏,杨峰,杨文,等ISGA-Ⅱ算法及其在天线综合中的应用[J 电子科技大学学报,2008,37(6):886-889 4总结 7]任庆生,叶中行,曾进等交叉算子的搜索能力门计算机研究与发 展,1999,36(11):1317-1322 针对NSGA-Ⅱ算法在多样性、收敛性和运行效率三方面 [8]蒋勇,李宏,焦永昌改进NSGA终止判断准则门计算机仿真, 的局限性,提岀四点改进策略:改进排序适应度策略,算术交 2009,26(2):196-200 叉算子策略,按需分层策略和设定阈值选择策略。通过实验 [9] Deb K, Pratap A, Agarwal S, et al. A fast and elitist multiobject 表明,改进算法比原有NSGA-算法具有更奷的种群收敛性 tive genetic algorithm: NSGA-IIpJ.IEEE Transactions on Evolu 更少的非支配集层数和更高的运行效率。正如优化领域中的 tionary Computation, 2002, 6(2): 182-197 没有免费的午餐( No free lunch)”定理阐述那样,虽然[10] Wolpert D H, Macready Wo. No free lunch theorems for opti- NSGA算法因其应用广泛受到越来越多的关注,得到了许多 mization[]. IEFF Transactions on Evolutionary Computation 研究人员创造性的改进,但不能一味将所有改进策咯同时运 1997,1(1):67-82

...展开详情
试读 4P 论文研究-NSGA-II算法的改进策略研究.pdf
img
  • 至尊王者

    成功上传501个资源即可获取

关注 私信 TA的资源

上传资源赚积分,得勋章
    最新推荐
    论文研究-NSGA-II算法的改进策略研究.pdf 18积分/C币 立即下载
    1/4
    论文研究-NSGA-II算法的改进策略研究.pdf第1页
    论文研究-NSGA-II算法的改进策略研究.pdf第2页

    试读已结束,剩余2页未读...

    18积分/C币 立即下载 >