蟻群算法螞蟻的生物學(xué)特征

螞蟻是一種既渺小而又平常的社會(huì)性昆蟲。生物學(xué)家通過對螞蟻的長期觀察研究發(fā)現(xiàn)，每只螞蟻的智能并不高，但它們卻能協(xié)同工作，集中食物，建筑蟻穴并撫養(yǎng)后代，依靠群體能力發(fā)揮出超出個(gè)體的智能。螞蟻有復(fù)雜的社會(huì)體制，“螞蟻”城市往往有5000萬個(gè)成員。螞蟻有四種不同的蟻型：蟻后、雄蟻、工蟻和兵蟻。

螞蟻的生物學(xué)特征尋找食物螞蟻尋找食物過程中總會(huì)自動(dòng)找到一條最短路徑。蟻群算法的基本原理

蟻群算法是對自然界螞蟻的尋徑方式進(jìn)行模似而得出的一種仿生算法。螞蟻在運(yùn)動(dòng)過程中，能夠在它所經(jīng)過的路徑上留下一種稱之為信息素(pheromone)的物質(zhì)進(jìn)行信息傳遞，而且螞蟻在運(yùn)動(dòng)過程中能夠感知這種物質(zhì)，并以此指導(dǎo)自己的運(yùn)動(dòng)方向，因此由大量螞蟻組成的蟻群集體行為便表現(xiàn)出一種信息正反饋現(xiàn)象：某一路徑上走過的螞蟻越多，則后來者選擇該路徑的概率就越大。蟻群算法的基本原理

在蟻群尋找食物時(shí)，它們總能找到一條從食物到巢穴之間的最優(yōu)路徑。這是因?yàn)槲浵佋趯ふ衣窂綍r(shí)會(huì)在路徑上釋放出一種特殊的信息素。當(dāng)它們碰到一個(gè)還沒有走過的路口時(shí)，就隨機(jī)地挑選一條路徑前行。與此同時(shí)釋放出與路徑長度有關(guān)的信息素。路徑越長，釋放的激索濃度越低。當(dāng)后來的螞蟻再次碰到這個(gè)路口的時(shí)候，選擇激素濃度較高路徑概率就會(huì)相對較大。這樣形成一個(gè)正反饋。最優(yōu)路徑上的激索濃度越來越大。而其它的路徑上激素濃度卻會(huì)隨著時(shí)間的流逝而消減。最終整個(gè)蟻群會(huì)找出最優(yōu)路徑。簡化螞蟻的尋食過程螞蟻從A點(diǎn)出發(fā)，速度相同，食物在D點(diǎn)，可能隨機(jī)選擇路線ABD或ACD。假設(shè)初始時(shí)每條分配路線一只螞蟻，每個(gè)時(shí)間單位行走一步，本圖為經(jīng)過9個(gè)時(shí)間單位時(shí)的情形：走ABD的螞蟻到達(dá)終點(diǎn)，而走ACD的螞蟻剛好走到C點(diǎn)，為一半路程。簡化螞蟻的尋食過程

