差分進化演算法

差分進化演算法（英語：differential evolution）又稱微分進化演算法，是一種求解最佳化問題的進化演算法。因為進化演算法對於最佳化問題的要求極少，所以被視為一種後設啟發式演算法（英語：metaheuristic）。雖然後設啟發式演算法適用於多種最佳化問題，但是並不保證可以找到全域最優解。

差分進化演算法被使用在多維度實數編碼的最佳化問題。因為此演算法不使用問題的梯度資訊，故可解不可微分的最佳化問題。也因此，差分進化演算法可用於不連續的，雜訊的，隨着時間改變的最佳化問題。

差分進化演算法類似遺傳演算法，包含變異，交叉操作，淘汰機制。本質上說，它是一種基於實數編碼的具有保優思想的貪婪遺傳演算法^[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）. 請檢查|date=中的日期值 (幫助)
^ 代碼編寫及提供者：[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）. 請檢查|date=中的日期值 (幫助)
^ 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）. 請檢查|date=中的日期值 (幫助)
^ 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

[liubo-1] 劉波，王凌，金以慧差分進化演算法研究進展，控制與決策，第22卷第7期,721-729

[das11surveyde-2] 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）. 請檢查|date=中的日期值 (幫助)

[rongekuta-3] 代碼編寫及提供者：[email protected]

[stornpub-4] 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）.

[storn96de-5] 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）. 請檢查|date=中的日期值 (幫助)

[storn97de-6] 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）. 請檢查|date=中的日期值 (幫助)

[price05differential-7] Price, K.; Storn, R.M.; Lampinen, J.A. Differential Evolution: A Practical Approach to Global Optimization. Springer. 2005. ISBN 978-3-540-20950-8.

[1]

[2]

[3]

[4]

[5]

[6]

[7]