資源描述：
《基于蟻群算法的路徑規(guī)劃.doc》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、MATLAB實現(xiàn)基于蟻群算法的機(jī)器人路徑規(guī)劃1、問題描述移動機(jī)器人路徑規(guī)劃是機(jī)器人學(xué)的一個重要研究領(lǐng)域。它要求機(jī)器人依據(jù)某個或某些優(yōu)化原則(如最小能量消耗，最短行走路線，最短行走時間等)，在其工作空間中找到一條從起始狀態(tài)到目標(biāo)狀態(tài)的能避開障礙物的最優(yōu)路徑。機(jī)器人路徑規(guī)劃問題可以建模為一個有約束的優(yōu)化問題，都要完成路徑規(guī)劃、定位和避障等任務(wù)。2算法理論蟻群算法（AntColonyAlgorithm，ACA），最初是由意大利學(xué)者DorigoM.博士于1991年首次提出，其本質(zhì)是一個復(fù)雜的智能系統(tǒng)，且具有較強(qiáng)的
2、魯棒性，優(yōu)良的分布式計算機(jī)制等優(yōu)點。該算法經(jīng)過十多年的發(fā)展，已被廣大的科學(xué)研究人員應(yīng)用于各種問題的研究，如旅行商問題，二次規(guī)劃問題，生產(chǎn)調(diào)度問題等。但是算法本身性能的評價等算法理論研究方面進(jìn)展較慢。Dorigo提出了精英蟻群模型（EAS），在這一模型中信息素更新按照得到當(dāng)前最優(yōu)解的螞蟻所構(gòu)造的解來進(jìn)行，但這樣的策略往往使進(jìn)化變得緩慢，并不能取得較好的效果。次年Dorigo博士給出改進(jìn)模型（ACS），文中改進(jìn)了轉(zhuǎn)移概率模型，并且應(yīng)用了全局搜索與局部搜索策略，來得進(jìn)行深度搜索。Stützle與Hoos給出了最
3、大-最小螞蟻系統(tǒng)（MAX-MINAS），所謂最大-最小即是為信息素設(shè)定上限與下限，設(shè)定上限避免搜索陷入局部最優(yōu)，設(shè)定下限鼓勵深度搜索。螞蟻作為一個生物個體其自身的能力是十分有限的，比如螞蟻個體是沒有視覺的，螞蟻自身體積又是那么渺小，但是由這些能力有限的螞蟻組成的蟻群卻可以做出超越個體螞蟻能力的超常行為。螞蟻沒有視覺卻可以尋覓食物，螞蟻體積渺小而蟻群卻可以搬運比它們個體大十倍甚至百倍的昆蟲。這些都說明螞蟻群體內(nèi)部的某種機(jī)制使得它們具有了群體智能，可以做到螞蟻個體無法實現(xiàn)的事情。經(jīng)過生物學(xué)家的長時間觀察發(fā)現(xiàn)，
4、螞蟻是通過分泌于空間中的信息素進(jìn)行信息交流，進(jìn)而實現(xiàn)群體行為的。下面簡要介紹蟻群通過信息素的交流找到最短路徑的簡化實例。如圖2-1所示，AE之間有兩條路ABCDE與ABHDE，其中AB，DE，HD，HB的長度為1，BC，CD長度為0.5，并且，假設(shè)路上信息素濃度為0，且各個螞蟻行進(jìn)速度相同，單位時間所走的長度為1，每個單位時間內(nèi)在走過路徑上留下的信息素的量也相同。當(dāng)t=0時，從A點，E點同時各有30只螞蟻從該點出發(fā)。當(dāng)t=1，從A點出發(fā)的螞蟻走到B點時，由于兩條路BH與BC上的信息素濃度相同，所以螞蟻以相
5、同的概率選擇BH與BC，這樣就有15只螞蟻選擇走BH，有15只螞蟻選擇走BC。同樣的從E點出發(fā)的螞蟻走到D點，分別有15只螞蟻選擇DH和DC。當(dāng)t=2時，選擇BC與DC的螞蟻分別走過了BCD和DCB，而選擇BH與DH的螞蟻都走到了H點。所有的螞蟻都在所走過的路上留下了相同濃度的信息素，那么路徑BCD上的信息素的濃度是路徑BHD上信息素濃度的兩倍，這樣若再次有螞蟻選擇走BC和BH時，或選擇走DC與DH時，都會以較大的概率選擇信息素濃度高的一邊。這樣的過程反復(fù)進(jìn)行下去，最短的路徑上走過的螞蟻較多，留下的信息素
6、也越多，蟻群這樣就可以找到一條較短的路。這就是它們?nèi)后w智能的體現(xiàn)。蟻群算法就是模擬螞蟻覓食過程中可以找到最短的路的行為過程設(shè)計的一種仿生算法。在用蟻群算法求解組合優(yōu)化問題時，首先要將組合優(yōu)化問題表達(dá)成與信息素相關(guān)的規(guī)范形式，然后各個螞蟻獨立地根據(jù)局部的信息素進(jìn)行決策構(gòu)造解，并根據(jù)解的優(yōu)劣更新周圍的信息素，這樣的過程反復(fù)的進(jìn)行即可求出組合優(yōu)化問題的優(yōu)化解。歸結(jié)蟻群算法有如下特點：（1）分布式計算：各個螞蟻獨立地構(gòu)造解，當(dāng)有螞蟻個體構(gòu)造的解較差時，并不會影響整體的求解結(jié)果。這使得算法具有較強(qiáng)的適應(yīng)性；（2）自
7、組織性：系統(tǒng)學(xué)中自組織性就是系統(tǒng)的組織指令是來自系統(tǒng)的內(nèi)部。同樣的蟻群算法中的各個螞蟻的決策是根據(jù)系統(tǒng)內(nèi)部信息素的分布進(jìn)行的。這使得算法具有較強(qiáng)的魯棒性；（3）正反饋機(jī)制與負(fù)反饋機(jī)制結(jié)合：若某部分空間上分布的信息素越多，那么在這個空間上走過的螞蟻也就越多；走過的螞蟻越多，在那個空間上留下的信息素也就越多，這就是存在的正反饋機(jī)制。但蟻群算法中解的構(gòu)造是通過計算轉(zhuǎn)移概率實現(xiàn)的，也就是說構(gòu)造解的時候可以接受退化解，這限制了正反饋機(jī)制，可以使得搜索范圍擴(kuò)大，這是蟻群算法中隱含的負(fù)反饋機(jī)制。3求解步驟應(yīng)用蟻群算法求
8、解機(jī)器人路徑優(yōu)化問題的主要步驟如下：（1）輸入由0和1組成的矩陣表示機(jī)器人需要尋找最優(yōu)路徑的地圖的地圖，其中0表示此處可以通過的，1表示此處為障礙物。上圖的表示矩陣為：00000000000000000000;01100000000000000000;01100011100000000000;00000011100000000000;00000011100000000000;01110011100000000000;01110
