摘 要：遺傳算法和蟻群算法是兩種具有代表性的智能算法。在解決組合優(yōu)化問題時，遺傳算法具有較快的全局搜索能力，但在解決規(guī)模較大的TSP問題時存在一定缺陷，不能取得全局最優(yōu)解。相反蟻群算搜索速度相對較慢，但有著較高的準(zhǔn)確性，對于大規(guī)模問題有較好的效果。本文改進(jìn)了兩種算法，將蟻群算法與遺傳算法融化起來，得到最優(yōu)解。

關(guān)鍵詞：蟻群算法；遺傳算法；TSP

中圖分類號：TG156

很多學(xué)者將兩種算法融合，形成了一種更加有效的算法去解決問題。通過對遺傳算法的使用來對蟻群算法的相關(guān)參數(shù)進(jìn)行調(diào)整，將算法的思路進(jìn)一步優(yōu)化。另一種方式是根據(jù)二者各自優(yōu)勢，前期使用遺傳算法來對問題進(jìn)行搜索，再用蟻群算法來解決后續(xù)問題，以快速找到最優(yōu)解。基于這種模式，本文提出了自己的想法和思路。

1 算法

由于遺傳算法的前期搜索能力較強，蟻群算法針對較大規(guī)模問題解決的較快，本文融合兩種算法，前期用遺傳算法來對初始信息素進(jìn)行計算，求解問題的過程由蟻群算法來完成。

算法定義如下：設(shè)對于N個城市的旅行商問題，G（V，W）表示城市之間的聯(lián)通關(guān)系。其中V表示城市的集合，W表示任意兩個城市之間的距離的集合。我們用vi序號為i的城市，wij表示vi和vj間的距離。

針對TSP問題，我們在遺傳算法的編碼上采用十進(jìn)制的編碼方式，用一串十進(jìn)制數(shù)字表示基因。其中每一個基因片段表示一個城市，基因片段的順序決定了TSP問題中旅行商所走的順序。設(shè)系統(tǒng)中的基因數(shù)為Ng，我們定義Genei為系統(tǒng)中第i個基因，其中0≤i

（1）

設(shè)第i個基因的適應(yīng)度為fi，則有：

（2）

下面給出選擇操作，交叉操作和變異操作：

選擇操作是對于當(dāng)前代次的基因，選擇N個基因加入繁殖池進(jìn)行繁殖，選擇的概率依據(jù)pi。

（3）

sa交叉操作是從繁殖池中選出N/2對基因，進(jìn)行基因交叉。具體的操作如下：

父代1： 12|3456

父代2： 65|4321

交叉之后得到：

子代1： 12|4365

子代2： 65|3412

子代1和子代2分別選取父代1和父代2的前半部分，然后將父代2和父代1的后半部分中重復(fù)的部分剔除，再與前半部拼接而成。將生成的子代基因最為新一代的基因。

變異操作是指將新一代中的部分基因進(jìn)行變異以增加種群的多樣性。具體的操作是隨機選擇兩個基因片段進(jìn)行位置交換。下面我們介紹蟻群算法部分：

我們將M個螞蟻放置在系統(tǒng)中，每一只螞蟻將在當(dāng)前代次選擇一個路徑遍歷所有城市，其中每一步的選擇依賴于路徑上的信息素。設(shè)ρkij為螞蟻k下一步從城市i到城市j的概率，則有：

（4）

α和β分別表示信息因子和啟發(fā)因子，τij（t）表示t時刻城市i到城市j之間的信息素。tabuk表示k已經(jīng)訪問的城市集合。信息素的更新規(guī)則如下：

（5）

（6）

（7）

ηij（t）表示算法的啟發(fā)函數(shù)， 。1-θ表示揮發(fā)程度，0<θ<1。

我們設(shè)tall為總時間，ta和tg分別為蟻群算法和遺傳算法的時間。則有：

tall=ta+tg （8）

設(shè)Wayk表示第k個基因所對應(yīng)路徑上的邊的集合。對于已經(jīng)通過遺傳算法求出的解，我們通過下面的公式對其進(jìn)行信息素的分布：

（9）

算法的整體流程如下：（1）初始化Ng個基因。（2）計算適應(yīng)度。（3）進(jìn)行選擇操作。（4）進(jìn)行交叉操作。（5）計算適應(yīng)度進(jìn)行變異操作。（6）如果t

2 仿真

仿真主要是為了驗證我們所使用的算法的正確性和高效性，本文針對TSPLIB中的Eil51問題，通過三種算法來進(jìn)行仿真，分別是遺傳算法、蟻群算法和GAACS算法。在仿真計算的時候，有兩個問題非常關(guān)鍵，如下：（1）遺傳算法與蟻群算法的時間比。即ta/tg的取值。（2）遺傳算法解對于信息素分布的影響。即Qa與Qg的關(guān)系。通過10次仿真計算，得到了如下的結(jié)果：

表1 仿真結(jié)果表

最優(yōu)解時間（秒）

GA48953.2

ACS42625.6

GAACS42623.3

426是TSPLIB給出的最優(yōu)解，從上述結(jié)果可以我們知道，GAACS和ACS算法都可以得到最優(yōu)解，相反，GA算法不但求解時間長，還找不到最優(yōu)解。通過ACS和GAACS兩種算法的比較，GAACS算法的處理速度更加快速。我們也可以看出，雖然GAACS算法處理速度較快，但優(yōu)勢并不明顯，可能是在對參數(shù)進(jìn)行設(shè)計時有一定影響。

3 結(jié)束語

本文對遺傳算法、蟻群算法二者進(jìn)行了分析和比較，并將二者融合和改進(jìn)，發(fā)揮了各自的優(yōu)勢，得到了GAACS算法這一解決辦法。這一算法不但能夠繼承遺傳算法的快速搜索功能，還繼承了蟻群算法對大規(guī)模問題的處理能力，對解決TSP問題提供了很好的辦法，在工作效率上有大大的提高。

雖然在算法上有所改進(jìn)和提高，但是效果并不是很明顯，所以在對GAACS算法進(jìn)行應(yīng)用的時候，對其參數(shù)的設(shè)定，以及算法的融合使用還有待加強?？梢钥闯觯@一算法還具有很大的開發(fā)潛力，筆者會繼續(xù)進(jìn)行研究，去進(jìn)一步優(yōu)化算法。

參考文獻(xiàn)：

[1]HOLLAND JH. Adaptation in natural and artificial systems[M].

Ann Arbor：University of Michigan Press，1975.遺傳算法

[2]Bonabeau E， Dorigo M， Theraulaz G. Inspiration for optimization from social insect behavior [J].Nature，2000（06）：39-42

[3]段海濱.蟻群算法原理及其應(yīng)用[M].北京：科學(xué)出版社，2005.

作者簡介：王春波（1986.12-），男，吉林九臺人，碩士，研究方向：計算機網(wǎng)絡(luò)與通信。

作者單位：長春理工大學(xué) 計算機科學(xué)技術(shù)學(xué)院，長春 130022