基本蟻群算法

1、蟻群算法淺析摘要：介紹了什么是蟻群算法，蟻群算法的種類，對四種不同的蟻群算法進(jìn)行了分析對比。 詳細(xì)闡述了蟻群算法的基本原理，將其應(yīng)用于旅行商問題，有效地解決了問題。通過對旅行 商問題C+莫擬仿真程序的詳細(xì)分析，更加深刻地理解與掌握了蟻群算法。 關(guān)鍵詞：蟻群算法；旅行商問題；信息素；輪盤選擇 一、引言蟻群算法( Ant Colony Optimization, ACO )，是一種用來在圖中尋找優(yōu)化路徑的算法。 它由 Marco Dorigo 于 1992 年在他的博士論文中提出，其靈感來源于螞蟻在尋找食物過程中 發(fā)現(xiàn)路徑的行為。蟻群算法是一種莫擬進(jìn)化算法，初步的研究表明該算法具有許多優(yōu)良的性 質(zhì)

2、。蟻群算法成功解決了旅行商問題( Traveling Salesman Problem, TSP )：一個(gè)商人要到 若干城市推銷物品，從一個(gè)城市出發(fā)要到達(dá)其他各城市一次而且最多一次最后又回到第一個(gè) 城市。尋找一條最短路徑，使他從起點(diǎn)的城市到達(dá)所有城市一遍，最后回到起點(diǎn)的總路程最 短。若把每個(gè)城市看成是圖上的節(jié)點(diǎn)，那么旅行商問題就是在N個(gè)節(jié)點(diǎn)的完全圖上尋找一條花費(fèi)最少的回路。最基本的蟻群算法見第二節(jié)。目前典型的蟻群算法有隨機(jī)蟻群算法、排序蟻群算法和最大最小蟻群算法，其中后兩種蟻群算法是對前一種的優(yōu)化。本文將終點(diǎn)介紹隨機(jī)蟻群算法。二、基本蟻群算法(一)算法思想各個(gè)螞蟻在沒有事先告訴他們食物在什么地

3、方的前提下開始尋找食物。當(dāng)一只找到食物 以后，它會(huì)向環(huán)境釋放一種信息素，信息素多的地方顯然經(jīng)過這里的螞蟻會(huì)多，因而會(huì)有更 多的螞蟻聚集過來。假設(shè)有兩條路從窩通向食物，開始的時(shí)候，走這兩條路的螞蟻數(shù)量同樣 多(或者較長的路上螞蟻多， 這也無關(guān)緊要)。當(dāng)螞蟻沿著一條路到達(dá)終點(diǎn)以后會(huì)馬上返回來， 這樣，短的路螞蟻來回一次的時(shí)間就短，這也意味著重復(fù)的頻率就快，因而在單位時(shí)間里走 過的螞蟻數(shù)目就多，灑下的信息素自然也會(huì)多，自然會(huì)有更多的螞蟻被吸引過來，從而灑下 更多的信息素。因此，越來越多地螞蟻聚集到較短的路徑上來，最短的路徑就找到了。蟻群算法的基本思想如下圖表示：圖1等概率選擇圖2最優(yōu)路徑圖3最優(yōu)比重

4、（二）算法描述基本蟻群算法的算法簡單描述如下：1 所有螞蟻遇到障礙物時(shí)按照等概率選擇路徑，并留下信息素;2 隨著時(shí)間的推移，較短路徑的信息素濃度升高；3 螞蟻再次遇到障礙物時(shí)，會(huì)選擇信息素濃度高的路徑；4 較短路徑的信息素濃度繼續(xù)升高，最終最優(yōu)路徑被選擇出來。三、隨機(jī)蟻群算法（一）算法思想在基本蟻群算法中，螞蟻會(huì)在多條可選擇的路徑中，自動(dòng)選擇出最短的一條路徑。但是, 一旦蟻群選擇了一條比之前短的路徑，就會(huì)認(rèn)為這條路徑是最好的，在這條路徑上一直走下 去。這樣的算法存在問題：螞蟻可能只是找到了局部的最短路徑，而忽略了全局最優(yōu)解。因此，在基本蟻群算法的基礎(chǔ)上，需要對螞蟻選路的方案加以改善：有些螞蟻并

