蟻群遺傳算法對(duì)于TSP問(wèn)題的應(yīng)用

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

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

中圖分類(lèi)號(hào)：TG156

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

1 算法

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

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

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

（1）

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

（2）

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

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

（3）

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

父代1： 12|3456

父代2： 65|4321

交叉之后得到：

子代1： 12|4365

子代2： 65|3412

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

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

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

（4）

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

（5）

（6）

（7）

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

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

tall=ta+tg （8）

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

（9）

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

2 仿真

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

表1 仿真結(jié)果表

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

GA48953.2

ACS42625.6

GAACS42623.3

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

3 結(jié)束語(yǔ)

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

雖然在算法上有所改進(jìn)和提高，但是效果并不是很明顯，所以在對(duì)GAACS算法進(jìn)行應(yīng)用的時(shí)候，對(duì)其參數(shù)的設(shè)定，以及算法的融合使用還有待加強(qiáng)。可以看出，這一算法還具有很大的開(kāi)發(fā)潛力，筆者會(huì)繼續(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.

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

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