论文研究-基于邻域引力学习的生物地理学优化算法.pdf

所需积分/C币:5 2019-09-10 22:41:57 575KB .PDF

针对生物地理学优化算法(Biogeography-Based Optimization,BBO)易发生早熟收敛、陷入局部最优的问题,提出一种基于邻域引力学习的生物地理学优化算法(Neighbor Force Learning Biogeography-Based Optimization,NFBBO)。该算法采用邻域选择的方法确定迁出栖息地,以充分利用栖息地的邻域信息,增加算法的种群多样性。同时采用引力学习策略对栖息地进行更新,拓展搜索空间,提高算法的搜索能力,避免早熟收敛问题。为使种群能够自适应地跳出局部最优,引入一种自适应高斯变异机制。基于高维标准测试函数的对比实验表明,NFBBO算法具有
马萍,等:基于邻域引力学习的生物地理学优化算法 2018,54(22)3 反比叫,即: 状态信息,对新解的搜素能力较差,特别是在迭代后期 M1×M2 (4)当种群候选解和最优解较为接近时,隨机变异不仅很难 勘探出较优解,还容易产生很多较差解,造成计算资源 其中,G为万有引力常数;M1和M2分别为两个物体的浪费 的质量;R12为两个物体之间的距离。根据牛顿第二定 基于以上分析,本文提出一种基于邻域引力学习的 律,物体1在物体2的万有引力作用下产生的运动加速迁移算子。在该算子中对满足迁入条件的栖息地采用 度为: 适应度距离比”的方法从其邻域中选择迁出栖息地。 (5 同时,采用引力学习的方式对迁入栖息地进行更新,不 同物种迁移的影响与距离和适应度有关。在此基础上, 从式(4)中可以看出,万有引力定律反应了物体质为了弥补BO算法随机变异策略的不足,引入一种门 量和距离对引力影响的律:在同等距离下,质量人的适应的高斯变异策略咯利用当前种群的信息进行随机扰 物体吸引力更大在质量相等的情况下距离越近的物心动,并根据进化过程调整变异强度,使算法能够自适应 体受到的引力越大。万有引力定律的这一特性,和自然 地跳出局部最优,寻找更优解 界中物种迁移规律有着相同之处,即物种的迁移与栖总31 NFBBO迁移策略 地之间距离的远近和适应度值有关。因此,本文将引力 在 NEBO算法的迁移算子中,对于满足迁入条件 定律应用到BBO算法中,构建新的栖息地吏新策略,提 的柄息地X,计算其与r个邻域粒子的适应度差和距 高算法的搜索能力 离差的比值,选择得到适应度距离比最大的邻域粒子作 为迁出栖息地X: 3生物地理学优化算法 在自然界中,栖息地适应度的提高是通过物种迁移 = arg max 实现的。物种在不同栖息地之间进行迁移时,需要同 时考虑两个因素:栖息地适应度和距离低适应度的栖其中,栖息地X的个邻城是根据适应度值排序之后 息地通过接受高适应度栖息地的物种迁移提高自身的依顺序在X的两边选取/2个栖总地组成。这样迁 质量。物种迁出栖息地的适应度越高,其物种间的兖争入栖息地就可以向其邻域中最邻近且优秀的栖息地学 也就越激烈,导致迁出的物种对环境的适应能力更强,习。在选择出合适的迁出栖息地之后,采用引力学习的 对迁入栖息地的影响更大。同时根据地理学邻近效应策略对迁入栖息地进行更新: 原理,栖息地吏容易受到邻近栖息地的影响。这主要 X?=X+rand×A M(Xk) (7) 是因为物种会选择距离较近的栖息地进行迁移,迁移距 X-XA‖ 离越远物种被猎杀的风险也就越高,距离越近,物种保其中,rn为0,1之间的随机数;M(X)为栖息地X 留得越好"。囚此,在两个迁出栖息地适应度相同的情的质量,计算公式为: 况下,迁移距离近的影晌大。特别地,当栖息地距离较 (X) HSI:-weorst(HSI) 远时,即使是高适应度的迁出栖息地,对迁入栖息地的 besi(hsi)-worsi(HSn 影响也较小。柄总地之间的这种相互关系与引力规律 式(7)中A是空间尺度囚子,随着当前解空间的扩 非常类似因而可以利用引力定律来描述不同物种迁移大或缩小而增减,计算公式为: 对栖息地的影响。 a(u) wd( (9) 原始BBO算法的迁移操作忽略了上述栖息地之间 复杂的迁移关系,通过“轮盘赌"的策略选择迁出牺息其中,x和ⅹ0分别是当前种群的第维解变量的 地,并对满足迁入条件的栖息地通过解变量替换的形式最大值和最小值 进行更新“轮盘赌”策略虽可有效地选取较优的栖息 NFBBO迁移算子的具体步骤如算法1所示。 地作为迁出栖息地,但是该选择方式具有一·定的随机 算法1NFBO迁移算子 性,忽视了栖息地之间距离和适应度对物种迁移的影 1.按照适应度值对栖息地进行排序,并划分邻域 响。解向量替换的更新方式使得迁入栖息地完全被动 2.计算所有粒子的迁入率A和迁出率p 地接收迁出栖息地的信息,导致搜索空间不再产生新的 变量,仅仅是当前所有解变量的组合,栖息地之间迅速 4. For d=1 to ddo 趋于相似,种群多样性降低艹。为了增加算法的种群多 5 Ir rund(O 1)<A, 样性,跳岀局部最优,BBO算法采用随机变异策略对栖 6 按照式(6)从X的r个邻域选择迁出栖息地X 息地进行变异操作。但是这种变异方式忽略了种群的 按照式(7)更新X 38 2018,54(22) Computer Engineering and4 pplications计算机工程与应用 End lf 33 NFBBO算法流程 9. End for 基于邻城引力学小的生物地理学优化算法的流程 10. End l 如图1所示 与BBO算法迁移算子不同, NFBBC算法中采川了 邻域选择策略确定冮出柄息地,允分利用了每个栖息地 开始 邻域粒子的距离和适应度信息,有效避免了“轮盘赌”策 初始化:设定算法的参数1、E、r和mmx, 略大概率选择高适应度栖息地所造成的早熟收敛问题, 随机产生N个栖息地作为初始种群 增加了算法的种群多样性,并且适应度信息的运用保证 ∫算法搜索精度。同时,引力学习的更新策略直接源于 计算每个栖息地的IS并按其 苁高到低对栖息地进行排月 基本的万有引力定律,使得迁入栖息地的改变受物种迁 移距离和适应度的综合影响,产生了新的解变量,拓展 对每个梱息地划分邻域并计算 了解空间;空间尺度因子的引入,可以根据种群的收敛 其迁入率和迁出率 状态调节引力的大小提高了算法的搜索能力 否 32自适应的高斯变异机制 满足迁入条件? 为了使算法跳出局部最优,BBO算法采用了∫随机 采用邻域选择策略确定迁出梄息地 变异策略。但是该变异策略忽略了种群在不同进化过 程中的状态差异,搜索新解的能力较差。为∫使算法 采用引力学习策略对迁入栖息地进行更新 更好地搜索到全局最优解,在迭代初期,应使种祥更大 程度地遍布整个搜索空间,较快地定位最优解的范围 对栖息地进行自适应高斯变异操作 在迭代后期使种群聚集在最优值的邻域范围内,进行吏 精细的搜索 达到迭代条件 基于这一点,本文提出一种自适应的高斯变异机 输出最优值 制。与随机变异不同,高斯变异是在原解的周围产生 个服从高斯分布的随机扰动,公式为 X=X+X 2(0,a (10) 图1 NEBO算法淀程图 式中,asia(0a)是服从均值为0方差为a的高斯分 布随机变量。受文献1启发,文中方差σ随着迭代次4实验结果与分析 数逐渐递减: 41测试函数 (11) 为验证算法的有效性,本文采用10个具有不同特 点的测试函数进行函数优化实验。测试函数的维度D 多是算法的最大迭代次数;是算法的当前均为30,其表达式搜索空间S以及真值如表1所示。 迭代次数。在迭代初期,n值较大高斯变异可以产生其中F1~F2为经典测试函数中的单峰函数,只有 较大的扰动步长,增大算法的搜索范围;而在迭代后期, 个最优值,可以检验算法的收敛特性;F3~F5为经典 σ变小,产生的扰动长较小,主要在当前候选解的局测试函数中的多峰函数,含有多个局部极小值,反映了 部范围进行精细搜索。同时,变异步长的计算利用了柄 算法跳出局部最优,逼近全局最优解的能力;F6~F10 息地x信息,因此,高斯变异机制可以根据不同栖息为CFC201旋转平移测试函数,其全局最优点不再位 地在不同过化过程中的状态自适应地产生变异粒子更于搜索空间的中心,且函数变量之问彼此不相关,用来 加高效地搜索新解,跳出局部最优。 检验算法解决复杂优化问题的能力。 自适应的高斯变异的步骤如算法2所示。 42参数设置 算法2自适应的高斯变异 1.计算所有粒子的变异率n 本文采用基本的BBO算法以及目前改进效果较 好的PBBO算法、DBBO算法和 RCBBO算法作为对 2. For i-1 to n do 3. for d-l to do 比算法。为∫保证对比实验的公平性,所有算法的终止 If m >rund 条件均设置为最大适应度计算数,FEx=5000,种 X:=X:+X!x Gaussian(o, o 群大小为N=50。同时为了发挥各个对比算法最优的 End 性能,算法的其他叁数都按照原文献经过测试后的参数 进行设定。 NFBBO算法中最大迁入率E=1,最大迁出 8. end for 率Ⅰ=1,初始变异率mmx=0.1,邻城大小r=15%×N」 马萍,等:基于邻域引力学习的生物地理学优化算法 2018,54(22)39 表1测试网数 类型两数 函数名称 日标函数 单峰 Sphere Fv 函数 F2 Schwefel s 1.2 function E a(=> 「-1C0,100 F3 Rastrigin function minF(x)=∑42-10c(2x)+1 512512y0 多峰 Ackley function mnF(x)=-20cx-.2 ∑o(2xr)+2-32,3210 函数 Grewal unction min Fs(r) +⊥ L-6C0,6000 F6 Rotated High Conditioned Elliptic Function L-100,100100 Hybrid Function I F()=8(M1a)+g(M2e2)+g(M!s)+F( 旋转平 Composition Function 2 min Fs(r)=2Yo: [. g(a)+bias, 1)+F [-1CO,1001000 移函数 Composition Function 4 minF(2)-2w:A: g()+bias ]j L-1C,1001200 F10 Composition Funetion 6 min F(x)=a, Ag, (x)+bias ]+F [-1C,1031400 对每个优化函数,每个算法独立运行30次,取运行数优化问题时的优越性。同时从表2中各个算法的 结果的平均值Men、标准差Sl、运行时间 runtime“Sia”值可以看出, NFBBO算法具有较好的稳定性。 进行比较。此外,本文采用 Wilcoxon秩和检验法对不除了函数F7和F10, NFBBO算法的标准差在其他8个 同算法进行非参统计检验,置信度a=0.05。非参检验测试函数的结果中都是最小的,且效果突出。 的实验结果由“h”表示,其中“+”表示测试结耒本文算 对于算法的搜索效率和收敛速度可以从实验结果 法显者占优,;“-”表示测试结果其他算法显者占优;表2的 runtime和收敛特性曲线中得出。由表2可知, ”表示測试结果不显著,即本文算法与其他算法所得( NEBO算法的运算时间在所有单峰函数和多峰函数上 的结果无显著性差异 都是最小的,验证了 NEBO高效的运算速度。尤其是 43实验结果及分析 在具有一个局部极值的单峰函数P2上, NEBO的运 实验结果如表2所示,可以看出,NFBO算法在所算速度明显优于其他对比算法。图2给出了5种算法对 有函数上获得的Men值都是最小的,要明显优于其他部分测试函数的收敛特性曲线,图中分别采用了5种不 4种对比算法,允分表现了本文算法在搜索能力和搜索同的线型表示不同的对比算法。从图2中可以看出, 凊度上的优越性。这主要是因为 NFBBO算法迁移操作NFBO算法具有优良的收敛性能。对于经典的单峰和 屮的邻域选择策略充分利用了梄息地的邻城信息,增加多峰函数F1、F2和F5, NFBBO算法在演化的初始阶 ∫种群的多样性;引力学习的更新方式拓展了解空间,段收敛速度就明显快于其他4种对比算法,表现出其优 提高了搜索能力,其中空间因子的侦用还可以调节搜索越的搜索能力,能迅速找到优秀解所在的区域。同时, 的步长,更好地找到全局最优解的范围,并在后期进行在收敛曲线中, NFBBO算法搜索到的最优值也是最小 精细的搜索对于含有多个局部极小值的多峰函数F3的,具有较高的收敛精度。但是对一些复杂的CEC205 和F5, NFBBO算法的优化效果更为显著,是唯一一个测试函数,算法的收敛速度有所变慢。对函数F6,在演 搜索到真值的算法,而其他算法在这两个函数上的优化化初期, NFBBO算法收敛曲线的下降速度要慢于PBBO 效果都较差。这表明 NFBBC使得种群能够有效地跳出和DBBO,但是随着迭代的进行, NFBBC算法的收敛速 局部最优,收敛到全局最优。在处理复杂的CFC2015度明显加快,且达到最好的收敛精度。同样在函数F8 测试函数时,5种算法所得到的平均最优值结果都不太的演化过程中,初期阶段 NFBBO算法收敛速度要慢于 理想这主要是因为旋转平移函数木身比较复杂,函数其他算法,随后曲线下降速度加快,当其他4种对比算 变量之间不相关,且真值不在函数的搜索空间中心处,法的收敛曲线不再变化,陷入局部最优时, NFBBO算法 加大了全局最优解的搜索难度。同时,BBO算法本身的收敛曲线能够继续下降且收敛到了最好的结果。与 不其备旋转不变特性,因此基于BBO改进的策略在以上CEC2015测试函数不同,对F10, NFBBO算法表 CF℃2015函数上效果较差。即便如此,相比较于其他4现出了明显的收敛性能优势,在整个演化过程中, NFBBO 种对比算法,NFBB○算法的处理效果仍然是最优的。算法的收敛速度均是最快的且达到了最好的收敛精 这些实验结果都证明了木文算法在处理不同特点的函度。基于以上分析,可以得出NBBO算法具有较快的 402018,54(22) Computer Engineering and4 pplications计算机工程与应用 表25种算法在不同测试函数上的性能对比 西数性能指标BBO箅法PBBo算法DBBO算法 RCBBO算法NFBO算法 Me4.268E+006.807E-10,6l2E-0l 2.300E-02 6.617E-42 9083F011.271F091 1.480F-41 F runtime/s Inr 14.72 12.42 Mean 8.325E03 80E+022.070E+03 1.148E+04 1442E-10 975E+03 149E+021.129E+03 4.598E+03 3.512E-10 12 timmie/ 03.20 In 55.56 1.700E+006.279E-06 890E+0 1.190E+00 7.185E-011.120E-0 1.604E+004.718E-01 F3 34.56 20.30 480.50 15.81 Mea8.665E-018.921E-063.967E-017.100E-024440E-15 1.967E-016.242E-063905E-01 1.565E-02 F4 11.13 1.019E002945L-024083E-01 1626E10 3.563E023.889E-02 233E01 5826E+00 runlirrie/s 52.78 9.64 Men1.124E+074.984E+066.047E+06 1.198E+07 4.604E+06 4.738E+062458E+003.854E+06 1.185E+07 2.838E+06 Inf Mean 919E+068.500E+05140lE+062857E+06 8.340E+05 Sta 4.007E+055823E+051.858E+06 3.253E+06 46lE+05 Inr 3.112E066.391E+052.736E+06 8.931E+05 5.407E+05 1.531E+062.182E+052.099E+06 886E+05 5.253E+05 runtime/s Inf Inf Inf h Mean 1.091E+021079EH0 l087E+02 1098EH02 1.072E+02 1.28lE+007.850E-011.399E+002077E+00 7754E-01 rennie Inf Inf Mean 3.346E+043.562E+04 318E+04 3.758E+04 1816E+04 1.086L+0 1317LH03 1.100E 103 2.079E+3 1.149E+0 F10 Inf Inf Inf 收敛柬度,在处理复杂的函数问题吋,能够很好地跳出5结束语 局部最优,拓展新的搜索区域,找到更加优秀的解集。 BBO算法具有较快的收敛速度,但其搜索能力较 表2统计了对比算法之间的非参检验结果。从结差,容易发生早熟收敛,陷入局部最优。为了克服这 果中可以看到,除函数κ6、7和F8,其他函数的非参缺点,夲攴提出一种基于邻域引力学习的迁移算了,该 验结果均为¨+”,即与其他对比算法相比, nFBBO算算子采用邻域选择策略确定迁出栖息地,并利用引力学 法具有显著的优越性。对函数F6和F7,NFBO算法的方式对栖息地进行新,增加了种群多样性,提高 要显著优于BBO和 RCBBO,与PBBO、DBBO算法无显了算法的搜索能力。同时引入了自适应高斯变异机制 著性差异。对函数P8,与PBBO算法无显著差异,但是充分利用了当前解的信息,使算法能够自适应地跳出局 要显著优于其他函数。从整个非参检验的结果可以得部最优。从实验结果中可以得出,NFBO算法不仅收 出, NFBBO算法与其他优化算法相比具有显著的优越性。敛速度较其他算法快,而且可以更大程度上逼近全局最 马萍,等:基于邻域引力学习的生物地理学优化算法 2018,54(22) 非影号店是 一一一 10° BBO 10 O DBBO 10 L4 PBBO RCBBO -+-NFBBO RCBBO -BBO ← NFBBO 10 A PBO 10 DBBO NFBBO 10 10 FF/10 FES/10 FEs/10 )F1 (c) 10 BBO DBBO DBBO RCBBO RCBBO -NFBBO NeBO 5d-3日日=号中 - PBO DBBO RCBBO 10° 4 5 0 0 2 TES/10- Fs/10 FEs/10- (d)F6 (e)F8 (f)F10 图2BBO, PBBO DBBO, RCBBO与 NFBBO在部分测试两数上的收敛曲线图 优解,在收敛速度和收敛精度上较标准BBO算法有较 and evaluation criteria for the cec 2015 competition 大提高。 on learning-based real-parameter single objective opti mization(2014)[R]. Computational Intelligence Laboratory 参考文献: Zhengzhou University, Zhengzhou, Nanyang Technologi [1] Simon D Biogeography-based optimization[J].IEEE Trans- cal University, Singapore, 2014 actions on Evolutionary Computation, 2008, 12(6): 702-713 [11] Rashedi e, Nezamabadi-pour H, Saryazdi SGSA: a grav [2]刘林,郑江.改进生物地理学算法求解柔性作业调度问题[J itational search algorithm [J]. Inform Sciences, 2009, 179 计算机工程与应用,2016,52(18):28-234 (13):2232-2248 [3 Wang Z, Wu X Salient object detection using biogeography [12 Zheng Y J, Ling H F, Xue J Y. Ecogeography-based opti based optimization Lo combine features[M]-[.1.]: Kluwer mization: cnhancing biogcography-bascd optimization with Academic publishers. 2016 ccogcographic barriers and differentiations[J]. Computers [4]范会联,曾广朴带自适应迁入的生物地理学优化算法[J Operations Rcscarch, 2014, 50: 115-127. 计算机应用研究,2015,32(12):3642-3645 13]尚玉昌.动物行为研究的新进展(十):栖息地选择[J自 5]毕晓君,王珏,基丁混合迁移策略的生物地理学优化算法[J 然杂志,2014,36(3):182-185 模式识别与人工智能,2012,25(5):768-774 [14]莫愿斌,刘付永,张宇楠带高斯变异的人工萤火虫优化 [6 Boussaid I, Chatterjee A, Siary P, et al.Two-stage update 算法[计算机应用研究,2013,30(1):121-123 biogeography-based optimization using differential evolu- [15] Zhan Z H, Zhang J, Li Y, et al. Adaptive particle swarm tion algorithm( DBBO )[J]. Comput Oper Res, 2011, 38(8) optimization. IEEE TransacTions on SysLeIns, Man and 1188-1198 Cybernetics,2009,39(6):1362-1381 [7] Gong W Y, Cai Z H, Ling C X, et al.A real-coded biogeo- [16] Li X T,Wang J Y, Zhou J P, et al. A perturb biogeo graphy-based optimization with mutation[]. Appl Math graphy based oplimization with mutaTion for global Comput,2010,216(9):2749-2758 numerical optimization[J].Appl Math Comput, 2011, 218 [8]徐志丹,莫宏伟.多目标扰动生物地理学优化算法[]控制 (2):598-609 与决策,2014,29(2):231-235 [17] Derrac J, Garcia S, Molina D, et al. A practical tutorial [9 Yao X, Liu Y, Lin G Evolutionary programming mad on the use of nonparametric statistical tests as a meth faster[.ILEI Transactions on Evolutionary Computation odology for comparing evolutionary and swarm intelli 1999,3(2):82-102 gence algorithms[]. Swarm Evolutionary Computa [10 Liang J, Qu B, Suganthan P, ct al. Problem dcfinition ion,20ll,1(1):3-18

...展开详情
img
  • 至尊王者

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

关注 私信 TA的资源

上传资源赚积分,得勋章
最新资源