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