基于自適應縮放比例因子的差分進化算法

沈佳杰，江 紅，王 肅

（華東師范大學 信息科學技術學院，上海200241）

0 引 言

差分進化算 法 （differential evolution，DE）是 由D.Storn和K.Price在1995年共同提出的一個在連續空間內啟發式搜索的隨機算法［1，2］。由于其優良的可擴展性和通用性，已經廣泛應用到各個領域。但是標準的差分進化算法依然存在很多問題，如早熟和對于在高維多峰函數條件下難以找到全局最優值等等。對于這一些問題已提出了很多新的解決辦法，如增加新的算子、混合算法等等，對于差分進化算法存在的問題和對于問題相應的改進可以參考文獻 ［3，4］。

本文針對差分進化算法在高維函數上易早熟和難以找到全局最優值的問題，提出一個基于自適應縮放比例因子改進的差分進化算法，通過理論推導和實驗證明了改進的基于自適應縮放比例因子差分進化算法可以有效地減少算法在高維多峰環境下的迭代步驟數以及更好的找到目標問題的全局最優值。

1 標準差分進化算法

1.1 差分進化算法簡介

差分進化算法是基于群體智能的進化算法，其主要的操作有變異操作、交叉操作和選擇操作，通過這3種不同操作，標準的差分進化算法［1，2］可以高效地找出函數的最優值，其主要定義如下：

個體種群由N個獨立的個體組成，記為

式中：N——種群數。

每一個個體是一個D維向量，記為

式中：D——問題維數。

類似于遺傳算法，需要通過差分進化算法中的變異、交叉和選擇操作對種群進行變換，從而找出最優值點。

1.1.1 變異操作

變異操作的主要作用是對于不同個體進行差分變換，從而產生新的變異個體。變異公式如下

新的變異個體Vi由3個不同的個體通過式 （3）計算而得。

1.1.2 交叉操作

交叉操作的主要作用是生成的實驗個體與原個體進行交叉操作，從而生成新的變異個體。交叉操作如下

式中：rand（0，1）為 ［0，1］之間隨機數，CR 為交叉概率其取值在 ［0，1］之間，rnbr（i）是指第i個個體的向量標號。

如式 （4）所示，交叉操作的本質是將變異個體與原個體在各個維度向量上以一定的概率進行交叉，生成新的實驗個體ui。

1.1.3 選擇操作

選擇操作的主要作用是在個體進入下一步迭代時，在現在個體和實驗個體中選擇一個適應度較高的個體生成下一代的種群。選擇操作如式 （5）所示

如式 （5）所示，當改進實驗個體的適應度大于原來個體適應度值，則采用改進后的實驗個體，其它情況下采用原來個體。

1.2 標準差分算法步驟

標準差分算法步驟如下：

步驟1 初始化種群X0進入差分進化算法，確定CR，將迭代步數t設為1，同時設定最大迭代步數tmax。

步驟2 調用變異操作。通過式 （3），計算所有個體的變異個體。

步驟3 調用交叉操作。通過式 （4），生成所有個體的實驗個體。

步驟4 調用選擇操作。通過式 （5），判斷生成的實驗個體是否比現存個體的適應度高，如果適應度高于現存個體，則讓實驗個體替當前個體；否則，保留，生成下一代。

步驟5 判斷是否已經達到最優值或迭代步驟數是已經超過最大迭代步驟數，如果是，轉向步驟6；否則轉向步驟2。

步驟6 輸出最優值點。

1.3 對標準差分算法的改進

從標準差分進化算法可以看出，標準的CR是一定的，極易造成差分進化算法的早熟，所以部分文獻針對于這個問題提出改進CR的計算方法［5，6］。文獻 ［5］中將CR的計算方法改為

式中：g——當前算法的步驟數，G——算法整體的迭代步驟上限，CRmin——變異值的最小值，CRmax——變異值的最大值。

其最大的優點是在算法開始時，盡量關注全局范圍的變異情況，而在算法接近于收斂的時候，更加關注局部的收斂情況，形成二次變異差分進化算法。

除此之外，許多文獻還對標準差分進化算法進行了其它方面的改進，如對差分進化算法交叉和變異操作的改進［7，8］，對編碼進行優化改進［9］、對個體進行排序以提高算法效率［10］、利用信息論中熵的概念提高算法效率［11］，以及對多目標問題使用差分進化算法的求解，如使用不同的理論對 進化算法進行改進［12，13］、 進化算法綜述［14，15］和對多目標差分算法收斂性的討論［16］。

2 改進的差分進化算法

