论文研究-NSGA-II中一种改进的分布性保持策略.pdf

所需积分/C币:7 2019-09-08 09:56:08 606KB .PDF

NSGA-II以其良好的收敛性和时间效率广泛应用于多目标优化中,然而其基于聚集距离的种群维护策略并不能很好地保持解集的分布性。提出一种改进的分布性保持策略,设置随种群密集程度自适应变化的阈值,动态地维护种群,使得分布性优秀的个体有更大的生存机会。与NSGA-II和ε-MOEA在5个测试函数上进行比较实验,结果表明改进算法在有效提高分布性的同时,拥有良好的收敛性。
文诗华,郑金华:NSGA∏口一种改进的分布性保持策略 2010,46(33) 即= dist/(2× popsize) 一层非攴配个体。 临近个体的选择:当前层中的任意两个体a和b,若两个体 间的欧氏距离小于或等于临界距离δ,找出临近个体c和d,其4实验与讨论 中c与a相邻,d与b相邻,求得个体c、d的中心位置e,选择a和4.1测试函数及实验环境 b中距离中心位置较近的个体,淘汰a和b中距离中心位置较 选择了5个不同的测试函数来验证算法,程序运行在 远的个体。如图3所示,a个体和b个体之间的距离小于临界1.6 GHZ CPU、768MB内存 Windows Xp+sp2环境下。测试 值,个体b被选择,个体a被淘汰。 函数的描述如表1所示,这些多目标测试函数有连续的、非连 续的、凸的、凹的等。参数的设置:在 Improved-NSGA和 NSGA-II中,种群规模 popsize=100,运行代数为ngen=200; 在E-MOEA中,归档集的大小是变化的,为了得到上述种群 规模大小的归档集,需调节ε的值,在这里,ε的取值尽量与文献 [1〕]相同。此外,三种算法均采用实数编码,交叉概率为p 0.9变异概率为p。=0.1 表1测试函数 测试问题 目标函数 约束条件及特征 f(x1)=x1 图3临近个体的选择方法 m=30,0≤x1≤ ZITI 12(x)=;(1-、(g) 临近个体的修剪策略如算法2所示。 g(x)=1+9∑x/(m-1) 真实 Pareto凸h 算法2临近个体的修剪策略 f(x1) 步骤1设档案集中已有m个个休,在当前的外部种群中 m=30:0<¥< ZDT2 f2(x)=g(-(f(g) 找到了个非劣解,rWnk=r,1≤i≤l,1≤j≤l。 真实 Pareto凹 g(x)=1+9〉x/(m-1) 步骤2对个非劣解按照任一子目标进行排序,删除重复 个体,按公式(5)计算出当前层个体的临界距离δ。 f1(x)=g(-、/g-(/g)m(10) m=30:0≤x≤1 步骤3循环比较相邻点的距离,修剪当前层的非劣解。 真实 Pareto凸且非连续 g(x)=1+9∑x/(m-1) i-1,-2∥个体i和个体为相邻的个体 while(j!=NULL) f(x, =1-exp(-4x )sin(6x) dist1,=dst(,);计算临近两个体的距离 ZDT6 f(x)=g(1-(1g) m=10,0≤x:≤1 while( dist;≤o)∥相邻个体的距离小于临界值 g(x)=1+9(∑x/(m-1)2) 真实 Pareto巴 m=30,-103≤x≤10)5 SCH f(dst.≤6&&i==1) f2(x)=(x-2) 真实 Pareto凹 del(i);I--ij++ dist, -dist(i, j); 4.2性能评价 ∥淘汏与边界点距离小于临界值的个体 多日标优化的两个基本日标为收敛性和分布性。在多日 else if(dist. so&&j==D) 标优化中解集的评价方法也是一个重要而复杂的问题,研究 del(i);I; i--;dist,:-dist(i, j); 者们提出了很多有效的方法24。这里采用 Generational dis ∥/汰与另一边界点距离小于临界值的个体 dance(GD)町法来估计算法的最终边界与全局非劣最优区域 o= compute(i-1,+1);计算中心点的位置 的趋近程度,计算如下 compare(dsto,dist.);比较临近个体与中 GD (6) 心点的距离,淘汰离中心点较近的个体 if del(i)l--i dist,=dist(i-1,j); 其中,n是解集中个体的数目,d是每个个体到全局非劣最优 if del(j)/--;disti. dist(i, j-1) 解的最小欧几里得距离。GD的值越小就说明解集越靠近全 局非劣最优区域,如果G冂=0说明算法的解都在全局非劣最 优区域上,这是最理想的情况。分布性评价采用 Schott提出的 方法,其函数定义如下: 步骤4外部种群中挑选的这l个个体进入下一代 步骤5如果}+m< popsize,r++,即找出外部种群的下 n-1(d-d)2 (7) 层非攴配个体,转步骤I。 其中,d=min,G(x)-f'(x)+f(x)-f2(x)(i,j=1,2,…,n), 步骤6如果l+m< popsize,则用算法1选择个体进入下 代 d是所有d的平均值。当算法获得的非劣解完全均匀地分布 从算法流程可以看出:在种群维护过程屮,删除了同层屮在目标空间时,SP=0。 的重复个体,临近个体根据临界距离δ进行筛选,其中临界距43实验与数据分析 离δ是随着进化过程以及同层个体的状态而动态调整的,分 使用改进的NSGA( Improved- NSGA-I)、 NSGA-II 布性较好的个体有更大的生存机会,而算法1仅仅是在当非支-MOEA在前述的环境下对表1的测试函数进行优化,得到的 配个体的数量大于种群时才会考虑分布性的,并且只考虑了 Pareto前沿如图4~图8所示。 2010,46(33) Computer Engineering and Applications计算机工程与应用 1.0 0.8 08 06 0.4 0.4 0.20.40.6081.0 0.100.20.40.60.81.0 0.1 0.20.40.60.81.0 (a)改进的NSGA-Il (b)NSGA-II (c)E-MOEA 图4三种算法在ZT1上的最终曲线 1.0 1.0 0.6 0.4 0.4 0.1 0.100.20.40.60.81.0 0.100.20.40.60.81.0 0.100 0.40.60.81.0 (a)改进的NSGA-II (bNSGA-II (c)8-MOEA 图5三种算法在ZDT2上的最终曲线 1.2 0.8 0.8 0.8 0.4 0.8 -0.8 -0.8 1.0 00.20.40.60.81.0 0.100.2040.60.81.0 0.100.20.40.60.81.0 (a)改进的NSGA-Il (b)NSGA-II (c)&-MOEA 图6三种算法在ZDT3上的最终曲线 1.0 0.8 0.8 0.6 0.6 0.4 0.2 0.1 0.1 0.30.40.50.60.70.80.91.0 0.30.40.50.60.70.80.91.0 0.30.40.50.60.70.80.91.0 (a)改进的NSGA-II b)NSGA-II (c)&-MOEA 图7三种算法在ZDT6上的最终曲线 4.0 4.0 4.0 3.0 3.0 3.0 2.0 0 20 1.0 1.0 1.0 ■ -0.5 0.50 0.50 f (a)改进的 NSGA-II (c)e-MOEA 图8三种算法在SCI上的最终曲线 从图4~图8叮以看出,三种算法无论是在分布的广度还匀,有些地方没有个体或者个体稀疏,有些地方则有很多的重 是在均匀性方面 Improved-NSGA比NSGA和-MOEA复或相似个体堆积的现象,特別是在测试各维聚集距离差异 要妤。主要表现在:NSGAⅡ和εMOEA的个体分布很不均的MOPs这种现象更加明显,如ZDT2、ZDT3。另外 文诗华,郑金华:NSGA∏口一种改进的分布性保持策略 2010,46(33) 表2算法的分布性平均SP及其方差σ的比较 Improved-NSGA-II NSGA-II E-MOEA SP(Avg) SP( SP(Avg) SP(a) SP(Avg) ZITI 0.003958730.0007023320.006878390.0006582200.005904630.000280124 ZDT2 0.004984690.0007715010007396370.0008046450.008615320.000881631 ZDT3 0.00454934 0.000527765 0.007101340.000687717 0.01116441 0.000516436 ZDT60.002127990.0002198240.005090280.0005678070.003638460.000420732 SCIl 0.026953320.0047030760.037911220.0040290710.038069800.003464291 表3算法的收敛度平均GD值及其方差σ的比较 Improved- NSGA-II NSGA-II E-MOEA GD(Avg) GD(a)( GD(G) GD(Avg) dia) ZDT1 0000150124.85742E0050000222061.48859E0050.004635011.52413E-004 ZDT2 0000104834.96187E0060.000119344.71238E0050.00612093332873E-004 0.000581853.53524E0050000559852.82579E-0050.000752103.33215E-004 ZDT6 0.000574631.01384E-0050.000577984.62057E-0050.00087653460292E-00 SCH0.000388181.44904E0050.000413292.24714E0050.05419124777212E-004 ε-MOEA很难找到边界点,造成边界的 Pareto前沿个体丢失 pur, India, 2000 如ZDT1、SCI。总之,从实验结果图上可以看出, Improved-6 I Corne d w, Knowles j d, Oates m J. The Pareto envelope-based NSGA-得到的 Pareto前沿要明显优于\SGA-和εMOEA。 selection algorithm for multiobjective optimization[C]/Schoenauer 为了定量的分析,表2和表3给出了三种算法在不同测试 M, Deb K, Rudolph G, et al. Proceedings of the Parallel Problem 函数上分布性(SP)和收敛性(GD)结果,其中的数据为算法运 Solving from Nature VI Conference. New York: Springer, 2000 行10次统计得到的SP和GD平均值(Avg)和方差(),表中加 839-848 粗的数据为最好值。从表2可以看出, Improved-NSGAⅡ得到 d-NSGA得到7c0 ,Jerram.Kno9p,a.PEs1 egion-base 的SP平均值都要明显好于 NSGA-1和ε-MOEA,这说明lm proved- NSGA-I能较好改进分布性,而从GD值的统计结果可 ings of the Genetic and Evolutionary Computation Conference (GECCO-2001)[S 1. ] Morgan Kaufmann Publishers, 2001: 283-290 以看出, Improved-NSGA在ZDT1、ZDT2、ZDT6、SCH都要18]崔逊学多目标进化算法及其应用M北京:国防工业出版社,2006 好于NGAI和8MOEA,ZDT3略差于NSGA。这说明, [9] Deb KMulti-objective optimization using evolutionary algorithm 新算法在改进分布性的同时也改善了算法的收敛性。 hichester, UK: John wiley Sons, 2001 [10] Deb K, Mohan M, Mishra s. a fast multi-objective evolutionary 5结论 algorithm for finding well-spread Pareto-optimal solutions,Kan 通过对NSGAⅡ中拥挤度计算方法的分析,提出了一种 GAL Report No 2003002[R]. 2003 改进的分布性保持策略。新算法中临界距离融入到进化过程g, eng Jin-hua Spread assessment for evolutionary mult 中,并且通过每一层非支配个体的状态进行动态调节,对每 objective optimization[C]/sth International Conference on Evo 层个体分布密集的区域进行修剪,具有一定的自适应性,分布 lutionary Multi-Criterion Optimization(EMO 2009), Nantes, france 2009:216-230. 性好的个体有更大的生存机会。将算法与NSGA 12]李密青,郑金华,谢炯亮,等.一种MOEA分布度的逐步评价方法J s-MOEA在5个测试函数上进行比较实验,结果表明改进的算 电子学报,2008,36(10):1986-1991 法具有良好的分布性能和收敛性能 [13] Ali F M, Aarm SAn information-theoretic metric for assess- ing multi-objcctive optimization solution sct quality[J] Journal 参考文献: of Mechanical Design, 2003, 125(4) ]郑金华多日标进化算法及其应用[M]北京:科学出版社,2007 1 14 Li Mi-qing, Zheng Jin-hua, Xiao Gui-xia Uniformity assessment [2] Zitzler E, Thiele L Multi-objective evolutionary algorithms: A com for evolutionary multi-objective optimization[C]//Proceedings of parative case study and the strength pareto approach[].IEEE IEEE Congress on Evolutionary Computation( CEC2008),Hon Transactions on Evolutionary Computation, 1999,3(4): 257-271 kong,2008:625-632. [3] Zitzler E Laumann M, Thiele I SPEA2: Improving the strength [15] Van Veldhuizen D A, Lamont G B Evolutionary computation and Pareto evolutionary algorithm, TIK2Report 103[R].2001 convergence to a pareto front[C]/Koza J R Late Breaking Papers [4] Srinivas N, Deb K Multi-objective optimization using non-domi- at the Genetic Programming 1998 Conference, Stanford Univer nated sorting in genetic algorithms[J]. Evolutionary Computation sity, California, 1998: 221-228 1994,2(3):221-248 [16 Schott JR Fault tolerant design using single and multicriteria [5] Deb K, Agrawal S, Pratab A, et al. A fast elitist non-dominated sort genetic algorithm optimization[D]. Department of Aeronautics genctic algorithm for multi-objcctivc optimization: NSGAll and Astronautics, Massachusetts Institute of Technology, Cam KanGAL Report 200001[R]. Indian Institute of Technology, Kan bridge, Massachusetts, 1995

...展开详情
试读 5P 论文研究-NSGA-II中一种改进的分布性保持策略.pdf
img
  • 至尊王者

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

关注 私信 TA的资源

上传资源赚积分,得勋章
    最新推荐
    论文研究-NSGA-II中一种改进的分布性保持策略.pdf 7积分/C币 立即下载
    1/5
    论文研究-NSGA-II中一种改进的分布性保持策略.pdf第1页
    论文研究-NSGA-II中一种改进的分布性保持策略.pdf第2页

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

    7积分/C币 立即下载 >