群智能優(yōu)化算法在機器人路徑規(guī)劃中的應用的畢業(yè)設計-資料下載頁

　　

【正文】 的某個分量的值由原始的0變成了1，或者是從原始的1變成了0。但是上述位置分量的變化也許有可能使的更新后的位置分量Xi39。=(Xi139。,Xi239。,Xi339。,……,XiD39。) 所映射的路徑不能達到安全避障的目標。因此，在我們改變某一微粒的位置Xi=(Xi1,Xi2,Xi3,……,XiD) 的某一維分量的值的時候，我們都要對系統(tǒng)進行越界檢查和避障檢查，看更新后的位置向量Xi39。=(Xi139。,Xi239。,Xi339。,……,XiD39。)，檢查其所對應的路徑是否超過視野域范圍或者是不是和障礙物相碰。如果即達到安全避障又沒有超過視野域范圍，就可以允許將Xi添加到Xi39。，不滿足上述條件就不允許更新。可以假設微粒更新后的位置向量為Xi39。=(Xi139。,Xi239。,Xi339。,……,XiD39。)，某一視野域中所走過的可行柵格均被記錄在此向量中，但是此法有個缺點就是，它并沒有折射出這些柵格被經(jīng)過的先后順序。如由5圖所示，其中位置向量為X=1000001100001000011000011，那么機器人可能經(jīng)過的的路徑為1→7→8→13→19→18→24→25或者1→7→8→13→18→19→24→25。但是，在實際的運算當中以及算法當中，當有多條路徑時，機器人最終只能選擇其中的一條。因此，怎樣對更新后的位置向量Xi39。=(Xi139。,Xi239。,Xi339。,……,XiD39。)是粒子位置更新的關鍵，并且對其進行越界檢查和避障檢查。本篇文章所使用的檢查策略為提取出來位置向量Xi=(Xi1,Xi2,Xi3,……,XiD) 中值為1的柵格序號，并將提取出來的這些序號構成集合CGS={u|u∈C,Xiu=1}，對其進行全排列P|CGS||CGS|，并且對P|CGS||CGS|中的每一個序列u1, u2, u3,......, u|CGS|進行避障檢查和邊界檢查。通過上述定義7可得到如果uiui+1(1≤i≤CGS1)可以表示柵格序號為ui、ui+1的柵格中心的連線，那么必須滿足uiui+1不會穿過任何障礙柵格才可以使得機器人運行的路徑完全避障，即不會超過當前視野域的任何一邊又不會出現(xiàn)圖5所示的情形，如果至少存在一個排列是滿足上述要求的，那么就能夠允許更新，否則不可以更新。　粒子群優(yōu)化算法的改進混合粒子群算法：該論文中采用的粒子群優(yōu)化算法是混合粒子群優(yōu)化算法，混合粒子群算法是指借鑒其他一些智能優(yōu)化算法的思想而形成的粒子群算法。除了粒子群算法外，還有遺傳算法/模擬退火算法以及神經(jīng)網(wǎng)絡智能算法，這些算法是目前應用比較廣泛的智能算法，每種智能算法都有其特點，因此自然而然就有了結合各種智能算法的優(yōu)點而形成的混合粒子群算法。在此我選擇的是基于自然選擇的粒子群優(yōu)化算法。算法的原理：借鑒遺傳算法中的雜交概念，在每次迭代中，選取指定數(shù)量的粒子放入雜交池中是依據(jù)雜交概率來進行選擇的，將池中的微粒任意進行兩兩雜交，并且產(chǎn)生的子代粒子（child）的數(shù)量和原始池中的數(shù)量是一樣的，此時可將子代微粒替換親代微粒（parent）。通過父代位置進行算術交叉得到子代位置：child(x)=P*parent1(x)+(1P)* parent2(x) ()其中P是0到1之間的隨機數(shù)。而且子代微粒的速度大小可由式()計算得到：child(v)=parent1v+parent2(v)|parent1v+parent2v||parent1(v)| ()算法步驟：1)種群中各微粒的位置和速度的初始化取值是隨機的；2)評價每個微粒的適應度，將當前各微粒的適應度值和位置儲存在各粒子的pbest中，將所有的pbest的適應值最優(yōu)個體的適應度值和位置儲存在gbest中；3)更新每個個體粒子的當前位置和當前速度；4)對于每一個粒子來說，將其所經(jīng)歷過的最好位置和該粒子的當前位置作比較，如果較好，則將該粒子的當前位置替換其所經(jīng)歷的最優(yōu)位置；5)通過將當前所有gbest和pbest的值做比較，根據(jù)比較結果來判斷是否要更新gbest；6)放在雜交池中的粒子的數(shù)量是由雜交概率決定的，池中的微粒隨機進行兩兩雜交并且產(chǎn)生與父代同樣數(shù)目的子代微粒，子代的速度和位置計算公式為式()()，此時要使得gbest和pbest的值保持不變；7)如果已經(jīng)滿足所設定的停止條件（即開始時設置的最大迭代次數(shù)或者預設的運算精度），則停止搜索，輸出運行結果，否則就返回3)繼續(xù)進行搜索。優(yōu)化后粒子群算法實現(xiàn)收斂效果圖：圖10 改進粒子群算法適應度曲線　仿真效果圖圖11 收斂曲線圖12 最優(yōu)化路徑仿真圖5　結論通過以上過程的論述，我起初用基本粒子群算法對問題進行優(yōu)化，但是基本粒子群算法雖然能夠進行優(yōu)化，但是其優(yōu)化效率低，而且運算精度也打不到要求，何況針對移動機器人路徑規(guī)劃這一復雜的問題，其運算復雜，而且要求的結果要比較精確，所以最終我就采用了混合粒子群算法，其與基本粒子群算法沒有很明顯的區(qū)別，只是在迭代運算的過程中加入了一些遺傳算法中交叉算子的思想，再加入該思想之后，通過matlab的編碼實現(xiàn)對機器人路徑的規(guī)劃，其效果可以通過上述仿真圖看出。本文利用粒子優(yōu)化群算法對機器人路徑進行規(guī)劃，我首先是采取柵格法的到所有可行路徑，最后用粒子群算法度路徑進行優(yōu)化最終選取一條最佳路徑，粒子群算法中初始參數(shù)的選擇會影響粒子最終的適應度值，迭代次數(shù)的多少會影響運算的精度，柵格法選取最短路徑實際上是根據(jù)權值的大小來決定的。通過粒子群優(yōu)化算法與路徑規(guī)劃方法的結合最終完成了機器人最優(yōu)路徑的選取。這是本篇論文最主要的隨想。6　致謝歷經(jīng)了幾個月的忙碌學習，這一次艱難卻有意義的畢業(yè)設計將要馬上結束，作為一個本科生的畢業(yè)設計，由于經(jīng)驗的匱乏，所以不可避免存在許多考慮不周全的地方，因此，假設沒有導師的循循善誘的知道和督促，以及一起研究的同學們的幫助和支持，能夠這么順利的完成這個畢業(yè)設計簡直是非常難的。雖然這次畢業(yè)設計做的很艱辛，但是通過輔導老師給予的參考資料和同學們給予的幫助以及自己不懈的努力，最終還是完成了。 所以，此時此刻我首先要感謝我的導師江祥奎老師給予我莫大的支持和幫助。雖然他平時有很多的工作，但是在我做畢設的每一個階段江老師都會及時給予我?guī)椭瑥牟殚嗁Y料到現(xiàn)場指導，文獻綜述和外文資料翻譯修改，中期檢查，后期詳細設計，程序實現(xiàn)等整個過程中都給予了我悉心的指導。我的設計較為復雜煩瑣，而且本身學習底子不是很好，但是江老師仍然細心地糾程序和文章中的錯誤。他的治學嚴謹和科學研究的精神及淵博的理論知識令我受益匪淺也是我永遠學習的榜樣，并將積極影響我今后的學習和工作，也要感謝西安郵電大學對我為期四年的培育。最后，值此論文完成之際，謹向我的導師江祥奎老師致以衷心的感謝和崇高的敬意。參考文獻[1]楊維．粒子群優(yōu)化算法綜述［J］．中國工程科學出版社，2004．6(5)：87－94．[2]馬兆青，袁曾任．基于柵格的移動機器人實時導航和避障[ 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]成偉明，唐振民，趙春霞，劉華軍．移動機器人路徑規(guī)劃中的圖方法應用綜述[J]．工程圖學學報，2008(4):6－14． [11]孫鐵波．單體移動機器人環(huán)境建模方法研究[J]．科技信息，2008(28):222．[5]章軍．小生境粒子群優(yōu)化算法及其在多分類器集成中的應用研究[D]：[博士學位論文]．合肥：中國科技大學研究生院，2007．[6]劉希玉，劉弘 編著．人工神經(jīng)網(wǎng)絡與微粒群優(yōu)化（第11章 粒子群算法）．北京郵電大學出版社，2008．3(1)．264—277．[7]俞歡軍，張麗平，陳德釗等．基于反饋策略的自適應粒子群優(yōu)化算法[J].浙江大學學報(工學版)，2005．39(9):1286－1291．[8]龔純，王正林編著，精通MATLAB最優(yōu)化計算（第2版）．273－342[9]霍迎輝，張連明．一種移動機器人的路徑規(guī)劃算法[J]．自動化技術與應用，2003．22(5)：8－10．[10]謝宏斌，劉國棟．動態(tài)環(huán)境中基于模糊神經(jīng)網(wǎng)絡的機器人路徑規(guī)劃的一種新方法[J]．江南大學學報（自然科學版），2003．2(1)：20－27．[11]周蘭鳳，洪炳熔．用基于知識的遺傳算法實現(xiàn)移動機器人路徑規(guī)劃[ J]．電子學報，2006．34( 5)：911－914．[12]姚亞峰．Dijkstra算法的一種高效率實現(xiàn)[ J]．計算機與數(shù)字工程，2007．7( 35)： 21－23．[13]于紅斌，李孝安．基于柵格法的機器人快速路徑規(guī)劃[J]．微電子學與計算機，2005．22(6)：98－100．[14]謝克煒．移動機器人室內(nèi)復雜場景下的動態(tài)路徑規(guī)劃[D]．大連:大連理工大學碩士學位論文，2008．15－23．[15]莊慧忠．機器人路徑規(guī)劃及相關算法研究[J]．科技通報，2004 ．210－215.附錄主程序：%基本粒子群優(yōu)化算法（Particle Swarm Optimization）%名稱：混合粒子群優(yōu)化算法（基于雜交的算法）%作用：求解優(yōu)化問題%說明：全局性，并行性，高效的群體智能算法%初始格式化clear all。clc。format long。%給定初始化條件c1=2。 %學習因子1%c1=3。%c2=2。Pc=。Sp=。c2=2。 %學習因子2w=。 %慣性權重%MaxDT=500。MaxDT=10000。 %最大迭代次數(shù)D=5。 %搜索空間維數(shù)（未知數(shù)個數(shù)）N=40。 %初始化群體個體數(shù)目%eps=10^(6)。 %設置精度(在已知最小值時候用)%初始化種群的個體(可以在這里限定位置和速度的范圍)for i=1:N for j=1:D x(i,j)=randn。 %隨機初始化位置 v(i,j)=randn。 %隨機初始化速度 endend%先計算各個粒子的適應度，并初始化Pi和Pgfigure(3)for i=1:N P(i)=fitness2(x(i,:))。 y(i,:)=x(i,:)。endPg=x(N,:)。 %Pg為全局最優(yōu)for i=1:(N1) if fitness2(x(i,:))fitness2(Pg) Pg=x(i,:)。 endend%進入主要循環(huán)，按照公式依次迭代，直到滿足精度要求for t=1:MaxDT for i=1:N v(i,:)=w*v(i,:)+c1*rand*(y(i,:)x(i,:))+c2*rand*(Pgx(i,:))。 x(i,:)=x(i,:)+v(i,:)。 if fitness2(x(i,:))P(i) P(i)=fitness2(x(i,:))。 y(i,:)=x(i,:)。 end if P(i)fitness2(Pg) Pg=y(i,:)。 endr1=rand()。if r1Pc %雜交概率 numPool=round(Sp*N)。 %雜交池大小 PoolX=x(1: numPool,:)。 %雜交池中粒子的位置 PoolVX=v(1: numPool,:)。 %雜交池中粒子的速度for i=1: numPool seed1=floor(rand()*(numPool1))+1。 seed2=floor(rand()*(numPool1))+1。 pb=rand()。 childx1(i,:)=pb*PoolX(seed1,:)+(1pb)*PoolX(seed2,:)。 %子代的位置計算childv1(i,:)=(PoolVX(seed1,:)+PoolVX(seed2,:))*norm(PoolVX(seed1,:))/norm(PoolVX(seed1,:)+PoolVX(seed2,:))。endx(1:numPool,:)=childx1。 %子代位置替換父代位置v(1:numPool,:)=childv1。 %子代速度替換父代速度 end Pbest(t)=fitness2(Pg)。endendplot(Pbest)TempStr=sprintf(39。c1= %g ,c2=%g39。,c1,c2)。title(TempStr)。xlabel(39。迭代次數(shù)39。)。ylabel(39。適應度值39。)。%最后給出計算結果disp(39。*************************************************************