蟻群算法-趙巖

蟻群算法蟻群算法的研究概況蟻群算法的基本原理蟻群算法的優(yōu)缺點蟻群算法的應(yīng)用范圍算例（TSP）蟻群算法簡史蟻群算法是一種由自然界真實螞蟻覓食行為提煉而成的優(yōu)化算法，于1991年，由意大利學(xué)者M.Dorigo在其博士論文中提出，并成功的解決了旅行商(TSP)問題。1996年，DorigoM等人在《IEEETransactionsonSystems,Man,andCybernetics-PartB》上發(fā)表了“Antsystem:optimizationbyacolonyofcooperatingagents”一文，系統(tǒng)地闡述了蟻群算法的基本原理和數(shù)學(xué)模型，蟻群算法逐漸引起了世界許多國家研究者的關(guān)注，其應(yīng)用領(lǐng)域也得到了迅速拓寬。1998年10月在比利時布魯塞爾召開了第一屆蟻群算法國際研討會(ANTS)，標(biāo)志著蟻群算法的正式國際化。2000年，M．Dorigo和BonabeauE等人在國際頂級學(xué)術(shù)刊物《Nature》上發(fā)表了蟻群算法的研究綜述，從而把這一領(lǐng)域的研究推向了國際數(shù)學(xué)的最前沿。而在我國，最早關(guān)于蟻群算法的研究見于，1997年10月張紀(jì)會與徐心和發(fā)表的“一種新的進化算法——蟻群算法”論文。蟻群算法的研究現(xiàn)狀目前，蟻群算法己經(jīng)成為一個備受關(guān)注的研究熱點和前沿性課題。人們對蟻群算法的研究已經(jīng)由當(dāng)初的TSP領(lǐng)域滲透到多個應(yīng)用領(lǐng)域，由解決一維靜態(tài)優(yōu)化問題發(fā)展到解決多維動態(tài)組合優(yōu)化問題，由離散域范圍內(nèi)研究逐漸拓展到了連續(xù)域范圍內(nèi)研究。同時在蟻群算法的模型改進以及其他仿生優(yōu)化算法的融合方面也取得了相當(dāng)豐富的研究成果，從而使這種新興的仿生優(yōu)化算法展現(xiàn)出前所未有的生機。蟻群算法蟻群算法的研究概況蟻群算法的基本原理蟻群算法的優(yōu)缺點蟻群算法的應(yīng)用范圍算例（TSP）

螞蟻覓食原理：自然界中，螞蟻這種視盲生物，在沒有任何先知經(jīng)驗的情況下總能找到從其巢穴到食物源的最佳路徑，甚至在該路徑上放置障礙物之后，它們?nèi)匀荒芎芸熘匦抡业叫碌淖罴崖肪€。這是因為在螞蟻個體之間是通過一種稱為信息素的物質(zhì)進行信息傳遞的。螞蟻在運動過程中，不但能夠在它所經(jīng)過的路徑上留下該物質(zhì)，而且能夠感知這種物質(zhì)的存在及其強度，并朝著該物質(zhì)強度高的方向移動，為此指導(dǎo)自己的運動方向。因此，由大量螞蟻組成的蟻群集體行為表現(xiàn)出一種信息正反饋現(xiàn)象。在一定時間內(nèi)較短路徑通過的螞蟻要多于較長路徑，而某一路徑上走過的螞蟻越多，則后來的螞蟻選擇該路徑的概率就越大。t=0,20只螞蟻出發(fā)；t=1，路徑1、2各10只螞蟻；t=4，到達食物源；t=5，相遇，路徑1、2各5只；t=8，前5只到達巢穴；t=9是前5只螞蟻面再次臨選擇，此時AB軌跡數(shù)20，AC軌跡數(shù)15。

人工螞蟻的特性共同目標(biāo)——總是尋找最小費用的可行解，人工螞蟻可以釋放和識別“信息素”，“信息素”會隨著時間蒸發(fā)、衰減，人工螞蟻具有記憶，用來儲存當(dāng)前路徑的信息，當(dāng)前螞蟻可以轉(zhuǎn)移至可行領(lǐng)域中的任一點，螞蟻按某種概率決策規(guī)則移至領(lǐng)域節(jié)點，人工螞蟻處理離散狀態(tài)。

