張暉+王水清

【摘 要】差分進(jìn)化算法是一類基于群體的全局優(yōu)化結(jié)果的算法。本文對(duì)差分進(jìn)化算法的三個(gè)算子進(jìn)行研究，并將此算法與旅行商問(wèn)題結(jié)合，針對(duì)旅行商問(wèn)題進(jìn)行最短路徑優(yōu)化測(cè)試與研究。實(shí)驗(yàn)結(jié)果表明差分進(jìn)化算法對(duì)于最短路徑問(wèn)題有較好的效果。

【關(guān)鍵詞】差分進(jìn)化算法；旅行商；算子

1 差分進(jìn)化算法

差分進(jìn)化算法（differential evolution，DE）作為演化算法的一種，其主要流程具有與其他演化算法類似的特點(diǎn)，是一種模擬生物進(jìn)化的算法模型，通過(guò)分別差分算子的操作，對(duì)種群進(jìn)行不斷進(jìn)化的迭代操作，將適應(yīng)性最高的個(gè)體保存下來(lái)，即選取出符合條件的最優(yōu)解。其主要包含了對(duì)群體的初始化、對(duì)種群個(gè)體進(jìn)行差分操作、將變異操作取得的結(jié)果與原始種群進(jìn)行交叉、通過(guò)適應(yīng)性函數(shù)進(jìn)行對(duì)比來(lái)選擇最優(yōu)解個(gè)體四部分操作。

差分變異算法通過(guò)差分變異策略來(lái)對(duì)不同個(gè)體之前進(jìn)行隨機(jī)操作，從而實(shí)現(xiàn)個(gè)體變異。其具體操作是將從種群中隨機(jī)選取的兩個(gè)不相同的個(gè)體Xvb、Xvc，對(duì)這兩個(gè)不相同的個(gè)體進(jìn)行向量差的縮放操作之后，將縮放操作的結(jié)果和另外一個(gè)待變異個(gè)體X0a進(jìn)行合成。得到一個(gè)差分變異后的個(gè)體Xv（a+1）。

通過(guò)對(duì)待變異的種群個(gè)體Xva及其對(duì)應(yīng)的變異的中間體Xv（a+1）之間的進(jìn)行個(gè)體間的雜交操作，得到一個(gè)新的種群個(gè)體，交叉操作表示如下：

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

DE算法通過(guò)交叉操作可以得到一組經(jīng)過(guò)進(jìn)化之后的解，現(xiàn)在為了確定這組交叉之后的解是否能夠作為下一代的解，就要將原本最初的那一組解和這一組變異解進(jìn)行適應(yīng)性的比較，如果變異過(guò)后的解優(yōu)于原解，則將原解替換掉，否則，就保留原來(lái)的解。

差分進(jìn)化算法作為演化算法的一種，其主要流程具有與其他演化算法類似的特點(diǎn)，例如主要包含了對(duì)群體的初始化、對(duì)種群個(gè)體進(jìn)行差分操作、將變異操作取得的結(jié)果與原始種群進(jìn)行交叉、通過(guò)適應(yīng)性函數(shù)進(jìn)行對(duì)比來(lái)從所有的結(jié)果當(dāng)中選擇最優(yōu)解個(gè)體等。差分進(jìn)化算法的關(guān)鍵流程步驟與部分操作如下：

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

2）隨機(jī)生成初始種群。將進(jìn)化的代數(shù)G進(jìn)行+1操作，即G=G+1。

3）將目標(biāo)種群個(gè)體設(shè)置索引號(hào)a=1。

4）對(duì)目標(biāo)個(gè)體進(jìn)行差分變異操作，生成變異個(gè)體。

5）將目標(biāo)個(gè)體與變異個(gè)體進(jìn)行交叉，生成試驗(yàn)個(gè)體。

6）計(jì)算初始個(gè)體和試驗(yàn)個(gè)體的適應(yīng)度值，進(jìn)行對(duì)比，作出選擇。

7）目標(biāo)個(gè)體索引號(hào)a=a+1，跳轉(zhuǎn)到步驟5，一直循環(huán)到a=Np，否則跳轉(zhuǎn)到步驟8.

8）算法運(yùn)行循環(huán)到G=Gmax，表示差分進(jìn)化算法迭代完畢，輸出結(jié)果，否則跳轉(zhuǎn)運(yùn)行到步驟3。

2 差分進(jìn)化算法解決旅行商問(wèn)題

通過(guò)Matlab編程語(yǔ)言，實(shí)現(xiàn)基于差分進(jìn)化算法的對(duì)路徑優(yōu)化，分別帶入不同數(shù)目的樣本數(shù)據(jù)進(jìn)行仿真數(shù)據(jù)測(cè)試。增加數(shù)據(jù)的多樣性和可靠性，以下進(jìn)行的數(shù)據(jù)樣本優(yōu)化均進(jìn)行了300次的迭代操作，并具有原始路徑與經(jīng)過(guò)算法優(yōu)化過(guò)后的路徑對(duì)比，能夠簡(jiǎn)單直接的看出原始路徑和最優(yōu)路徑的差別。

3 以City10為數(shù)據(jù)樣本進(jìn)行仿真測(cè)試

City10數(shù)據(jù)坐標(biāo)的初始狀態(tài)如下所示：

以City10數(shù)據(jù)坐標(biāo)為樣本，通過(guò)算法優(yōu)化，得出最短路徑長(zhǎng)度是：276.6526，得出的最優(yōu)路徑如下所示：

通過(guò)Matlab繪圖工具，可以得出以City10數(shù)據(jù)坐標(biāo)為樣本的原始路徑和進(jìn)過(guò)差分進(jìn)化算法優(yōu)化過(guò)后的路徑對(duì)比如下圖1所示：

從圖1可以看出，對(duì)以City10數(shù)據(jù)坐標(biāo)為樣本進(jìn)行城市路徑模擬，使用差分進(jìn)化算法進(jìn)行原始路徑優(yōu)化后，優(yōu)化路徑的順序變?yōu)椋?、7、3、2、10、6、1、路徑優(yōu)化過(guò)后具有優(yōu)點(diǎn)：完成了所選取的路徑長(zhǎng)度是所有可行性路徑的最小值，即最優(yōu)解的任務(wù)目標(biāo)。對(duì)于City10問(wèn)題，原始路徑的總距離是665.1982，而差分進(jìn)化算法的總距離為276.6526，很明顯差分進(jìn)化算法求得的距離比原始路徑小很多，達(dá)到了路徑優(yōu)化的目的。

4 總結(jié)

本文主要實(shí)現(xiàn)了差分進(jìn)化算法中的定義參數(shù)與編碼初始化、種群初始化、差分變異操作、交叉操作和選擇操作，并用差分算法解決旅行商問(wèn)題，分別帶入不同的數(shù)據(jù)來(lái)驗(yàn)證差分進(jìn)化算法在旅行商問(wèn)題中的實(shí)用性和有效性。

【參考文獻(xiàn)】

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

[2]張春美.差分進(jìn)化算法理論與應(yīng)用 [M].北京：北京理工大學(xué)出版社，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.

[責(zé)任編輯：朱麗娜]