蔣騰旭

( 九江職業(yè)大學(xué)，江西 九江 332000)

0 引 言

旅行商問(wèn)題(Traveling Salesman Problem，TSP)又稱(chēng)貨郎擔(dān)問(wèn)題，其圖論描述是:給定圖G=(V，E)，其中V為頂點(diǎn)集，E為各頂點(diǎn)相互連接組成的邊集，已知各頂點(diǎn)間的邊接距離，要求確定一條長(zhǎng)度最短的Hamilton 回路，即遍歷所有頂點(diǎn)當(dāng)且僅當(dāng)一次的最短回路。TSP是一個(gè)著名的組合優(yōu)化問(wèn)題，也是一個(gè)典型的、易于描述卻難于處理的NP 完全問(wèn)題，它具有很高的實(shí)用意義和理論意義。在應(yīng)用中，像網(wǎng)絡(luò)路由優(yōu)化問(wèn)題、車(chē)輛路徑選擇與調(diào)度等問(wèn)題，其實(shí)質(zhì)就是TSP 問(wèn)題;而在理論上，TSP 問(wèn)題常常被用來(lái)衡量?jī)?yōu)化算法的有效性和作為評(píng)價(jià)其性能的標(biāo)準(zhǔn)。

遺傳算法(Genetic Algorithm，GA)［1］是一類(lèi)借鑒生物界自然選擇和自然遺傳機(jī)制的隨機(jī)化搜索算法，它是由美國(guó)Michigan 大學(xué)的J.Holland 教授于1975年首次提出的。遺傳算法模擬生物進(jìn)化的基本過(guò)程，用數(shù)碼串來(lái)類(lèi)比生物中的染色個(gè)體，通過(guò)選擇、交叉、變異等遺傳算子來(lái)仿真生物的基本進(jìn)化過(guò)程，利用適應(yīng)度函數(shù)來(lái)表示染色體所蘊(yùn)涵問(wèn)題解的質(zhì)量?jī)?yōu)劣，通過(guò)種群的不斷“更新?lián)Q代”，從而提高每代種群的平均適應(yīng)度，通過(guò)適應(yīng)度函數(shù)引導(dǎo)種群的進(jìn)化方向，并在此基礎(chǔ)上，使得最優(yōu)個(gè)體所代表的問(wèn)題解逼近問(wèn)題的全局最優(yōu)解。遺傳算法因其具有良好的魯棒性、可并行性與全局優(yōu)化性，因此在求解組合最優(yōu)化問(wèn)題時(shí)獲得了廣泛的應(yīng)用。但是，在實(shí)際應(yīng)用中，由于GA本質(zhì)上是一種基于概率的啟發(fā)式隨機(jī)搜索方法，GA也有自身的缺陷:如GA是對(duì)種群進(jìn)行概率性操作，在全局尋優(yōu)上效果良好，而在局部尋優(yōu)上存在不足;在算法進(jìn)行的前期搜索效果良好，而在算法進(jìn)行的后期搜索速度緩慢;GA 雖然實(shí)現(xiàn)簡(jiǎn)單，但實(shí)現(xiàn)的效果很大程度上取決于問(wèn)題的多種參數(shù)，如果這些參數(shù)設(shè)置不好，此時(shí)的GA 類(lèi)似隨機(jī)搜索算法，甚至?xí)霈F(xiàn)“早熟收斂”現(xiàn)象。

蟻群算法(Ant Colony Algorithm，ACA)［2］是受到人們對(duì)自然界中真實(shí)的蟻群集體行為研究成果的啟發(fā)而提出的一種基于蟻群的模擬進(jìn)化算法，屬于隨機(jī)搜索算法，由意大利學(xué)者M(jìn).Dorigo 等人于1991 年首次提出。作為一種仿生智能優(yōu)化算法，ACA 應(yīng)用的關(guān)鍵是既要使蟻群算法的搜索空間盡可能大，以尋找那些可能存在最優(yōu)解的解空間，又要充分利用螞蟻群體內(nèi)當(dāng)前所擁有的有用信息，使蟻群算法盡可能將搜索空間縮小到那些可能具有較高適應(yīng)值個(gè)體的解空間內(nèi)，以使蟻群算法以較大的概率收斂到全局最優(yōu)解。

ACA 群體間的信息交互主要通過(guò)信息素完成，算法收斂到最優(yōu)解的過(guò)程即為信息正反饋的動(dòng)態(tài)過(guò)程。這種正反饋機(jī)制能強(qiáng)化性能較好的解，但另一方面，由于在搜索的初期可利用的信息少，使得蟻群算法搜索時(shí)間較長(zhǎng);在搜索的中后期，由于正反饋機(jī)制的作用，有可能使算法陷于局部最優(yōu)。

