混合差分進化算法

李麗蓉，高衛峰

（1.山西警官高等專科學校 計算機科學與技術系，山西 太原030021；2.西安電子科技大學 應用數學系，陜西 西安710071）

0 引 言

差分進化（DE）算法［1］是繼遺傳算法、蟻群算法之后的又一種新興的群體智能優化算法。與其他進化算法一樣，DE是一種模擬生物進化的隨機模型，通過反復迭代，使得那些適應環境的個體被保存下來。由于該算法結構簡單、易于實現、無需梯度信息、參數較少等特點，一經提出便受到眾多學者的關注和研究，并在濾波器設計、PID控制、圖像分割以及其他科學或工程應用方面［2－4］得到廣泛應用。

然而，與其他智能算法類似，DE也存在易于過早陷入局部最優點，進化后期收斂速度慢，對過于復雜的問題可能搜索不到最優解，計算精度不高等問題。針對這些缺點，學者們提出了多種改進策略［5－15］來優化DE的性能。其中，文獻 ［5］引入3種變異策略和適當的控制參數，以提高DE的性能；文獻 ［6］給出了優先交叉DE，利用變異產生的個體的概率密度函數分析了縮放比例參數的缺陷，并提出了優先交叉準則以彌補缺陷；文獻 ［7］采用正交設計的方法加速DE的收斂速度，從而提高了DE的尋優性能；文獻 ［8］對DE算法加入了懲罰函數，從而使其較好地應用于具有約束條件的優化環境。文獻 ［9］提出了趨藥性差分進化算法（CDE），在一定程度上提高了DE的性能，但并不能徹底解決早熟現象和收斂速度慢的問題。

本文在CDE算法的基礎上，融合遺傳算法的變異雜交機制。對一半的較優個體進行變異操作，以提高種群的多樣性，從而避免早熟；對剩下的一半較差個體，通過與較優個體的雜交，以增強子代的開采能力，從而提高收斂速度。該算法能很好的平衡算法的探索和開采能力。對幾種典型Benchmarks函數測試表明，該算法是一種高效的高維復雜函數優化算法。

1 趨藥性差分進化算法

DE是一種基于種群的并行進化算法，在初始化階段，種群個體以平均分布概率在搜索空間隨機初始化。在進化階段，種群個體進行變異、交叉和選擇3個迭代過程，直到滿足停止條件，具體描述如下

（1）變異：對于個體Xi，按式（1）生成變異個體

式中：Xr1、Xr2、Xr3——從進化群體中隨機選取的互不相同的3個個體；F——縮放比例因子，用于控制差向量的影響大小。

（2）交叉：為增加群體多樣性，交叉操作（2）被引入差分進化算法

式中：D——解空間維數，CR∈ ［0，1］——雜交參數，p—— ［0，l］之間的隨機數。

（3）選擇：在基本差分進化算法中，選擇操作采取貪婪策略，即只有當產生子代個體優于父代個體時才被保留，否則父代個體將保留至下一代。

趨藥性差分進化算法就是在每一次迭代過程中，引入趨藥性循環，具體步驟如下。

步驟1：計算目標函數值J（i，j，t）。

步驟2：令Jlast＝J（i，j，t），存儲J（i，j，t）的值和將來得到的目標函數值做比較。

步驟3：翻轉：隨機產生一個向量Δ（i）∈Rn，滿足Δm（i），m＝1，2，…，D為 ［－1，1］之間的隨機數。

步驟4：前進

步驟5：計算J（i，j＋1，t）。

步驟6：游動：假定只有第i各細菌游動，其他細菌不發生移動。其偽代碼如下：

令m＝0；

其中，θ（i，j，t）表示第i個細菌在第j次趨化第t次差分進化循環時的位置；J（i，j，t）為細菌θ（i，j，t）對應的目標函數值；S：菌群數模；D：問題的維數；Nc：細菌趨藥性行為步驟數；C（i）：趨化步長。

2 混合差分進化算法

