基于单纯形局部搜索的自适应差分进化算法

收稿日期:2013 － 02 － 18 基金项目:国家自然科学基金项目(11161001) ;商洛学院科研基金项目(11SKY002) 作者简介:李会荣(1979 －) ，男，陕西洛南人，商洛学院数学与计算科学系讲师，硕士． 第 31 卷 第 2 期 海 南 大 学 学 报 自 然 科 学 版 Vol． 31 No． 2 2013 年 6 月 NATURAL SCIENCE JOURNAL OF HAINAN UNIVERSITY Jun. 2013 文章编号:1004 － 1729(2013)02 － 0143 － 06 基于单纯形局部搜索的自适应差分进化算法 李会荣 (商洛学院 数学与计算科学系，陕西 商洛 726000) 摘 要:针对 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 的差分进化(DE)算法在高维复杂的函数优化中易早熟收敛，进而导致搜索精度低甚至优 化失败的问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 ，提出一种基于单纯形局部搜索的自适应的差分进化算法(SSADE)．将 DE算法的快速全局搜 索能力与单纯形的强局部寻优能力有机结合起来，进一步提高了解的精度．参数自适应变化有效地维持了种 群的多样性，自适应的变异策略扩大了个体的搜索范围，增强了算法寻优效果，仿真实验验证了新混合算法 的有效性 . 关键词:差分进化;单纯形局部搜索;自适应变异 中图分类号:TP 301. 6 文献 标志 禁止坐卧标志下载饮用水保护区标志下载桥隧标志图下载上坡路安全标志下载地理标志专用标志下载 码:A 现实中很多实际优化问题(如模糊系统结构和参数优化、神经元的结构等)常存在多个最优解或者一 个最优解和多个局部最优解，如何构造一种能够快速有效地求出全局最优解的智能算法，已成为智能计 算领域的一个重要研究方向 . 目前，已经提出了多种混合智能优化算法，如协同多群体遗传算法［1］、多种 群进化策略［2］、融合 Powell搜索法的粒子群优化算法［3］等，这些算法取得了一定的效果，但也存在着求解 精度不高等问题 . 差分进化(DE)算法［4］是由 STORN R和 PRICE K等人于 1995 年提出的一种基于群体智能理论的随 机搜索的优化算法 . 由于 DE 算法原理简单、参数少、收敛速度快等优点，目前已在滤波器设计、聚类分 析、图像分割、函数优化，以及其他科学工程等方面取得了广泛应用［5 － 6］. 由于差分进化算法与其他智能 优化算法一样，容易陷入局部最优，从而出现早熟收敛现象 . 为此，许多学者对 DE 算法提出各种不同的 改进，例如 GONG Wen-yin［7］利用正交设计的方法加速 DE算法的收敛速度;BREST J［8］提出了利用种群的 减少和 3 种策略的自适应差分进化算法;HRSTKA［9］等人将遗传算法的设计思想引入 DE 算法，使得部分 染色体通过 DE算法的变异操作产生，同时利用二进制竞争选择策略选择下一代;贾东立［10］等提出一种 基于混沌和高斯局部优化的混合差分进化算法等，虽然这些改进算法都在一定程度上提高了 DE 算法的 寻优性能，但都存在收敛速度慢、运行时间过长等缺点 . 本文融合 DE 算法和单纯形搜索法的各自优点， 提出了一种基于单纯形局部搜索的自适应的差分进化算法(SSADE). 将 DE 算法的快速全局搜索能力与 单纯形搜索法的强局部寻优能力结合起来，在保证求解速度的同时提高了解的精度 . 最后仿真实验验证 了新算法的有效性 . 1 标准差分进化算法 1． 1 变异算子 对于一个最小化问题 min f(x) ，x ［xl，xu］，假设种群的规模为 N，空间的维数为 D，在搜 索空间中随机产生 N个初始种群 xi =(xi1，xi2，…，xiD) ，i = 1，2，…，N. 在变异操作中，任一随机矢量v t i 根 据下式产生 vti = x t r1 + F(x t r2 － x t r3) ， (1) 其中，r1，r2，r3 {1，2，…，N}为各不相同的整数且与 i也不相同，F ［0，1］为缩放比例因子，t为当前代迭 代次数 . 在本文中如果vti 的某一分量跳出搜索边界，则取边界值，即 vtid = xud，v t id ＞ x u d xld，v t id ＞ x{ ld . (2) 1． 2 交叉算子 在交叉操作中，新种群试验向量uti =(u t i1，u t i2，…，u t iD)由随机矢量v t i =(v t i1，v t i2，…，v t iD)和 目标矢量xti =(x t i1，x t i2，…，x t iD)共同产生． utij = vtij，如果 rand(0，1)≤CR或 j = jrand xtij，{ 其他 ， (3) 其中，CR ［0，1］是交叉概率． rand(0，1)是 0 与 1 之间的随机数，jrand是集合{1，2，…，D}的一个均匀分布 的随机整数，它确保uti 能从变异个体v t i 中得到至少一个分量 . 1． 3 选择算子 为了决定试验向量uti 是否会进化到下一代，DE算法按照贪婪的选择方式，在试验向量u t i 与原种群的目标向量xti 之间进行比较，目标函数值较优的个体将进入下一代，即表示如下 xt + 1i = uti f(u t i)≤f(x t i) xti f(u t i)＞ f(x t i { )， (4) 其中，xt + 1i 为下一代的第 i个个体，f(x t i)表示个体x t i 的适应值 . 2 基于单纯形局部搜素的自适应差分进化算法 2． 1 单纯形搜索法 单纯形搜索法［11］是一个为无约束最优化问题设计的不需要导数的非线性直接局部 搜索方法，不需要计算导数而只利用函数值，通过构造单纯形来逼近极小点 . 每构造一个单纯形，确定其 最高点和最低点，然后通过反射、扩展、压缩等方法构造新的单纯形，目的是使得极小点能够包含于单纯 形内 . 利用单纯性搜索法求解无约束优化问题 min f(x) ，x ［xl，xu］的步骤(算法 1)如下 Step 1 选取初始单纯形{x0，x1，…，xn}，xi Rn，i = 0，1，…，n，反射系数 α ＞ 0，紧缩系数 θ (0，1) ， 扩展系数 γ ＞ 1，收缩系数 β (0，1)以及精度 ε ＞ 0，置 k = 0; Step 2 将单纯形的 n + 1 个顶点按目标函数值的大小排序，使得 f(x0)≤f(x1)≤…≤f(xn － 1)≤f(xn) ; Step 3 令 xn+1 = 1n∑ n－1 j = 0 xj，若{ 1n + 1∑ n j = 0 ［f(xj)－ f(xn+1) ］2}1 /2 ≤ ε，则停止迭代输出 x0，否则转 Step4; Step 4 计算 xn + 2 = xn + 1 + α(xn + 1 － xn) ，若 f(xn + 2)＜ f(x0)转 Step5，否则当 f(xn + 2)＜ f(xn － 1)时转 Step6，当 f(xn + 2)≥f(xn － 1)转 Step7; Step 5 计算 xn + 3 = xn + 1 + γ(xn + 2 － xn + 1) ，若 f(xn + 3)＜ f(x0) ，令 xn = xn + 3转 Step2，否则转 Step6; Step 6 令 xn = xn + 2转 Step2; Step 7 令 xn ={xi | f(xi)= min{f(xn) ，f(xn + 2) }}，计算 xn + 4 = xn + 1 + β(xn － xn + 1) ，若 f(xn + 4)＜ f(xn) ，令 xn = xn + 4转 Step2，否则转 Step8; Step 8 令 xj = x0 + θ(xj － x0) ，j = 0，1，…，n转 Step2. 2． 2 参数的自适应调整 在标准的 DE算法中，缩放比例因子 F、交叉概率 CR和种群规模 NP 这 3 个参 数需要人为指定，一般来说 F ［0. 5，1］，CR ［0. 8，1］，NP = 10D 被认为是一种较为良好的参数选取范 围［12］. 然而在实际问题的求解中，应该根据算法的迭代周期按照一定的概率自适应的加以调整，以便于 扩大个体的搜索范围，为此笔者对第 i个个体的缩放比例因子 F 和交叉概率 CR 根据历史经验在 t + 1 代 的按照一定的概率随机变化如下 Ft + 1i = Fl + rand1·(Fu － Fl) 如果 rand2 ＜ 0. 2 Fti{ 其他 ， (5) 441 海 南 大 学 学 报 自 然 科 学 版 2013 年 CRt + 1i = CRl + rand3·(CRu － CRl) 如果 rand4 ＜ 0. 2 CRti{ 其他 ， (6) 其中，randi(i = 1，2，3，4)分别为［0，1］中服从均匀分布的随机数，Fu，CRu 和 Fl，CRl 分别为 F 和 CR 的上 界与下界 . 2． 3 自适应的变异策略 DE算法与其他智能优化算法一样，种群中的个体都会出现早熟收敛现象 . 为 了定量描述种群进化状态，引入群体适应度方差如下 . 定义 1［10］ 设 n为种群的规模，第 i个个体的适应度为 f(i) ，种群目前的平均适应度为 favg，群体适 应度方差为 δ2，则 δ2 = 1n∑ n i = 1 ( f(i)－ favg f ) 2， (7) 其中，f是归一化定标因子，其作用是限制 δ2 的大小． f的取值如下 f = max{1，max{| f(i)－ favg |}}，i ［1，n］. (8) 群体适应度方差 δ2 反映的是种群中所有个体的“聚集”或发散的程度，δ2 越小，则种群的“聚集”程 度就越大，“聚集”将使群体多样性就越来越小，从而陷入早熟收敛，所以当 δ2≤Pm(Pm 为一给定常数，称 为变异概率)时，在第 t代种群进化过程中随机选择 10%的个体按照下式进行随机变异 xij = xij + rand(0，1)·(xgj － xij) ， (9) 其中，rand(0，1)为［0，1］中服从均匀分布的随机数，xij与 xgj分别表示第 i个个体和当前全局最优个体的第 j个分量 . 2． 4 SSADE算法的实现步骤 Step 1 设置种群的规模 N，收缩因子 F，收缩因子的上下界 Fu，Fl，交叉概率 CR，交叉概率上下界 CRu，CRl，最大迭代次数 T，设置当前迭代代数 t = 1; Step 2 初始化种群，并计算每个个体的适应度，记最优个体为 xg; Step 3 按照式(1)～(3)对种群进行变异、交叉和选择，分别生成xti，u t i，x t + 1 i ; Step 4 重新计算种群中每个个体的适应度，更新最优个体 xg; Step 5 按照式(5)和(6)自适应调整收缩因子 F与交叉概率 CR; Step 6 按照式(7)计算群体适应度方差 δ2，并按式(9)进行随机变异; Step 7 当迭代次数为 10 的倍数时，以当前的最优个体 xg 为初始点，进行单纯形搜索，并更新最有 个体 xg; Step 8 置 t = t + 1，返回到 Step3，直止达到设定的最大迭代次数 T停止，输出全局最优值． 3 数值试验 3． 1 测试函数 为了验证算法的有效性，笔者利用标准的测试函数进行数值试验，测试函数如下 . 1)Sphere function f1(x)= ∑ n i = 1 x2i，| xi |≤ 100; 2)Schwefel’s Problem 2． 2 f2(x)= ∑ n i = 1 | xi | +∏ n i = 1 | xi |，| xi |≤ 10; 3)Generalized Rastrigin’s function f3(x)= ∑ n i = 1 (x2i － 10 cos (2πxi)+ 10) ，| xi |≤ 5. 12; 4)Generalized Griewank Function f4(x)= 1 4 000∑ n i = 1 x2i －∏ n i = 1 cos( xi 槡i )+ 1，| xi |≤ 600; 5)Ackley’s Function 541第 2 期 李会荣:基于单纯形局部搜索的自适应差分进化算法 f5(x)= － 20 exp［－ 0. 2 ∑ n i = 1 x2i槡 /n］－ exp(∑ n i = 1 cos(2πxi)/n)+ 20 + e，| xi |≤ 30; 6)Rosenbrock Function f6(x)= ∑ n－1 i = 1 (100(xi+1 － x 2 i) 2 + (xi － 1) 2) ，| xi |≤ 30. 以上测试函数都是高维复杂的最小化问题，且最优值均为 0，其中 f1，f2 为单模态函数，f3，f4，f5 为多峰 函数，在其定义域内存在多个局部极小点，而且局部极小点个数会随着搜索空间的维数的增加按指数递 增 . f6 是一个比较难优化达到单峰函数，它的函数曲面上有一段狭长的区域，具有非凸的病态特征 . 3． 2 实验设置 为了算法性能比较的方便，将基本的差分进化算法记为 DE，将带有单纯形搜索的差分 进化算法记为 SSDE，将基于单纯形搜索的自适应的差分进化算法记为 SSADE. 在性能测试的过程中分为 2 组进行试验，当空间的维数 D = 30，种群的大小为 NP = 100，当空间的维数 D = 50，种群的大小为 NP = 150. 在 DE与 SSDE中 F = 0. 5，CR = 0. 8，在 SSADE中，(Fl，Fu)=(0. 5，0. 9) ，(CRl，CRu)=(0. 6，0. 9) ， 变异概率 Pm = 0. 3，每个测试函数的最大的迭代次数为 3 000． 3． 3 结果分析 每个测试函数独立运行 30 次，所得到的最好的最优值(BOV)、最优值的平均值(MOV) 和最优值的方差(SD)如表 1 所示 . 表 1 DE，SSDE和 SSADE测试结果 (D = 30) f DE BOV MOV SD SSDE BOV MOV SD SSADE BOV MOV SD f1 0． 20e － 31 3． 1e － 29 3． 4e － 31 0． 37e － 33 0． 25e － 32 1． 86e － 33 0． 69e － 111 0． 33e － 108 1． 2e － 108 f2 0． 33e － 15 0． 93e － 15 7． 33e － 16 0． 30e － 15 0． 11e － 14 5． 40e － 16 0． 11e － 56 0． 15e － 55 1． 4e － 56 f3 132． 656 8 157． 902 6 11． 628 5 47． 859 0 81． 354 2 45． 741 5 44． 773 1 68． 983 6 17． 098 6 f4 0 0． 044 2 0． 085 2 0 0 0 0 0 0 f5 0． 44e － 14 0． 59e － 14 1． 79e － 15 0． 44e － 14 0． 69e － 14 1． 65e － 15 0． 44e － 14 0． 44e － 14 0 f6 0． 360 5 1． 484 6 0． 671 6 0． 55e － 8 1． 020 6 1． 113 0 0． 66e － 21 0． 953 3 0． 850 9 表 2 DE，SSDE和 SSADE测试结果 (D = 50) f DE BOV MOV SD SSDE BOV MOV SD SSADE BOV MOV SD f1 0． 50e － 10 0． 24e － 9 1． 50e － 9 0． 52e － 14 0． 30e － 13 2． 29e － 14 0． 38e － 77 0． 12e － 75 1． 19e － 76 f2 0． 11e － 4 0． 55e － 4 3． 18e － 5 0． 52e － 5 0． 54e － 4 2． 57e － 5 0． 17e － 41 0． 11e － 42 7． 62e － 42 f3 311． 447 0 355． 509 9 17． 031 3 107． 606 8 264． 060 8 86． 008 5 106． 460 4 143． 141 0 20． 475 2 f4 0． 74e － 9 0． 31e － 10 3． 06e － 10 0． 96e － 10 0． 28e － 9 1． 41e － 10 0 0． 014 9 0． 019 8 f5 0． 17e － 4 0． 44e － 5 1． 45e － 6 0． 22e － 5 0． 41e － 5 1． 36e － 6 0． 44e － 14 0． 117 5 0． 364 8 f6 36． 053 7 37． 018 3 0． 520 7 0． 13e － 7 1． 203 5 2． 286 2 0． 78e － 18 1． 063 0 1． 793 1 从表 1、表 2 都可以看出，SSDE算法和 SSADE算法 30 次运行的最好的最优值、最优值的平均值和最 优值的方差都优于标准的 DE算法，可见单纯形局部搜索对算法的性能大大提高 . 从最优值的方差来看， SSADE算法的测试结果优于 SSDE算法，方差相对来说比较小，这表明自适应的参数变化和变异策略，有 效地维持了种群的多样性，提高了最优解的精度 . 图 1 为函数 f1，f3，f5，f6 在搜索空间 30 维运行 30 次的平均最优值随着迭代次数的变化曲线图 . 从图 1 可以看出，SSADE算法和 SSDE算法收敛速度都明显地优于 DE 算法，特别是引入自适应参数变化和变 异策略的 SSADE算法能够逃逸局部极值点，在较小的迭代次数内收敛到最优点，寻优性能明显优于 DE 算法和 SSDE算法 . 641 海 南 大 学 学 报 自 然 科 学 版 2013 年 平 均 最 优 值 1 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0 ×10-4 0 500 1 000 1 500 2 000 2 500 3 000 迭代次数 (a) Sphere 平 均 最 优 值 迭代次数 450 400 350 300 250 200 150 100 50 0 500 1 000 1 500 2 000 2 500 3 000 (b) Rastrigin (c) Ackley (d) Rosenbroc 平 均 最 优 值 迭代次数 平 均 最 优 值 迭代次数 3 2.5 2 1.5 1 0.5 0 0 500 1 000 1 500 2 000 2 500 3 000 0 500 1 000 1 500 2 000 2 500 3 000 450 400 350 300 250 200 150 100 50 0 图 1 测试函数的平均最优值随迭代次数的进化曲线 ┅┅DE ……SSDE ———SSADE ┅┅DE ……SSDE ———SSADE ┅┅DE ……SSDE ———SSADE ┅┅DE ……SSDE ———SSADE 4 小 结 本文将 DE算法的快速全局搜索能力与单纯形的强局部寻优能力有机地结合起来，提出了 SSADE 算 法，缩放比例因子和交叉概率根据历史经验自适应调整，有效地维持种群多样性;自适应的变异策略进一 步扩大了个体的搜索范围，增强了算法寻优性能 . 对标准 Benchmark 函数的仿真结果表明，SSADE 算法 收敛速度快、精度高、寻优能力强 . 参考文献: ［1］李敏强，寇纪淞．多模态函数优化的协同多群体遗传算法［J］．自动化学报，2002，28(4) :497 － 504． ［2］王湘中，喻寿益．多模态函数优化的多种群进化策略［J］．控制与决策，2006，21(3) :285 － 288． ［3］吴建辉，章兢，陈红安．融合 Powell搜索法的粒子群优化算法［J］．控制与决策，2012，27(3) :343 － 348． ［4］STORN R，PRICE K． Differential evolution-a simple and efficient heuristic for global optimization over continuous space［J］． Journal of Global Optimization，1997，11(4) :341 － 359． ［5］STORN R． Designing，nonstandard filters with differential evolution［J］． IEEE Signal Processing Magazine，2005，22(1) :103 － 106． ［6］ASLANTAS V，TUNCKANA T. Differential evolution algrithm for segmentation of wound images:proceeding of 2007 symposium on Intelligent Signal Proceesing，Madrid，October 3 － 5，2007［C］.［S. l.］:IEEE Xplore，2007. ［7］GONG Wen-yin，CAI Zhi-hua，JIANG Liang-xiao． Enhancing the performance of differential evolution using orthogonal design method［J］． Applied Mathematics and Computation，2008，206(1) :56 － 59． ［8］BREST J，MAUCEC M S． Self-adaptive differential evolution algorithm using population size reduction and three strategies［J］． Soft Comput，2011，15:2157 － 2174． 741第 2 期 李会荣:基于单纯形局部搜索的自适应差分进化算法 ［9］HRSTKA O，KUCEROVA A． Improvements of real coded genetic algorithms based on differential operators preventing prema- ture convergence［J］． Advances in Engineering Software，2004，35(3) :237 － 246． ［10］贾东立，郑国莘．基于混沌和高斯局部优化的混合差分进化算法［J］．控制与决策，2010，25(6) :899 － 902． ［11］陈宝林．最优化理论与方法［M］．第 2 版．北京:清华大学出版社，2005:343 － 349． ［12］BREST J，GREINER S，BOSˇKOVIC＇ B，et al． Self-adapting control parameters in differential evolution:a comparative study on numerical benchmark problems［J］． IEEE Transactions on Evolution Computation，2006，10(6) :646 － 657． ［13］吕振肃，侯志荣．自适应变异的粒子群优化算法［J］．电子学报，2004，32(3) :416 － 420． Self-adaptive Differential Evolution Algorithm Based on the Simplex Local Search LI Hui-rong (Department of Mathematics and Computer Science，Shangluo University，Shangluo 726000，China) Abstract:In the report，self-adaptive differential evolution algorithm based on the simplex search (SSADE)was proposed to solve the premature convergence and low precision of standard differential evolution (DE)applied for the optimization of high-dimensional complex function． The SSADE hybrid algorithm organically integrated DE algorithm which has powerful global search capability with the simplex search method which has strong local search ability，and which further improved the precision of solution． The parameter self-adaptive adjustment maintained the diversity of the population，the self-adaptive mutation strategy expanded the search range of the individual，enhanced the effect of the algorithm optimization． The simulation results confirmed the effectiveness of the new hybrid algorithm． Key words:differential evolution;simplex local search;self-adaptive mutation (上接第 142 页) ［4］POLIKAR Robi． The engineer’s ultimate guide to wavelet analysis［J］． Hosted by Rowan University，College of Engineering Web Servers，2001，12(1) :323 － 328． ［5］DONOHO D L． Denoising via soft thresholding［J］． IEEE Transactions on Information Theory，1995，5 (41) :613 － 627． ［6］TASWELL Carl，COMPUTATIONAL Toolsmiths． What，Hoe，and Why of Wavelet Shrinkage Denoising［J］． Computing in Science ＆ Engineerng，2000，5(2) :12 － 19． ［7］DONOHO D L，JOHNSTONE M Iain． Ideal spatial adaption via wavelet shrinkage［J］． Biometrika，1994，81(3) :425 － 455． ［8］AAPO Hyvarinen ，ERKKI Oja． Independent Component Analysis，Neural Networks［M］． New York :Academic Press，2000． Decomposition of Blind Signal Based on Wavelet Analysis LIN Zhi-yang，BAI Yang，ZHANG Chun-yuan，YI Jia-fu (College of Information Science ＆ Technology，Hainan University，Haikou 570228，China) Abstract:In the report，a new algorithm for blind source separation (BSS)was proposed，which introduce dis- crete wavelet transform into independent component analysis (ICA)algorithm to obtain the useful signal． The ICA algorithm is a linear non-Gaussian statistical method，not only makes the components independent or inde- pendent as possible，but also highlights the nature structure of the source signal． The new BSS algorithm can combine frequency-domain ICA and time-domain ICA，which achieves a better blind source separation． Key words:blind source separation;discrete Wavelet transforms;independent component analysis 841 海 南 大 学 学 报 自 然 科 学 版 2013 年