1 GA與ACA的融合思路

一些研究表明，GA［3-5］沒(méi)有利用系統(tǒng)中的反饋信息，這往往導(dǎo)致無(wú)謂的冗余迭代，求解效率低。ACA［6-8］則通過(guò)信息素的累積和更新而收斂于最優(yōu)解，具有并行、分布、全局收斂特點(diǎn)，但初期信息素匱乏，導(dǎo)致算法收斂速度慢。許多學(xué)者［9-12］將遺傳算法與蟻群算法實(shí)行融合，以克服兩種算法各自的缺陷，形成優(yōu)勢(shì)互補(bǔ)，大體上有兩類(lèi):一類(lèi)是以蟻群算法為主體的混合蟻群算法，利用遺傳算法尋找蟻群算法中α、β、ρ的最優(yōu)組合;另一類(lèi)是以遺傳算法為主體的混合蟻群遺傳算法。

2 混合算法的改進(jìn)

本文在文獻(xiàn)［9，11］算法的基礎(chǔ)上，給出了一種改進(jìn)的遺傳蟻群混合算法，改進(jìn)后的混合算法通過(guò)個(gè)體適應(yīng)度的計(jì)算判定最優(yōu)解的改良情況，從而自動(dòng)尋找最優(yōu)融合點(diǎn)，通過(guò)動(dòng)態(tài)設(shè)置信息素全局更新參數(shù)，采用帶獎(jiǎng)懲項(xiàng)的信息素更新機(jī)制增強(qiáng)算法尋找全局最優(yōu)解的能力和加快算法的收斂速度。

2.1 串行融合點(diǎn)的設(shè)置

串行融合是在遺傳算法進(jìn)化到最優(yōu)點(diǎn)tbest之前采用遺傳算法生成初始信息素分布，以利用遺傳算法的全局搜索能力，避免早熟;在tbest點(diǎn)之后采用蟻群算法尋優(yōu)，以利用蟻群算法的正反饋機(jī)制，加速收斂。這里tbest點(diǎn)的控制是串行混合遺傳蟻群算法的關(guān)鍵，文獻(xiàn)［12］通過(guò)設(shè)置固定的遺傳迭代次數(shù)退出遺傳算法而進(jìn)入蟻群算法，這樣會(huì)造成遺傳算法過(guò)早或過(guò)晚結(jié)束，沒(méi)有實(shí)現(xiàn)兩者最佳時(shí)刻融合。本文的改進(jìn)措施是:

(1)對(duì)遺傳算法設(shè)置一迭代范圍［tmin，tmax］［12］，使tbest∈［tmin，tmax］。

則△Ft可用來(lái)判定解群中最優(yōu)解的改良情況。

(3)若連續(xù)若干代中，子代群體的改良率都小于某一指定的閾值(ξ)，表明此時(shí)遺傳算法的優(yōu)化速度降低，此時(shí)可保存GA 生成的若干組最優(yōu)解，結(jié)束遺傳算法進(jìn)入蟻群算法。

2.2 信息素更新規(guī)則的改進(jìn)

經(jīng)過(guò)遺傳算法的前期運(yùn)行，再運(yùn)用蟻群算法尋優(yōu)時(shí)，在前期，為保持解的多樣性，避免早熟收斂，最優(yōu)路徑與最差路徑上的信息素量差距不宜過(guò)大，以使蟻群算法保持較大的搜索空間;在后期，為加速收斂，確定信息素更新機(jī)制的指導(dǎo)思想是對(duì)可能是最優(yōu)解的潛在解進(jìn)行較大限度的信息素增強(qiáng)，而對(duì)最差解則進(jìn)行一定程度的信息素削弱，使得最優(yōu)路徑邊上的信息素量與最差路徑邊上的信息素量的差異進(jìn)一步增大，從而使蟻群的搜索行為更集中于最優(yōu)解的附近，以加速算法收斂。

還記得上小學(xué)三年級(jí)時(shí)，補(bǔ)習(xí)悄然成風(fēng)，無(wú)論優(yōu)生、差生，只要家長(zhǎng)愿意，統(tǒng)統(tǒng)請(qǐng)老師在每周唯一的星期天上午進(jìn)行有償補(bǔ)課。于是同學(xué)們就三個(gè)一群五個(gè)一伙，背著小書(shū)包到某同學(xué)家去補(bǔ)習(xí)兩個(gè)小時(shí)。老師按成績(jī)的優(yōu)劣分層教學(xué)，除了周末，寒暑假亦如此。一晃幾年過(guò)去了，幸運(yùn)的是我小學(xué)畢業(yè)后考上了九中（省屬重點(diǎn)中學(xué)），直到現(xiàn)在我也不明白是我天資聰慧，勤奮努力，還是后天老師進(jìn)行了大量的奧數(shù)補(bǔ)習(xí)而成。

