1.2 差分進化算法介紹

差分進化（Differential Evolution，DE）算法是由Storn與Price在1995年提出的一種社會性的、基于種群的尋優算法。差分進化算法屬于進化算法（Evolutionary Algorithm，EA）的子領域，也是簡單但很有效的隨機進化算法。與其他隨機優化進化算法類似，DE算法采用了與標準進化算法類似的計算方法步驟，主要通過變異（Mutation）、交叉（Crossover）和選擇（Selection）3種操作進行智能搜索。但與傳統的進化算法有所不同，DE算法通過隨機選擇不一樣的個體生成比例差分向量擾動當代種群，并運用與候選解之間的差別產生新的個體。與其他進化算法相比，DE算法具有結構簡單（該算法只有3個控制參數）、容易實現（Matlab實現的核心的代碼僅有幾十行）、全局搜索性能好、穩健性強等優勢[7]。

DE算法需要經過個體的初始化、變異、交叉和選擇4個基本流程。個體經過初始化操作之后，由差分進化算法中最重要的差分變異（Differential Mutation）算子將同一種群中的2個個體進行差分和縮放，并且加上該種群內另外的隨機個體向量來產生變異個體向量（Mutant Vector），然后父代個體和變異個體的向量采用交叉操作獲得實驗個體向量（Trial Vector），最后比較實驗個體向量和父代個體向量的適應度值，將較優者保存到進化的下一代中。DE算法利用差分變異、交叉和選擇等方式不停迭代地對種群進行演變，直到滿足停止的要求為止。

（1）個體的初始化

傳統的DE算法采用實數編碼，更加適宜處理實數優化問題。DE算法保持了一個規模為（NP，D）的實參類型種群（NP為種群大小，D為決策變量的個數），其中第i個個體xi如式（1-1）所示。

其中，xi,j∈[Lj,Uj]。在種群初始化之前，確定參數的上界Uj和下界Lj，xi,j在[Lj,Uj]內隨機均勻初始化，如式（1-2）所示。

其中，函數randj(0,1)表示從區間[0,1)隨機選擇一個數，j表示在第j維上產生的隨機數。

（2）差分變異操作

DE算法正因為差分變異操作而得名，通常統一采用“DE/a/b”的形式表示，其中，“DE”表示差分進化算法；“a”表示挑選被變異個體的方式，常運用“rand”和“best”兩種方式，“rand”為從種群中任意挑選個體向量，“best”為挑選當前適應度最優的個體向量；“b”表示在變異流程內采用的向量的數目。在變異過程中，個體xi,G可采用變異策略產生變異向量vi,G，被廣泛采用的5種變異策略具體如式（1-3）～（1-7）所示。

其中，r1、r2、r3、r4和r5為{1,…,NP}之間隨機選擇的5個互不相等的整數，xbest,G為在當前G代中具備最好適應度函數值的向量，縮放因子F為在區間[0,1]的加權差分向量的控制參數。

在變異操作中，DE算法要判斷差分變異產生的新向量是否能保證變異向量在搜索的空間范圍內。如果變異向量不在搜索空間內，則要通過運用修復操作對變異向量進行處理，通常連續向量采用式（1-8）或式（1-9）所示方法進行處理。

其中，表示變異向量v第G代中第i個向量的第j維的值。

（3）交叉操作

為了進一步完善差分變異搜索流程，DE算法運用了交叉方法，該方法包括二項式交叉（Binomial Crossover，BIN）和指數交叉（Exponential Crossover，EXP），其中二項式交叉如式（1-10）所示。

其中，表示實驗向量U中第G代的第i個向量的第j維的值。jrand表示從{1,2,…,D}中隨機選擇的一個數。CR表示交叉概率。

當進行指數交叉操作時，開始在[1,D]任意挑選整數n，作為進行交叉的開始位置，另一個整數L再在[1,D]隨機挑選，L代表變異向量占目標向量位置的數量。利用上述方法選定n和L，最終進行指數交叉產生實驗向量的值。指數交叉如式（1-11）所示。

其中，<·>D表示對D取模函數，整數L按如下偽代碼生成。

生成整數L的偽代碼
L=0;
do {
L=L+1;
} while (rand(0,1)≤CR&L≤D)

（4）選擇操作

DE算法經過差分變異和交叉進化流程后，采取選擇操作把實驗向量與目標向量進行對比。若實驗向量ui,G的適應度函數值小于或等于目標向量xi,G的適應度函數值，那么實驗向量取代相應的目標向量，從而獲得進入下一代的機會；反之目標向量就一直維持到下一代進化過程。最小化優化問題中的選擇操作可以作如式（1-12）所示的描述。

其中，f(xi,G)是計算出的第G代個體xi,G適應度目標的函數值。

總之，DE算法的一次進化過程包含了初始化種群、變異、交叉和選擇4個基本步驟。DE算法的偽代碼如下。

初始化種群規模NP，縮放因子F和交叉概率CR，設定進化代數G=0；
執行初始化操作，產生和初始化有NP個個體的種群X，并評估適應度f(X)；
while停止條件非真do
for種群中的每個個體xi,G ∈ XG do
根據差分變異策略生成差分變異向量vi,G；
判斷差分變異向量是否在搜索空間范圍內，如不在，則采用修復操作；
通過交叉策略得到實驗向量ui,G；
通過選擇操作，確定下一代種群中的個體xi,G+1；
end For
G=G+1;
end while
返回最佳適應度的個體xbest,G；