螞蟻算法的應(yīng)用與發(fā)展

葉 凡

(成都理工大學(xué) 管理科學(xué)學(xué)院，四川 成都 610059)

1 引言

螞蟻算法是一種用于解決搜索問(wèn)題的優(yōu)化方法。1992年，Dorigo在他的博士畢業(yè)論文中首次提出了此算法并用于解決了經(jīng)典的離散組合問(wèn)題商旅問(wèn)題、二次分配問(wèn)題。十多年來(lái)，螞蟻算法以及各種改進(jìn)過(guò)的螞蟻算法，被廣泛的應(yīng)用在實(shí)際生活的各個(gè)方面，應(yīng)用范圍不斷擴(kuò)大，在計(jì)算機(jī)技術(shù)應(yīng)用、交通控制，圖表制作等都有螞蟻算法的影響。

2 螞蟻算法簡(jiǎn)介

2.1 算法思想

螞蟻在路徑上前進(jìn)時(shí)會(huì)根據(jù)前邊走過(guò)的螞蟻所留下的分泌物選擇其要走的路徑，我們把這種分泌物叫做信息素。其選擇一條路徑的概率與該路徑上信息素的強(qiáng)度成正比。因此，由大量螞蟻組成的群體的集體行為實(shí)際上構(gòu)成一種學(xué)習(xí)信息的正反饋現(xiàn)象：某一條路徑走過(guò)的螞蟻越多，后面的螞蟻選擇該路徑的可能性就越大。螞蟻的個(gè)體間通過(guò)這種信息的交流尋求通向食物的最短路徑。

2.2 算法原理

下面介紹螞蟻算法的原理：第1步：初始化，NC=0，將m只螞蟻置于n個(gè)頂點(diǎn)上;第2步：將各螞蟻的初始出發(fā)點(diǎn)置于當(dāng)前解集中;對(duì)每一個(gè)螞蟻k，按概率P選擇移至下一頂點(diǎn)j上;將頂點(diǎn)j置于當(dāng)前解集;第3步：計(jì)算各螞蟻的目標(biāo)函數(shù)值;記錄當(dāng)前的最好解;第4步：按更新方程修改信息素軌跡強(qiáng)度;第5 步：對(duì)各邊弧(i，j)，Δτij=0，NC=NC+1;第 6 步：若搜索次數(shù)NC＜預(yù)定迭代次數(shù)且無(wú)退化行為(即找到的都是相同解)，則轉(zhuǎn)第二步;第7步：輸出目前的最好解。

2.3 基本螞蟻算法的優(yōu)缺點(diǎn)

(1)優(yōu)點(diǎn)：蟻群算法與其他啟發(fā)式算法相比，在求解性能上，具有很強(qiáng)的魯棒性和搜索較好解的能力，是一種基于種群的進(jìn)化算法，具有本質(zhì)并行性，易于并行實(shí)現(xiàn)，容易與多種啟發(fā)式算法結(jié)合，以改善算法性能。

(2)缺點(diǎn)：如果參數(shù)設(shè)置不當(dāng)，導(dǎo)致求解速度很慢且所得解的質(zhì)量特別差。計(jì)算量大，求解所需時(shí)間較長(zhǎng)實(shí)際操作中很難讓所有螞蟻都選擇最優(yōu)路線。

3 螞蟻算法的研究進(jìn)展

3.1 改進(jìn)的蟻群優(yōu)化算法

螞蟻優(yōu)化算法在提高螞蟻的搜索性能方面有著顯著的發(fā)展。但是在實(shí)際應(yīng)用中，不同的搜索優(yōu)化問(wèn)題，基本螞蟻算法受到了許多條件的局限，并且這些束縛都要根據(jù)具體問(wèn)題進(jìn)行相應(yīng)的處理，因此產(chǎn)生了許多改進(jìn)的螞蟻算法以適應(yīng)各領(lǐng)域的問(wèn)題特點(diǎn)。

(1)基于優(yōu)化排序的螞蟻系統(tǒng)

在螞蟻系統(tǒng)中加入遺傳算法排序的概念，當(dāng)每只螞蟻都走完一條路徑后，根據(jù)路徑長(zhǎng)度對(duì)螞蟻排序，根據(jù)該螞蟻的排名對(duì)激素軌跡量更新的貢獻(xiàn)進(jìn)行加權(quán)。只考慮其中最好的W只螞蟻，并要避免很多螞蟻過(guò)分重視某些局部極優(yōu)路徑的情況發(fā)生。

(2)最大-最小螞蟻算法。