基于以上分析，混合算法的蟻群信息素更新規(guī)則改進(jìn)如下:

當(dāng)每只螞蟻生成一條路徑時(shí)，按M.Dorigo 提出的蟻周模型［2，13］中信息素量局部更新策略進(jìn)行。

當(dāng)所有螞蟻完成一次循環(huán)后，應(yīng)用式(1)對(duì)所建立的路徑進(jìn)行信息素量的全局更新:

其中，

其中，0 ＜ρ ＜1，fgb表示全局最優(yōu)解，fib表示當(dāng)前循環(huán)中的最優(yōu)解，fiw表示當(dāng)前循環(huán)中最差解，τ(i，j)表示邊(i，j)上的信息素量，Δτ(i，j)表示邊(i，j)上的信息素增量。λ為獎(jiǎng)勵(lì)因子，0 ＜λ ＜1，γ為懲罰因子，-1＜γ ＜0，它們的定義為:

λ 及γ 公式中的△Ft為2.1 節(jié)定義的式(1)。λ 及γ 公式是典型的Logistic方程，式(4)及式(5)的作用如下:

在蟻群算法運(yùn)行的前期，解的多樣性較大，△Ft較大，λ 及∣γ∣較小，依據(jù)式(2)更新的最優(yōu)路徑與最差路徑上的信息素量差距不大，使蟻群算法保持了較大的搜索空間，可避免早熟收斂;在蟻群算法運(yùn)行的后期，解的多樣性較小，△Ft較小，λ 及∣γ∣較大，依據(jù)式(2)更新的最優(yōu)路徑與最差路徑上的信息素量差距逐漸變大，從而使蟻群的搜索行為更集中于最優(yōu)解的附近，加速算法收斂。

3 算法流程

本文提出的改進(jìn)遺傳蟻群混合算法求解TSP 流程可描述如下:

(1)運(yùn)用GA 生成若干組優(yōu)化解，其中，GA 采用遍歷城市的順序排列為編碼方案，采用順序交叉、逆轉(zhuǎn)變異、最優(yōu)個(gè)體保留及輪盤(pán)賭選擇策略，適應(yīng)度函數(shù)取為Hamilton 圈的長(zhǎng)度的倒數(shù);

(2)當(dāng)遺傳算法運(yùn)行效率較低時(shí)跳轉(zhuǎn)到(3)，進(jìn)入蟻群算法，否則轉(zhuǎn)到(1);

(3)初始化ACA 參數(shù)，其中的τ0按式τ0=τc+τg設(shè)置，其中，τc是依具體求解問(wèn)題模型給定的一個(gè)信息素常數(shù)，τg是遺傳算法結(jié)束時(shí)其求解結(jié)果轉(zhuǎn)換的信息素值;

(4)根據(jù)信息素初始分布，將m 只螞蟻隨機(jī)置于n個(gè)結(jié)點(diǎn);

(5)蟻群迭代過(guò)程的偽代碼如下:

(6)輸出計(jì)算結(jié)果。

4 實(shí)驗(yàn)結(jié)果及分析

本文選用TSPLIB中的Oliver30 和att48 作為仿真算例，以驗(yàn)證本文提出的算法性能，并與基本遺傳算法、基本蟻群算法求解Oliver30TSP 和att48TSP進(jìn)行比較［13-16］。

基本遺傳算法采用文獻(xiàn)［1］中的程序和參數(shù)，GA的參數(shù)為:染色體個(gè)數(shù)N=30，Pc=0.2，Pm=0.5，迭代次數(shù)為100?；鞠伻核惴ú捎梦墨I(xiàn)［2］中的蟻周模型，其參數(shù)設(shè)為:α=1.5，β=2，ρ=0.90，Q=80，m=30，Ncmax=100。本文提出的GACA的參數(shù)為:染色體個(gè)數(shù)N=30，Pc=0.2，Pm=0.5，α=1.5，β=2，m=30，ρ=0.90。最大迭代次數(shù)為100。對(duì)各種算法測(cè)試20 次，結(jié)果如表1、表2所示。

表1 幾種算法測(cè)試Oliver30TSP 20 次的結(jié)果

表2 幾種算法測(cè)試att48TSP 20 次的結(jié)果

