高志娥　薛艷鋒　蘭靜

摘要摘要：蟻群優(yōu)化算法——螞蟻系統(tǒng)（Ant System，AS）是Dorigo M在20世紀(jì)90年代最早提出的一種新型生物智能算法，Dorigo M將蟻群優(yōu)化算法應(yīng)用于解決經(jīng)典的旅行商問題（TSP），取得了較好的應(yīng)用效果。采用混合型蟻群算法進行優(yōu)化求解，探討其實現(xiàn)TSP問題的求解流程，以更好地指導(dǎo)實際問題解決。

關(guān)鍵詞關(guān)鍵詞：蟻群優(yōu)化算法；混合型蟻群算法；TSP問題

DOIDOI：10.11907/rjdk.1431040

中圖分類號：TP312

文獻標(biāo)識碼：A文章編號文章編號：16727800（2015）004007302

0引言

TSP是一個典型的NP完全問題，沒有確定的算法能夠在多項式時間內(nèi)得到問題的解。因此，如何解決旅行商問題，具有很重要的實際應(yīng)用意義與價值。

TSP問題：假設(shè)有n個城市，每一個城市看作一個點，城市的實際距離轉(zhuǎn)化為點的距離，如何尋找一條遍歷所有城市且每個城市只被訪問一次的路徑，并保證總路徑距離最短。

其數(shù)學(xué)描述如下：

其中，K是V的全部非空子集，|K|是集合K中包含圖G的全部頂點的個數(shù)。

1蟻群算法基本原理

蟻群算法是一種新型的模擬生物習(xí)性的智能進化算法。蟻群算法又簡稱ACO算法，蟻群在搜索食物源過程中，總是表現(xiàn)出極好的尋優(yōu)路線，使得路程最短。蟻群算法模仿蟻群這一尋優(yōu)能力特性，解決了很多離散系統(tǒng)優(yōu)化問題。蟻群算法現(xiàn)已廣泛應(yīng)用于調(diào)度問題、旅行商問題（TSP問題）、指派問題、函數(shù)優(yōu)化問題等，均取得了較好的應(yīng)用效果[1]。

單只螞蟻的行為比較簡易，隨機地在搜索區(qū)域內(nèi)尋找食物，但由這樣的單只螞蟻組成的蟻群群體，則可以表現(xiàn)出極其復(fù)雜、信息共享的尋優(yōu)能力，究其原因主要是因為螞蟻個體之間的信息傳遞，稱之為信息素（pheromone）。螞蟻在尋找食物過程中，能夠在它所通過的路徑（位置）上留下信息素，并以此指導(dǎo)自己的運動方向，也可以給其它螞蟻提供參考作用[2]，且螞蟻特性是傾向于朝著信息素濃度高（向著食物源）的方向移動。

蟻群算法是一種隨機生物智能搜索算法，與其它生物智能算法一樣，通過初始化很多組可行解，然后通過迭代尋優(yōu)，即生物進化功能，來尋求最優(yōu)解。螞蟻的特性具體有以下3個方面：

（1）若一只螞蟻搜索過某條路徑，它在下次搜索時，就不會選擇該條路徑，映射到蟻群算法上，則需要建立禁忌列表模擬螞蟻的記憶功能。

（2）利用信息素實現(xiàn)個體之間的信息共享。

（3）螞蟻的群集活動。通過一只螞蟻的運動很難到達食物源（花費時間可能很長，且容易陷入局部最優(yōu)），但整個蟻群進行搜索效果則完全不同。蟻群這種行為足以讓螞蟻更加快速地找到食物，且能找到食物最好、最多的位置，也就避免了陷入局部最優(yōu)等缺陷[3]。

2基于混合型蟻群算法的TSP求解

蟻群算法ACO利用信息素進行信息互享，而粒子群優(yōu)化算法（又稱PSO算法）利用當(dāng)前個體的位置信息、當(dāng)前迭代前的個體極值與全局極值這3個信息，通過速度更新，達到個體的位置更新，從而實現(xiàn)問題的優(yōu)化求解。實驗研究表明，簡單的蟻群算法也容易出現(xiàn)早熟以及陷入局部最優(yōu)解等情況，且蟻群算法求解收斂速度不是很快，因此采用蟻群算法和粒子群算法的混合算法，可達到算法的互補，從而提高算法的收斂速度以及避免求解個體陷入局部最優(yōu)等[4]。

