群智能優(yōu)化算法在機(jī)器人路徑規(guī)劃中的應(yīng)用的畢業(yè)設(shè)計(jì)-文庫吧在線文庫

　　

【正文】 置pbest和整個(gè)種群目前的全局最優(yōu)位置gbest，它們分別代表了粒子個(gè)體對自身和社會(huì)的認(rèn)知水平[7]。在N維空間里，粒子i位置被看做是一個(gè)矢量，粒子i的飛行速度也被看做是一個(gè)矢量。群體中第i個(gè)微粒為Xi=(xi1,xi2,...,xid,..,xiD)第i個(gè)粒子(i=1,2,.....,n)的D維位置矢量，它經(jīng)歷過的位置為Pi=(pi1,pi2,....,pid,...piD)依據(jù)之前給定的適應(yīng)度函數(shù)來計(jì)算微粒此時(shí)的適應(yīng)值，適應(yīng)值的大小可以衡量當(dāng)前粒子位置的優(yōu)劣；Vi=(vi1......vid.....viD)為第i個(gè)微粒的飛行速度，就是粒子在一段時(shí)間內(nèi)運(yùn)行的長度， pbesti=(pbesti1,pbesti2,.......,pbestiD)為粒子到目前尋找到的最優(yōu)位置；gbesti =(gbest1,......,gbestD)為整個(gè)微粒群到目前尋找到的最優(yōu)位置。通常情況下，每一維速度值的取法是vdmin=kxdmin,k[9]。在此總結(jié)出，粒子群算法是主要遵循了五項(xiàng)基本原則，分別為：(1)鄰近原則(proximity)：在簡單的時(shí)間和空間計(jì)算方面，粒子群必須有能力執(zhí)行；(2)品質(zhì)原則(quality)：在周圍環(huán)境的品質(zhì)因數(shù)有所變化時(shí)，粒子群必須有所感應(yīng) (變量pbest和gbest隱含著這一原則)；(3)多樣性反應(yīng)原則(diverse response)：粒子群盡量避免在過于狹小的空間內(nèi)運(yùn)動(dòng)；(4)定性原則(stability)：在每次環(huán)境改變的時(shí)候，粒子群不應(yīng)該每一次都改變自己的行為準(zhǔn)則；(5)適應(yīng)性原則(adaptability)：在能夠接受的計(jì)算量下，粒子群能夠在適當(dāng)?shù)臅r(shí)候改變他們的行為。 y(i,:)=x(i,:)。 end end Pbest(t)=fitness2(Pg)。所以，我們此刻面臨的問題就是急切需要找到一種有效的方法、有效的機(jī)制讓粒子群算法克服早熟收斂的現(xiàn)象，逃離陷入局部極小點(diǎn)。作為移動(dòng)機(jī)器人研究領(lǐng)域中的一個(gè)比較核心的問題—路徑規(guī)劃，它也是研究人工智能的一個(gè)主要方面，怎樣可以規(guī)劃出一條有效的通路，這個(gè)才是研究領(lǐng)域的的核心問題。同時(shí)，也只有有了路徑規(guī)劃得出的可行路徑，導(dǎo)航才能有目標(biāo)的進(jìn)行，機(jī)器人才能避免與障礙物碰撞。因而，在智能機(jī)器人路徑規(guī)劃系統(tǒng)中，有以下幾點(diǎn)主要要求，它們分別是：1）在周圍環(huán)境的建模中尋找一條路徑，確保機(jī)器人沿這條路徑運(yùn)行時(shí)，不會(huì)與外界產(chǎn)生碰撞。所以為了解決上述所提出的問題，要對對應(yīng)的 4個(gè)技術(shù)展開研究：1）自動(dòng)定位技術(shù)。4）對路徑規(guī)劃系統(tǒng)來說，環(huán)境事先是部分未知的或未知的，障礙物的形狀或是大小怎樣，只要是動(dòng)態(tài)障礙物，其在環(huán)境中一定是可變的。 即A = FS∪NFS。其中tabui0表示初始時(shí)刻第i個(gè)粒子已走柵格位置的集合，即tabui0為空集。因此，粒子的維數(shù)由某時(shí)刻柵格gi處視野域BRi中柵格總數(shù)m決定，因此整個(gè)路徑規(guī)劃過程中粒子群的維數(shù)是可變的。2)下一個(gè)路徑點(diǎn)的選擇范圍可由式(4)所決定,基于式(5)的公式計(jì)算概率的方式并且采用賭輪盤法在當(dāng)前位置gi的視野域BRi范圍內(nèi)，即將路過的節(jié)點(diǎn)由柵格gw承擔(dān)，即gw必須滿足w∈C，gw∈NGS且gw不∈tabuk。對機(jī)器人進(jìn)行路徑規(guī)劃的目的就是使機(jī)器人最終繞過障礙物到達(dá)目標(biāo)點(diǎn)，并且從起始點(diǎn)到達(dá)目標(biāo)點(diǎn)的路徑長度最短。一個(gè)適當(dāng)?shù)沫h(huán)境模型有助于對環(huán)境的理解，有利于降低路徑規(guī)劃決策搜索空間的計(jì)算量，從而減小不必要的消耗。它是俄國數(shù)學(xué)家Voronoi最早提出的，也因此而命名。l 自由空間法首先把環(huán)境空間中的障礙物抽象為二維平面內(nèi)的各種凸多邊形，然后在這個(gè)空間內(nèi)構(gòu)造連通圖，即完成了自由空間法的環(huán)境建模。使用柵格法所產(chǎn)生的環(huán)境建摸圖如下圖所示：網(wǎng)格賦值矩陣為：G1=[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0。 0 1 1 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0。 0 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 0 1 1 0。 0 0 0 0 0 0 1 1 0 0 0 0 1 0 0 1 0 0 0 0。 0 0 0 0 1 1 0 0 1 1 1 0 0 0 0 0 0 0 0 0。 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0。 %關(guān)聯(lián)矩陣的稀疏矩陣表示G(9,9)=0。Method39。))。經(jīng)過環(huán)境建摸以及dijkstra搜索算法的操作，機(jī)器人從起點(diǎn)到終點(diǎn)的路徑有很多條，而我們就是要運(yùn)用粒子群優(yōu)化算法把這些可達(dá)路徑中的最優(yōu)路徑找出來。在此過程中我們可以設(shè)想移動(dòng)機(jī)器人在水平方向上的移動(dòng)的距離為δ，xmax、ymax為AS在x、y方向的移動(dòng)的最大值，一個(gè)柵格的形成是根據(jù)δ為步長對環(huán)境進(jìn)行劃分的，則Nx=xmax/δ為每行的柵格數(shù)， Ny=ymax/δ作為每列的柵格數(shù)，其中bi(i=1,2,3,......,n) 或者占一個(gè)柵格或著占多個(gè)柵格，當(dāng)不滿一個(gè)柵格時(shí)算一個(gè)柵格。基于柵格法所建立的環(huán)境模型, 智能機(jī)器人可以在二維有限空間內(nèi)可以向8個(gè)方向中的任意一個(gè)方向移動(dòng), 如圖8所示。微粒位置更新問題是機(jī)器人路徑規(guī)劃二進(jìn)制粒子群算法的最重要的部分。的差別就是其中的某個(gè)分量的值由原始的0變成了1，或者是從原始的1變成了0。=(Xi139。=(Xi139。=(Xi139。除了粒子群算法外，還有遺傳算法/模擬退火算法以及神經(jīng)網(wǎng)絡(luò)智能算法，這些算法是目前應(yīng)用比較廣泛的智能算法，每種智能算法都有其特點(diǎn)，因此自然而然就有了結(jié)合各種智能算法的優(yōu)點(diǎn)而形成的混合粒子群算法。這是本篇論文最主要的隨想。參考文獻(xiàn)[1]楊維．粒子群優(yōu)化算法綜述［J］．中國工程科學(xué)出版社，2004．6(5)：87－94．[2]馬兆青，袁曾任．基于柵格的移動(dòng)機(jī)器人實(shí)時(shí)導(dǎo)航和避障[ J]．機(jī)器人， 1996．18( 6): 344－348． [3]Eberhart R，Kennedy new optimizer using particle swarm theory[C]．Proc of the SixthInternational Symposium on Micro Machine and Human Science,Nagoya，Japan．1995:39－43．[4]成偉明，唐振民，趙春霞，劉華軍．移動(dòng)機(jī)器人路徑規(guī)劃中的圖方法應(yīng)用綜述[J]．工程圖學(xué)學(xué)報(bào)，2008(4):6－14． [11]孫鐵波．單體移動(dòng)機(jī)器人環(huán)境建模方法研究[J]．科技信息，2008(28):222．[5]章軍．小生境粒子群優(yōu)化算法及其在多分類器集成中的應(yīng)用研究[D]：[博士學(xué)位論文]．合肥：中國科技大學(xué)研究生院，2007．[6]劉希玉，劉弘 編著．人工神經(jīng)網(wǎng)絡(luò)與微粒群優(yōu)化（第11章 粒子群算法）．北京郵電大學(xué)出版社，2008．3(1)．264—277．[7]俞歡軍，張麗平，陳德釗等．基于反饋策略的自適應(yīng)粒子群優(yōu)化算法[J].浙江大學(xué)學(xué)報(bào)(工學(xué)版)，2005．39(9):1286－1291．[8]龔純，王正林編著，精通MATLAB最優(yōu)化計(jì)算（第2版）．273－342[9]霍迎輝，張連明．一種移動(dòng)機(jī)器人的路徑規(guī)劃算法[J]．自動(dòng)化技術(shù)與應(yīng)用，2003．22(5)：8－10．[10]謝宏斌，劉國棟．動(dòng)態(tài)環(huán)境中基于模糊神經(jīng)網(wǎng)絡(luò)的機(jī)器人路徑規(guī)劃的一種新方法[J]．江南大學(xué)學(xué)報(bào)（自然科學(xué)版），2003．2(1)：20－27．[11]周蘭鳳，洪炳熔．用基于知識的遺傳算法實(shí)現(xiàn)移動(dòng)機(jī)器人路徑規(guī)劃[ J]．電子學(xué)報(bào)，2006．34( 5)：911－914．[12]姚亞峰．Dijkstra算法的一種高效率實(shí)現(xiàn)[ J]．計(jì)算機(jī)與數(shù)字工程，2007．7( 35)： 21－23．[13]于紅斌，李孝安．基于柵格法的機(jī)器人快速路徑規(guī)劃[J]．微電子學(xué)與計(jì)算機(jī)，2005．22(6)：98－100．[14]謝克煒．移動(dòng)機(jī)器人室內(nèi)復(fù)雜場景下的動(dòng)態(tài)路徑規(guī)劃[D]．大連:大連理工大學(xué)碩士學(xué)位論文，2008．15－23．[15]莊慧忠．機(jī)器人路徑規(guī)劃及相關(guān)算法研究[J]．科技通報(bào)，2004 ．210－215.附錄主程序：%基本粒子群優(yōu)化算法（Particle Swarm Optimization）%名稱：混合粒子群優(yōu)化算法（基于雜交的算法）%作用：求解優(yōu)化問題%說明：全局性，并行性，高效的群體智能算法%初始格式化clear all。c2=2。 %隨機(jī)初始化位置 v(i,j)=randn。 y(i,:)=x(i,:)。 pb=rand()。,c1,c2)。%最后給出計(jì)算結(jié)果disp(39。)。 %子代位置替換父代位置v(1:numPool,:)=childv1。 %雜交池大小 PoolX=x(1: numPool,:)。 %Pg為全局最優(yōu)for i=1:(N1) if fitness2(x(i,:))fitness2(Pg) Pg=x(i,:)。 %最大迭代次數(shù)D=5。 %學(xué)習(xí)因子1%c1=3。雖然他平時(shí)有很多的工作，但是在我做畢設(shè)的每一個(gè)階段江老師都會(huì)及時(shí)給予我?guī)椭瑥牟殚嗁Y料到現(xiàn)場指導(dǎo)，文獻(xiàn)綜述和外文資料翻譯修改，中期檢查，后期詳細(xì)設(shè)計(jì)，程序?qū)崿F(xiàn)等整個(gè)過程中都給予了我悉心的指導(dǎo)。而且子代微粒的速度大小可由式()計(jì)算得到：child(v)=parent1v+parent2(v)|parent1v+parent2v||parent1(v)| ()算法步驟：1)種群中各微粒的位置和速度的初始化取值是隨機(jī)的；2)評價(jià)每個(gè)微粒的適應(yīng)度，將當(dāng)前各微粒的適應(yīng)度值和位置儲(chǔ)存在各粒子的pbest中，將所有的pbest的適應(yīng)值最優(yōu)個(gè)體的適應(yīng)度值和位置儲(chǔ)存在gbest中；3)更新每個(gè)個(gè)體粒子的當(dāng)前位置和當(dāng)前速度；4)對于每一個(gè)粒子來說，將其所經(jīng)歷過的最好位置和該粒子的當(dāng)前位置作比較，如果較好，則將該粒子的當(dāng)前位置替換其所經(jīng)歷的最優(yōu)位置；5)通過將當(dāng)前所有g(shù)best和pbest的值做比較，根據(jù)比較結(jié)果來判斷是否要更新gbest；6)放在雜交池中的粒子的數(shù)量是由雜交概率決定的，池中的微粒隨機(jī)進(jìn)行兩兩雜交并且產(chǎn)生與父代同樣數(shù)目的子代微粒，子代的速度和位置計(jì)算公式為式()()，此時(shí)要使得gbest和pbest的值保持不變；7)如果已經(jīng)滿足所設(shè)定的停止條件（即開始時(shí)設(shè)置的最大迭代次數(shù)或者預(yù)設(shè)的運(yùn)算精度），則停止搜索，輸出運(yùn)行結(jié)果，否則就返回3)繼續(xù)進(jìn)行搜索。)是粒子位置更新的關(guān)鍵，并且對其進(jìn)行越界檢查和避障檢查。)，某一視野域中所走過的可行柵格均被記錄在此向量中，但是此法有個(gè)缺點(diǎn)就是，它并沒有折射出這些柵格被經(jīng)過的先后順序。)，檢查其所對應(yīng)的路徑是否超過視野域范圍或者是不是和障礙物相碰。,Xi339。,Xi339。假設(shè)itermax為最大迭代次數(shù)，存儲(chǔ)當(dāng)前迭代次數(shù)和的為變量iter，設(shè)置粒子群優(yōu)化算法中每個(gè)參數(shù)w、ccVmax、wmax、wmin的初始值，并且定義一個(gè)路徑表Path，此路徑表是用來表示結(jié)果的；2)以移動(dòng)機(jī)器人現(xiàn)在所在的位置和此時(shí)視野域信的息為依據(jù)，并且采用初始粒子群產(chǎn)生方法初始化種群中各粒子速度向量Vi和位置向量Xi (1≤i≤N)，如果初始化不成功則退出整個(gè)算法程序；3)每一個(gè)粒子的適應(yīng)值Fi(即目標(biāo)函數(shù)值)的值通過式(10)來進(jìn)行計(jì)算；4)每一個(gè)粒子i(1≤i≤N) 的歷史最優(yōu)解pbest通過式(7)來進(jìn)行更新；Pbesti(t+1)=Pbestit，若Fi（Xit+1Fi(Pbestit)）Xit+1，若Fi（Xit+1Fi(Pbestit)） (7)5)種群的全局最優(yōu)解Gbest通過式(8)來完成更新，其中i = 1, 2,.....,N；Gbest(t+1)=Gbestt， 若GbesttminFi(Pbestit+1）PbestiargminFiPbestitt+1，若GbesttminFi(Pbestit+1）(8)6)每一個(gè)微粒的速度通過式(1)來完成更新, 如果更新后的速度Vij(t+1) 大于+Vmax或者小于Vmax，則需要調(diào)整Vij(t+1)，確保更新后速度不小于Vmax，且不大于+Vmax，調(diào)整的計(jì)算式，如式(9)：Vij(t+1)=Vmax，若Vijt+1Vmax+Vmax，若Vijt+1+Vmax (9)7)每一個(gè)微粒的位置通過式(2)并且采用粒子位置和速度的方法來完成更新，當(dāng)前迭代次數(shù)iter加1；8)如果iter itermax 那么就返回(3)，否則就繼續(xù)執(zhí)行下一步；9)在路徑表Path中追加當(dāng)前得到的此視野域中的最優(yōu)路徑；10)如果到達(dá)目標(biāo)位置Gend或者到達(dá)柵格g(xg,yg) 滿足g∈ARGend，并且gGend不可能出現(xiàn)圖5情形，則轉(zhuǎn)11)，否則更新機(jī)器人的當(dāng)前位置作為此局部路徑終點(diǎn)，并且轉(zhuǎn)2)；11)從起始位置到達(dá)目標(biāo)位置的最優(yōu)路徑保存到路徑表Path保存，此時(shí)算法結(jié)束。g∈A在坐標(biāo)系中都有確定的坐標(biāo)(x, y)，記做g(x, y)，g所在的行號為x，g所在的列號為y。所以本論文我采用的是柵格法[ 5]，柵格法環(huán)境搭建方便、易于實(shí)現(xiàn)并且計(jì)算量小，不妨為路徑規(guī)劃所選擇的一個(gè)好的方法。set(edges,39。Color39。on39。 %起始節(jié)點(diǎn)向量 E=[2 3 5 4 4 6 5 7 8 6 7 8 9 9 9]。 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0。 0 1 1 1 0 0 0 1 1 1 0 0 0 1 0 1 0 0 0 0。]。 0