蟻群算法的由來：螞蟻是地球上最常見、數(shù)量最多的昆蟲種類之一，常常成群結(jié)隊地出現(xiàn)在人類的日常生活環(huán)境中。這些昆蟲的群體生物智能特征，引起了一些學(xué)者的注意。意大利學(xué)者M.Dorigo，V.Maniezzo等人在觀察螞蟻的覓食習(xí)性時發(fā)現(xiàn)，螞蟻總能找到巢穴與食物源之間的最短路徑。經(jīng)研究發(fā)現(xiàn)，螞蟻的這種群體協(xié)作功能是通過一種遺留在其來往路徑上的叫做信息素(Pheromone)的揮發(fā)性化學(xué)物質(zhì)來進行通信和協(xié)調(diào)的�；瘜W(xué)通信是螞蟻采取的基本信息交流方式之一，在螞蟻的生活習(xí)性中起著重要的作用。通過對螞蟻覓食行為的研究，他們發(fā)現(xiàn)，整個蟻群就是通過這種信息素進行相互協(xié)作，形成正反饋，從而使多個路徑上的螞蟻都逐漸聚集到最短的那條路徑上。
這樣，M.Dorigo等人于1991年首先提出了蟻群算法。其主要特點就是：通過正反饋、分布式協(xié)作來尋找最優(yōu)路徑。這是一種基于種群尋優(yōu)的啟發(fā)式搜索算法。它充分利用了生物蟻群能通過個體間簡單的信息傳遞，搜索從蟻巢至食物間最短路徑的集體尋優(yōu)特征，以及該過程與旅行商問題求解之間的相似性。得到了具有NP難度的旅行商問題的最優(yōu)解答。同時，該算法還被用于求解Job-Shop調(diào)度問題、二次指派問題以及多維背包問題等，顯示了其適用于組合優(yōu)化類問題求解的優(yōu)越特征。
多年來世界各地研究工作者對蟻群算法進行了精心研究和應(yīng)用開發(fā)，該算法現(xiàn)己被大量應(yīng)用于數(shù)據(jù)分析、機器人協(xié)作問題求解、電力、通信、水利、采礦、化工、建筑、交通等領(lǐng)域。
蟻群算法之所以能引起相關(guān)領(lǐng)域研究者的注意，是因為這種求解模式能將問題求解的快速性、全局優(yōu)化特征以及有限時間內(nèi)答案的合理性結(jié)合起來。其中，尋優(yōu)的快速性是通過正反饋式的信息傳遞和積累來保證的。而算法的早熟性收斂又可以通過其分布式計算特征加以避免，同時，具有貪婪啟發(fā)式搜索特征的蟻群系統(tǒng)又能在搜索過程的早期找到可以接受的問題解答。這種優(yōu)越的問題分布式求解模式經(jīng)過相關(guān)領(lǐng)域研究者的關(guān)注和努力，已經(jīng)在最初的算法模型基礎(chǔ)上得到了很大的改進和拓展。
經(jīng)過一定時間，從食物源返回的螞蟻到達D點同樣也碰到障礙物，也需要進行選擇。此時A, B兩側(cè)的信息素濃度相同，它們?nèi)匀灰话胂蜃�，一半向右。但是當A側(cè)的螞蟻已經(jīng)完全繞過障礙物到達C點時，B側(cè)的螞蟻由于需走的路徑更長，還不能到達C點。如圖3所示。
圖3蟻群在障礙物前經(jīng)過一段時間后的情形
此時對于從蟻巢出發(fā)來到C點的螞蟻來說，由于A側(cè)的信息素濃度高，B側(cè)的信息素較低，就傾向于選擇A側(cè)的路徑。這樣的結(jié)果是A側(cè)的螞蟻越來越多，最終所有螞蟻都選擇這條較短的路徑。如圖4所示。
圖4 蟻群最終選擇的路徑
上述過程，很顯然是由螞蟻所留下的信息素的“正反饋”過程而導(dǎo)致的。螞蟻個體就是通過這種信息的交流來達到搜索食物的目的。蟻群算法的基本思想也是從這個過程轉(zhuǎn)化而來的。
蟻群算法的特點1)蟻群算法是一種自組織的算法。在系統(tǒng)論中，自組織和它組織是組織的兩個基本分類，其區(qū)別在于組織力或組織指令是來自于系統(tǒng)的內(nèi)部還是來自于系統(tǒng)的外部，來自于系統(tǒng)內(nèi)部的是自組織，來自于系統(tǒng)外部的是他組織。如果系統(tǒng)在獲得空間的、時間的或者功能結(jié)構(gòu)的過程中，沒有外界的特定干預(yù)，我們便說系統(tǒng)是自組織的。在抽象意義上講，自組織就是在沒有外界作用下使得系統(tǒng)墑增加的過程(即是系統(tǒng)從無序到有序的變化過程)。蟻群算法充分休現(xiàn)了這個過程，以螞蟻群體優(yōu)化為例子說明。當算法開始的初期，單個的人工螞蟻無序的尋找解，算法經(jīng)過一段時間的演化，人工螞蟻間通過信息激素的作用，自發(fā)的越來越趨向于尋找到接近最優(yōu)解的一些解，這就是一個無序到有序的過程。
2)蟻群算法是一種本質(zhì)上并行的算法。每只螞蟻搜索的過程彼此獨立，僅通過信息激素進行通信。所以蟻群算法則可以看作是一個分布式的多agent系統(tǒng)，它在問題空間的多點同時開始進行獨立的解搜索，不僅增加了算法的可靠性，也使得算法具有較強的全局搜索能力。
3)蟻群算法是一種正反饋的算法。從真實螞蟻的覓食過程中我們不難看出，螞蟻能夠最終找到最短路徑，直接依賴于最短路徑上信息激素的堆積，而信息激素的堆積卻是一個正反饋的過程。對蟻群算法來說，初始時刻在環(huán)境中存在完全相同的信息激素，給予系統(tǒng)一個微小擾動，使得各個邊上的軌跡濃度不相同，螞蟻構(gòu)造的解就存在了優(yōu)劣，算法采用的反饋方式是在較優(yōu)的解經(jīng)過的路徑留下更多的信息激素，而更多的信息激素又吸引了更多的螞蟻，這個正反饋的過程使得初始的不同得到不斷的擴大，同時又引導(dǎo)整個系統(tǒng)向最優(yōu)解的方向進化。因此，
正反饋是螞蟻算法的重要特征，它使得算法演化過程得以進行。