雖然趨藥性差分進化算法在一定程度提高了DE的性能。然而，仍然存在著早熟現象和收斂速度慢的缺點，嚴重影響算法的性能。針對這一問題，本文提出了一個改進的混合差分進化算法。在每次迭代中，經過趨藥性差分進化算法的操作步驟后，對種群的個體以適應值大小排序。把種群分為兩部分，一部分是較優個體（種群的一半），另一部分就是較差個體。對較優個體通過變異操作進行更新，以提高種群的多樣性，從而避免早熟。對較差個體通過與最優個體雜交進行更新，以提高算法的開采能力，進而提高收斂速度。

本文采用如下的雜交算子

式中：λ∈ ［0，1］為均勻分布的隨機數，X（best）——到目前為止種群找到的最優位置。在式（3）所示的雜交算子中，通過與最優個體的雜交，充分利用了已有的信息，能很好地提高算法的收斂速度。

本文采用如下的變異算子

將本文提出的混合算法稱為CDEH算法，具體步驟如下：

初始化收縮因子F和交叉因子CR，最大函數評價次數MFE。

在定義空間中，隨機初始化方法產生M，計算個體的適應值。

輸出最優解及最優值。

表1 測試函數

3 仿真實驗

為了測試本文提出的差分進化算法的效果，對表1中的12個標準測試函數進行仿真實驗。其中，f1－f4為單峰函數，f6－f12為多峰函數。表1給出了12個測試函數的表達式。種群規模M，縮放比例因子F，交叉概率CR采用文獻 ［5］的參數設置方案，即 M＝30，F＝0.9，CR＝0.9。將本文的算法與 DE、GA－PSO［16］和CDE比較，它的參數設置見文獻 ［8，16］。采用 Matlab7.0編程工具進行試驗仿真。Best、Worst、Mean和Std分別為算法獨立實驗20次的最好值、最差值、平均值和標準差。Best、Worst反映了解的質量；Mean顯示了在給定的函數評價次數下算法所能達到的精度，反映了算法的收斂速度；Std反映了算法的穩定性和魯棒性。結果如表2所示。由表2數據對比可以看出，在所有的標準測試函數中，無論是解的質量，還是算法的收斂精度和穩定性，CDEH算法都比其他3種算法有了很大的提高。特別地，在這4種算法中，CDEH算法幾乎在所有的測試函數上都取得了最好的優化結果，除了在f3函數上，CDE算法也達到了同樣的求解精度。

表2 GA－PSO，DE，CDE和CDEG算法性能比較

f9 1×104 GA－PSO 2.79e－00 2.08e＋01 2.15e＋01 3.34e－00 DE 3.95e－00 1.02e＋01 2.06e＋01 5.34e－00 CDE 1.18e－02 2.13e－02 4.61e－02 8.60e－03 CDEG 8.88e－15 8.88e－15 8.88e－15 0 f10 1×104 GA－PSO 1.01e－00 1.28e－00 1.82e－00 2.01e－01 DE 1.55e－00 2.81e－00 7.80e－00 1.24e－00 CDE 8.29e－06 3.27e－05 1.29e－04 2.28e－05 CDEG 0 0 0 0 f11 5×104 GA－PSO 1.80e－09 3.55e－03 1.04e－01 1.86e－02 DE 1.57e－32 1.03－31 2.58e－30 4.61－31 CDE 1.57e－32 1.58e－32 1.70e－32 3.22e－34 CDEG 1.57e－32 1.57e－32 1.57e－32 5.47e－48 f12 5×104 GA－PSO 7.97e－11 4.14e－02 1.76e－01 4.75e－02 DE 1.17e－10 3.97e－03 5.43e－02 1.06e－02 CDE 1.35e－32 2.92e－32 4.64e－31 8.09e－32 CDEG 1.35e－32 1.48e－32 3.32e－32 4.92e－33

為更直觀地反映算法的尋優效果，將DE、GA－PSO、CDE和CDEH算法對相關測試函數的收斂曲線如圖1－圖5所示。由圖可知，本文提出的差分進化算法由于引入雜交和變異，使算法在處理多峰函數時能很快跳出局部最優，收斂到全局最優，在處理單峰函數時有較快的收斂的速度。

