差分进化算法
差分进化算法(英语:differential evolution)又称微分进化算法,是一种求解优化问题的进化算法。因为进化算法对于优化问题的要求极少,所以被视为一种后设启发式算法。虽然后设启发式算法适用于多种优化问题,但是并不保证可以找到全局最优解。
差分进化算法被使用在多维度实数编码的优化问题。因为此算法不使用问题的梯度资讯,故可解不可微分的优化问题。也因此,差分进化算法可用于不连续的,噪声的,随着时间改变的优化问题。
差分进化算法类似遗传算法,包含变异,交叉操作,淘汰机制。本质上说,它是一种基于实数编码的具有保优思想的贪婪遗传算法[1]。而差分进化算法与遗传算法不同之处,在于变异的部分是随选两个解成员变量的差异,经过伸缩后加入当前解成员的变量上,因此差分进化算法无须使用几率分布产生下一代解成员 [2]。
算法的原理采用对个体进行方向扰动,以达到对个体的函数值进行下降的目的,同其他进化算法一样,差分进化算法不利用函数的梯度资讯,因此对函数的可导性甚至连续性没有要求,适用性很强。同时,算法与粒子群优化有相通之处,但因为差分进化算法在一定程度上考虑了多变量间的相关性,因此相较于粒子群优化在变量耦合问题上有很大的优势。由于差分进化算法在连续域优化问题的优势已获得广泛应用,并引发进化算法研究领域的热潮。算法的实现参考实现代码部分[3]
历史
[编辑]- 1995年3月,Storn与Price所撰写的差分进化算法技术报告,是差分进化算法的起源[4]。
- 1996年5月,Storn与Price在国际电机电子工程师学会演化计算研讨会公开发表差分进化算法[5]。
- 1997年12月,在全局优化国际学术期刊上刊出Storn与Price所著之差分进化算法论文[6]。
- 2005年,Springer (页面存档备份,存于互联网档案馆)出版Storn与Price所著之差分进化算法专书[7]。
算法原理
[编辑]差分进化算法之目的为求解优化问题,使用突变、交叉、选择计算以演化多个可能的解。首先,产生足量的随机变量,做为初始的可能解。接着,依序进行突变、交叉、选择计算,做完一轮后,检查某个终止条件。若终止条件尚未满足,则回到突变、交叉、选择计算,否则终止差分进化算法,输出最后一轮的最佳解。
突变
[编辑]在进化计算中,突变是用于产生随机解的计算方法。
交叉
[编辑]在突变之后,差分进化算法使用交叉计算以增强随机解的多样性。
选择
[编辑]在交叉之后,差分进化算法对随机解做选择,移除演化失败的解,留下演化成功的解。选择之后,进行突变计算,直到满足某个终止条件。
实现代码(MATLAB)
[编辑]tic
F = 0.9;
CR = .1;
n = 2; %问题维数,以简单的球函数为目标函数
NP = 30;
lu = [-10,-10 ;10 ,10]; %求解空间的上下界
LB = repmat(lu(1,:),NP,1);
UB = repmat(lu(2,:),NP,1);
%用于生成随机选择个体的表
tab = 1:NP; tab = tab(ones(1,NP),:)';
dig = 1:NP; D =(dig-1)*NP +(1:NP);
tab (D) = [];
tab = reshape(tab,NP-1,[])';
TAB = tab;
%测试次数
TIMES = 10;
Solve = zeros(1,TIMES);
numOfevol = zeros(1,TIMES);
for time = 1:TIMES
%
Result = []; %记录结果
rand('seed',sum(100*clock));
%
X = LB+rand(NP,n).*(UB-LB);
U = X;
%%
fit = fitness (X); %首次评价
FES = NP;
while FES<n*10000
%产生随机个体参与变异
tab = TAB;
rand1 = floor(rand(NP,1)*(NP-1))+1;
rand2 = floor(rand(NP,1)*(NP-2))+2;
rand3 = floor(rand(NP,1)*(NP-3))+3;
RND1 =(rand1-1)*NP+(1:NP)';
RND2 =(rand2-1)*NP+(1:NP)';
RND3 =(rand3-1)*NP+(1:NP)';
r1 = tab (RND1); tab (RND1)=tab(:,1);
r2 = tab (RND2); tab (RND2)=tab(:,2);
r3 = tab (RND3);
% rand/one/变异模式
V = X(r1,:) + F.*(X(r2,:)-X(r3,:));
%越界检验
BL = V<LB ; V(BL) = 2*LB(BL) - V(BL);
BLU = V(BL)>UB(BL); BL (BL) = BLU ; V(BL) = UB (BL);
BU = V>UB; V (BU) = 2*UB(BU) - V(BU);
BUL = V(BU)<LB(BU); BU (BU) = BUL ; V(BU) = LB (BU);
%交叉操作
J_= mod(floor(rand(NP,1)*n),n)+1;
J =(J_-1)*NP+(1:NP)';
C = rand(NP,n)<CR;
U (J) = V(J);
U (C) = V(C);
%评价子代
fit_ = fitness (U);
%比较并竞争
S = fit_<fit;
X(S,:) = U(S,:);
fit(S) = fit_(S);
%记录函数评价次数
FES = FES + NP;
%记录结果(用于绘图,并不是算法必要环节)
Result = [Result ,min (fit)];
end
Solve (time) = min (fit);
%试验次数
plot(log10(Result),'b');hold on;
end
disp(['求解结果:',num2str(Solve)]);
toc
%附上球函数代码(新建一个M文件即可)
function Y = fitness (X)
Y = sum(X.^2 ,2);
参看
[编辑]参考文献
[编辑]- ^ 刘波,王凌,金以慧差分进化算法研究进展,控制与决策,第22卷第7期,721-729
- ^ S. Das; P. N. Suganthan. Differential Evolution: A Survey of the State-of-the-Art. IEEE Transactions on Evolutionary Computation. Feb. 2011, 15 (1): 4–31 [2019-02-12]. doi:10.1109/TEVC.2010.2059031. (原始内容存档于2021-03-08).
- ^ 代码编写及提供者:[email protected]
- ^ R. Storn; K. Price. Differential Evolution - a Simple and Efficient Adaptive Scheme for Global Optimization over Continuous Spaces. Technical Report TR-95-012, ICSI, March 1995. [2019-02-12]. (原始内容存档于2020-06-09).
- ^ R. Storn; K. Price. Minimizing the real functions of the ICEC'96 contest by differential evolution. Proceedings of IEEE International Conference on Evolutionary Computation. Nagoya, Japan: 842–844. 20-22 May 1996 [2019-02-12]. doi:10.1109/ICEC.1996.542711. (原始内容存档于2019-02-13).
- ^ R. Storn; K. Price. Differential Evolution – A Simple and Efficient Heuristic for global Optimization over Continuous Spaces. Journal of Global Optimization. Dec. 1997, 11 (4): 341–359 [2019-02-12]. doi:10.1023/A:1008202821328. (原始内容存档于2021-03-08).
- ^ Price, K.; Storn, R.M.; Lampinen, J.A. Differential Evolution: A Practical Approach to Global Optimization. Springer. 2005. ISBN 978-3-540-20950-8.
外部链接
[编辑]- Storn's Homepage on DE featuring source-code for several programming languages.
- SwarmOps Parameter tuning / calibration of DE and other optimization methods using a Meta-Optimization approach. Source-code library is for the C and C# programming languages.
- Global Optimization by Differential Evolution and Particle Swarm Methods: Evaluation on Some Benchmark Functions(webng.com)– FORTRAN 77 Codes for DE optimization with a large number of benchmark problems
- Differential Evolution and Particle Swarm Optimization(webng.com)– Performance Evaluation on Benchmark functions
- List of References on Constraint-Handling Techniques used with Evolutionary Algorithms(cs.cinvestav.mx) (页面存档备份,存于互联网档案馆)– Comprehensive bibliography of constraint methods for evolutionary optimization
- Differential Evolution(MathWorld.wolfram.com) (页面存档备份,存于互联网档案馆)
- A SPICE Circuit Optimizer(sourceforge.net) (页面存档备份,存于互联网档案馆)– Parallel version of the Differential Evolution
- A forthcoming special issue on DE organized by IEEE Transactions on Evolutionary Computation (页面存档备份,存于互联网档案馆)
- GenerationZ (页面存档备份,存于互联网档案馆) – A multi-threaded differential evolution library
- A Fast Differential Evolution Algorithm using k-Nearest Neighbour Predictor