5、沒有象 其它螞蟻一樣總重復(fù)同樣的路，他們會(huì)另辟蹊徑，也就是它會(huì)按照一定的概率不往信息素高 的地方。如果令開辟的道路比原來的其他道路更短，那么，漸漸地，更多的螞蟻被吸引到這 條較短的路上來。最后，經(jīng)過一段時(shí)間運(yùn)行，可能會(huì)出現(xiàn)一條最短的路徑被大多數(shù)螞蟻重復(fù) 著，這就是優(yōu)化的隨機(jī)蟻群算法。為了實(shí)現(xiàn)螞蟻的“隨機(jī)”選路，我們需要做以下假設(shè)：1 范圍：螞蟻觀察到的范圍是一個(gè)方格世界，螞蟻有一個(gè)參數(shù)為速度半徑，如果半徑等 于 2 ，那么它能觀察到的范圍就是 2*2 個(gè)方格世界，并且能移動(dòng)的距離也在這個(gè)范圍之內(nèi)。2環(huán)境：環(huán)境以一定的速率讓信息素消失。3覓食規(guī)則：在每只螞蟻能感知的范圍內(nèi)尋找是否有食物，如果有就

6、直接過去。否則看 是否有信息素，并且比較在能感知的范圍內(nèi)哪一點(diǎn)的信息素最多，那么它朝哪個(gè)方向走的概 率就大。這就意味著每只螞蟻多會(huì)以小概率犯錯(cuò)誤，從而并不是往信息素最多的點(diǎn)移動(dòng)。4避障規(guī)則：如果螞蟻要移動(dòng)的方向有障礙物擋住，它會(huì)隨機(jī)的選擇另一個(gè)方向，并且 有信息素指引的話，它會(huì)按照覓食的規(guī)則行為。5播撒信息素規(guī)則：每只螞蟻在找到食物后撒發(fā)的信息素。 自然想到一個(gè)問題：開始時(shí)環(huán)境沒有信息素，螞蟻為什么會(huì)相對有效的找到食物呢 這個(gè)問題用螞蟻的移動(dòng)規(guī)則同樣可以解釋。首先，它要能盡量保持某種慣性，這樣使得 螞蟻盡量向前方移動(dòng)（開始，這個(gè)前方是隨機(jī)固定的一個(gè)方向） ，而不是原地?zé)o謂的打轉(zhuǎn)或者 震動(dòng)；其次

7、，螞蟻要有一定的隨機(jī)性，雖然有了固定的方向，但它也不能像粒子一樣直線運(yùn) 動(dòng)下去，而是有一個(gè)隨機(jī)的干擾。這樣就使得螞蟻運(yùn)動(dòng)起來具有了一定的目的性，盡量保持 原來的方向，但又有新的試探，這就解釋了為什么單個(gè)螞蟻在復(fù)雜的諸如迷宮的地圖中仍然 能找到隱蔽得很好的食物。（二）算法描述隨機(jī)蟻群算法的算法描述如下：算法輸入：城市數(shù)量N,兩兩城市間的距離，所有路徑的信息素濃度算法輸出：螞蟻?zhàn)哌^的路徑長度1設(shè)置全部城市都沒有去過，走過的路徑長度為 0；2隨機(jī)選擇一個(gè)出發(fā)的城市；3i = 14while（i < N）4根據(jù)可選擇路徑的信息素濃度，計(jì)算出各自選中的概率；5根據(jù)不同選擇的概率，使用輪盤選擇算法，