該算法在蟻群算法的基礎(chǔ)上進(jìn)行了改進(jìn)，當(dāng)在最佳路徑上時(shí)，此路徑的信息素的跡才會(huì)增加，通過(guò)信息素的跡被限定在一個(gè)范圍內(nèi)，從而使得在當(dāng)前找出的最好路徑的領(lǐng)域內(nèi)螞蟻的搜索更集中。螞蟻算法的任務(wù)就是使問(wèn)題不斷地向著最優(yōu)化的方向進(jìn)行。該算法的本質(zhì)是對(duì)最優(yōu)的解進(jìn)行強(qiáng)化，并且對(duì)最差的解進(jìn)行弱化，使最優(yōu)路徑和最差路徑之間的差異化信息量變大，使螞蟻的搜索行為向最優(yōu)路徑集中。

(3)多群螞蟻算法。

Middendorf和Martin提出多群螞蟻算法，利用若干個(gè)蟻群并行操作，每次迭代完成后，蟻群之間交換一次信息。螞蟻間進(jìn)行交換信息的信息素有正信息素和負(fù)信息素兩種類型，進(jìn)而提高了尋優(yōu)過(guò)程的速度。MCAS在TSP和QAP問(wèn)題的求解上有比AS更好的表現(xiàn)。

螞蟻算法的改進(jìn)還可以與其他更多的智能算法進(jìn)行結(jié)合，在許多問(wèn)題上都能弱化自身單一的缺點(diǎn)，增強(qiáng)各自的優(yōu)點(diǎn)來(lái)改進(jìn)和完善算法的性能。

3.2 螞蟻算法在優(yōu)化問(wèn)題中的應(yīng)用

蟻群優(yōu)化算法已應(yīng)用于許多組合優(yōu)化問(wèn)題，包括蛋白質(zhì)折疊或路由車(chē)輛的二次分配問(wèn)題，很多派生的方法已經(jīng)應(yīng)用于實(shí)變量動(dòng)力學(xué)問(wèn)題，隨機(jī)問(wèn)題，多目標(biāo)并行的實(shí)現(xiàn)。它也被用于產(chǎn)生貨郎擔(dān)問(wèn)題的擬最優(yōu)解。下面分別介紹了螞蟻算法在不同領(lǐng)域中的基本應(yīng)用：

3.2.1 離散組合中的應(yīng)用

除TSP早期最為經(jīng)典以外，螞蟻算法早已應(yīng)用到其他離散組合優(yōu)化問(wèn)題中：二次分配問(wèn)題(QAP)指的是在n個(gè)地點(diǎn)分配n個(gè)設(shè)備使得分配代價(jià)最少，其實(shí)質(zhì)也是TSP問(wèn)題的一種。車(chē)間任務(wù)調(diào)度問(wèn)題(job-shop)指的是一組M臺(tái)機(jī)器和一組T個(gè)任務(wù)，任務(wù)有一組制定的將在這些機(jī)器上執(zhí)行的操作序列組成。還有許多問(wèn)題，如指派問(wèn)題、車(chē)輛路線問(wèn)題(VRP)、有序排列問(wèn)題(SOP)、圖著色問(wèn)題(GCP)，電力系統(tǒng)故障檢測(cè)等。

3.2.2 連續(xù)空間中的應(yīng)用

連續(xù)空間優(yōu)化問(wèn)題中的特點(diǎn)是隨著時(shí)間變化問(wèn)題的解決方案也在變化。其中通信網(wǎng)絡(luò)問(wèn)題是螞蟻算法解決連續(xù)空間優(yōu)化問(wèn)題中有代表性的一類問(wèn)題。在國(guó)際上，Sehoonderwerd，White等人在路由有向和網(wǎng)絡(luò)路由問(wèn)題中較早使用螞蟻算法.而Diearogy等人根據(jù)路由的自適應(yīng)問(wèn)題改進(jìn)了螞蟻算法并更適用于此類問(wèn)題的解決。在國(guó)內(nèi)，也有了基于解決的QoS路由調(diào)度問(wèn)題的螞蟻算法。

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

蟻群算法的本質(zhì)是受自然界啟發(fā)的一種隨機(jī)優(yōu)化算法，由于它具有很強(qiáng)的魯棒性和搜索較好解的能力使得在許多方面顯示出良好的計(jì)算性能。求解范圍由初始離散空間優(yōu)化的組合擴(kuò)大到約束多目標(biāo)和連續(xù)的空間區(qū)域，并在社會(huì)學(xué)宏觀領(lǐng)域表現(xiàn)出強(qiáng)大的生命力。但是，不是所有的基本螞蟻算法都能解決優(yōu)化問(wèn)題，改進(jìn)后的算法模型往往不是普遍適用，并且螞蟻在真實(shí)自然界中還有很多其他的智能行為可以研究。

［1]溫文波，杜維.蟻群算法綜述［J].石油化工自動(dòng)化，2002(1).

［3]張賢達(dá)，保錚.通信信號(hào)處理［M].北京：國(guó)防工業(yè)出版社，2000.