基于改進(jìn)的遺傳算法求解旅行商問題

吳軍++嚴(yán)麗娜

【摘 要】論文提出了一種改進(jìn)的遺傳算法求解旅行商問題（TSP）。該算法結(jié)合TSP的特點，采用實數(shù)編碼方式減少算法計算復(fù)雜度；等位交叉方式擴(kuò)大算法的搜索空間，改善尋優(yōu)能力；輪盤賭選擇策略加快算法的收斂速度。通過30個城市的benchmark實例進(jìn)行仿真試驗，試驗結(jié)果表明，改進(jìn)的遺傳算法改善了全局搜索能力，具有較快的收斂速度和較高的收斂精度。

【Abstract】In this paper， an improved genetic algorithm for traveling salesman problem （TSP） is proposed.The algorithm combines the characteristics of TSP， using real number encoding to reduce the computational complexity of the algorithm， a cross way to expand the search space and improve searching ability， roulette selection strategy to accelerate the convergence of the algorithm.In this paper， it has simulated benchmark examples in thirty cities.The simulation results show that the improved genetic algorithm can improve the global search ability， and its convergence speed and the convergence precision is higher.

【關(guān)鍵詞】旅行商問題；遺傳算法；收斂速度

【Keywords】traveler problem；genetic algorithm；convergence precision

【中圖分類號】TP18 【文獻(xiàn)標(biāo)志碼】A 【文章編號】1673-1069（2017）03-0096-03

1 引言

旅行商問題（TSP）也稱貨郎擔(dān)問題，它旨在尋求旅行商在遍歷諸多城市一次最后回到起點城市的最短路徑，是數(shù)學(xué)圖論中的經(jīng)典問題。在實際生活中，像物流路徑優(yōu)化、車間調(diào)度和網(wǎng)絡(luò)路由選址等都可歸結(jié)為TSP，因此，TSP的研究具有重要的理論意義和實際價值。

Karp[1]證明了TSP是一個NP難問題，傳統(tǒng)的優(yōu)化算法在求解TSP問題時往往會陷入局部最優(yōu)，尤其隨著城市數(shù)量的增加，計算量也急劇增加，致使很多算法癱瘓。因此智能優(yōu)化算法強(qiáng)的搜索效率、快速的收斂速度在求解TSP中得到了廣泛應(yīng)用。Aziz[2]提出了廣義的蟻群算法，算法中融合了局部和全局兩種信息素更新機(jī)制，提高全局迅游能力。何湘竹[3]將混沌搜索機(jī)制融入基于教與學(xué)的優(yōu)化算法求解TSP，通過benchmark實例仿真試驗顯示，新算法性能更優(yōu)越。段艷明[4]將果蠅優(yōu)化算法的連續(xù)空間對應(yīng)到離散規(guī)劃，利用了遺傳算法的交叉、變異操作進(jìn)行路徑的尋優(yōu)，加快局部搜索能力和收斂速度。

遺傳算法是一種模擬生物進(jìn)化過程的隨機(jī)搜索優(yōu)化方法，與其他的局部搜索算法相比，遺傳算法具有更強(qiáng)的魯棒性，隱形的并行搜索機(jī)制增強(qiáng)了算法尋優(yōu)能力，但遺傳算法也存在缺陷，例如： 種群常常會出現(xiàn)早熟收斂、易陷入局部最優(yōu)的問題，使算法的搜索性能大大降低[5]。針對這些問題，學(xué)者提出了許多解決方法，如參數(shù)控制、多種群的運(yùn)用和交配限制[6-8]等。

2 求解TSP的改進(jìn)遺傳算法

鑒于目前遺傳算法在優(yōu)化領(lǐng)域的優(yōu)越性能，論文以TSP為例，提出了改進(jìn)的遺傳算法。

2.1 實數(shù)編碼

對包含n個城市的TSP問題，我們提出一種新的有效編碼方法——實數(shù)編碼。它是指整數(shù)1到的一個全排列所構(gòu)成的實數(shù)序列a1，a2，…，an，其中a∈[1，n）之間的整數(shù)，編碼中ai表示編號為的城市排在路徑上的第ai個位置。

2.2 輪盤賭選擇

輪盤賭選擇法是遺傳算法中常用的選擇方式，首先計算每個個體的適應(yīng)度值fi，i∈[1，ps），ps為種群規(guī)模。這里fi的值越大，說明這個個體越優(yōu)秀；其次，計算每個個體的選擇概率pi=fi/（∑fi）和累積概率Pi=∑■■pi；最后，隨機(jī)產(chǎn)生一個實數(shù)num∈[0，1]，選取滿足num

2.3 等位交叉

交叉算子是遺傳算法中關(guān)鍵的操作，它涉及種群的多樣性和算法的搜索效率等，論文基于等位交叉來改變兩個交叉?zhèn)€體的局部基因片段，使每個個體都能遺傳到對方的基因。具體操作如圖1所示。

■

圖1 等位交叉具體操作圖

2.4 改進(jìn)的遺傳算法

基于以上操作算子，求解 TSP的改進(jìn)遺傳算法步驟如下：

步驟1 初始化遺傳算法種群個數(shù)ps、最大迭代次數(shù)inmax、交叉概率pc和變異概率pm等；

步驟2 根據(jù)各城市的坐標(biāo)計算各個城市之間的距離，記作Cij，i，j∈[1，n]，代表第i個城市到第j個城市的距離，初始生成ps個個體，即ps個城市路線；

步驟3 計算每條路線的距離Si，計算適應(yīng)度值根據(jù)公式fi=1/Si，計算選擇概率pi=fi/（∑fi）和累積概率Pi=∑■■pi；

步驟4 根據(jù)選擇概率和累積概率采用輪盤賭選擇法選擇要交叉的兩個個體；

步驟5 根據(jù)交叉概率判斷是否交叉，交叉采用等位交叉法，產(chǎn)生兩個等位基因互換的兩個交叉?zhèn)€體；