2.1 假設和定義

本文中改進的差分進化算法的假設和定義如下：

假設1：個體適應度為正數，其隨著個體對于環境適應能力的增強而變大，即需要將問題歸一為正數最大值問題。

假設2：多峰函數是連續的且最優值點存在且可以被找到。

假設3：多峰函數每一維變量是獨立的影響函數的取值。

定義1 整個種群適應度的方差稱為適應度方差，記為

式中：fi——當前個體的適應度，favg——平均適應度，N——種群數。δ2的值越大，說明種群越分散，對于隨機搜索越有利；反之，δ2的值越小，說明種群越集中。

定義2 種群整體集中程度反比于種群的方差，稱為早熟比例基數，記為

式中：f——一個比例系數。

定義3 個體的適應度相對于最大適應度和最小適應度歸一化的值，稱為歸一化適應度，記為

定義4 早熟比例基數與歸一化適應度的乘積稱為個體的健康值，記為Hi＝Fsimi＊Kbase（10）

當個體的健康值大于某個閾值，則此個體稱為優勢個體；當個體的健康值小于該閾值，此個體稱為劣勢個體。

根據以上定義，對于不同個體的改進，Ki計算公式如下

式中：a——一個系數，rand（0，1）為 （0，1）之間的隨機數，Kmin為在健康度較低條件下的K的低維比例因子，Kmax為在健康度較高條件下的K的高維比例因子。

定義5 對于函數極值點的第i極值點中第j維存在一個領域，使得在對于每一個個體的進行一次小于比例因子Kminij的變異、交叉和選擇后，落在整個領域外的實驗個體的適應度值小于原來個體的值，領域叫做Kminij步長最極值領域。在極值點比例系數中最小的比例系數稱為這極值點的最小比例系數，記為Kmini，所有極值點最小比例系數Kmini的最小值稱為最小比例系數，記為Kmin。

2.2 改進差分進化算法的步驟

本文中改進的差分進化算法的算法步驟如下：

步驟1 初始化種群X0進入差分進化算法，確定CR，將迭代步數T設為1，同時設定最大迭代步數Tmax。

步驟2 根據式 （7）和式 （8），以及現在的迭代步數T和適應度，計算δ2、比例基值Kbase。

步驟3 根據式 （9）、式 （10）確定本個體的健康值Hi，根據式 （11）計算當前個體的Ki。

步驟4 根據式 （3）調用變異操作，計算變異個體。

步驟5 根據式 （4）和CR進行交叉操作，計算得到實驗個體。

步驟6 根據式 （5），調用選擇操作生成下一代個體，檢查是否所有的個體都完成了迭代。如果還有個體未完成迭代，回到步驟3。

步驟7 判斷是否已經達到最優值或迭代步驟數已經超過最大迭代步驟數，如果是轉向步驟8，否則轉向步驟2。

步驟8 輸出最優值點。

2.3 算法性質及其定理證明

本文中改進的差分進化算法的性質及其定理證明如下：

定理1 當所有的個體每一維分量都落在極值而不是最優值的Kminij步長最極值領域，且算法的比例系數值小于對應的最小比例系數值，即K＜Kmin時，則標準差分進化算法無法找到最優值點。

證明：假設原先個體為的個體編號是r0，而隨機選中的個體的編號為r1、r2和r3，所以對于t＋1步實驗個體有以下組成

其中K≤Kmin，xr0j表示r0的第j維的分量，xr1j表示r1的第j維的分量、xr2j表示r2的第j維的分量、xr3j表示r3的第j維的分量。

對于式 （13），由于實驗個體中的分量相較于上一步的個體分量沒有發生變化，所以只需要討論式 （12）。對于t＋1步的迭代，對于每一個個體的每一維變量有以下兩種可能：

（1）下一步迭代時跳出r1的最極值領域內

由于所有的個體每一維都在極值而不是最值的Kminij步長最極值領域內且差分進化算法的比例系數小于最小比例系數 （即K＜Kmin），所以這一維變量的改變必然導致個體適應度值的變小。又因為多峰函數每一維變量是獨立的影響函數，所以產生的實驗個體必然小于原個體的適應度值，在選擇步驟中必然會選擇原個體，而不是變異個體。

（2）下一步依然在r1的最極值領域內

由于所有的個體的每一維分量都在極值而不是最優值的Kminij步長最極值領域，所以迭代后的個體也一定不在最優值的Kminij步長最極值領域內，因此不會達到最優值。

綜上所述，原命題成立。

推論1 當多維函數的維數和函數極值點足夠多時，傳統的差分進化算法很難找到全局最優值點。