8、得到選擇的下一個(gè)城市；6將所在城市標(biāo)記為不可選擇；7end8計(jì)算走過路徑的長度； 用隨機(jī)蟻群算法解決旅行商問題，實(shí)際上是多次使用蟻群算法，不斷更新最短路徑的過 程。由此，我們?nèi)菀椎玫铰眯猩虇栴}的算法描述：算法輸入：所有城市的X、丫坐標(biāo)，螞蟻數(shù)量n，迭代次數(shù)K 算法輸出：旅行商的最短路徑1計(jì)算兩兩城市間的距離，初始化所有路徑信息素為0；2for i = 1 : K3 for j = 1 : n4第 j 只螞蟻搜索一遍；567if 走過的路徑小于最短路徑更新最短路徑；更新走過路徑的信息素；8end9end四、改進(jìn)的隨機(jī)蟻群算法（一）排序蟻群算法與隨機(jī)蟻群算法不同的是，當(dāng)螞蟻遇到障礙物選擇路徑時(shí)，根

9、據(jù)不同路徑上信息素的濃 度，通過計(jì)算可能達(dá)到最優(yōu)解的概率算法，將路徑進(jìn)行排序，選擇最好的路徑作為下一個(gè)通 往的城市。（二）最大最小蟻群算法 與隨機(jī)蟻群算法和排序蟻群算法都不同的是，當(dāng)螞蟻遇到障礙物選擇路徑時(shí)，使用貪心 策略，優(yōu)先選擇達(dá)到下一個(gè)城市最短的城市，即得到局部最優(yōu)解。這樣以來，更多的信息素 將在較短的路徑聚集，使算法更快地得到全局最短路徑。五、算法比較本文介紹了四種蟻群算法，其中第一種比較簡單，描述了最基本的蟻群算法思想。但是， 它忽略了更優(yōu)路徑存在的可能性，沒有考慮到更普遍的情況。因此，該算法只適用于小規(guī)模， 無特殊情況的問題。后三種蟻群算法屬于實(shí)際中典型的蟻群算法，對不同情況的考慮

10、比較全面，因此應(yīng)用比 較廣泛。三者的差別主要在于螞蟻對不同路徑的選擇上，其中，隨機(jī)蟻群算法首先根據(jù)不同 路徑上信息素的濃度，計(jì)算出選擇各條路徑的概率，而后使用輪盤算法選擇一條路徑，適用 于規(guī)模不太大的場合；排序蟻群算法則根據(jù)選擇各條路徑的概率，對路徑進(jìn)行優(yōu)先排序，選 擇最好的路徑作為下一個(gè)通往的城市，這樣做增加了空間復(fù)雜度，有效改善了時(shí)間復(fù)雜度， 適用于規(guī)模較大的場合；最大最小蟻群算法則是采用貪心策略，優(yōu)先選擇達(dá)到下一個(gè)城市最 短的城市，先得到局部最優(yōu)解，再通過聚類效應(yīng)得到全局最短路徑，適合對時(shí)間和空間要求 都較高的場合。參考文獻(xiàn)：1. 丁洋 . 蟻群優(yōu)化算法分析 . 論文期刊 . .蟻群優(yōu)化

11、算法 . 附錄：1預(yù)編譯所需頭文件#pragma once_nPathj;n=m_cAntAryi.m_nPathj-1;dbTempArynm=dbTempArynm+DBQ/m_cAntAryi.m_dbPathLength;dbTempArymn=dbTempArynm;_nPath0;dbTempArynm=dbTempArynm+DBQ/m_cAntAryi.m_dbPathLength;dbTempArymn=dbTempArynm;earch();_dbPathLength <m_cBestAnt=m_cAntAryj;f",i+1,;printf(cBuf);9 main 函數(shù)主文件#include ""#include ""int main()/ 初始化隨機(jī)種子time_t tm;time(&tm);unsigned int nSeed=(unsigned int)tm;srand(nSeed);/ 旅行商開始搜索CTsp tsp;();();/ 輸出結(jié)果printf("nThe best tour is :nn");char cBuf128;for (int i=0;i<N_CITY_COUN