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