證明：隨著函數維數和局部極值點的增多，陷入局部極值點的概率將增大，所以隨著函數維數和局部極值點增多其越難找到全局最優值點。

定理1與推論1說明了標準的差分進化算法在多峰函數條件下，如果比例系數值選擇過小，則較容易發生早熟現象，即過早進入找到局部最優值的搜索而忽略了全局的最優值點，而如果比例因子取得太大的話，又會因為其迭代跨度太大，不利于最優值點的局部搜索。

定理2 如果高維比例因子足夠大，在迭代步驟數足夠多的情況下，改進差分進化算法可以找到最優值。

證明：由于迭代步驟足夠多，那么當陷入局部極值的個體必然有n步迭代進入式 （11）中高維部分，又因為高維的步長足夠長，所以必然存在個體高維的迭代可以跳出局部極值。而與此同時在最優值周圍的個體，由于迭代步驟足夠多，必然存在個體通過式 （11）的低維搜索找到最優值。

所以改進差分進化算法可以在迭代步驟數足夠多的情況下找到最優值。

3 實 驗

本實驗是在MATLAB2010b環境下進行測試，本文選擇表1所示的5個函數作為本實驗的測試函數，其中測試函數1～5的性質各不相同：函數1、函數4和函數5是多峰函數，函數2和函數3為單峰函數。在實驗中分別對于低維數據 （2，2，2，3，3）和高維數據 （2，15，10，10，15）各自獨立進行10次實驗，分別對10次試驗迭代次數的最大值、最小值和平均值進行統計。

表1 模擬使用的測試函數

為了減少CR對于實驗結果的影響，實驗中采用規定CR為常數的方法。表2是在低維 （2，2，2，3，3）情況下標準差分進化算法和改進后的差分進化算法迭代步驟數的對比，表3是在高維 （2，15，10，10，15）情況下標準差分進化算法和改進后的差分進化算法迭代步驟數的對比。

其中SDE代表標準差分進化算法，IDE代表本文中的差分進化算法。

由表2可知，改進差分進化算法相較于傳統差分進化算法沒有明顯的改進，在某些函數上，甚至有時性能還低于標準的差分進化算法，其主要原因是改進的差分進化算法為了提高對于全局最優值的查找能力，進行了不必要的高維搜索。由表3可知，隨著測試函數維度的增加，在多維函數4和函數5中改進差分進化算法其達標時的迭代次數相較傳統的差分進化算法明顯減少，甚至在函數4中，在交叉概率CR為0.2的情況下，有1000次無法迭代出結果的情況，而改進的差分進化算法依然可以在最多343步下找到函數的達標值點，這符合推論1和定理2。

圖1 顯示了迭代結束時傳統差分進化算法和改進差分進化算法在算法終止時，高維和低維不同環境下，對于5個實驗中的測試函數的平均最小值。

表2 對于第一組維數 （2，2，2，3，3）其優化結果前后迭代步數比較

表3 對于第一組維數 （2，15，10，10，15）其優化結果前后迭代步數比較

圖1 低維和高維條件下，差分算法平均最小值的比較

從圖1（a）中可以看出，低維的條件下，改進差分進化算法與傳統方法找到函數最小值相似，圖1（b）高維條件下，改進后的差分進化算法的平均最小值小于或等于標準的差分進化算法，尤其是在多維函數4中其平均值相差較大。

4 結束語

本文中通過對于標準差分進化算法引入自適應的比例因子，提出了一個基于自適應比例算子的改進的差分進化算法，通過實驗分析和理論推導證明改進的差分進化算法較傳統差分進化算法在高維多峰函數環境下，可以有效地提高算法對于全局最優值點的查找能力以及減少差分進化算法的迭代步驟數，但是由于本文中對于改進的差分進化算法的實驗數量有限，是否可以找出一個即可以不依賴于函數先驗知識的通用比例因子的計算方法，依然是值得研究的問題。

［1］Storn R，Price K.Differential Evolution－a simple and efficient heuristic for global optimization over continuous spaces ［J］.Journal of Global Optimization，1997，11 （4）：341－359.

［2］Storn R，Price K.Minimizing the real functions of the ICEC’96contest by differential evolution ［C］／／Proceedings of IEEE International Conference on Evolutionary Computation，1996.

［3］LIU Bo，WANG Ling，JIN Yihui.Advances in differential evolution ［J］.Control and Decision，2007，22 （7）：721－729（in Chinese）.［劉波，王凌，金以慧.差分進化算法的研究進展 ［J］.控制與決策，2007，22 （7）：721－729.］