蟻群算法的基本步驟

蟻群算法的系統(tǒng)學(xué)特征系統(tǒng)性:整體大于部分之和分布式計算:強適應(yīng)能力，依賴于個體行為，但不單獨依賴于與個體行為，體現(xiàn)了容錯能力（行為的冗余）自組織性:仿生算法共有的特性，由此具有魯棒性，（組織力或組織指令來源于系統(tǒng)內(nèi)部還是外部）正反饋性:信息素累計，算法演化過程得以進行的基礎(chǔ)，也造成了初值敏感性和群體迷失現(xiàn)象。蟻群算法蟻群算法的研究概況蟻群算法的基本原理蟻群算法的優(yōu)缺點蟻群算法的應(yīng)用范圍算例（TSP）蟻群算法的優(yōu)點不依賴于所求問題的具體數(shù)學(xué)表達式描述，具有很強的找到全局最優(yōu)解的優(yōu)化能力。該算法具有正反饋、較強的魯棒性、全局性、普遍性、優(yōu)良的分布式并行計算機制、易于與其他方法相結(jié)合等諸多優(yōu)點。蟻群算法的缺點：蟻群算法的成功主要在實驗層次上，很少有理論來解釋利用蟻群算法為什么能夠成功地解決這些問題，它沒有堅實的數(shù)學(xué)基礎(chǔ)；蟻群算法的模型普適性不強，其模型不能直接應(yīng)用于實際優(yōu)化問題；蟻群算法的局部搜索能力較弱，易于出現(xiàn)停滯和局部收斂、收斂速度慢等問題，因而往往需要嵌入一些專門的輔助技巧；長時間花費在解的構(gòu)造上，從而導(dǎo)致搜索時間過長，算法最先基于離散問題，不能直接解決連續(xù)優(yōu)化問題。蟻群算法蟻群算法的研究概況蟻群算法的基本原理蟻群算法的優(yōu)缺點蟻群算法的應(yīng)用范圍算例（TSP）

蟻群算法的應(yīng)用領(lǐng)域由于蟻群算法對圖的對稱性以及目標(biāo)函數(shù)無特殊要求，因此，可以解決各種對稱、非對稱問題，線性非線性問題。其本質(zhì)是圖上尋優(yōu)，蟻群算法已經(jīng)成功地運用于求解旅行商（TSP）問題、調(diào)度問題、圖形著色、機器人路徑規(guī)劃、數(shù)據(jù)挖掘、聚類分析、機器學(xué)習(xí)與推理、網(wǎng)絡(luò)路由、無線網(wǎng)絡(luò)配置、頻率分配、數(shù)字濾波、二次分配、序列求序、武器-目標(biāo)配置及各種組合優(yōu)化問題，并取得了較好的結(jié)果；廣泛應(yīng)用于電力、通信、化工、交通、機器人、冶金等多個領(lǐng)域中。蟻群算法蟻群算法的研究概況蟻群算法的基本原理蟻群算法的優(yōu)缺點蟻群算法的應(yīng)用范圍算例（TSP）

算例(TSP)旅行商問題（TSP）:給定n個城市和兩個兩個城市之間的距離，要求確定一條經(jīng)過各個城市一次當(dāng)且僅當(dāng)一次的最短路徑。即要求確定一條長度最短Haimilton回路。第一步、初始化（蟻周算法）將m只螞蟻隨機放到n個城市，每只螞蟻的禁忌表為螞蟻當(dāng)前所在城市，各邊信息初始化為c。禁忌表體現(xiàn)了人工螞蟻的記憶性，使得螞蟻不會走重復(fù)道路，提高了效率。

第二步、構(gòu)造路徑在t時刻，螞蟻k從城市i轉(zhuǎn)移到城市j的概率為：為邊（i，j）的軌跡強度，為邊（i，j）的能見度，為，軌跡的相對重要程度，（0,5）能見度的相對重要程度（1,5）。第三步、更新信息在所有螞蟻找到一條合法路徑后對信息進行更新。ρ（0<ρ<1）表示邊上信息素的蒸發(fā)系數(shù)（0.1，0.9），0.7最優(yōu)。1-ρ表示信息素的持久性系數(shù)，表示第k只螞蟻在本次迭代中留在邊