根據(jù)蟻群算法和粒子群算法的混合算法，螞蟻按照蟻群算法完成一次遍歷后，再讓螞蟻根據(jù)粒子群算法中的個體最優(yōu)極值和全局最優(yōu)極值進行螞蟻的位置調(diào)整，則蟻群算法和粒子群算法的混合算法應(yīng)用于旅行商問題的具體求解流程如下：

（1）nc←0；（nc為迭代次數(shù)），進行蟻群算法的參數(shù)初始化操作，產(chǎn)生大量的可行路徑（例如50條路徑），即可行解，從這50個可行路徑中選擇較好的路徑——旅行距離和最短，使螞蟻在這些初始路徑上留下信息素。

（2）根據(jù)螞蟻當(dāng)前位置計算適應(yīng)度值（各路徑的長度疊加和，滿足旅行商求解條件）ltsp0，計算當(dāng)前適應(yīng)值個體最優(yōu)極值，當(dāng)前位置為個體極值位置，根據(jù)各個粒子的個體極值，找出全局極值和全局極值位置。

（3）將各螞蟻的初始出發(fā)點置于當(dāng)前解集中，對每只螞蟻k（k=1，2，3，…，m），按照概率pkij移至下一頂點j，并將頂點j置于當(dāng)前解集。

（4）進入主循環(huán)，對每只螞蟻進行位置更新，第j只螞蟻路徑C0（f）與gcbest交叉得到C1（f），C1（f）與pcbest交叉、變異到C1（f），根據(jù)當(dāng)前位置計算路徑長度ltsp1，如果新的適應(yīng)度值更優(yōu)，則接受新的可行解值；否則拒絕，第j個粒子路徑C1（f）仍為C0（f），重新找到各只螞蟻的個體極值ptbest和極值位置pcbest，以及找出全局極值gtbest和全局極值位置gcbest。

（5）計算各螞蟻的路徑長度Lk（k=1，2，3…，m），記錄當(dāng)前的最好解。

（6）按螞蟻位置更新方程修改軌跡強度。

（7）對各邊?。╥，j），置Δτij←0，nc←nc+1。

（8）輸出目前最好解。

選取下列對象進行混合型蟻群算法的TSP問題分析，該地圖信息如圖1所示，包括30個城市，各城市之間的位置關(guān)系確定。選取軌跡相對重要性α=1.5，能見度相對重要性β=2，螞蟻數(shù)量m=30，軌跡持久性ρ=0.9，針對圖1所示城市位置關(guān)系，進行混合型蟻群算法尋優(yōu)求解，得到相應(yīng)的結(jié)果如圖2所示。

由圖2可知，該混合型蟻群算法具有快速收斂、不易陷入局部最優(yōu)的特點，避免了螞蟻個體局部早熟等現(xiàn)象發(fā)生，因此混合型蟻群算法較之于簡單的蟻群算法具有較好的應(yīng)用價值[5]。

3結(jié)語

蟻群算法是一種用來在圖中尋找優(yōu)化路徑的機率型

算法。該算法是一種新型的模擬進化算法，蟻群在搜索食物源的過程中，總是表現(xiàn)出極好的尋優(yōu)路線，蟻群算法模仿蟻群這一尋優(yōu)能力特性，解決了很多離散系統(tǒng)優(yōu)化問題。而在蟻群算法和粒子群算法的混合算法中，螞蟻根據(jù)粒子群算法中的個體最優(yōu)極值和全局最優(yōu)極值進行螞蟻的位置調(diào)整，使螞蟻具有“粒子”的特性，從而達到算法的互補，可提高算法的收斂速度以及避免求解個體陷入局部最優(yōu)等。

參考文獻參考文獻：

[1]曹振新，朱云龍.混流轎車總裝配線上物料配送的研究與實踐[J].計算機集成制造系統(tǒng)，2006，12（6）：289291.

[2]張文諾.基于Petri網(wǎng)的汽車生產(chǎn)物流流程仿真優(yōu)化研究[D].吉林：吉林大學(xué)，2007.

[3]王旭，張芳珍，李文川.汽車混流裝配線物料動態(tài)配送研究[J].電子技術(shù)應(yīng)用，2010，36（9）：4349.

[4]錢芳，扈靜，葛茂根，等.面向機械產(chǎn)品裝配過程的物料配送方法研究[J].機械工程師，2011（5）：3437.

[5]朱哲，薛善良，王珉，等.航天產(chǎn)品裝配物料配送系統(tǒng)的研究[J].中國制造業(yè)信息化，2012，41（15）：912.

責(zé)任編輯（責(zé)任編輯：黃?。?