matlab蟻群算法精講及仿真圖

蟻群算法matlab精講及仿真4.1根本蟻群算法4.1.1根本蟻群算法的原理蟻群算法是上世紀(jì)90年代意大利學(xué)者M(jìn).Dorigo,v.Maneizz。等人提出來的,在越來越多的領(lǐng)域里得到廣泛應(yīng)用。蟻群算法，是一種模擬生物活動的智能算法，蟻群算法的運作機理來源于現(xiàn)實世界中螞蟻的真實行為，該算法是由MarcoDorigo首先提出并進(jìn)行相關(guān)研究的，螞蟻這種小生物，個體能力非常有限，但實際的活動中卻可以搬動自己大幾十倍的物體，其有序的合作能力可以與人類的集體完成浩大的工程非常相似，它們之前可以進(jìn)行信息的交流，各自負(fù)責(zé)自己的任務(wù)，整個運作過程統(tǒng)一有序，在一只螞蟻找食物的過程中，在自己走過的足跡上灑下某種物質(zhì)，以傳達(dá)信息給伙伴，吸引同伴向自己走過的路徑上靠攏，當(dāng)有一只螞蟻找到食物后，它還可以沿著自己走過的路徑返回，這樣一來找到食物的螞蟻走過的路徑上信息傳遞物質(zhì)的量就比擬大，更多的螞蟻就可能以更大的機率來選擇這條路徑，越來越多的螞蟻都集中在這條路徑上，螞蟻就會成群結(jié)隊在蟻窩與食物間的路徑上工作。當(dāng)然，信息傳遞物質(zhì)會隨著時間的推移而消失掉一局部，留下一局部，其含量是處于動態(tài)變化之中，起初，在沒有螞蟻找到食物的時候，其實所有從蟻窩出發(fā)的螞蟻是保持一種隨機的運動狀態(tài)而進(jìn)行食物搜索的，因此，這時，各螞蟻間信息傳遞物質(zhì)的參考其實是沒有價值的，當(dāng)有一只螞蟻找到食物后，該螞蟻一般就會向著出發(fā)地返回，這樣，該螞蟻來回一趟在自己的路徑上留下的信息傳遞物質(zhì)就相對較多，螞蟻向著信息傳遞物質(zhì)比擬高的路徑上運動，更多的螞蟻就會選擇找到食物的路徑，而螞蟻有時不一定向著信息傳遞物質(zhì)量高的路徑走，可能搜索其它的路徑。這樣如果搜索到更短的路徑后，螞蟻又會往更短的路徑上靠攏，最終多數(shù)螞蟻在最短路徑上工作?！净谙伻核惴ê瓦z傳算法的機器人路徑規(guī)劃研究】該算法的特點：自我組織能力，螞蟻不需要知道整體環(huán)境信息，只需要得到自己周圍的信息，并且通過信息傳遞物質(zhì)來作用于周圍的環(huán)境，根據(jù)其他螞蟻的信息素來判斷自己的路徑。正反應(yīng)機制，螞蟻在運動的過程中，收到其他螞蟻的信息素影響，對于某路徑上信息素越強的路徑，其轉(zhuǎn)向該路徑的概率就越大，從而更容易使得蟻群尋找到最短的避障路徑。易于與其他算法結(jié)合，現(xiàn)實中螞蟻的工作過程簡單，單位螞蟻的任務(wù)也比擬單一，因而蟻群算法的規(guī)那么也比擬簡單，穩(wěn)定性好，易于和其他算法結(jié)合使得避障路徑規(guī)劃效果更好。具有并行搜索能力探索過程彼此獨立又相互影響，具備并行搜索能力，這樣既可以保持解的多樣性，又能夠加速最優(yōu)解的發(fā)現(xiàn)。4.1.2根本蟻群算法的生物仿真模型a為螞蟻所在洞穴,food為食物所在區(qū),假設(shè)abde為一條路徑,eadf為另外一條路徑,螞蟻走過后會留下信息素,5分鐘后螞蟻在兩條路徑上留下的信息素的量都為3,概率可以認(rèn)為相同,而30分鐘后baed路徑上的信息素的量為60,明顯大于eadf路徑上的信息素的量。最終螞蟻會完全選擇abed這條最短路徑,由此可見,螞蟻之間的信息交換是一個正反應(yīng)過程,螞蟻的覓食過程就是一個尋優(yōu)路徑過程。螞蟻沒有視覺,只能靠在行走過的路徑上釋放出的信息素來尋找路徑,因此,螞蟻走的路徑越長,那么釋放的信息量越小。當(dāng)后來的螞蟻再次碰到這條路徑時,選擇信息量較大路徑的概率相對較大,此時形成了一個正反應(yīng)機制。最短路徑上的信息素t越來越大,而其他路徑上的信息素t就會隨著時間的流逝越來越少直至消失,最終螞蟻群會找出最短的一條路徑。當(dāng)在路徑上出現(xiàn)障礙物時,螞蟻能夠很快適應(yīng)環(huán)境重新找到最優(yōu)路徑。蟻群算法就是根據(jù)螞蟻這一智能群體的自組織覓食行為尋找出一種新的智能計算模式。4.2蟻群算法的數(shù)學(xué)模型4.2.2根本蟻群算法的實現(xiàn)首先引入如下記號：為蟻群中螞蟻的數(shù)量；為城市和城市之間的距離；為t時刻路徑上的信息素數(shù)量；為城市的數(shù)量。初始時刻，每條路徑上的信息素相等，設(shè)〔A為常數(shù)〕，螞蟻在移動中根據(jù)路徑上信息素的多少來決定下一次前進(jìn)的方向。根本蟻群算法一般采取隨機比例規(guī)那么，其表示在當(dāng)前城市的螞蟻k轉(zhuǎn)移到下一個城市j的概率。為t時刻螞蟻k由城市轉(zhuǎn)移到城市j的狀態(tài)轉(zhuǎn)移概率如式4.1所示：(4.1)(4.1)其中，表示螞蟻k當(dāng)前選擇的城市集合；為禁忌表，它記錄了螞蟻k走過的城市；為信息啟發(fā)因子；為t時刻城市的能見度；為期望啟發(fā)因子，表示能見度的重要性。為防止信息素殘留過多而影響后面螞蟻對啟發(fā)信息的識別，每只螞蟻移動一次或者周游所有的城市以后，必須要更新路徑上留下的信息素。經(jīng)過n個時刻，所有螞蟻完成一次循環(huán)。各路徑上的信息素按式(4.2)和(4.3)更新：(4.2)(4.2)(4.3)(4.3)其中，表示信息素?fù)]發(fā)系數(shù)，為信息殘留因子，通常；表示本次循環(huán)中路徑上的信息素增量；表示螞蟻k留在路徑的信息素。由于信息素的更新方式繁多，M.Dorigo提出了三種不同的根本蟻群算法模型，分為Ant-Cycle模型，Ant-Quantity模型和Ant-Density模型，其差異在于的數(shù)學(xué)運算方式不一樣。Ant-Cycle模型中其中，Q表示信息素強度，特定情形下是算法收斂性的表達(dá)；表示螞蟻k在本次循環(huán)中所走路徑的總長。Ant-Quantity模型中式和利用的是局部信息，即螞蟻完成一步后對這條路徑上的信息素進(jìn)行更新；而式利用的是全局信息，即螞蟻完成一個迭代后對所有路徑上的信息素進(jìn)行更新。【基于蟻群算法的機器人路徑規(guī)劃張美玉黃翰郝志峰楊曉偉】螞蟻不僅利用了路徑上的信息素,而且用到了城市間距離的倒數(shù)作為啟發(fā)式因子4.2.3蟻群算法的實現(xiàn)(1)蟻群參數(shù)狀態(tài)初始化：當(dāng)前節(jié)點初始化為起始點爬行路線初始化爬行路徑長度初始化初始化禁忌表初始化鄰接矩陣將m只螞蟻放到n個城市中確定每一次迭代時螞蟻下一步可以前往的節(jié)點；按照概率公式選擇下一個節(jié)點狀態(tài)更新：路徑增加，路徑長度增加，更新禁忌表；判斷是否滿足終止條件：螞蟻找到食物那么終止，輸出最短路徑，否那么繼續(xù)迭代。螞蟻限入陷阱，用輪賭法選擇其他節(jié)點。其算法流程圖如下列圖所示【基于蟻群算法的移動機器人路徑規(guī)劃算法研究】：開始信息初始化，將m信息初始化，將m只螞蟻放到n個城市將螞蟻所在初始城市放到各自的禁忌表將螞蟻所在初始城市放到各自的禁忌表是否是否到達(dá)最大循環(huán)或以收斂YYNN輸出最正確路徑對所有的螞蟻計算下一步狀態(tài)轉(zhuǎn)移概率，選擇下一個城市，將該城市參加禁忌表中Y各禁忌表的中的城市數(shù)<Y各禁忌表的中的城市數(shù)<NN更新最優(yōu)路徑，并更新所有路徑上的信息素更新最優(yōu)路徑，并更新所有路徑上的信息素循環(huán)次數(shù)加1循環(huán)次數(shù)加1，清空所有禁忌表結(jié)束蟻群算法流程圖根據(jù)柵格法建立的復(fù)雜環(huán)境模型〔圖〕，在matlab環(huán)境下進(jìn)行仿真，機械手的起始坐標(biāo)為(0.5,29.5),終點坐標(biāo)為(26.5,0.5)。黑色柵格表示障礙物，白色柵格表示自由空間，仿真結(jié)果如下圖。Figure1為根本蟻群算法實現(xiàn)機械手在靜態(tài)環(huán)境中的自動避障路徑規(guī)劃得到的路徑Figure2為根本蟻群算法實現(xiàn)機械手在靜態(tài)環(huán)境中的自動避障路徑規(guī)劃最短路徑圖3為根本蟻群算法的自動避障路徑規(guī)劃的平均路徑長度和最小路徑長度最小路徑長度平均路徑長度最小路徑長度平均路徑長度4.2.4根本蟻群算法的評價指標(biāo)算法的時間復(fù)雜度和空間復(fù)雜度是算法性能的主要評價。但是為了更加全面的衡量根本蟻群算法性能的好壞程度，在這里例舉出了三個根本指標(biāo)來評價根本蟻群算法。(1)相對誤差這里將定義為最優(yōu)性能指標(biāo)，公式如所示。(4.4)(4.4)其中，表示算法運行后得到的最優(yōu)值，為想要得到的理想最優(yōu)值。如果一開始理想最優(yōu)值是未知的，這時就可以用來代替。相對誤差表示算法經(jīng)過屢次運行所得到的結(jié)果與理想值之間的差異程度，所以它越小就代表著算法的性能越好。(2)時間性能指標(biāo)定義蟻群算法的時間性能指標(biāo)如式4.4所示。(4.5)(4.5)其中，是算法滿足結(jié)束條件時的平均迭代次數(shù)，是之前人為給定的迭代次數(shù)的最大值，是算法完成一次迭代運行的平均時間。根本蟻群算法的收斂性就是通過時間性能指標(biāo)來衡量的，當(dāng)?shù)闹倒潭〞r，越小就代表著算法的收斂速度越快。(3)適應(yīng)性指標(biāo)定義根本蟻群算法的適應(yīng)性指標(biāo)如式4.5所示。(4.6)(4.6)其中，是算法運行后得到的平均值，為想要得到的理想最優(yōu)值。根本蟻群算法對初始值和操作的依賴程度是通過適應(yīng)性來衡量的。因此，根本蟻群算法的綜合性能指標(biāo)就可以用上面三個性能指標(biāo)來表示:其中，分別代表三個性能指標(biāo)的加權(quán)系數(shù)，并且它們滿足：值越小，根本蟻群算法的綜合性能就越好。根本蟻群算法的缺乏之處從上面針對路由選擇優(yōu)化問題的分析可以看出，雖然蟻群算法已經(jīng)被證明是一種有效的解決組合優(yōu)化問題的方法，但是由于問世的時間比擬短，還存在如下缺乏：(1)限于局部最優(yōu)解．從算法解的性質(zhì)而言，蟻群算法也是在尋找一個比擬好的局部最優(yōu)解，而不是強求是全局最優(yōu)解．(2)工作過程的中間停滯問題．和算法開始時收斂速度快一樣，在算法工作過程當(dāng)中，迭代到一定次數(shù)后，螞蟻也可能在某個或某些局部最優(yōu)解的鄰域附近發(fā)生停滯．(3)較長的搜索時間．盡管和其他算法相比，蟻群算法在迭代次數(shù)和解的質(zhì)量上都有一定的優(yōu)勢，但對于目前計算機網(wǎng)絡(luò)的實際情況，還是需要較長的搜索時間．雖然計算機計算速度的提高和蟻群算法的并行性在一定程度上可以緩解這一問題，但是對于大規(guī)模復(fù)雜的計算機網(wǎng)絡(luò)，這還是一個很大的障礙．【根本蟻群算法及其改良孔令軍，張興華，陳建國?！?.3改良后的蟻群算法及其仿真實現(xiàn)4.3.1基于人工勢場的改良后的蟻群算法機器人路徑規(guī)劃的勢場蟻群算法(antcolonyoptimlzationwithpotentialfield，ACOPF)，其思想是，利用機器人受到的人工勢場力及其距目標(biāo)的距離構(gòu)造綜合啟發(fā)信息，以蟻群算法作為全局路徑搜索策略。勢場力啟發(fā)信息可以有效引導(dǎo)機器