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

龍艷群，王蕾蕾（西安建筑科技大學(xué) 信息與控制工程學(xué)院，西安 710055）

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

龍艷群，王蕾蕾
（西安建筑科技大學(xué) 信息與控制工程學(xué)院，西安 710055）

針對遺傳算法收斂速度過慢的問題，將蟻群算法與遺傳算法相結(jié)合，應(yīng)用于求解旅行商問題，同時(shí)對兩種算法求解旅行商問題的結(jié)果進(jìn)行模擬與對比分析，實(shí)驗(yàn)結(jié)果表明結(jié)合算法可以有效地解決旅行商問題，在求解效率和求解質(zhì)量上都取得了很好的效果。

遺傳算法；蟻群遺傳結(jié)合算法；旅行商問題

1　前言

20世紀(jì)70年代以來，人工智能的應(yīng)用研究得到了迅速的發(fā)展，其中關(guān)于智能優(yōu)化算法的研究與應(yīng)用越來越多，遺傳和蟻群作為兩種比較流行的算法，都具有各自的優(yōu)勢，本文主要研究在對比兩種算法性能優(yōu)勢與不足的基礎(chǔ)上，采用兩種算法相結(jié)合來解決旅行商問題，從而避免單一算法的缺點(diǎn)。通過實(shí)驗(yàn)數(shù)據(jù)仿真表明，將蟻群與遺傳算法相結(jié)合可以更有效地解決旅行商問題。

2　旅行商問題（TSP）模型

“旅行商問題”也被稱為“旅行推銷員問題”，指一名推銷員要拜訪多個(gè)地點(diǎn)時(shí)，如何找到拜訪多個(gè)地點(diǎn)的最短路徑。求其最短路徑可以用數(shù)學(xué)模型表示：

假設(shè)路徑R=（c0，c1，…，cn-1），滿足 f（R）的值最小，則路徑R就是所求的路徑。

其中ci為城市號，i=（0，1，2，…，n-1）。d（ci，cj）表示城市ci到城市cj的距離。

2.1遺傳算法求解TSP

遺傳算法 （GA）是由美國Michignan大學(xué)的Holland于20世紀(jì)60年代提出的，其主要原理是以自然選擇和遺傳進(jìn)化論為基礎(chǔ)，模擬生物界的遺傳規(guī)律，對種群中的個(gè)體不斷進(jìn)化，達(dá)到產(chǎn)生更優(yōu)秀種群的目的。

該算法主要特點(diǎn)是：具有自組織、自適應(yīng)和自學(xué)習(xí)性，良好的全局優(yōu)化性和穩(wěn)健性，較強(qiáng)的魯棒性，易于和其他算法結(jié)合，計(jì)算過程簡單，操作性強(qiáng)。但存在早熟、收斂速度過慢等缺點(diǎn)。

2.2蟻群遺傳結(jié)合算法求解TSP

通過將遺傳算法與蟻群算法結(jié)合，形成一種全局優(yōu)化算法，使得遺傳算法和其他算法取長補(bǔ)短，有效提高了算法的收斂速度，并且還能防止早熟收斂，改進(jìn)的結(jié)合算法的具體實(shí)現(xiàn)是，利用蟻群算法經(jīng)過一次螞蟻全局循環(huán)，得到一個(gè)較優(yōu)解集，再將所獲得的優(yōu)解集作為遺傳算法的初始種群，加快遺傳算法的收斂速度，減少遺傳算法的尋優(yōu)次數(shù)，提高算法的執(zhí)行效率。

（1）初始化蟻群算法的信息啟發(fā)式因子α=1，期望值啟發(fā)式因子β=2，信息素?fù)]發(fā)系數(shù)ρ=0.1，信息素強(qiáng)度Q=100，其中路徑初始信息量為1，初始時(shí)刻為0。

（2）初始化螞蟻的位置，將m只螞蟻隨機(jī)分配到n個(gè)城市中。

（3）根據(jù)式（2）計(jì)算螞蟻k的狀態(tài)轉(zhuǎn)移概率，即選擇下一個(gè)城市概率。

（4）將新加入的城市移動(dòng)到螞蟻k的禁忌表中，更新禁忌表。

（5）重復(fù)步驟（3）、（4），分別求出每只螞蟻遍歷一次的路徑。

（6）將步驟（1）至（5）得到的m只螞蟻的遍歷的路徑作為遺傳算法的初始種群。

（7）初始化遺傳算法的交叉概率pc，變異概率 pm以及最大迭代次數(shù)的值。

（8）若i大于最大迭代次數(shù)，則結(jié)束循環(huán)，比較每次循環(huán)最短路徑，得到算法的最優(yōu)解。

下面通過實(shí)例來驗(yàn)證比較兩種算法求解TSP問題的實(shí)驗(yàn)結(jié)果。

表1　Oliver 30數(shù)據(jù)對比結(jié)果

通過以上實(shí)例數(shù)據(jù)的仿真對比分析，可以看出結(jié)合算法具有更好的優(yōu)化性能。

圖1　結(jié)合算法求解Oliver 30的最優(yōu)路徑

3　結(jié)語

本文采用的改進(jìn)的蟻群遺傳結(jié)合算法，通過蟻群算法迭代獲得一個(gè)較優(yōu)解集，作為遺傳算法的初始種群，然后采用遺傳算法尋求最優(yōu)解。實(shí)驗(yàn)仿真表明，結(jié)合算法在解決 TSP問題上具有較快的收斂速度和較強(qiáng)的全局尋優(yōu)能力。

主要參考文獻(xiàn)

［1］王超學(xué)，孔月萍，董麗麗.智能優(yōu)化算法與應(yīng)用［M］.西安：西北大學(xué)出版社，2012，9（1）.

［2］于瑩瑩，陳燕，李桃迎.改進(jìn)的蟻群遺傳算法求解旅行商問題［J］.計(jì)算機(jī)仿真，2013（11）：30-11.

10.3969/j.issn.1673-0194.2016.17.103

TP312

A

1673-0194（2016）17-0184-02

2016-07-19其解決TSP問題的流程說明：