［4］YANG Qiwen，CAI Liang，XUE Yuncan.A survey of differential evolution algorithms ［J］.Pattern Recognition and Artificial Intelligence，2008，21 （4）：506－513 （in Chinese）.［楊啟文，蔡亮，薛云燦.差分進化算法綜述 ［J］.模式識別與人工智能，2008，21 （4）：506－513.］

［5］WU Lianghong，WANG Yaonan，YUAN Xiaofang，et al.Differential evolution algorithm with adaptive second mutation［J］.Control and Decision，2006，21 （8）：898－902 （in Chinese）.［吳亮紅，王耀南，袁小芳，等.自適應二次變異差分進化算法 ［J］.控制與決策，2006，21 （8）：898－902.］

［6］DENG Zexi，CAO Dunqian，LIU Xiaoji，et al.new differential evolution algorithm ［J］.Computer Engineering and Applications，2008，44 （24）：40－42 （in Chinese）.［鄧澤喜，曹敦虔，劉曉冀，等.一種新的差分進化算法 ［J］.計算機工程與應用，2008，44 （24）：40－42.］

［7］Zaharie D.Influence of crossover on the behavior of Differential Evolution Algorithms［J］.Applied Soft Computing，2009，9（3）：1126－1138.

［8］Epitropakis M G，Pavlidis N G，Plagianakos V P，et al.Enhancing differential evolution utilizing proximity－based mutation operators ［J］.Evolutionary Computation，2011，15 （1）：99－119.

［9］HE Yichao，WANG Xizhao，KOU Yingzhan.A binary differential evolution algorithm with hybrid encoding ［J］.Journal of Computer Research and Development，2007，44 （9）：1476－1484（in Chinese）.［賀毅朝，王熙照，寇應展.一種具有混合編碼的二進制差分演化算法 ［J］.計算機研究與發展，2007，44 （9）：1476－1484.］

［10］SHAO Liang.Differential evolutin algorithm based on individual ordering and samplng ［J］.Computer Engineering and Applications，2012，48 （1）：49－52 （in Chinese）.［邵梁.基于排序采樣策略的差分演化算法 ［J］.計算機工程與應用，2012，48 （1）：49－52.］

［11］YONG Longquan，CHEN Tao，ZHANG Jianke.Solving complementarity problem based on maximum differential evolutionary algorithm ［J］.Application Research of Computers，2010，27 （4）：1308－1310 （in Chinese）.［雍龍泉，陳濤，張建科.求解互補問題的極大熵差分進化算法 ［J］.計算機應用研究，2010，27 （4）：1308－1310.］

［12］WANG Xiaozhen，LI Peng，YU Guoyan.Multi－objective chaotic differential evolution algorithm with grading second mutation ［J］.Control and Decision－Making，2011，26 （3）：457－163（in Chinese）.［王筱珍，李鵬，俞國燕.分階段二次變異的多目標混沌差分進化算法 ［J］.控制與決策，2011，26 （3）：457－163.］

［13］MENG Hongyun，ZHANG Xiaohua，LIU Sanyang.A differential evolution based on double populations for constrained multi－objective optimization problem ［J］.Chinese Journal of Computers，2008，31 （2）：228－235 （in Chinese）.［孟紅云，張小華，劉三陽.用于約束多目標優化問題的雙群體差分進化算法 ［J］.計算機學報，2008，31 （2）：228－235.］

［14］GONG Maoguo，JIAO Licheng，YANG Dongdong，et al.A differential evolution based on double populations for constrained multi－objective optimization problem ［J］.Journal of Software，2009，20 （2）：272－289 （in Chinese）.［公茂果，焦李成，楊咚咚，等.進化多目標優化算法研究 ［J］.軟件學報，2009，20 （2）：272－289.］

［15］XIE Tao，CHEN Huowang，KANG Lishan.Evolutionary algorithms of multi－objective optimization problems ［J］.Chinese Journal of Computers，2003，26 （8）：997－1003 （in Chinese）.［謝濤，陳火旺，康立山.多目標優化的演化算法［J］.計算機學報，2003，26 （8）：997－1003.］

［16］ZHOU Yuren， MIN Huaqing，XU Xiaoyuan，et al.A multi－objective evolutionary algorithm and its convergence［J］.Chinese Journal of Computers，2004，27 （10）：1415－1421（in Chinese）.［周育人，閔華清，許孝元，等.多目標演化算法的收斂性研究 ［J］.計算機學報，2004，27 （10）：1415－1421.］