【正文】 適應度值39。endendplot(Pbest)TempStr=sprintf(39。 %雜交池中粒子的速度for i=1: numPool seed1=floor(rand()*(numPool1))+1。 x(i,:)=x(i,:)+v(i,:)。 %初始化群體個體數(shù)目%eps=10^(6)。Pc=。他的治學嚴謹和科學研究的精神及淵博的理論知識令我受益匪淺也是我永遠學習的榜樣，并將積極影響我今后的學習和工作，也要感謝西安郵電大學對我為期四年的培育。本文利用粒子優(yōu)化群算法對機器人路徑進行規(guī)劃，我首先是采取柵格法的到所有可行路徑，最后用粒子群算法度路徑進行優(yōu)化最終選取一條最佳路徑，粒子群算法中初始參數(shù)的選擇會影響粒子最終的適應度值，迭代次數(shù)的多少會影響運算的精度，柵格法選取最短路徑實際上是根據(jù)權值的大小來決定的。通過上述定義7可得到如果uiui+1(1≤i≤CGS1)可以表示柵格序號為ui、ui+1的柵格中心的連線，那么必須滿足uiui+1不會穿過任何障礙柵格才可以使得機器人運行的路徑完全避障，即不會超過當前視野域的任何一邊又不會出現(xiàn)圖5所示的情形，如果至少存在一個排列是滿足上述要求的，那么就能夠允許更新，否則不可以更新。但是，在實際的運算當中以及算法當中，當有多條路徑時，機器人最終只能選擇其中的一條。不滿足上述條件就不允許更新。) 所映射的路徑不能達到安全避障的目標。)?！?shù)的選擇該篇論文中優(yōu)化算法的學習因子cc2都取2，w的變化趨勢是隨著迭代次數(shù)的增加線性減小的，計算如下式：W=wmax—iter*(wmaxwmin)/itermax (11)式中，截止到目前的迭代次數(shù)為iter，當前總的迭代次數(shù)為itermax，wmax=，wmin=，其余參數(shù)均根據(jù)合理參數(shù)范圍選擇即可。gi∈A的坐標(xi,yi)與序號i∈C形成映射關系，可以用式()確定序號i的坐標：xi= ((i 1)modNx) + 1，yi=( int) ((i 1) /Nx) + 1 (6)式中,取整運算用int來計算,求余運算用mod來計算。認為AS為任何形狀, 因此,，可在AS邊緣處補全為障礙的柵格,，將其補為長方形或正方形。,)。%以下三條語句用紅色修飾最短路徑edges=getedgesbynodeid(H,get((Path),39。%建立有向圖對象PH=view(P)。 %邊權值向量，有向圖，G(9,9)=0。 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0 0 1 1 0。 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0。 0 1 1 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 1 1 0 0 0 0 1 1 1 1 0。 0 1 1 1 0 0 1 1 1 0 0 0 0 0 0 1 0 0 0 0。在柵格模型中我們可以隨意規(guī)劃障礙物的位置，是路徑規(guī)劃常采用的方法。它的優(yōu)點在于，處理障礙物的邊界時，避免了復雜的數(shù)學計算。缺點也是顯而易見的，如果環(huán)境空間發(fā)生了變化，比如障礙物個數(shù)改變了，這樣就比較麻煩了，就不得不再從新構造一張圖，也由此看出了它缺乏靈活性和實時性，而且位置誤差對機器人無碰撞安全行走的影響很大。所謂環(huán)境建模就是合理而有效地表示移動機器人的工作空間(環(huán)境信息)。6)對種群中所有粒子的初始位置均由上述算法產生，最后得到了種群初始位置。則式(4)可以計算下一個節(jié)點的柵格集合可選項。如圖4所示，(其中陰影部分表示障礙柵格)，假設某一條局部路徑為{1, 7, 8, 13, 18, 19, 24, 25}, 則此條路徑對應的粒子編碼為X=1000001100001000011000011。定義5 很多個柵格所構成的集合{gi1, gi2, gi2,....., gin}，其中將SS記為{ij|1≤j≤n,ij∈C}，gk∈FS(k∈SS)，并且滿足dist(gij,gij+1)=1或者dist(gij,gij+1)= 2，則此集合表示一條路徑，而且gk為此可行路徑上的一個路徑點。與從空間方面不同，以機器人獲取周圍環(huán)境信息的多少，大致可以分為：1)機器人對周圍的環(huán)境信息基本不熟悉，就連周圍障礙物的幾何性質和位置都不了解；2)機器人對周圍的環(huán)境信息基本不熟悉或者是只知道一部分，只能借用傳感器在線地探測機器人的移動環(huán)境的信息，以此方法來獲得障礙物的幾何性質和位置等信息，所以，上述的規(guī)劃方法可以隨時對周圍環(huán)境信息的采集以及機器人所處環(huán)境模型的動態(tài)信息進行更正和更新；3)機器人周圍的環(huán)境信息中存在某種障礙物，其能夠以某種可知或可預知的方法來不斷移動，這就是所謂的動態(tài)障礙物。2）已知環(huán)境下的動態(tài)障礙物的大小、形狀和位置對規(guī)劃系統(tǒng)的影響，但是它與靜態(tài)不同，它的位置是動態(tài)可變的。3）智能機器人機怎樣確定它的下一步行動策略，依據(jù)當前地圖中的信息和其處于當前地圖的位置。本文系統(tǒng)地討論路徑規(guī)劃技術的研究現(xiàn)狀與發(fā)展趨勢。事實上，移動機器人的定位、導航以及規(guī)劃路徑這三者是相輔相成、缺一不可的。在這樣的需要下，我們的研究者就提出了路徑規(guī)劃的這一概念，這樣我們就很清楚研究路徑規(guī)劃的實際意義。PSO算法的不足：對于粒子群算法容易存在局部最優(yōu)化問題，也就是容易存在早熟收斂問題。 y(i,:)=x(i,:)。每一個粒子在多維度的搜索空間中不斷改變它們的狀態(tài)，直到達到平衡或最優(yōu)狀態(tài)，或者超過了算法的截止范圍。式(1)則是根據(jù)粒子之前一次的速度及現(xiàn)在的位置和自身最好的飛行經驗與群體中最好經驗之間的差距來不斷改變速度的當前值。位置更新值xidk+1是上一步的位置xidk與更新后的速度vidk+1之和。假設群體由n個微粒所組成。而且這兩位研究者Eherhart和Kennedy也將此優(yōu)化算法在神經網(wǎng)絡權重的訓練上有所應用，而且針對求解一些測試函數(shù)的最優(yōu)值方面有很大的效果，以上的一些應用都驗證了粒子群算法的實際應用性。第一個向量決定它的飛向速度，第二個向量決定它的飛行方向。粒子群算法是一種仿生優(yōu)化算法，它是通過模擬鳥類群體的捕食行為，其中每只鳥都代表模擬中的一個粒子，這種優(yōu)化算法是：設想有一塊每個小鳥都想吃到的食物在一片未知的區(qū)域內(即最優(yōu)化問題中解的位置)，并且要求每只鳥(即個體粒子)都不知道食物的精確位置，但是在這種情況下，它們每個個體是知道它們自己的具體位置的，并且它們每一個個體都有能力判斷，它們的位置是不是食物所在的位置以及它們現(xiàn)在離食物的距離，此外它們還知道群體中別的鳥的大體位置，所以我們大家肯定想知道它們是如何快速的尋找到到食物的呢？最簡單效的方法是尋找種群中離食物距離最近的鳥的位置。 　主要工作本論文中我們既然要研究群智能優(yōu)化算法以及機器人路徑規(guī)劃，那么我們最主要的工作有兩方面。本論文主要分析的是粒子群優(yōu)化算法的應用，以它當前的發(fā)展狀況來說，我們熟知的有基于粒子群優(yōu)化算法的無人機航跡規(guī)劃、基于粒子群優(yōu)化算法的機器人最短路徑規(guī)劃、基于群智能算法的CDMA多用戶檢測方法研究、基于粒子群優(yōu)化算法的集群調度策略研究等等，這些研究成果足以說明其現(xiàn)在的發(fā)展狀況和研究方向。讓大家充分了解機器人的路徑是可以通過一種群智能算法來優(yōu)化的。移動機器人在存在障礙物的環(huán)境中遵循一定的評價標準(如行走路徑最短，工作代價最小, 行走所需時間最短等標準),搜尋一條從所給起點到達目標終點的無碰撞路徑，這就是移動機器人路徑規(guī)劃技術。所以最優(yōu)化這個詞語成為人們的社會生活中經常使用的術語，它體現(xiàn)出了人們社會活動的非常常見的現(xiàn)象，可以用這樣一句話總結最優(yōu)化這個術語：它就是在人力、物力、財力不變條件況下，怎樣可以使得資源的利用率最大，而且獲得利潤最大。最優(yōu)化實際上是以數(shù)學技術為基礎的一門技術，一直以來人們?yōu)榱藵M足生活的需要不斷地對最優(yōu)化進行不斷地努力和探索，在很久以前，就有科學家發(fā)明了具有優(yōu)化思想的微積分、以梯度下降法解決無約束優(yōu)化問題。移動機器人路徑規(guī)劃的方式有很多種，在此我介紹兩種:一種是基于算法的不同,分為智能路徑規(guī)劃和傳統(tǒng)路徑規(guī)劃。我們不僅僅是讓機器人沿著一條路徑來移動，而是要讓機器人不斷地搜尋最佳路徑，最終確定出一條最優(yōu)路徑來完成任務。 　電子資源身處信息和網(wǎng)絡時代的我們是幸運的，豐富的電子資源能讓我們受益匪淺。一方面，我們要很清楚粒子群算法的工作原理以及如何最實際問題進行優(yōu)化的以及我們應該怎樣對基本粒子群算法進行優(yōu)化，使其精度最高、效率最大；另一方面，既然我們要研究路徑規(guī)劃，那么我們就需要對機器人運行的環(huán)境進行模擬，即我們首先要解決環(huán)境建模的問題，同時在環(huán)境建模的基礎上對機器人的路徑進行規(guī)劃?；谶@種思想,就出現(xiàn)了粒子群算法(Particle Swarm Optimization，PSO)，它是一種進化了的計算機技術（evolutionary putation），最早出現(xiàn)是在1995年由Russell Eberhart和James Kennedy博士在文獻[67]中提出了粒子群優(yōu)化算法，它的核心想法是受到鳥類的群體行為，并且它們對這種群體行為進行環(huán)境建模與仿真研究，這種研究給予他們了一些啟發(fā)，但是他們的環(huán)境模型和仿真優(yōu)化算法主要還是借用了生物學家Frank Heppner的建模模型[6]。通過粒子群的初始化后，基于迭代的運算方式搜索最佳解，并且在每一次迭代運算的過程中，每個粒子通過尋找兩個極值來不斷地改變更新自己的速度和位置?！∷惴ㄔ碓赑SO算法中，搜索空間中的每一只鳥都對應著優(yōu)化問題的解，每一只鳥被形象的化作沒有體積和質量的粒子，并將其延伸到N維空間。N代表了群體規(guī)模的大小，n的大小會直接影響算法的收斂性和運算速度。為了讓每個粒子不遠離搜索空間，所有微粒每一維的速度vd都會被限制在[vdmin, vdmin]之間，vdmin取值過大，就會導致這個區(qū)間的范圍過大，而且微粒很容易脫離最優(yōu)位置，這個區(qū)間過小就會使粒子群陷入局部最優(yōu)的麻煩。然后微粒根據(jù)式(2)逼近新的位置?！』玖Ｗ尤核惴∕atlab主要代碼及效果圖主要代碼：%先計算各個粒子的適應度，并初始化Pi和Pgfigure(3)for i=1:N P(i)=fitness2(x(i,:))。 end if P(i)fitness2(Pg) Pg=y(i,:)。而且這種早熟收斂問題，在粒子群算法處理高維或者超高維復雜函數(shù)優(yōu)化問題就會出現(xiàn)，這種早熟收斂問題是受粒子更新機制的限制，而且這種問題是指在粒子找到最優(yōu)解之前粒子已經提早聚集到一點再也不會變化。機器人在復雜的環(huán)境中，從起始點到目標點，并可以繞過障礙物，移動機器人通過其內部存儲的周圍環(huán)境地圖的信息，或者是借助傳感器探測的環(huán)境信息，這就是路徑規(guī)劃的作用。通過移動機器人的定位技術，機器人就能了解到它本身所位于的位置。路徑規(guī)劃問題是移動機器人在各個研究領域中的重要的一項研究內容，它是依據(jù)某一性能指標尋求一條從起始位置到達目標位置的最優(yōu)或近似最優(yōu)的無碰撞的路徑[10]。4）智能機器人怎樣發(fā)出有效的驅動信號，促使智能機器人在預定的軌跡上移動。3）對規(guī)劃系統(tǒng)來說，環(huán)境的狀況是部分未知的或者是未知的，其障礙物的形狀和大小是在那樣的，只要是靜態(tài)障礙物，它在環(huán)境中都是靜止不動的?！∠嚓P定義為了敘述方便, 給出如下定義和約束條件：定義1 ?g∈A，g不∈S則將g稱為可用的柵格，可行柵格集就是由所有可用的的柵格組成的，可以將其以FS作為標記；?g∈A, g∈S此時可將g稱為障礙物（即障礙柵格），所以，障礙柵格集就是指由所有的障礙柵格所組成的，記為NFS。定義6 tabuit為第i個粒子在t時刻已走柵格位置的集合，稱為禁忌集合，防止粒子重復走某一個柵格。這樣，每一位置向量都表示了一條或者多條路徑。而本篇論文采用賭輪盤法來決定即將走的下一個路徑點，式(9)計算概率，得到：NGS={gj|j∈C, gj∈ARi, gj∈FS, gj≠NS} (4)Prob=1/|NGS| (5) 圖5 路徑排除情況　路徑規(guī)劃的規(guī)劃流程以第k個微粒為例，其產生初始位置的算法的完整步驟為以下6步:1)gi(gi∈FS,i∈C)作為當前出發(fā)的初始柵格，由上述所做的定義可知當前的tabuk0為空集?！÷窂揭?guī)劃所要達到的目的通過使用柵格法使用二進制編碼方法對機器人的路徑進行規(guī)劃，該方法所要實現(xiàn)的目的也是很有實際意義的，通過環(huán)境建模得到機器人運行路徑的模型，最后根據(jù)位置編碼的方法，得到機器人路徑的路線。環(huán)境建模是移動機器人實現(xiàn)導航定位的基礎與前提。l Voronoi圖法是對可視圖法的改進，此方法有效地減少了搜索時間。作為一種有效的環(huán)境表示方法，柵格法越來越得到人們的重視，并表現(xiàn)出很好的發(fā)展前景。而本篇論文我采用的是柵格法，原因是其操作容易而且能夠達到所要的效果。 0 1 1 1 0 0 0 1 1 0 0 0 0 1 0 1 0 0 0 0。 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0。 0 1 1 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0。 0 0 0 0 0 0 0 1 1 0 0 0 1 1 0 0 0 0 0 0。 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0。 9個節(jié)點G=sparse(S,E,W)。%顯示各個路徑權值[Dist,Path]=graphshortestpath(G,1,9,39。ID39?！÷窂剿阉鞣椒▽ふ液虾鯒l件的路徑的算法。在AS中原點O以以其左上角的坐標來表示，系統(tǒng)的直角坐標系依據(jù)橫向為x軸，縱向為y軸的規(guī)則建立。針對所有的不規(guī)則多性邊形而且是二維的的，其進行路徑