论文研究-求解大规模优化问题的正交反向混合差分进化算法.pdf

所需积分/C币:6 2019-07-22 18:44:57 2.17MB .PDF

差分进化算法简单高效,然而在求解大规模优化问题时,其求解性能迅速降低。针对该问题,提出一种正交反向差分进化算法。首先,该算法利用正交交叉算子,加强了算法的局部搜索能力。其次,为防止过强的局部搜索使算法陷入早熟收敛,利用反向学习策略调节种群多样性,从而有效地平衡算法的全局和局部搜索能力。利用11个标准测试函数进行实验,并和差分进化算法的四种优秀改进版本进行比较,实验结果表明提出的算法求解精度高、收敛速率快,是一种求解大规模优化问题的有效算法。
1658· 计算机应用研究 笃33卷 b)随机产生1,7]之间的三个随机数,设分别为24、6。其中,=1,2,…,D 则将7维空间分为4段,分别为 factor1=(x1,x)、 factor2=(x GOBL依据k的取值不同,有多种不同的方案,其中搜索 x4)、 factor3=(x3,x6)及 factors4=(x-) 效率最高的是k取值为[0,1]之间的随机数。为了能适应单 c)使用正交表L(34)进行正交交叉,所得9个后代个模、多模等各类优化问题,避免远离全局最优的反向解进入到 休为 下一代种群中,GOR采用」一种精英选择机制,即将所有当 u1=L1.0,2.0.6.0,2.0,13.0,7.03.0」 前解和反向解合并成一个解集,然后依据适应度从低到高排 u2=[1.0,2.0,8.0,5.5,16.5,7.54.0 序,诜取前面的NP(NP为种群大小)个解作为新的解集。 u2=[1.0,2.0,10.0,9.0,20.0,8.0,5.0 2.3正交反向混合差分进化算法 u4=[4.5,5.5,6.0,2.0,16.5,7.5,5.0] 正交交叉和反向学匀策略分别从两个不同方面对标准DE U=;us=[4.5,5.5,8.0,5.5,20.0,8.0,3.0 算法进行改进。正交交义通过对局部空间的充分搜索,较好地 =[4.5,.5,10.0,9.0,13.0,7.0,4.0 提高了算法的局部寻优能力;而反向学习策略本质上是变换了 =[8.0,9.0,6.0,2.0,20.0,8.0,4.0 算法的搜索空间,在搜索当前空间的同时,对反向空间也进行 u=[8.0,9.0,8.0,5.5,13.0,7.0.5.0] 搜索,这在一定程度上避免了陷入局部最优,提高了算法找到 u=[8.0,9.0,10.0,9.0,16.5,7.5,3.0 最优解的概率。 QOX方法利用正交性选取搜索空间中均匀分散、整齐可 为了进一步提高D算法的整体性能,使其在求解大规模 比的代表点进行实验安排,有效地减少了实验的次数,节省了优化问题吋获得较好的结果,充分结合正交交叉和反向学匀策 实验资源和时间。 略的优势,本文提出正交反向混合差分进化(H上OO)算法。 2.2反向学习策略 IDEOO算法是将DE算法的每一次迭代过程划分为两个阶 反向学习是近年来计算智能领域新出现的概念,已被证明段。第一阶段,在标准DE算法的每一次迭代屮利用正交交叉 能够显著提高优化方法性能9-11反向学习策略一经提出 算子,对一个随机选取的个体进行交叉操作。同时,为提高搜 便在计算智能领域引起了广泛关注 索效率,该个体变异操作采用随机数作为缩放因子。仅对一个 2.2.1反向学习 个体进行正交交叉,目的是增强算法局部寻优能力的同时避免 中国古代经典《易经》有“太极生两仪,两仪生四象,四象评价次数的急剧增加。第一阶段,为了避免过强的局部寻优使 生八卦”之说,其所表达的哲学理念是相反相成是事物发生、算法陷人局部优化而导致早熟收敛,从种群(大小为NP)中选 发展、演化的规律和根源。从这些对立又互补的哲学理念及自取20%的个体,利用般反向学习策略GOBL求得对应的反 然事物所表现出来的各种相反相成的规律性获得灵感 向解,然后将原有种群和所有反向解合并,依据适应度值从低 Tizhoosh等人于205年首次提出反向学习的概念( oppositon-到高排序,选取前NP个作为下一代种群。 HDEOO算法的具 based learning, OBL)212),并证明了与随机产生的近似解相比休步骤如下 较,反向候选解能以更大的慨率接近全局最优解。 Tizhoosh等 )初始化参数(包括缩放因子F交叉概率CR、种群规模 人的研究成果推动了反向学习策略在优化问题上的应用。反MP以及正交表l2(34),设置代数G=0,产生搜索空间内的 向学习相关定义如下: NVP个个体构成初始种群P0。 定义1令P=(x1,x2…,xD)为D维空间中的一个点,其 b)对种群P进行评价,FES=NP。 中x2∈[,b],且i=1,2,…,D,则点P的反向点定义为P= c)判断结東条件是否满足。若满足,转步骤p);否则,转 ),其中 步骤d) 定义2令P=(x1,x2…,x)是D维空间中的一个点(候 d)随机产生[1,NP内的一个整数K 选解),P=(1,2,…,)是其反向点,f(·)是德量侯莲解优 )设置变量i=1 劣的适应度函数。如果f(P)≥f(P),那么用点P来代替点P; f)判断i==K是合满足。若满足转步骤g);则转步骤j 否则继续使用点P。通过同时评价点P和反向点P的适应度, g)对个体P,c进行变异产生个体Vc; 得到相对优秀的候选解。 h)对Pc和Vc按照正交表L(3)进行正交交义操作, 2.22一般反向学习 生9个实验个体 在反向学习理论的基础之上,王晖等人为进一步提高优化 i)评价这9个个体,并选择最优个体作为P.c的后代个体 算法找到最优解的概率,提出一般反向学习( generalized OBI,U,,同时FES=FES+9,转步骤k)。 GOBI)的概念。一般反向学习理论具体描述如下: j)直接对P进行变异和二项式交叉操作产生后代个体 设x是当前空间s上的个解,x∈[a,b]。则对应反向空U,6,评价U,同时FES=FES+1,转步骤k)。 间上x的反向解x定义为 k)判断,若i=-NP,转步骤c);否则i-i+1,转步骤f); 其中是一个可计算值,根物式(7)可第,== 1)选择,判断若f(Uc)<f(P,c),使 U/;c;则 GIIiG, 使△=k(a+b),其中k为实数,则GOBL的定义为 选取种群Pc中20%的个体,依据式(7)(其中参数k 将GOBL理论,一般化到D维空间上如式(9)所示 取值为[0,1之间的随机数),求其反向个体P(P大小为 NP×0.2) 第6期 董小刚,等:求解大规模优化问题的正交反向泥合差分进化算法 1659 n)评价P,同时FES=FES+NPx0.2 续表2 o)P∪P,,并依据适应度值,选取前N个重新作为n算法最好值 最差值 方 Pc+1。转步骤c) 0.00e+0005.00e+0004.40e+000-1.05e+00l p)输出最优解,结束算法 DE 2.74e+0041.33e+004 fa OXDE3.36e+0036.80e+0035.09e+003-8.69e+002 HDEO00.00e+0000.00e+0000.00e+0000.00e+000 3实验与分析 CODE3.83e-0015.65e-0014.88e-0014.82e-002 后DE 31e+000 52e+0023.84e+001 3.49e+001 3.1测试函数 OXDE2.42e+0004.75e+0003.35e+000-6.l7e-00l 本文实验选择∫11个广泛使用的标准测试函数,进行 HDEOO3.31e-0065.46e-0052.88e-0051.22e-005 仿真,函数维度取1000。这11个函数的特点各不相同,其中 2.88e+005-2.70e+005-2.78e+005-4.l8e+003 D4.19c+0054.l8c+0054.19c+0052.02c+002 ∫1灬是单峰函数,6~f1是多峰两数。各两数特征揹述如表1 DF-4.19e+0054.17e+005-4.18e+005≈5.37e+002 所示。 OXOPDE-4.19c+0054.16c+0054.l8c10056.02c+002 表1测试函数 Code 2 3e+0032.4le+003-1.63e+002 iDL4.618e-0112.39e+0017.26e+000-7.18e+00 类凼数 名称 最优解 OXDE3.49e+0025,64e+0024.27e+00 4.63e+001 Sphere Model [-100,100] LIDEOC0.00e+0000.00e+00 0.00e+0000.00e+000 f? Schwefel s 1.2 [-100,100 000 CoDE1.9c+0002.68e+0002.24e+000-1.79e-001 单峰3 Rosenbrock -30,30 007.56e+0C 8.33e-00 f a -100.100 006.80e+0006.36c+000-2.23e-001 HDFO8.88e-0164.44e-0154.09e-0151.08e-015 fs Quartic WiLh Nuist 1.28,1,28 0 CDE6,6e-0165.47e-0013.87e-002 66 Schwefel's 2.26 -50.500 418.98 1.25-010 4.03e+0001.32e+000-1.l8e+000 [-5.12,5 0 OXDE1.73e-001 73e+0007.48e-001 多峰 Ackley -32 HDEOC0.00e+0000.O0e+0000.00e+000.00e+000 [-600,60] CODE7.47e-0133.75e-0027.80e-003≈1.0le-002 -50,50] D2.39e-0106.12c+0067.46e+005-1.42e+006 0XDE6.95e-0012.27e+0001.48e+000-4.l4e-001 /1 Penalized 2 [-50,50] 0 HDEO02.93e-005 80e-0036.22e-0041.le-003 3.2实验设置和结果 7.47c-0l33.75c023.13c-00l+9.04c-00l 为充分验证 HDEOO算法的性能,分别进行了两组实验。 fil DE 9.47e+006 OXDE6.36c+OO21.22c+0039.(8c+0021.28c+002 实验1将HDEO0算法与三种经典的DE算法(DE, HDFO05.40e-0013.74e+0002.00e+0008.9le-001 oDE,OXDE)进行比较,该实验中所有四种算法的种群规模设 表3Col、jDE、OXDE与HDLO0的 Wilcoxon检验结果统计 置为MP=100,OXDE和本文算法 HDEOO的缩放因子和交义 北较 CoDE OXDE 概率设置为F=0.9,CR=0.9,其他两种算法采用算法原有设 10 詈。算法结束条件均设置为D×10000次评价。各算法对每 个问题独立执行30次,记录最差解、最优解、均值和方差。实 0 验结果见表2。为使仿真结果更加公平客观,采用 MATLAB所 1 提供的 Wilcoxon秩和检验方法进行统计分析,显著水平值取 0.05,在表2中均值之后分别用“+”“-”“≈”表示优、劣和相 日 似(与HDOO比较)。检验结果的统计数据见表3。图2~6 给出了四种算法30次运行的平均收敛曲线图,为节省篇幅,仅 诜取五个问题绘制收敛曲线图。将四种算法对11个问题的求 -100 解均值进行 Friedman检验排名,检验结果如表4所示 表2CDF、jDF、OXDF及0XOP结果比较和 WilCoxon检验结果 fun算法 最好值 最差值 均值 方差 CoDE.43e-0l64.7le-0149.62e-0l5-1.03e-0 函数评价次数 jDE1.26c-0351.27c-0195.45c-0212.37c-020 图2HDEO0、Co、jDE、OXD匹种算法收敛曲线图 1.1le+0001.5e+0022.8le+001-4.46e+001 IDEO00.00e+0000.00e+0000.00e+0000.00e+000 e- HDE0o CoDE1.97e+0043.72e+0042.8e+0044.09e+003 DE 4.40e+008.80e+004 2 OXDE4.54e+0057.8le+0055.83e+005 英 HDEO00.O0e+0000.00e+0000.00e+0000.00e+00 CoDE1.47e+0032.36e+0031.85e+003-1.95e+002 。。含是 DE 1.54c+0031.97c+0031.76c+003 l8c+02 212346;810 0XDE3.28e+0038.43e+0035.06e+003-1.12e+003 函数评价次数 HDEOC9.13e+0029.57e+0029.21e+0027.85t+000 图3 HDEOO、CoDE、jDE、OXDE匹种算法/收敛曲线图 1660 计算机应用研究 笃33卷 f√foJ1六个问题的结果来看,对多峰问题的求解, HDEOO算 法总体优于其他三和算法,在fff和f四个问题上优势较 -C IDE 大。在问题f6上, HDEOO算法和OXDE算法均收敛于最优 解,性能相当,jDE算法结果稍弱,CODE结果最差。在问题f 上, HDEOO算法所得结果的均值略差于CoDE算法,但强于其 他两种算法。以上结果表明,HDE0O算法在多峰问题的求解 上总休优于其他三种算法。从表3的 Wilcoxon检验统计来看 4 函数评价次数 在所有优化问题上, HDEOO算法9个优于CoDE、10个优于 图4 HDEOO、CoDE、jDE、OXDE四种算法/s收敛曲线图 jDE和OXDE,只有一个问题上差于CoDE算法。图2~6的收 敛曲线图表明,对于单峰问题, HDEOO算法收敛能力显著增 -O-HCEDO OXDc ¥co 强。对多峰问题, HDEOO算法虽然没有收敛于最优解,但多数 问题的收敛能力均强于其他三种算法,只是f1在进化后期弱 于CoD算法。表4的 Friedman检验排名结果,HD上OO算法 的值最小,排名第一,说明在叫种算法中,HDEO算法的优化 09° 性能整体优于OoDE、jDE、OXDE一种算法。综上所述.实验I 的结果,表明 HDEOO算汏在对大规模优化问题的求解上精度 函数评价次数 好,牧敛快,整体优于其他三种知名DE算法 图5HDEO0、CoDE、jDE、OXDE匹种算法fo收敛曲线图 表5 DECCG、 HDEOO结果比较和 WilCoxon检验结果 算法 最优值 10 DECCG4.45c-0291.58c-0289.61E-029 2.lle-029 HDFO00.00e+000.00e+0 00e+0000.00e+000 1DC2.25e-0042.80e-0031.20E-003-6.70-004 HDFO00.00e+0000.00e+0000.00e+0000.00e+000 S, DECCG 9.87e+0029.86E+002-4.lle-00l DECCG0.00e+0000.00e+ 0.00e+000≈0.00e+000 f4 HDEO00.00e+0000.00e+ 0.00e+0000.00e+000 函数评价次数 图6 HDEOO、CoDE、jDE、OXDE匹种算法/1收敛曲线图 万DECG1.50e-0033.70e-0032.2e-003-6.68e-004 HDEO03.92e-0061.06e-0075.25e-0052.7le-005 表4CoDE、jDE、OXDE、 HDEOO四种算法 Friedman检验排名 DECCG-4.19e+0054.19e+005-4.19:+005+9.28e-011 HDEO0-4.18e+005 4.15e+005 4.17e+0055.59e+002 算法 HDEOO CoDE jDE OXDE 排名 2.45 3.32 DEC.0.0+03.5-0141.25-014-149-05 HDEO00.00e+000 实验2将 HDEOO算法和基于协同框架的知名算法11-013139-0312013-11-05 DECCG进行比较,该实验中两种算法的种群设置均为NP 100, HDEOO算法的缩放因子和交叉概率设置为F=0.9,CR 人 DECCG6.66e-016 33e-0159.50e-016-1.44e-0l6 HDEO00.00e+0000.00e+0000.00e+0000.00e+000 0.9, DECCG算法的其他参数采用其原有设置,两种算法的结 DECCG6.20e-0281.95e-0271.24e-027+3.30e-028 束条件均设置为D×5000次评价。两种算法对每个问题独立 HDEO07.59e-0046.80e-003 执行25次,记录最差解、最优解、均值和方差。具体实验结果 ECCG5.27e-0241.l0e-0022.64e-003 如表5所示。同样,采用0.05显著水平的 Wilcoxon检验方法 HDEOU4.10c+0X3.78c+0018.50e+0006.48c+000 对实验结果进行了检验,表5中“+”“-”“≈”三种符号与实 表6 DECCG与HDEO0的 Wilcoxon检验结果统计 验一种所表示含义相同,表6对检验进行∫统计,图7~11给 比较 DECCG 出了两种算法对五个问题的25次平均收敛曲线图(为与原 DECCG算法保持·致,收敛图横轴坐标为进化代数)。 3.3结果分析 表2的实验结果表明 TIDEOO算法所取得的结果多数优 于 CODE JDE和OXDE一种算法。f√23JJ五个问题的数 据结果表明,在单峰优化问题上, HDEOO算法的求解性能全面 优于其他三种算法。尤其是f√24三个问题 HDEOO算法迅 速收敛于问题的最优解,而CoDE、jDE、OXDE均未能求得最优 解,且岀现了不同程度的进化停滞, HDEOO算法优势非常明 显。在和f两个问题上, HDEOO算法虽没有取得最优解 1.522.5 但其所获得的最优解、最差解及均值郤优于其他三种算法,且 进化代数 104 方差值明显较小,说明 HDEOO算法稳定性较好。从f6√ 图7 HDEOO、DECG两种算法方收敛曲线图 第6期 董小刚,等:求解大规模优化问题的正交反向泥合差分进化算法 1661 HDEOO算法取得的结果7优、3劣、1相当,因此总体上优于 DECCG算法。 s-100 4结束语 针对大规模优化问题,提出了一种新的正交反向混合差 分进化算法 HIDEOO, HDEOO算法充分结合了正交交叉和反 向学习两种策略的优势,使得其能在整个进化过程中既能保 1.5 3.5 进化代数 持较强的局部寻优能力,乂能及时对种群进行调节,有效所 图8 HDEOO、DCCG两朴算法收敛世线图 止了进化停滞。实验结果和统计分析表明HDEO0算法在对 大规模优化问题的求解上收敛精度高,收敛速率快,是种 有效求解大规模优化问题的方法。后期,将尝试把 HDEOO 算法以异构优化器的方式嵌入到协同进化框架中,进一步提 升其优化能力。 参考文献: [1 Storn R, Price K. Differential evolution: a simple and efficient heuris tie for global optimization over continuous spaces J]. Global Optimi- 0.5 5 3.54 zation,1997,11(4):341-359 讲化代数 L2 Tang K, Yao X, Suganthan P N, et aL. Benchmark functions for th 图9HDEO0、 DECCG两科算法收敛曲线图 CEC2008 special session and competition on large scale global opti c ation[ R- Hefei: Nalure Inspired Compul ation and Applicat ions Laboratory, USTC, 2007 [3 Brest J, Greiner S, Boskovic B, et al. Self-adapting control parame ters in differential evolution: a comparative study on numerical bench mark problems[ J]. IEEE Trans on Evolutionary Computation [4 Wang Yong, Cai Zixing, Zhang Qingfu. Differential evolution with mposite trial vector generation strategies and control parameters[J] 1.5 3.54 进化代数 x10 IEEE Trans on Evolutionary Computation, 2011, 15(1) 图10 IIDEOO、 DECCG两种算法收敛曲线图 [5 Wang Yong, Cai Zixing, Zhang Qingfu. Enhancing the search ability of differential evolution through orthogonal crossover [J J tion sciences,2012,18(1):153-177 [6 Yang Zhenyu, Tany Ke, YHo Xin. I arye scale evolut unary optinnizH- tion using cooperative coevolution [J. Information Sciences 42024 2008,178(15):2986-2999 「7吴浩扬,常炳国,未长纯.遗传算法的一种特例——正交试验设计 法[J].软件学报,2001,12(1):148-153 5 52 2.5 [8 Leung Y W, Wang Yuping. An orthogonal genetic algorithm with 进化代数 ×103 quantization for global numerical optimization[ J]. IEEE Trans on 图11 HDEOO、 DECCG两种算法f1收敛曲线图 Evolutionary Computation, 2001, 5(1): 41-53 比较表5的实验结果, HDEOO算法在五个单峰问题上的[9 Rahnamayan S, Tizhoosh h r, Salama mm a. Opposition based dif- 表现依然明显胜出,其中对f1√2个问题, HDEOO算法 ferential evolution algorithms[ C]//Proc of IEEE Congress on Evolu- 均最终收敛于全局最优解,而 DECCG算法,只在f上收敛于 tionary Computation. 2006: 2010-2017 全局最优。在f5问题上, HDEOO算法的结果均值比 DECCG L10」 Rahnamayan S, Tizhoosh iir, Salama mm a. Opposition based dif- 高出两个数量级,其中最优解和最差解优势更大,且方差进 ferential evolution for optimization of noisy problems [c]/ 步缩小,说明 HDEOO算法优势显著。然而,问题f的两种 IEEE Congress on Evolutionary Computation. 2006: 1865-1872 算法所取得结果接近,说明两种方法对该问题的求解性能相 [11 Wang Hui, Wu Zhijian, Rahnamayan S Enhanced opposition-based difFerential evolution for solving 似。在另外的六个多峰问题上, HDEOO算法在、三个 high-climensional continIous pplinniza tion problems J 1. Soft Computing, 2011, 15(11) 2127-2140 问题上胜出,且优势比较明显;在f、f0、1三个问题上[12]向万里,马寿峰,一种高效率收敛的反向差分进化算法[J小型 HDEOO算法的表现差于 DECCG。对f6问题, HDEOO算法的 微型计算机系统,2014,35(2):343-347 结果在均值上相差不大,主要是稳定性上弱于 DECCG U对13] Yan xin, Liu Yong,IinG; langming. Evolutionary porgramming made o1两个问题 HDEOO算法明显弱于DECG算法。表6的 faster[ J]. IEEE Trans on Evolutionary Computation, 1991, 3 Wilcoxon检验数据的统计结果显示出,在所有11个问题上 (2):82-102

...展开详情
试读 6P 论文研究-求解大规模优化问题的正交反向混合差分进化算法.pdf
img

关注 私信 TA的资源

上传资源赚积分,得勋章
    最新推荐
    论文研究-求解大规模优化问题的正交反向混合差分进化算法.pdf 6积分/C币 立即下载
    1/6
    论文研究-求解大规模优化问题的正交反向混合差分进化算法.pdf第1页
    论文研究-求解大规模优化问题的正交反向混合差分进化算法.pdf第2页

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

    6积分/C币 立即下载 >