基本差分进化算法
基本模拟退火算法概述
DE 算法是一种基于群体进化的算法,其本质是一种基于实数编码的具有保优思想的贪婪遗传算法。
由于DE 算法操作简单,寻优能力强,自提出以来引起了国内外学者的高度关注,目前已在电力系统优化调度、配网重构等领域得到了应用。
1、算法原理
DE 算法首先在N 维可行解空间随机生成初始种群P
0001[,,]N =X x x L ,其中000T 1[,,]i i iN x x =x L ,p N 为DE 种群规模。
DE 算法的核心思想在于采取变异和交叉操
作生成试验种群,然后对试验种群进行适应度评估,再通过贪婪思想的选择机制,将原种群和试验种群进行一对一比较,择优进入下一代。
基本DE 算法主要包括变异、交叉和选择三个操作。
首先,在种群中随机选取三个个体,进行变异操作:
1123()t t t t
i r r r F +=+-v x x x
其中1t i +v 表示变异后得到的种群,t 表示种群代数,F 为缩放因子,一般取(0,2],它的大小可以决定种群分布情况,使种群在全局范围内进行搜索;1t r x 、2t r x 、3t r x 为从种群中随机抽取的三个不同的个体。
然后,将变异种群和原种群进行交叉操作:
1,R 1
,,R () or () () and ()t i j t i j
t i j
v rand j C j randn i u
x rand j C j randn i ++⎧≤=⎪=⎨>≠⎪⎩ 其中t 1,i j u +表示交叉后得到的种群,()rand j 为[0,1]之间的随机数,j 表示个体的第j 个分量,R C 为交叉概率,()randn i 为[1,,]N L 之间的随机量,用于保证新个体至少有一维分量由变异个体贡献。
最后,DE 算法通过贪婪选择模式,从原种群和试验种群中选择适应度更高的个体进入下一代:
11t 11 ()() ()()t t t
i i i i t
t t
i
i i f f f f ++++⎧<=⎨≥⎩u u x x x u x 1()t i f +u 、()t i f x 分别为1t i +u 和t i x 的适应度。
当试验个体1t i +u 的适应度优于t i x 时,
试验个体取代原个体,反之舍弃试验个体,保留原个体。
2、算法步骤
基本DE算法的基本步骤如下:
3、算法的matlab实现
见程序
4、算法举例
采用DE算法求取Sphere Mode函数
30
2
1
()
i
i
f x x
=
=∑的最小值。
1) 基本测试
在matlab命令窗口输入:
>> [xm,fv] = SA(@fitness,3,1e-5,0.99,200,30) 得到如下收敛曲线
100
200
300
400
500
600
700
退温次数
目标值
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) 将上面求得的结果列表比较如下:
M 100 200 500 x 1 0.033087185 -1.29E-02 1.77E-04 x 2 0.202701957 -4.05E-02 -1.08E-04 x 3 -0.081038245 9.89E-03 5.80E-05 x 4 0.028932023 -2.05E-02 7.00E-05 x 5 -0.151716543 6.23E-03 -1.66E-04 x 6 0.154352242 8.34E-03 9.47E-05 x 7 0.051436736 -1.79E-02 -3.01E-04 x 8 0.057500363 -5.54E-03 -2.23E-04 x 9 -0.058409634 9.74E-03 4.80E-05 x 10 0.060435634 3.02E-02 -4.12E-05 x 11 0.005562026 -1.64E-02 1.00E-04 x 12 0.124679757 8.56E-03 2.75E-05 x 13 -0.217063076 -6.15E-03 2.45E-05 x 14 -0.156305243 -3.49E-03 -1.35E-04 x 15 0.142613078 4.24E-02 2.66E-05 x 16 -0.003189876 -5.84E-02 1.35E-04 x 17 -0.152339667 5.51E-02 -4.93E-05 x 18 -0.229525992 -1.10E-02 2.51E-04 x 19 0.076502493 1.47E-02 1.50E-04 x 20 0.049598038 1.11E-02 -4.13E-05 x 21 0.123235808 6.87E-02 8.12E-05 x 22
0.183832078
-1.80E-02
-3.78E-05
x 23 -0.111816229 1.32E-03 -2.59E-04 x 24 0.232072926 -2.25E-02 -9.06E-05 x 25 0.043585057 2.47E-02 -6.93E-05 x 26 -0.235073466 -1.73E-03 2.36E-04 x 27 -0.008428201 2.95E-02 -2.37E-04 x 28 -0.075163759 2.49E-02 -7.77E-05 x 29 -0.099728761 -1.92E-02 -6.94E-05 x 30 0.143423027 2.06E-02 1.28E-04 f(x) 0.509858129 2.13E-02 5.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所示
50100150200250300350400450500
迭代代数
最优解
图1 缩放因子F 的变化对DE 算法收敛性的影响
将上面求得的结果列表比较如下: F 1
0.75 0.5 x 1 -0.048297313 1.17E-02 3.34E-05 x 2 0.290359155 2.38E-02 2.83E-04 x 3 0.521732371 6.99E-02 -1.55E-04 x 4 0.051018562 1.64E-01 4.35E-05 x 5 0.019475097 -7.12E-03 -9.68E-05 x 6 0.42968677 -9.49E-02 -5.01E-05 x 7 -0.321318581 -6.41E-02 -8.94E-06 x 8 0.498844481 -1.31E-01 -7.83E-05 x 9
0.227559274
-1.08E-01 2.23E-04
x10-0.1918635-2.42E-02 3.35E-05
x11-0.31447571-3.28E-028.51E-05
x12-0.606327332 1.70E-02-3.99E-06
x130.350158841 4.43E-03 1.05E-04
x14-0.821069691 5.64E-02-4.23E-05
x15-0.347167183 1.71E-02 1.51E-04
x16-0.317157615-3.32E-02 4.38E-05
x170.72521956-2.19E-02 1.83E-04
x180.481632273 1.47E-028.01E-05
x19-0.0799399879.42E-02-4.57E-05
x200.760236255-5.11E-02-5.28E-05
x210.0420996679.46E-02 1.17E-04
x220.072662335-5.08E-037.40E-06
x23-0.850118661 2.45E-02 1.02E-04
x240.466896387-4.43E-02-3.81E-05
x25-0.389142662-9.67E-02-1.17E-05
x260.543536141 3.05E-02-2.36E-05
x270.274990037-9.75E-02 1.58E-04
x280.258766803 1.17E-02-1.54E-04
x29-0.845121974 5.25E-02 2.75E-04
x30-0.515377261 1.55E-01-6.77E-05
f(x) 6.330850356 1.52E-01 4.20E-07可见缩放因子F对收敛性有较大的影响,应根据实际情况进行F参数的选取。