為進一步展示CDEG算法的先進性，我們將CDEG算法與文獻 ［14］中DEahcSPX、Orth－DE和ODE算法的結果進行比較，如表3所示。這3種算法的最大函數評價次數與文獻 ［14］相同，即300，000。從表中可以看出，CDEG算法在較少的函數評價次數下性能有較大幅度的改善，優化結果和理論值的誤差最小。

表3 4種算法對7個函數的計算結果比較

4 結束語

為了解決差分進化算法早熟收斂和收斂速度慢等問題，本文提出一種改進的協同差分進化算法。對12個函數尋優的實驗結果表明，本文算法在優化效率、優化性能和魯棒性方面比標準DE及其他改進的差分進化算法有了較大的改善。此外，將本文所提出的算法應用到多目標優化、約束優化、網絡組播路由、線性系統逼近、圖像處理等領域，將是我們下一步的研究工作。

［1］Stron R，Price K.Differential evolution：A survey of the state－ofthe－art ［J］.IEEE Transaction on Evolutionary Computation，2011，15（1）：4－31.

［2］Babu B B，Chakole P G，Mubeen J H S.Differential evolution strategy for optimal design of gas transmission network ［J］.Journal of Multidisciplinary Modeling in Materials and Struc－tures，2005，1（4）：315－328.

［3］Onwubolu G，Davendra D.Scheduling flow shops using differential evolution algorithm ［J］.European Journal of Operational Research，2006，171（2）：674－692.

［4］NING Guiying，ZHOU Yong.Improved differential evolution algorithm for finding all roots of equations ［J］.Computer Engineering and Design，2008，29（12）：3173－3176（in Chinese）.［寧桂英，周永.一類求解方程全部根的改進差分進化算法 ［J］.計算機工程與設計，2008，29（12）：3173－3176.］

［5］WANG Y，CAI Z X，ZHANG Q F.Differential evolution with composite trial vector generation strategies and control parameters ［J］.IEEE Transaction on Evolutionary Computation，2011，15（1）：55－66.

［6］Ali M M.Differential evolution with preferential crossover ［J］.European Journal of Operational Research，2007，181（3）：1137－1147.

［7］GONG W Y，CAI Z H，JIANG L X.Enhancing the performance of differential evolution using orthogonal design method ［J］.Applied Mathematics and Computation，2008，206（1）：56－69.

［8］Ali M M，Kajee－Bagdadi Z.A local exploration－based differential evolution algorithm for constrained global optimization ［J］.Applied Mathematics and Computation，2009，208（1）：31－48.

［9］Arijit B，Sambarta D，Swagatam D，et al.A synergy of differential evolution and bacterial foraging algorithm for global optimization［J］.Neural Network World，2007，17（6）：607－626.

［10］ZHANG J Q，Sanderson A C.JADE：Adaptive differential evolution with optional external archive ［J］.IEEE Transaction on Evolutionary Computation，2009，13（5）：945－958.

［11］Mininno E，Neri F，Cupertino F，et al.Compact differential evolution ［J］.IEEE Transaction on Evolutionary Computation，2009，15（1）：32－54.

［12］Dorronsoro B，Bouvry P.Improving classical and decentralized differential evolution with new mutation operator and population topologies ［J］.IEEE Transaction on Evolutionary Computation，2011，15（1）：67－98.

［13］Epitropakis M G，Tasoulis D K，Pavlidis N G，et al.Enhancing differential evolution utilizing proximity－based mutation operators ［J］.IEEE Transaction on Evolutionary Computation，2011，15（1）：99－119.

［14］Nasimul N，Hitoshi I.Accelerating differential evolution using an adaptive local search ［J］.IEEE Transaction on Evolutionary Computation，2008，12（1）：107－125.

［15］Rahnamayan S，Tizhoosh H R，Salama M A.Oppositionbased differential evolution ［J］.IEEE Transaction on Evolutionary Computation，2008，12（1）：107－125.

［16］KAO Y T，Erwie Z.A hybrid genetic algorithm and particle swarm optimization for multimodal functions ［J］.Applied Soft Computing，2008，8（2）：849－857.