计算机科学

首页 > 计算机科学

差分进化算法

2018-07-27 10:04:58     所属分类:算法

差分进化算法英语:Differential Evolution)又称微分进化算法,是一种用于最优化问题的后设启发式算法英语metaheuristic。本质上说,它是一种基于实数编码的具有保优思想的贪婪遗传算法[1]

差分进化算法类似遗传算法,包含变异,交叉操作,淘汰机制,而差分进化算法与遗传算法不同之处,在于变异的部分是随选两个解数据成员的差异,经过伸缩后加入当前解成员的变量上,因此差分进化算法无须使用机率分布产生下一代解成员 [2]

差分进化算法的起源,根据学术调查研究[2]最早可追溯至1995年由Storn与Price所作的技术报告。1996年5月,差分进化算法在国际电机电子工程师学会演化计算研讨会(Conference on evolutionary computation)公开发表 [3]

1997年,Storn与Price在全域最优化国际学术期刊(Journal of global optimization) [4]发表了差分进化算法。

算法的原理采用对个体进行方向扰动,以达到对个体的函数值进行下降的目的,同其他进化算法一样,差分进化算法不利用函数的梯度信息,因此对函数的可导性甚至连续性没有要求,适用性很强。同时,算法与粒子群优化有相通之处,但因为差分进化算法在一定程度上考虑了多变量间的相关性,因此相较于粒子群优化在变量耦合问题上有很大的优势。由于差分进化算法在连续域优化问题的优势已获得广泛应用,并引发进化算法研究领域的热潮。算法的实现参考实现代码部分[5]

目录

  • 1 实现代码(MATLAB)
  • 2 参看
  • 3 参考文献
  • 4 外部链接

实现代码(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);

参看

  • 遗传算法
  • 粒子群优化

参考文献

  1. ^ 刘波,王凌,金以慧差分进化算法研究进展,控制与决策,第22卷第7期,721-729
  2. ^ 2.0 2.1 Das, S.; Suganthan, P. N. Differential evolution: a survey of the state-of-the-art. IEEE Transactions on Evolutionary Computation. 2011, 15: 4–31. 
  3. ^ Storn, R.; Price, K. V. Minimizing the real functions of the ICEC 1996 contest by differential evolution. International Conference on Evolutionary Computation. 1996. 
  4. ^ Storn, R.; Price, K. Differential evolution - a simple and efficient heuristic for global optimization over continuous spaces. Journal of Global Optimization. 1997, 11: 341–359. 
  5. ^ 代码编写及提供者:rongekuta@gmail.com

外部链接

  • 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
版权声明:本文由北城百科网创作,转载请联系管理获取授权,未经容许转载必究。https://www.beichengjiu.com/computerscience/338744.html

相关推荐