步驟6 根據(jù)變異概率判斷是否變異，選擇變異基因位置，隨機(jī)產(chǎn)生基因片段，替換要變異的基因片段，產(chǎn)生新個體；

步驟7 計算新個體的適應(yīng)度值，依據(jù)適應(yīng)度值判斷保留新個體還是原個體。循環(huán)迭代，返回步驟3，當(dāng)?shù)螖?shù)達(dá)到最大結(jié)束算法；

步驟8 輸出最優(yōu)解，畫出路線圖。

3 仿真試驗及分析

為了驗證該算法的正確性和有效性，選用30個城市的benchmark實例進(jìn)行仿真實驗。

3.1 實驗測試環(huán)境與參數(shù)設(shè)置

實驗測試環(huán)境為：操作系統(tǒng)Windows 7，處理器為Intel（R） Core（TM）i3-2350，CPU@2.30GHz，內(nèi)存6GB，編程軟件MATLAB R2010a。種群設(shè)置為100，對于算例Oliver30最大迭代次數(shù)設(shè)置為200，交叉概率pc=0.8，變異概率pm=0.4。

3.2 試驗結(jié)果及分析

通過遺傳算法對30個城市的benchmark實例進(jìn)行20次測試得到其最優(yōu)解，數(shù)據(jù)結(jié)果如表1所示。表1列舉了該算法20次獨立運(yùn)行結(jié)果，最優(yōu)值表示20次獨立運(yùn)行中最好結(jié)果，最差值表示20次獨立運(yùn)行中最差結(jié)果，平均值表示20次獨立運(yùn)行結(jié)果的平均值，已知最優(yōu)值表示目前TSPLB標(biāo)準(zhǔn)庫收錄的最優(yōu)結(jié)果。

表1 TSP測試結(jié)果

■

由表1試驗結(jié)果可以看出，該算法在求解TSP中有較好的效果，20次獨立運(yùn)行結(jié)果中最好值423.949與標(biāo)準(zhǔn)數(shù)據(jù)庫中最好值423.7406相差0.2084，誤差結(jié)果在可以接受的范圍，平均值424.4247與最優(yōu)值423.949相差0.4757，表明該算法對求解TSP具有較高的穩(wěn)定性。

圖2中給出了算法迭代200次的部分路線圖，分別是第50、第100和第200代結(jié)果，由圖可以看出，算法在運(yùn)行至第100次時，結(jié)果430.8781已經(jīng)接近最優(yōu)值，表明算法有較強(qiáng)的收斂能力，第200次結(jié)果423.949非常接近已知最優(yōu)值，表明了算法具有較強(qiáng)的全局搜索能力。圖3給出了該算法是以寧都值變化圖，也可直觀地看出該算法具有較強(qiáng)的收斂性能。

【參考文獻(xiàn)】

【1】Karp R.M. Reducibility Among Combinatorial Problems. Plenum Press. 1972：85-103.

【2】Zalilah Abd Aziz. Ant Colony Hyper-heuristics for Travelling Salesman[J]. Procedia Computer Science.2015，76：534-538.

【3】何湘竹.一種改進(jìn)的基于教與學(xué)的優(yōu)化算法求解旅行商問題[J].中南民族大學(xué)學(xué)報（自然科學(xué)版）.2015，34（4）：89-93.

【4】段艷明，肖輝輝.求解TSP問題的改進(jìn)果蠅優(yōu)化算法[J].計算機(jī)工程與應(yīng)用，2016，52（6）：144-149.

【5】Park T，Ryu K R. A dual population genetic algorithm with evolving diversity[C]. IEEE Congress on Evolutionary Computation. 2007： 3516-3522.

【6】黃江波，付志紅.基于自適應(yīng)遺傳算法函數(shù)優(yōu)化與仿真[J].計算機(jī)仿真，2011，28（5）：237-240.

【7】鞏敦衛(wèi)，孫曉燕.變搜索區(qū)域多種群遺傳算法[J].控制理論與應(yīng).2006，23（2）：256-260.

【8】徐曉艷.基于聚類思想的改進(jìn)混合遺傳算法[D].北京：北京工業(yè)大學(xué)計算機(jī)學(xué)院，2013.