從表1 及表2 可以看出，采用本文提出的混合算法求解Oliver30 和att48，其最優(yōu)解的質(zhì)量均有明顯的提高。例如，本文提出的算法求解att48 平均值誤差為0.4057%，而GA 及ACA分別為15.0349%、6.7180%，可見(jiàn)，與GA 及ACA 相比，本文算法求解質(zhì)量有了一定提高。

另外，文獻(xiàn)［13］實(shí)驗(yàn)數(shù)據(jù)表明，GA 及ACA 在固定的100 次迭代次數(shù)內(nèi)，無(wú)法收斂到TSPLIB 提供的Oliver30 及att48 已知最優(yōu)解上，而本文提出的GACA平均在第68 代收斂到Oliver30 已知最優(yōu)解，平均在第78 代收斂到att48 已知最優(yōu)解。由此可見(jiàn)，本文提出的GACA的收斂速度較單純的GA 及ACA 要快。

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

本文利用遺傳算法和蟻群算法的特性，通過(guò)判定最優(yōu)解的改良情況，動(dòng)態(tài)設(shè)置最佳融合點(diǎn)，使GA 和ACA 實(shí)現(xiàn)最佳時(shí)機(jī)串行融合，形成優(yōu)勢(shì)互補(bǔ)。針對(duì)ACA中信息素在正反饋過(guò)程中的重要作用，通過(guò)動(dòng)態(tài)設(shè)置信息素全局更新參數(shù)，提出了一種帶獎(jiǎng)懲項(xiàng)的信息素更新機(jī)制，使得本文提出的GACA 混合算法在深度搜索和廣度搜索之間取得了較好的平衡。實(shí)驗(yàn)結(jié)果表明，本文提出的遺傳蟻群混合算法在求解TSP方面其求解速度和解的品質(zhì)均優(yōu)于基本蟻群算法和遺傳算法，求解效果比較好。

［1］李敏強(qiáng)，寇紀(jì)淞，林丹，等.遺傳算法的基本理論與應(yīng)用［M］.北京:科學(xué)出版社，2002.

［2］李士勇，陳永強(qiáng)，李研.蟻群算法及其應(yīng)用［M］.哈爾濱:哈爾濱工業(yè)大學(xué)出版社，2004.

［3］王小平，曹立明.遺傳算法——理論、應(yīng)用與軟件實(shí)現(xiàn)［M］.西安:西安交通大學(xué)出版社，2002.

［4］張文修，梁怡.遺傳算法的數(shù)學(xué)基礎(chǔ)［M］.西安:西安交通大學(xué)出版社，2001.

［5］高尚.基于MATLAB 遺傳算法優(yōu)化工具箱的優(yōu)化計(jì)算［J］.微型電腦應(yīng)用，2002，18(8):52-54.

［6］陳永強(qiáng).人工蟻群算法及其在組合優(yōu)化中的應(yīng)用［D］.哈爾濱:哈爾濱工業(yè)大學(xué)，2003.

［7］侯文靜，馬永杰，張燕，等.求解TSP的改進(jìn)蟻群算法［J］.計(jì)算機(jī)應(yīng)用研究，2010，27(6):2087-2089.

［8］陳建軍.蟻群算法在物流配送路徑優(yōu)化中的研究［J］.計(jì)算機(jī)仿真，2011，28(2):268-271.

［9］丁建立，陳增強(qiáng)，袁著祉.遺傳算法與螞蟻算法的融合［J］.計(jì)算機(jī)研究與發(fā)展，2003，40(9):1531-1536.

［10］劉立東，蔡淮.融入遺傳算法的混合蟻群算法［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2008，29(5):1248-1249，1252.

［11］曹文梁，康嵐蘭.基于遺傳算法的混合蟻群算法及其在TSP中的應(yīng)用研究［J］.制造業(yè)自動(dòng)化，2011，33(1):91-93.

［12］段海濱.蟻群算法原理及其應(yīng)用［M］.北京:科學(xué)出版社，2005.

［13］Dorigo M，Maniezzo V，Colorni A.Ant system:Optimization by a colony of cooperating agents［J］.IEEE Transactions on Systems，Man，and Cybernetics，Part B:Cybernetics，1996，26(1):29-41.

［14］Thomas S，Holger H H.MAX-MIN ant systems［J］.Future Generation Computer Systems，2000，16(9):889-914.

［15］Universit?t Heidelberg.att48.tsp.gz［DB/OL］.http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/tsp/，2008-08-06.

［16］TSP.Tourning the United States［EB/OL］.http://www.tsp.gatech.edu/data/usa，2013-07-20.