差分優化算法及其應用

張暉+王水清

【摘 要】差分進化算法是一類基于群體的全局優化結果的算法。本文對差分進化算法的三個算子進行研究，并將此算法與旅行商問題結合，針對旅行商問題進行最短路徑優化測試與研究。實驗結果表明差分進化算法對于最短路徑問題有較好的效果。

【關鍵詞】差分進化算法；旅行商；算子

1 差分進化算法

差分進化算法（differential evolution，DE）作為演化算法的一種，其主要流程具有與其他演化算法類似的特點，是一種模擬生物進化的算法模型，通過分別差分算子的操作，對種群進行不斷進化的迭代操作，將適應性最高的個體保存下來，即選取出符合條件的最優解。其主要包含了對群體的初始化、對種群個體進行差分操作、將變異操作取得的結果與原始種群進行交叉、通過適應性函數進行對比來選擇最優解個體四部分操作。

差分變異算法通過差分變異策略來對不同個體之前進行隨機操作，從而實現個體變異。其具體操作是將從種群中隨機選取的兩個不相同的個體Xvb、Xvc，對這兩個不相同的個體進行向量差的縮放操作之后，將縮放操作的結果和另外一個待變異個體X0a進行合成。得到一個差分變異后的個體Xv（a+1）。

通過對待變異的種群個體Xva及其對應的變異的中間體Xv（a+1）之間的進行個體間的雜交操作，得到一個新的種群個體，交叉操作表示如下：

其中，CR代表交叉概率，rand（0，1）產生一個在0～1區間內的一個隨機實數，將其與交叉概率CR比較，如果此時隨機數小于等于交叉概率CR，將選擇變異操作中產生的變異個體的一個解作為此時交叉的結果，這里的是取值范圍在[1，2，3…，D]之間的整數，j=jrand是為了保證變異操作的有效性，來保證交叉結果中存在一個變異個體的一個解。

DE算法通過交叉操作可以得到一組經過進化之后的解，現在為了確定這組交叉之后的解是否能夠作為下一代的解，就要將原本最初的那一組解和這一組變異解進行適應性的比較，如果變異過后的解優于原解，則將原解替換掉，否則，就保留原來的解。

差分進化算法作為演化算法的一種，其主要流程具有與其他演化算法類似的特點，例如主要包含了對群體的初始化、對種群個體進行差分操作、將變異操作取得的結果與原始種群進行交叉、通過適應性函數進行對比來從所有的結果當中選擇最優解個體等。差分進化算法的關鍵流程步驟與部分操作如下：

1）對差分進化算法中所有相關的參數進行初始化，初始設為當前代數G=0，最大迭代次數Gmax、種群規模大小Np、交叉概率CR、差分縮放因子F和每一個種群所涉及的解的維度D。

2）隨機生成初始種群。將進化的代數G進行+1操作，即G=G+1。

3）將目標種群個體設置索引號a=1。

4）對目標個體進行差分變異操作，生成變異個體。

5）將目標個體與變異個體進行交叉，生成試驗個體。

6）計算初始個體和試驗個體的適應度值，進行對比，作出選擇。

7）目標個體索引號a=a+1，跳轉到步驟5，一直循環到a=Np，否則跳轉到步驟8.

8）算法運行循環到G=Gmax，表示差分進化算法迭代完畢，輸出結果，否則跳轉運行到步驟3。

2 差分進化算法解決旅行商問題

通過Matlab編程語言，實現基于差分進化算法的對路徑優化，分別帶入不同數目的樣本數據進行仿真數據測試。增加數據的多樣性和可靠性，以下進行的數據樣本優化均進行了300次的迭代操作，并具有原始路徑與經過算法優化過后的路徑對比，能夠簡單直接的看出原始路徑和最優路徑的差別。

3 以City10為數據樣本進行仿真測試

City10數據坐標的初始狀態如下所示：

以City10數據坐標為樣本，通過算法優化，得出最短路徑長度是：276.6526，得出的最優路徑如下所示：

通過Matlab繪圖工具，可以得出以City10數據坐標為樣本的原始路徑和進過差分進化算法優化過后的路徑對比如下圖1所示：

從圖1可以看出，對以City10數據坐標為樣本進行城市路徑模擬，使用差分進化算法進行原始路徑優化后，優化路徑的順序變為：9、7、3、2、10、6、1、路徑優化過后具有優點：完成了所選取的路徑長度是所有可行性路徑的最小值，即最優解的任務目標。對于City10問題，原始路徑的總距離是665.1982，而差分進化算法的總距離為276.6526，很明顯差分進化算法求得的距離比原始路徑小很多，達到了路徑優化的目的。

4 總結

本文主要實現了差分進化算法中的定義參數與編碼初始化、種群初始化、差分變異操作、交叉操作和選擇操作，并用差分算法解決旅行商問題，分別帶入不同的數據來驗證差分進化算法在旅行商問題中的實用性和有效性。

【參考文獻】

[1]郁磊，史峰，王輝，胡斐.MATLAB智能算法30個案例分析（2版）[M].北京：北京航空航天大學出版社，2015：10-52.

[2]張春美.差分進化算法理論與應用 [M].北京：北京理工大學出版社，2014：22-45.

[3]N. Hansen， A. Auger， S. Finck， and R.Ros，“Real-parameter black-box optimization benchmarking 2012： Experimental setup，” Dept. Comput.Sci. Contr.， INRIA， France， Tech. Rep.， Mar. 2012.

[4] J. J. Liang， B. Y. Qu， P. N. Suganthan， and A. G. Hernandez-Diaz，“Problem definitions and evaluation criteria for the CEC 2013 special session on real-parameter optimization，” Zhengzhou Univ.， China， and Nanyang Technol. Univ.， Singapore， Tech. Rep. 201212， Jan. 2013.

[責任編輯：朱麗娜]