差分进化算法研究及其应用

第 9卷 　第 22期 　2009年 11月 167121819 (2009) 2226673204　 科 　学 　技 　术 　与 　工 　程Science Technology and Engineering 　Vol19　No122　Nov. 2009Ζ 　2009　Sci1 Tech1Engng1 差分进化算法研究及其应用 万 　东 (广东交通职业技术学院 ,广州 510650) 摘 　要 　针对一种新兴的进化算法 ———差分进化算法 ,介绍了该算法的基本原理、算法流程和控制参数选择 , 然后利用差分 进化算法求解了多元函数的极值问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 。差分进化算法具有随机选取初始值的优点 ,数值实验结果表明了该 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 的正确性和 有效性。 关键词 　差分进化算法 　　多元函数的极值 　　最小值 中图法分类号 　TP183; 　　　　文献标志码 　A 2009年 8月 18日收到 　　多元函数极值问题是一类经常出现在 工程 路基工程安全技术交底工程项目施工成本控制工程量增项单年度零星工程技术标正投影法基本原理 设 计中的问题。传统的算法大都基于传统的梯度类 算法 ,并依赖于初始点的选取 ,而在一些实际问题 中如何选取合适的初始点本身是一个比较困难的 问题 [ 1—3 ]。此外 ,对一般函数 ,要求出它的次梯度 , 甚至近似梯度都是相当困难 ,所以在不可微规划方 面还有许多工作要做。 近年来 ,随着计算机技术的发展 ,一些群体智 能算法也得到了迅速发展 ,文献 [ 4 ]尝试应用粒子 群算法求解函数极值问题 ,获得较好的数值结果。 Storn R和 Price K于 1995年提出的差分进化 (D if2 ferential Evolution, DE)算法 [ 5—6 ]是一种随机的并行 直接搜索算法 ,它可对非线性不可微连续空间函数 进行最小化 ,以其易用性、稳健性和强大的全局寻 优能力在多个领域取得成功。在 1996年举行的第 一届国际 IEEE进化优化竞赛上 ,对提出的各种方 法进行了现场验证 , DE被证明是最快的进化算法。 目前 , DE已经在许多领域得到了应用 [ 7, 8 ]。 本文首先介绍了 DE的算法原理、算法流程和 控制参数选择 ,然后利用 DE算法求解了多元函数 的极值问题。数值实验结果表明了该方法的正确 性和有效性。实验表明 ,和其它算法相比 ,该算法 在搜索成功率和计算效率上有很大的优势 ,是求解 此类不可微优化问题一种好的计算方法。 1　差分进化算法 差分进化算法 (D ifferential Evolution, DE)是一 种新兴的进化计算技术。它是由 Storn等人于 1995 年提出的 ,最初的设想是用于解决切比雪夫多项式 问题 ,后来发现 DE也是解决复杂优化问题的有效 技术。DE与人工生命 ,特别是进化算法有着极为 特殊的联系。DE和微粒群算法 ( PSO,也称粒子群 算法 )一样 ,都是基于群体智能理论的优化算法 ,通 过群体内个体间的合作与竞争产生的群体智能指 导优化搜索。DE算法通过把种群中两个成员之间 的加权差向量加到第三个成员上来产生新参数向 量 ,该操作称为“变异 ”。然后将变异向量的参数与 另外预先确定的目标向量参数按一定规则混合来 产生试验向量 ,该操作称为“交叉 ”。若试验向量的 代价函数比目标向量的代价函数低 ,试验向量就在 下一代中代替目标向量。最后的操作称为“选择 ”, 种群中所有成员必须被作为目标向量这样操作一 次 ,以便在下一代中出现相同个竞争者。在进化过 程中对每一代都评价最佳参数向量 ,以 记录 混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载 最小化 过程 ,这样利用随机偏差扰动产生新个体的方式可 以获得一个有非常好收敛性的结果。 1. 1　基本 DE算法 1. 1. 1　初始化 DE利用 N P个维数为 D 的实数值参数向量作 为每一代的种群 ,每个个体表示为 : ( i = 1, 2, ⋯, N P) (1) 式 (1)中 : i—个体在种群中的序列 ; G—进化代数 ; N P—种群规模 ,在最小化过程中 N P保持不变。 为了建立优化搜索的初始点 ,种群必须被初始 化。通常寻找初始种群的一个方法是从给定边界 约束内的值中随机选择。在 DE研究中 ,一般假定 对所有随机初始化种群均符合均匀概率分布。设 参数变量的界限为 xLj ≤xj≤xUj ,则 : xji, 0 = rand [ 0, 1 ] ( xUj - xLj ) + xLj , ( i = 1, 2, ⋯, N P; j = 1, 2, ⋯, D ) (2) 式 (2)中 : rand [ 0, 1 ]———在 [ 0, 1 ]之间产生的均匀 随机数。如果预先可以得到问题的初步解 ,初始种 群也可以通过对初步解加入正态分布随机偏差来 产生 ,这样可以提高重建效果。 1. 1. 2　变异 对于每个目标向量 xi, G , i = 1, 2, ⋯, N P,基本 DE算法的变异向量如下产生 : vi, G + 1 = xr1, G + F ( xr2, G - xr3, G ) (3) 式 (3)中 ,随机选择的序号 r1 , r2 和 r3 互不相同 ,且 r1 , r2 和 r3 与目标向量序号 i也应不同。所以须满 足 N P≥4。变异算子 F∈[ 0, 2 ]是一个实常数缩放 因子 ,控制偏差变量的放大作用。 1. 1. 3　交叉 为了增加干扰参数向量的多样性 ,引入交叉操 作。则试验向量变为 : ui, G + 1 = ( u1 i, G + 1 , u2 i, G + 1 , ⋯, uD i, G + 1 ) (4) uji, G + 1 = vji, G + 1 , if ( randb ( j) ≤CR ) or j = rnbr( i) ; xji, G + 1 , else, ( i = 1, 2, ⋯, N P, j = 1, 2, ⋯, D ) (5) 式 (5)中 : randb ( j) —产生 [ 0, 1 ]之间随机数发生器 的第 j个估计值 ; rnbr ( i) ∈1, 2, ⋯, D—个随机选择 的序列 ,用它来确保 ui, G + 1至少从 vi, G + 1获得一个参 数 ; CR—交叉算子 ,取值范围为 [ 0, 1 ]。 1. 1. 4　选择 为决定试验向量 ui, G + 1是否会成为下一代中的 成员 , DE按照贪婪准则将试验向量与当前种群中 的目标向量 xi, G进行比较。如果目标函数要被最小 化 ,那么具有较小目标函数值的向量将在下一代种 群中赢得一席地位。下一代中的所有个体都比当 前种群的对应个体更佳或者至少一样好。注意在 DE选择程序中试验向量只与一个个体相比较 ,而 不是与现有种群中的所有个体相比较。 1. 1. 5　边界条件的处理 在有边界约束的问题中 ,确保产生新个体的参 数值位于问题的可行域中是必要的 ,一个简单方法 是将不符合边界约束的新个体用在可行域中随机 产生的向量代替。即若 uji, G + 1 < xLj 或 uji, G + 1 > xUj , 那么 : uji, G + 1 = rand [ 0, 1 ] ( xUj - xLj ) + xLj , ( i = 1, 2, ⋯, N P; j = 1, 2, ⋯, D ) (6) 另外一个方法是根据式 ( 6 )重新产生试验向 量 ,然后进行交叉操作 ,直到产生的新个体满足边 界约束为止 ,但这样做效率较低。 1. 2　D E算法流程 (1) 确定 DE控制参数和所采用的具体策略 , DE控制参数包括 :种群数量、变异算子、交叉算子、 最大进化代数、终止条件等 ; (2) 随机产生初始种群 ,进化代数 k = l; (3) 对初始种群进行评价 ,即计算初始种群中 每个个体的目标函数值 ; (4) 判断是否达到终止条件或进化代数达到最 大。若是 ,则进化终止 ,将此时的最佳个体作为解 输出 ;若否 ,继续 ; (5) 进行变异和交叉操作 ,对边界条件进行处 理 ,得到临时种群 ; (6) 对临时种群进行评价 ,计算临时种群中每 个个体的目标函数值 ; (7) 进行选择操作 ,得到新种群 ; (8) 进化代数 k = k + 1,转步骤 (4)。 4766 科 　学 　技 　术 　与 　工 　程 9卷 2　多元函数极值问题的求解 下面通过例子来阐明该方法。 算例 1　试确定函数 z = f ( x, y) = ( x2 - 2x) e- x2 - y2 - xy , | x | ≤3, | y | ≤2极值。 解 　首先绘制出该函数的图形 ,这里我们采用 数学软件 Matlab作图 [ 9 ] (见图 1 ( a) )。从图形上我 们明显可以看到存在极值点 ;因此绘制该函数的等 高线 (见图 1 ( b) ) ,即把函数投影到二维空间 ,观察 等高线的走向。 图 1　例 1的函数图形与相应的等高线 从三维图形不能很好的观察出该函数的极值 所在的精确范围 ,但是通过画等高线 ,立刻可以观 察出该函数的 2 个极值分别在 ( - 1, 0. 5 ) 和 (0. 8, - 0. 3)附近. 因此可以在这两个点的附近取 一个初始值 ,然后调用一些优化软件包便可以快速 地达到最优解 ,传统算法在选取初试点的时候必须 这样做。 下面我们采用 DE算法来求解该函数在给定范 围内的最小值 , DE算法的初始点是随机产生的 , DE 算法的选择操作直接将目标函数值作为适应度值 , 然后比较适应度值 ,适应度值小的个体保存到下一 代 (目标函数值为最小值 ) ,而不像遗传算法有各种 复杂的选择策略。与遗传算法相比 ,差异演化算法 操作简单 ,控制参数少 ,易编程实现 ,它尤其擅长求 解多变量、非凸、多峰以及非线性的函数优化问题 , 所以很受研究者的青睐。取群体规模 N P = 60,初始 交叉 CR = 0. 3,初始缩放因子 F = 0. 1,算法终止的 最大进化代数 G = 50, 调用 DE算法 ,运行结果如图 2所示。 图 2　 DE算法求解算例 1的计算结果 由计算结果知 , DE算法能够快速收敛到上述函 数在给定范围内的最优值 (0. 611 05, - 0. 305 52) , 相应的目标值为 - 0. 641 424。 算例 2 　试确定函数 z = f ( x, y ) = 3 ( 1 - x) 2 e- x2 - ( y + 1) 2 - 10 ( 15 x - x 3 - y5 ) e- x2 - y2 - 13 × e - ( x + 1) 2 - y2 ,在给定范围 | x |≤3, | y |≤3内的最小值。 解 　参数设置和算例 1一致 ,调用 DE算法 ,计 算结果如图 3所示。 图 3　DE算法求解算例 2的计算结果 576622期 万 　东 :差分进化算法研究及其应用 　 由计算结果知 , DE算法能够快速收敛到上述 函数在给定范围内的最优值 ( 0. 228 28, - 1. 625 5) ,相应的目标值为 - 6. 551 133。 3　结束语 本文针对多元函数极值问题 ,给出了此类问题 的一种新的有效算法 ———差分进化算法来搜索最 优解。计算结果表明 ,在计算的准确性方面能够得 到和文献 [ 10 ]相当的结果。可见 ,利用差分进化优 化算法求解此类问题 ,可使算法简单直观 ,容易实 现 ,计算成功率高 , 是求解此类问题的一种有效 算法。 参 　考 　文 　献 1　陈宝琳. 最优化理论与算法. 北京 :清华大学出版社 , 1989 2　粟塔山. 最优化计算原理与算法程序 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 . 长沙 :国防科技大学 出版社 , 2001 3　袁亚湘 , 孙文瑜. 最优化理论与方法. 北京 :科学出版社 , 1997 4　赵晓颖 , 刘国志 ,姜凤利. 求解一类不可微优化问题极大熵微粒 群混合算法. 江西师范大学学报 , 2007; 31 (2) : 193—196 5　Storn R, Price K. D ifferential evolution———a simp le and efficient a2 dap tive scheme for global op tim ization over continuous spaces. Berke2 ley: University of California, 2006 6　Lamp inen J. A bibliography of differential evolution algorithm. ht2 tp: / /www. lut. fi /～jlamp ine /debiblio. htm. 2002210214 7　L in Y C, Hwang K S, W ang F S. Co2evolutionary hybrid differential evolution for m ixed2integer op tim ization p roblem s. Engineering Op ti2 m ization, 2001; 33 (6) : 663—682 8　Cheng S, Hwang C. Op timal app roximation of linear system s by a dif2 ferential evolution algorithm. IEEE Trans on System s, Man and Cy2 bernetics: A, 2001; 31 (6) : 698—707 9　王沫然. MATLAB 5. X与科学计算. 北京 :清华大学出版社 , 2000 10　王　凌. 智能优化算法及其应用. 北京 :清华大学出版社 , 2001 Research and Applica tion Ba sed on D ifferen tia l Evolution A lgor ithm WAN Dong (Department of Computer, Guangdong Communication Polytechnic, Guangzhou 510650, P. R. China) [ Abstract] 　A imed at a recently developed evolution algorithm, differential evolution algorithm, the p rincip le, p rocess and parameters of differential evolution algorithm are introduced and analyzed systematically, then differen2 tial evolution algorithm is established for extremum p roblem s of multivariate function. This method has advantage of choosing initial point random ly; the reliability and efficiency of this algorithm are demonstrated by some numerical experiments. [ Key words] 　differential evolution algorithm　　extremum value of multivariate function　　m inimum value 6766 科 　学 　技 　术 　与 　工 　程 9卷