蟻群算法在路徑優(yōu)化中的應(yīng)用

《蟻群算法在路徑優(yōu)化中的應(yīng)用》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

1、安慶師范學(xué)院數(shù)學(xué)與計(jì)算科學(xué)學(xué)院2015屆畢業(yè)論文蟻群算法在路徑優(yōu)化中的應(yīng)用作者：孫陽陽指導(dǎo)老師：劉沖摘要如何在繁雜的道路系統(tǒng)中選擇最優(yōu)的路徑是蟻群算法在路徑優(yōu)化中的重要問題.本文在理解蟻群算法概念和原理的基礎(chǔ)上，用數(shù)學(xué)形式給出了蟻群算法的數(shù)學(xué)模型，得到蟻群算法在應(yīng)用中的基本步驟.通過解決幾路徑規(guī)劃的問題，分析蟻群算法的優(yōu)缺點(diǎn)，就其發(fā)展現(xiàn)狀對該算法未來研究方向做展望.關(guān)鍵詞蟻群算法算法模型分析應(yīng)用發(fā)展現(xiàn)狀及趨勢1引言隨著社會的飛速發(fā)展和信息的不斷交流，生活中越來越多的事情要求在短時(shí)間內(nèi)完成.如城市化的速度加快，如何選擇城市交通的最佳路徑已成為一個(gè)亟待解決的問題、以車載導(dǎo)航系統(tǒng)

2、為代表的路徑搜說問題以及近些年研究熱門（機(jī)器人路徑規(guī)劃問題）都需要一個(gè)最優(yōu)路徑解決方案.當(dāng)然隨著科學(xué)研究的發(fā)展，已經(jīng)有越來越多的方法來解決路徑優(yōu)化問題如：遺傳算法，A*算法，神經(jīng)網(wǎng)絡(luò)算法，人工勢場法，模糊邏輯法.但是這些算法都有不小的弊端：遺傳算法具有隨機(jī)優(yōu)化的特點(diǎn)，但是其局部搜素能力并不強(qiáng)，容易出現(xiàn)早熟現(xiàn)象；A*算法雖然往往能得到最優(yōu)的路徑，但是其局限性比較差而且算式中的啟發(fā)式函數(shù)如果選擇錯(cuò)誤會使得在搜索中進(jìn)入一個(gè)死循環(huán)；神經(jīng)網(wǎng)絡(luò)算法雖然具有學(xué)習(xí)能力很強(qiáng)的特點(diǎn)，但是訓(xùn)練過程比較困難，操作不太容易；模糊邏輯算法的適應(yīng)能力比較差.為此我們利用蟻群算法來解決實(shí)際應(yīng)用問題，研究和

3、相關(guān)文獻(xiàn)得出算法的可行性和優(yōu)越性.運(yùn)用蟻群算法在幾路徑規(guī)劃上的應(yīng)用，掌握其解決實(shí)際問題的過程及應(yīng)用.2蟻群算法2.1蟻群算法的概念蟻群算法(antcolonyoptimization),又稱螞蟻算法，簡稱ACO.是由Dorigom、Maniezzov、Colorni等人在1992年所發(fā)表的論文提出的，其靈感來源于螞蟻在尋找食物中發(fā)現(xiàn)路徑的行為.它是一種模擬進(jìn)化算法，通過人工模擬螞蟻覓食過程，即個(gè)體間的信息交流與合作不斷排除不適合的路途，最終尋找到從蟻穴到食物源的最短路徑.2.2蟻群算法的基本原理螞蟻在搜尋食物過程中總能找到一條從蟻穴到到食物的最優(yōu)路徑，這是因?yàn)槲浵佋谒褜ぢ窂?/p>

4、上釋放一種特殊的信息素.當(dāng)它們遇到一個(gè)還沒有被走過的路口時(shí)，會隨機(jī)的選擇一條路徑，而選擇的路徑與信息素的濃度有關(guān)，同時(shí)在該路徑上它們也會釋放自己的信息素.路徑越短，信息素濃度越大；反正路徑越長信息素堆積的越少.則過一段時(shí)間螞蟻選擇信息素濃度高的路徑的概率越來越大，而其它路徑隨著螞蟻越來越少的選擇信息素濃度逐漸減小，這一就形成了一個(gè)正反饋現(xiàn)象，最終指導(dǎo)整個(gè)蟻群找到從蟻穴到食物源的最短路徑.2.3蟻群算法數(shù)學(xué)模型2.3.1問題的描述求解兩地間最優(yōu)路徑，即為求某兩地間用時(shí)最少的行進(jìn)路線.如在一個(gè)城市中，有A、B第14頁共14頁安慶師范學(xué)院數(shù)學(xué)與計(jì)算科學(xué)學(xué)院2015屆畢業(yè)論文兩個(gè)地