假設(shè)螞蟻每經(jīng)過一處所留下的信息素為一個(gè)單位，則經(jīng)過36個(gè)時(shí)間單位后，所有開始一起出發(fā)的螞蟻都經(jīng)過不同路徑從D點(diǎn)取得了食物，此時(shí)ABD的路線往返了2趟，每一處的信息素為4個(gè)單位，而ACD的路線往返了一趟，每一處的信息素為2個(gè)單位，其比值為2：1。尋找食物的過程繼續(xù)進(jìn)行，則按信息素的指導(dǎo)，蟻群在ABD路線上增派一只螞蟻（共2只），而ACD路線上仍然為一只螞蟻。再經(jīng)過36個(gè)時(shí)間單位后，兩條線路上的信息素單位積累為12和4，比值為3：1。若按以上規(guī)則繼續(xù)，蟻群在ABD路線上再增派一只螞蟻（共3只），而ACD路線上仍然為一只螞蟻。再經(jīng)過36個(gè)時(shí)間單位后，兩條線路上的信息素單位積累為24和6，比值為4：1。若繼續(xù)進(jìn)行，則按信息素的指導(dǎo)，最終所有的螞蟻會(huì)放棄ACD路線，而都選擇ABD路線。這也就是前面所提到的正反饋效應(yīng)。蟻群算法模型的建立對螞蟻個(gè)體的抽象 蟻群算法是對自然界真實(shí)螞蟻覓食行為的一種模擬，因此首先必須對真實(shí)螞蟻進(jìn)行抽象，而不可能也沒必要對螞蟻個(gè)體進(jìn)行完全再現(xiàn)。把螞蟻能夠有效刻畫出真實(shí)蟻群中能為算法所借鑒的特征抽象出來，同時(shí)建立與算法模型無關(guān)的因素。蟻群算法模型的建立問題空間的描述 蟻群算法所求解的問題空間可用一個(gè)重要的數(shù)學(xué)工具——圖（graph）來描述。尋找路徑的抽象 把覓食過程抽象成算法中解的構(gòu)造過程，將信息素抽象為存在于圖的邊上的軌跡。在每一節(jié)點(diǎn)上人工螞蟻感知相鄰節(jié)點(diǎn)邊上的信息素濃度。蟻群算法模型的建立啟發(fā)因子的引入 蟻群算法的自組織性，似的系統(tǒng)的演化需要耗費(fèi)較長的時(shí)間，而實(shí)際應(yīng)用時(shí)對算法運(yùn)行時(shí)間的要求也是必不可少的。因此引入一個(gè)啟發(fā)因子，給蟻群算法一個(gè)初始的引導(dǎo)，增加算法的時(shí)間有效性。

蟻群算法的基本步驟

基本蟻群算法的優(yōu)缺點(diǎn)優(yōu)點(diǎn)較強(qiáng)的魯棒性、全局性、普遍性分布式計(jì)算易于與其它方法結(jié)合缺點(diǎn)需要較長的計(jì)算時(shí)間，容易停滯所有路徑的信息素增量，會(huì)導(dǎo)致錯(cuò)誤的引導(dǎo)信息素的均勻分配策略未體現(xiàn)出路段的重要性蟻群算法的應(yīng)用一、物流中的應(yīng)用蟻群算法可以用于網(wǎng)絡(luò)的優(yōu)化用以解決不同領(lǐng)域的不同問題,比如說運(yùn)輸工具、運(yùn)輸路線、運(yùn)輸人員的選擇方案等,比較典型的例子有指派問題、運(yùn)輸問題、車輛路徑問題等。

二、聚類中的應(yīng)用蟻群算法在聚類問題中的應(yīng)用產(chǎn)生了蟻群聚類算法。蟻群聚類算法是一種全局優(yōu)化的啟發(fā)式算法。能根據(jù)聚類中心的信息素把周圍數(shù)據(jù)歸并到一起,從而得到數(shù)據(jù)分類。蟻群算法的應(yīng)用三、機(jī)器人中的應(yīng)用在機(jī)器人的應(yīng)用中,蟻群算法可以幫助搜索最優(yōu)路徑,幫助確定機(jī)器人的行動(dòng)路徑。四、其他應(yīng)用旅行商問題Job-Shop調(diào)度問題網(wǎng)絡(luò)路由問題大規(guī)模集成電路綜合布線問題圖像處理蟻群算法的發(fā)展趨勢蟻群算法主要的應(yīng)用領(lǐng)域還是離散的應(yīng)用域,而在連續(xù)域的應(yīng)用相對較少。隨著算法研究的深入,連續(xù)域問題的解決難度會(huì)降低,算法中的參數(shù)比如說信息素,將會(huì)由線性的發(fā)展到更加復(fù)雜的數(shù)學(xué)關(guān)系,甚至是時(shí)變的,使整個(gè)算法構(gòu)成一個(gè)動(dòng)態(tài)的、實(shí)時(shí)的、連續(xù)的、多維的復(fù)雜系統(tǒng)。隨著多核電腦的普及以及電腦計(jì)算性能的提高,