混合型蟻群算法及其應(yīng)用

高志娥　薛艷鋒　蘭靜

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

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

DOIDOI：10.11907/rjdk.1431040

中圖分類號(hào)：TP312

文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)文章編號(hào)：16727800（2015）004007302

0引言

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

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

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

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

1蟻群算法基本原理

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

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

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

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

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

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

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

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

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

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

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

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

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

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

（6）按螞蟻位置更新方程修改軌跡強(qiáng)度。

（7）對(duì)各邊弧（i，j），置Δτij←0，nc←nc+1。

（8）輸出目前最好解。

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

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

3結(jié)語(yǔ)

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

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

參考文獻(xiàn)參考文獻(xiàn)：

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

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

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

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

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

責(zé)任編輯（責(zé)任編輯：黃健）