5、點(diǎn)，從A到B有多條路徑線路可選，即求一條從A到B用時(shí)最少的路線.又比如在當(dāng)今熱門研究項(xiàng)目機(jī)器人路徑規(guī)劃問題中，其本質(zhì)為在規(guī)劃空間內(nèi)依據(jù)環(huán)境信息，在某些評價(jià)標(biāo)準(zhǔn)下，找出從出發(fā)點(diǎn)到目標(biāo)點(diǎn)最優(yōu)的路線，比較有代表的問題是噴涂機(jī)器人，即在一個(gè)復(fù)雜曲面上如何規(guī)劃噴涂機(jī)器人的路徑，使其噴涂效率最高.這些問題都符合蟻群算法的思想，因此可以用蟻群算法來求解.2.3.2模型的建立首先將螞蟻覓食與路徑優(yōu)化問題進(jìn)行對照如表1所示表1螞蟻覓食路徑優(yōu)化問題螞蟻要遍歷的各個(gè)路徑各個(gè)狀態(tài)整個(gè)蟻群經(jīng)過的一條完整的路徑解最短路徑最優(yōu)解信息素的濃度各狀態(tài)的吸引度信息素的更新狀態(tài)更新路徑的長度目標(biāo)函數(shù)以旅行商問題

6、（TSP）為例來構(gòu)建模型，定義路與路段的交叉口為節(jié)點(diǎn)，路段為邊.即TSP問題可描述為給定n個(gè)節(jié)點(diǎn)和每兩個(gè)節(jié)點(diǎn)之間的距離，要尋找到一條路徑，從某個(gè)節(jié)點(diǎn)出發(fā)周游到其它節(jié)點(diǎn)一次且僅一次，最終回到出發(fā)節(jié)點(diǎn)的封閉環(huán)路徑長度最短.設(shè)節(jié)點(diǎn)數(shù)為n，螞蟻的數(shù)目為m，螞蟻從一個(gè)節(jié)點(diǎn)到另一個(gè)節(jié)點(diǎn)逐步完成搜索的過程.螞蟻k(k=1,2,3...m)，根據(jù)概率轉(zhuǎn)換的規(guī)則選擇下一個(gè)節(jié)點(diǎn).由此可以生成一個(gè)由n個(gè)節(jié)點(diǎn)組成的行動路線，并伴有信息素的不斷更新.表示位于t時(shí)刻節(jié)點(diǎn)i的螞蟻數(shù)目.則有：d表示兩個(gè)節(jié)點(diǎn)i和j之間的距離在基本蟻群算法模型中，人工智能螞蟻有以下特點(diǎn)：(1)人工智能螞蟻具有記憶功能.每一個(gè)

7、螞蟻k(k=1,2,3,....m)都有一個(gè)禁忌表()，即螞蟻經(jīng)過節(jié)點(diǎn)i()后，不能再經(jīng)過節(jié)點(diǎn)i.(2)兩個(gè)節(jié)點(diǎn)的距離越近，能見度則越大，被選擇的期望也就越高，由此來指引人工智能螞蟻的搜索.定義，被稱為期望因子，所以螞蟻k在t時(shí)刻從節(jié)點(diǎn)i轉(zhuǎn)移到節(jié)點(diǎn)j的概率可表示為：（1）其中表示禁忌例表中第s個(gè)元素，即螞蟻所走過的第s個(gè)節(jié)點(diǎn)；第14頁共14頁安慶師范學(xué)院數(shù)學(xué)與計(jì)算科學(xué)學(xué)院2015屆畢業(yè)論文為螞蟻所允許到達(dá)的節(jié)點(diǎn)的集合，；期望因子表示對邊上的期望程度；表示信息素的相對重要程度；表示啟發(fā)式因子的相對重要程度.這里需要重