基本差分进化算法.pdf
基本差分进化算法 基本模拟退火算法概述 DE 算法是一种基于群体进化的算法， 其本质是一种基于实数编码的具有保优思 想的贪婪遗传算法。由于DE 算法操作简单，寻优能力强，自提出以来引起了国内 外学者的高度关注，目前已在电力系统优化调度、配网重构等领域得到了应用。 1、算法原理 DE 算法首先在N 维可行解空间随机生成初始种群 P 000 1 , N XxxL，其中 000T 1 , iiiN xxxL， p N 为 DE 种群规模。 DE 算法的核心思想在于采取变异和交叉操 作生成试验种群，然后对试验种群进行适应度评估，再通过贪婪思想的选择机制， 将原种群和试验种群进行一对一比较，择优进入下一代。 基本 DE 算法主要包括变异、交叉和选择三个操作。首先，在种群中随机选取 三个个体，进行变异操作： 1 123 () tttt irrr Fvxxx 其中 1t i v表示变异后得到的种群，t 表示种群代数，F为缩放因子，一般取 (0,2，它 的大小可以决定种群分布情况，使种群在全局范围内进行搜索； 1 t r x 、 2 t r x、 3 t r x为从 种群中随机抽取的三个不同的个体。 然后，将变异种群和原种群进行交叉操作： 1 ,R1 , ,R ( ) or ( ) ( ) and ( ) t i jt i jt i j vrandjCjrandn i u xrandjCjrandn i 其中 t 1 , i j u表示交叉后得到的种群， ( )randj为0,1之间的随机数，j表示个体的第j个 分量， R C 为交叉概率，( )randn i为1,NL之间的随机量，用于保证新个体至少有 一维分量由变异个体贡献。 最后， DE 算法通过贪婪选择模式，从原种群和试验种群中选择适应度更高的 个体进入下一代： 11 t 1 1 ()() ()() ttt iii i ttt iii ff ff uux x xux 1 () t i f u、() t i f x分别为 1t i u和 t i x 的适应度。当试验个体 1t i u的适应度优于 t i x 时， 试验个体取代原个体，反之舍弃试验个体，保留原个体。 2、算法步骤 基本 DE 算法的基本步骤如下： 设定DE算法的种群大小，最大 迭代次数，缩放因子，交叉概率 DE算法变异操作 DE算法交叉操作 进行适应度评估 随机生成初始 DE种群， 置迭代次数 k为0 DE算法选择操作 是否达到最大迭代次数？ k=k+ 1 是 输出结果， 退出程序 否 开始 3、算法的 matlab实现 见程序 4、算法举例 采用 DE 算法求取 Sphere Mode函数 30 2 1 ( ) i i f xx的最小值。 1) 基本测试 在 matlab命令窗口输入： xm,fv = SA(fitness,3,1e-5,0.99,200,30) 得到如下收敛曲线 0100200300400500600700 0 5 10 15 20 25 30 退温次数 目 标 值 2) 参数对算法性能的影响 在 matlab命令窗口输入： xm,fv = DE(fitness,40,0.5,0.5,100,30) xm,fv = DE(fitness,40,0.5,0.5,200,30) xm,fv = DE(fitness,40,0.5,0.5,500,30) 将上面求得的结果列表比较如下： M100200500 x10.033087185-1.29E-021.77E-04 x20.202701957-4.05E-02-1.08E-04 x3-0.0810382459.89E-035.80E-05 x40.028932023-2.05E-027.00E-05 x5-0.1517165436.23E-03-1.66E-04 x60.1543522428.34E-039.47E-05 x70.051436736-1.79E-02-3.01E-04 x80.057500363-5.54E-03-2.23E-04 x9-0.0584096349.74E-034.80E-05 x100.0604356343.02E-02-4.12E-05 x110.005562026-1.64E-021.00E-04 x120.1246797578.56E-032.75E-05 x13-0.217063076-6.15E-032.45E-05 x14-0.156305243-3.49E-03-1.35E-04 x150.1426130784.24E-022.66E-05 x16-0.003189876-5.84E-021.35E-04 x17-0.1523396675.51E-02-4.93E-05 x18-0.229525992-1.10E-022.51E-04 x190.0765024931.47E-021.50E-04 x200.0495980381.11E-02-4.13E-05 x210.1232358086.87E-028.12E-05 x220.183832078-1.80E-02-3.78E-05 x23-0.1118162291.32E-03-2.59E-04 x240.232072926-2.25E-02-9.06E-05 x250.0435850572.47E-02-6.93E-05 x26-0.235073466-1.73E-032.36E-04 x27-0.0084282012.95E-02-2.37E-04 x28-0.0751637592.49E-02-7.77E-05 x29-0.099728761-1.92E-02-6.94E-05 x300.1434230272.06E-021.28E-04 f(x)0.5098581292.13E-025.98E-07 可见达到一定迭代次数后，DE 算法能优化得到很好的结果。 在 matlab命令窗口输入： xm,fv = DE(fitness,40,1,0.5,500,30) xm,fv = DE(fitness,40,0.75,0.5,500,30) xm,fv = DE(fitness,40,0.5,0.5,500,30) 收敛曲线如图 1 所示 050100150200250300350400450500 0 2 4 6 8 10 12 14 16 18 迭代代数 最 优 解 F=1 F=0.75 F=0.5 图 1 缩放因子F 的变化对 DE 算法收敛性的影响 将上面求得的结果列表比较如下： F10.750.5 x1-0.0482973131.17E-023.34E-05 x20.2903591552.38E-022.83E-04 x30.5217323716.99E-02-1.55E-04 x40.0510185621.64E-014.35E-05 x50.019475097-7.12E-03-9.68E-05 x60.42968677-9.49E-02-5.01E-05 x7-0.321318581-6.41E-02-8.94E-06 x80.498844481-1.31E-01-7.83E-05 x90.227559274-1.08E-012.23E-04 x10-0.1918635-2.42E-023.35E-05 x11-0.31447571-3.28E-028.51E-05 x12-0.6063273321.70E-02-3.99E-06 x130.3501588414.43E-031.05E-04 x14-0.8210696915.64E-02-4.23E-05 x15-0.3471671831.71E-021.51E-04 x16-0.317157615-3.32E-024.38E-05 x170.72521956-2.19E-021.83E-04 x180.4816322731.47E-028.01E-05 x19-0.0799399879.42E-02-4.57E-05 x200.760236255-5.11E-02-5.28E-05 x210.0420996679.46E-021.17E-04 x220.072662335-5.08E-037.40E-06 x23-0.8501186612.45E-021.02E-04 x240.466896387-4.43E-02-3.81E-05 x25-0.389142662-9.67E-02-1.17E-05 x260.5435361413.05E-02-2.36E-05 x270.274990037-9.75E-021.58E-04 x280.2587668031.17E-02-1.54E-04 x29-0.8451219745.25E-022.75E-04 x30-0.5153772611.55E-01-6.77E-05 f(x)6.3308503561.52E-014.20E-07 可见缩放因子 F 对收敛性有较大的影响，应根据实际情况进行F 参数的选取。
