蟻群算法的原理、數(shù)學模型及其經(jīng)典改進分析目錄TOC\o"1-3"\h\u1940蟻群算法的原理、數(shù)學模型及其經(jīng)典改進分析 1327081.1蟻群算法的原理 187981.1.1蟻群算法的基本原理 1273331.1.2蟻群算法的數(shù)學模型 2194211.2蟻群算法中的經(jīng)典改進 3227461.2.1精英蟻群算法 3172811.2.2優(yōu)化排序的螞蟻系統(tǒng) 3100811.2.3最大最小蟻群算法 4179721.3蟻群算法的參數(shù)分析 4103891.3.1螞蟻數(shù)量 4108351.3.2信息啟發(fā)因子 5148871.3.3期望啟發(fā)因子 5236621.3.4信息素揮發(fā)系數(shù) 534611.4蟻群算法的特征 61.1蟻群算法的原理1.1.1蟻群算法的基本原理蟻群優(yōu)化算法是模擬螞蟻覓食的原理設(shè)計出的一種群集智能算法。螞蟻在覓食過程中能夠在幾天過的路徑上留下一種稱之為信息素的物質(zhì)。并在覓食過程中能夠感知這種物質(zhì)的強度。并指導自己的行動方向，他們總是朝著該物質(zhì)強度高的方向移動，因此大量螞蟻組成的集體覓食就表現(xiàn)為一種對信息素的正反饋現(xiàn)象。某一條路徑越短，路徑上經(jīng)過的螞蟻越多，即信息素遺留的也就越多。信息素的濃度也就越高，螞蟻選擇這條路徑的幾率也就越高，由此構(gòu)成的正反饋過程。從而逐漸逼近最優(yōu)路徑，找到最優(yōu)路徑。螞蟻在覓食過程中將信息素作為媒介從而進行信息交流。當螞蟻從食物源走到蟻穴，或者從蟻穴走到食物源地，都會在經(jīng)過的路徑上釋放信息素，從而形成的一條含有信息素的路徑。螞蟻可以通過他們的觸角感覺中路徑上信息素濃度的大小，并且高概率選擇信息素濃度較高的路徑。螞蟻的搜索主要包括三種智能行為：一、螞蟻的記憶避免重復(fù)搜索。當一條路徑已經(jīng)被某種螞蟻搜索過后，若這只螞蟻再次來到這條路徑前，則不會再搜索。因此仿照這行為，在蟻群算法中建立禁忌表進行模擬。二、螞蟻間通過信息素進行信息傳遞。螞蟻在經(jīng)過的路徑上會釋放信息素標記道路，當后面螞蟻進行路徑探索時，路徑上的信息素濃度會是他們做出選擇的指標。這樣信息素就成為前后螞蟻之間傳遞信號的重要載體。三、螞蟻的集體活動。一只螞蟻的力量是渺小的，很難達到目的地。但螞蟻成群結(jié)隊出動搜索時就效果明顯，當某些路徑上通過的螞蟻越來越多時，路徑上留下信息素的速率比信息素揮發(fā)的速率大，路徑上的信息素越來越多，螞蟻選擇該路徑的概率就越來越大，又引導后續(xù)螞蟻的選擇，從而進一步增加該路徑的信息素濃度，而通過螞蟻較少的路徑上的信息素保持穩(wěn)定揮發(fā)，而沒有新的信息素進行補充，形成入不敷出的局面，從而越來越少。1.1.2蟻群算法的數(shù)學模型螞蟻系統(tǒng)是最早的蟻群算法。其搜索過程如下：在初始時刻，只螞蟻隨機放置于城市中，各條路徑上的信息素初始值相等，因此螞蟻受信息素影響而選擇每條路的概率相等。時刻螞蟻在城市選擇下一個目標城市時，由狀態(tài)轉(zhuǎn)移概率決定，狀態(tài)轉(zhuǎn)移概率的函數(shù)表達式為 （式2-1）其中，為時刻路徑上的信息素濃度，為時刻路徑的期望函數(shù)，為螞蟻不曾經(jīng)過、訪問的城市，表示禁忌表，里面存儲著螞蟻訪問過的地點，防止螞蟻走回頭路，為算法中信息素啟發(fā)因子，用來表示在螞蟻搜索過程中信息素的重要程度，數(shù)值越大，路徑上積累的信息素就愈多，經(jīng)過這段路徑的螞蟻就多，同時增加了這條路上的信息素數(shù)量；為算法中信息素啟發(fā)因子，用來表示在螞蟻搜索過程中信息素的重要程度，數(shù)值越大，啟發(fā)信息在螞蟻選擇路徑的過程中就越受重視；為啟發(fā)函數(shù)，傳統(tǒng)的啟發(fā)函數(shù)定義為（式2-2）在此表達式中，表示兩個城市之間的距離，當兩個城市之間的距離越小時，螞蟻選擇這條路的概率就越大。隨著信息素濃度的逐漸提高，有可能會出現(xiàn)因為信息素濃度過高而遮蔽了啟發(fā)因子的問題，為防止出現(xiàn)這種情況，信息素就需要在每一次螞蟻完成一次迭代后進行更新。更新的公式為（式2-3）通常用表示信息素揮發(fā)系數(shù)，在0到1之間，那么為信息素殘留系數(shù)，表示路徑上信息素的損失程度；表示此次迭代中螞蟻在路徑上所留下的信息素含量，表示在本次迭代中所有螞蟻在此路徑上信息素的增加量。1.2蟻群算法中的經(jīng)典改進1.2.1精英蟻群算法帶精英系統(tǒng)的螞蟻系統(tǒng)（AntSystemWithElitistStrategy,AS）是在每次循環(huán)之后給最優(yōu)解獎賞額外的信息素，從而在下一次的循環(huán)中本次的最優(yōu)解會對螞蟻產(chǎn)生更高的吸引力，提高收斂速度。信息素的更新公式為： （式2-4）其中，和通過公式（2-5）和公式（2-6）求解。 (式2-5）其中，表示螞蟻k在本次循環(huán)中經(jīng)過的路徑（i，j） （式2-6）其中，表示（i,j）是最優(yōu)解的一部分。表示最優(yōu)路徑的長度表示精英螞蟻的數(shù)量表示精英螞蟻經(jīng)過路段（i,j）時該路段上的信息素增量。經(jīng)實驗證明，當使用帶有精英策略的蟻群系統(tǒng)后，能夠在前期快速搜索路徑，但同時也有過早成熟的風險，所以要慎重確定精英螞蟻的數(shù)量，在保證路徑搜索的多樣性下適當提高收斂速度。1.2.2優(yōu)化排序的螞蟻系統(tǒng)基于優(yōu)化排序的螞蟻系統(tǒng)(Rank-BasedVersionOfSystem，簡稱)是一個以為基礎(chǔ)的改進系統(tǒng)，該系統(tǒng)的排序思想來源于遺傳算法，它將所有螞蟻經(jīng)過的路徑按照從小到大進行排序()，并且根據(jù)路徑長度賦予它們不同的權(quán)重()，較短路徑分配的權(quán)重較大()，然后優(yōu)化排序螞蟻系統(tǒng)將依據(jù)它們的權(quán)重進行加權(quán)處理，使得權(quán)重跟路徑上信息素濃度的高低成正比例關(guān)系，從而達到加快路徑搜索速度的效果。由于會對精英螞蟻所產(chǎn)生的信息素進行額外加強作用，所以本質(zhì)上，系統(tǒng)是一個融合了精英理論和優(yōu)化排序思想的綜合型改進策略。1.2.3最大最小蟻群算法1996年，Stutzle和Hoos提出了最大最小蟻群算法（Max-MinAntSystem,MMAS）,能夠有效跳出局部最優(yōu)，提高收斂速度，保證解的質(zhì)量。MMAS主要在以下幾個方面進行改進：（1）信息素更新。每完成一次循環(huán)，MMAS只對本次循環(huán)所得最優(yōu)解或全局最優(yōu)解進行信息素更新。（2）信息素濃度。MMAS規(guī)定每條路徑上的信息素濃度范圍，控制局部路徑的信息素濃度，避免由于局部信息素含量過高或過低使得結(jié)果局部最優(yōu)甚至搜索停滯，同時提高搜索的隨機性。（3）信息素初始化。MMAS初始化各路徑上的信息素含量為最大可能值，每完成一次循環(huán)遍歷按參數(shù)戶進行揮發(fā)，只對最優(yōu)路徑上的信息素進行更新，在算法初期保證較寬泛的搜索空間。了解過蟻群算法的基本改進后，再結(jié)合上文了解到的蟻群算法的現(xiàn)階段研究成效：帶精英策略思想的最大最小蟻群系統(tǒng)算法在求解中性能較好，因此本文也采用最大最小蟻群系統(tǒng)算法的思想對傳統(tǒng)蟻群算法進行改進。1.3蟻群算法的參數(shù)分析通過研究算法模型，我們可以了解到蟻群算法的效率以及最后輸出結(jié)果和數(shù)學模型的參數(shù)設(shè)置有相當大的關(guān)聯(lián)度，因此，需分析各個參數(shù)變化對算法性能所產(chǎn)生的影響。1.3.1螞蟻數(shù)量在自然界中，螞蟻覓食都是傾巢而出，并不是只有一只工蟻獲得一條路徑開始。在算法使用過程中也是一樣，是通過多個解獲得其中的最優(yōu)解。一只螞蟻完成一次迭代獲得一個解，當有一群螞蟻并行迭代時，就可以獲得一個龐大的解集，每只螞蟻對應(yīng)一個解集。在一定范圍內(nèi)，較大的子集可擴大算法的搜索范圍，增強全局搜索能力，提高算法的可靠性。但蟻群數(shù)量過大，又會減小路徑間信息素濃度差異，減弱正反饋機制，減緩算法的收斂速度。相反如果蟻群數(shù)量過少，意味著路徑上信息素濃度較低，相對劣質(zhì)的路徑上信息素含量過低甚至趨近于零，造成算法的全局搜索能力差，易出現(xiàn)停滯現(xiàn)象。根據(jù)大量的實驗驗證，為保證較好的全局搜索能力和較快的收斂速度，蟻群數(shù)目一般為節(jié)點數(shù)目的0.6~0.9倍，由于在本文中，只有障礙物不可行區(qū)域，沒有節(jié)點數(shù)目，柵格地圖規(guī)模一般大小，因此螞蟻數(shù)量選取50。1.3.2信息啟發(fā)因子通過算法原理可知，蟻群對路徑的選擇主要受兩個因素影響:路徑的啟發(fā)信息量和積累的信息素濃度。其中，信息素濃度越高，該路徑被螞蟻選中的可能性越大，反之越小。信息啟發(fā)因子表示路徑上信息素濃度在螞蟻選擇路徑的影響程度，能夠反映螞蟻在搜索過程中的隨機性大小。因此，參數(shù)的設(shè)置將直接影響最優(yōu)解的質(zhì)量。設(shè)置越大，螞蟻受信息素影響的程度越大，選擇己遍歷過的路徑的概率越大，隨機性減小，由于正反饋機制的作用，易造成過早收斂;相反，越小，信息素作用減弱甚至被忽略，螞蟻的決策受啟發(fā)信息影響越大，同樣易出現(xiàn)早熟現(xiàn)象。通過己有實驗分析，信息啟發(fā)因子常取1~5，一般取1。1.3.3期望啟發(fā)因子 相對于參數(shù)，期望啟發(fā)因子表示啟發(fā)信息在螞蟻對路徑?jīng)Q策中的影響程度，反映路徑長度等確定性因素在搜索過程中所發(fā)揮的作用。越大，螞蟻越容易選擇局部最短路徑，隨著較短路徑上信息素含量的不斷積累，算法的隨機性下降，算法同樣容易過早收斂;相反，越小，算法過于依賴隨機概率進行決策，收斂速度下降，難以獲得全局最優(yōu)解。根據(jù)大量仿真實驗，可知期望啟發(fā)因子通常為1~5，常取31.3.4信息素揮發(fā)系數(shù)由于蟻群算法的信息素揮發(fā)機制，路徑中所遺留的信息素會隨算法迭代搜索而逐漸減少，主要參數(shù)信息素揮發(fā)系數(shù)(0<<1)、信息素衰減系數(shù)(1-)能夠反映路徑上信息素的減少程度。越大，信息素揮發(fā)越多，路徑?jīng)Q策的隨機性提高，全局搜索能力相應(yīng)提高，但信息素在路徑?jīng)Q策中的決定作用越小，當處理大規(guī)模優(yōu)化問題時，局部路徑上的信息素尚未被利用就己揮發(fā)殆盡，而陷于局部最優(yōu)，并弱化蟻群算法的特點;相反，越小，信息素揮發(fā)越少，己被遍歷過的局部路徑上信息素積累過多，雖然算法收斂速度加快，但路徑多樣性降低，全局搜索能力減弱。通過實驗分析可知，信息素揮發(fā)系數(shù)通常為0.1~0.9。1.4蟻群算法的特征蟻群算法中，人工蟻群不僅是抽象自然界蟻群的行為特征，還具有其他特點。人工蟻群群能夠記憶自身行為，這是在離散空間中的狀態(tài)轉(zhuǎn)移過程。其次，蟻群算法可針對具體情況，取不同的信息素更新方式，對路徑上的信息濃度按不同的參數(shù)設(shè)置進行濃度更新。另外，為盡可能的提高算法執(zhí)行效率，通過引入不同的局部優(yōu)化策略或與其他算法原理相融合。綜上，對蟻群算法的優(yōu)點概括為以下幾點:(1)信息交換的正反饋機制。通過狀態(tài)轉(zhuǎn)移概率對路徑選擇，信息素含量越高的路徑被選擇的概率越大，而被越多的螞蟻經(jīng)過會積累更多的