【正文】 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 1 1 1 0。 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0。假設機器人要從Node1到達Node9如果不使用任何優(yōu)化算法，那么該機器人有8條路徑可走，但是這8條路徑的長短都不一樣，有比較長的，有比較短的，而此時我們使用dijkstra搜索算法，就可以對每一條路徑的權(quán)值之和進行比較，最終選擇權(quán)值之和最小的一條路徑，作為機器人從起點到達終點的最優(yōu)路徑，下圖中的紅色線條標示的路徑就是我們要尋找的最優(yōu)路徑。l 在上世紀60年代柵格法應運而生，并迅速在之后的移動機器人系統(tǒng)中得到實踐。顧名思義，可視圖法是基于障礙物頂點連線的，所以適用于多邊形多頂點的障礙物，不適用于無頂點的圓形障礙物。　建立移動機器人移動的環(huán)境模型建立環(huán)境模型就要將實際生活中的問題進行抽象化處理后再建立相關的環(huán)境模型。5)通過上述方法將會產(chǎn)生移動機器人的原始節(jié)點集{gi1, gi2, gi2,....., gin}，其中n≤m。從柵格gi(gi∈FS,i∈C)出發(fā)，設ARi為它的鄰域，視野域為BRi，此時能夠選擇的下一個節(jié)點gj(j∈C) 必須要滿足條件gj∈ARi且gj∈FS, 此時除去如圖5所示的那種情況(其中障礙柵格有黑色部分表示)，意思就是移動機器人不可能從兩個障礙物柵格之間經(jīng)過。此視野域中存在某一條路徑{gi1, gi2, gi2,....., gin}，其中n≤m，gk∈FS(k∈SS)。i∈C}，那么，可知柵格gi處的視野域即為BRi，其中L39。因此從空間這個方面來看，基本可以分為：1)依據(jù)C空間，即構(gòu)形空間(configuration space)的拓撲法和幾何法；2)人工勢場法，該法依據(jù)笛卡爾的直角坐標空間。僅從機器人本身來考慮對于研究機器人的路徑規(guī)劃是不夠的，我們還需要研究環(huán)境的狀況?；谝陨蠋c要求，智能機器人路徑規(guī)劃中就會關聯(lián)到 4個問題：1）智能機器人怎樣才能從周圍的環(huán)境中獲取障礙物的信息和與其相關的其他信息。隨著科學技術水平的提高和智能技術高速的發(fā)展，在功能和技術層次方面，使得機器人的路徑規(guī)劃都有了很大提高和改善，比如，一個典型的代表就是智能機器人的觸覺和視覺技術[9]。當環(huán)境全部未知時，智能機器人通過借助傳感器對周圍環(huán)境進行探測從而獲得到有效的信息，使用這些信息對機器人進行實時的路徑規(guī)劃。根據(jù)不同的應用環(huán)境采用不同的改進算法，使得粒子群算法的計算精度以及優(yōu)化效率更高［8］。就目前研究成果來說，改進的粒子群算法雖多，但對其理論研究并不是很好。 x(i,:)=x(i,:)+v(i,:)?！』玖Ｗ尤核惴鞒虉D初始化粒子的速度和位置計算每個微粒當前的適應值 與pbesti比較大小 pbesti較小 pbesti較大交換它的值，更新微粒在位置保持其值不變與gbest比較大小 Gbest較小 gbest較大交換它的值，更新微粒在位置保持其值不變根據(jù)(1)(2)式進化粒子位置和速度結(jié) 束根據(jù)以上流程圖，可對微粒群算法做此小結(jié)：粒子群算法是一種群體搜索尋優(yōu)的過程，群體中的每一個個體可以稱作粒子，在D維搜索看空間中，該粒子可作為待優(yōu)化問題的一個潛在解，該解保存有粒子群中所有粒子的最優(yōu)位置和歷史最優(yōu)位置的記憶，以及速度。式(1)的第二部分c1rand1(pbestidkxidk)是“認知”部分(cognition part)，體現(xiàn)了微粒對自身的學習。vidk是粒子i在第k次迭代中第d維的速度分量，它的更新值vidk+1由三部分組成：上一步的慣性vidk；向該粒子自身的最優(yōu)位置pbest逼近的加速度c1rand1(pbestidkxidk)；向所有粒子的最優(yōu)位置gbest逼近的加速度c2rand2(gbestdkxidk)。此時我們就知道了粒子能夠快速找到食物的原因了，粒子就是基于自己的飛行經(jīng)驗和同伴經(jīng)驗決定自己下一步的如何運動。遺傳算法中的交叉算子就和該算法中局部最優(yōu)靠近全局最優(yōu)的調(diào)整非常的相像。Frank Heppner的鳥類模型中在反映群體行為方面與其他類模型有許多相同之處，不同之處在于：鳥類是被誘引飛向這塊棲息地。2　粒子群優(yōu)化算法　粒子群優(yōu)概述群居昆蟲以集體的力量，進行覓食、御敵、筑巢的能力。這些未公開發(fā)表的文章往往是Maurice Clerc博士的一些設想，而且在不斷更新，如“Back to random topology”、“Initialisations for particle swarm optimization”、“Some ideas about PSO” 對PSO研究人員很有啟發(fā)，以及像中國知網(wǎng)、萬方這種大的學習網(wǎng)站都是為我們可以學習的地方。實際工業(yè)應用有：訓練人工神經(jīng)網(wǎng)絡、解決多目標優(yōu)化問題、求解帶有約束滿足的問題、電力系統(tǒng)、濾波器設計、自動控制、數(shù)據(jù)聚類、模式識別與圖像處理、化工、機械、通信、機器人、經(jīng)濟、生物信息、醫(yī)學、任務分配、TSP等等。最優(yōu)化技術我們的日常生活中的應用帶來了巨大的社會效益和經(jīng)濟效益，基于大量的實踐效果表明，在相同的人力、物力、財力的條件下，通過優(yōu)化技術處理過的，對系統(tǒng)效率的提高、能耗的降低和資源最高效率的使用等都具有明顯的效果，而且這種優(yōu)勢隨著群體規(guī)模的不斷增大而變得越來越顯著。這種算法不需要目標函數(shù)和約束的連續(xù)性與凸性、可導、可行域連通，即使沒有解析表達式也可以進行優(yōu)化，而且這些算法在計算復雜方面也表現(xiàn)除了相當大的優(yōu)勢，為優(yōu)化思想理論的發(fā)展提供了一個很有利的平臺。不管是國家的發(fā)展還是人民生活的發(fā)展不再僅僅是追求最基本的滿足，不再是僅僅只追求表面化的經(jīng)濟數(shù)據(jù)，社會在發(fā)展人們的思想觀念也在發(fā)展，人們渴望更優(yōu)秀的科研技術來滿足他們精神生活和物質(zhì)生活的需要。雖然人類不斷地對最優(yōu)化進行探索，但是有很多限制因素的存在，所以，一直都沒有很大的突破。其中機器人局部的路徑規(guī)劃方法,其又被稱為在線的或是動態(tài)的機器人路徑規(guī)劃方法,其中的作業(yè)環(huán)境部分或完全已知或完全未知或部分已知,有: 蟻群智能算法、粒子群智能算法、人工勢場算法和免疫算法以及模糊邏輯算法等方法?！妙I域該選題具有很大的應用范圍內(nèi)，它對人們的生活、工作都有很大的啟發(fā)意義。對一些初學者而言，哪里能下載得到PSO的源程序，是他們很關心的話題；即使對一些資深的讀者，為了驗證自己提出的新算法或改進算法，如果能找到高級別國際期刊或會議上最近提出的算法源程序，那也是事半功倍的美事。　研究內(nèi)容的創(chuàng)新點該篇論文我主要是環(huán)繞粒子群算法的優(yōu)化以及路徑規(guī)劃來完成的。系統(tǒng)初始化為一組隨機解，通過迭代搜索最優(yōu)值。另外也可以使用粒子鄰居個體尋找最優(yōu)解而不用整個種群尋找全局最優(yōu)解，這樣在所有鄰居中的極值就是局部極值。每一個都有一個適應度值（fitness），這個值是由被優(yōu)化的函數(shù)決定的，每個粒子飛翔的距離和力向取決于一個速度。每一次迭代運算，微?？筛鶕?jù)式(1)、(2)更新自身的速度和位置：vidk+1=vidk+c1rand1(pbestidkxidk)+c2rand2(gbestdkxidk) (1)xidk+1=xidk+vidk+1 (2)其中，i=1，2，．．．，n，d=l，2，．．．，D，k是迭代運算進行的次數(shù)，rand1和rand2為（0,1）之間的任意常數(shù)，保持群體的多樣性是通過這兩個參數(shù)來完成的。粒子群算法的結(jié)束條件是取得的最優(yōu)解在迭代計算的過程中值變化很小或者算法迭代步數(shù)超過事先所預設的值。以上式(1)、(2)的各個參數(shù)制定的準則：粒子數(shù)：粒子數(shù)的多少應該根據(jù)問題的自身的復雜程度進行選取。endPg=x(N,:)。end　代碼運行效果圖:圖1 粒子初始位置圖圖2 粒子初始速度圖圖3 不同參數(shù)的適應度曲線對比圖　特點與不足粒子群算法（PSO）是一種新型的放生優(yōu)化算法，是一種基于迭代的優(yōu)化算法。目前，在PSO算法的使用以及擴展研究方面，怎樣使得PSO算法結(jié)合像遺傳算法這種優(yōu)化算法來解決現(xiàn)實生活中的實際應用問題，這是我們需要不斷學習、不斷研究、不斷深入的方向。任何一種智能機器人，他在完成工作的過程中，總是需要基于某一規(guī)則，譬如，所要話費的時間要少，或是所要經(jīng)過的路徑長度要最短，或是其消耗的資源要少，再或是要求資源的利用率要高等等。　機器人路徑規(guī)劃的思想起源最近幾年, 隨著移動機器人技術快速發(fā)展, 其應用領域也在不斷擴展發(fā)展。2）對于傳感器感知的環(huán)境模型中的不確定性因素和路徑運行中出現(xiàn)的誤差，該規(guī)劃系統(tǒng)能夠?qū)ζ溥M行及時的處理。2）傳感技術?？傊?，之所以要研究機器人路徑規(guī)劃這個問題，就是因為在我們的生活中，我們?yōu)榱颂岣吖ぷ餍?，為了讓機器人從起始點到達目標點，即要過障礙物，又要讓其經(jīng)過的路徑最短，這樣既節(jié)省了時間，又節(jié)約了資源，而且對于工業(yè)上的各個方面都有很大的幫助，這就是為什么我們要研究這個課題的原因。定義2兩個柵格之間連線的長度指任意兩個柵格之間的距離，稱為dist（gi (xi,yi ), gj(xj, yj)），其中gi，gj∈A，i,j∈C。定義7 gigj(i,j∈C,gi,gj∈FS) 稱為柵格gi gj的中心線。使用這種方式進行編碼，保證了每一時刻所有的粒子都是同維的，因而粒子群的位置和速度向量均是定長的。3)改變gi的當前值做為本次所要選取的柵格gw，所以此次加入禁忌集合tabuk的柵格為gw。這樣既可以節(jié)約時間，而且可以提高機器人的運行效率，同時對我們的實際生活也會有所啟發(fā)，促使我們做出更深入的研究。環(huán)境建模的方法紛繁復雜，在應用于移動機器人路徑規(guī)劃方面，絕大多數(shù)是將實際的環(huán)境信息轉(zhuǎn)換為了圖的問題，進而抽象為對環(huán)境空間的骨架圖進行描述[4]。出于安全性考慮，設計的Voronoi圖具有獨特的幾何特性。優(yōu)點主要表現(xiàn)在：即使環(huán)境空間發(fā)生局部變化，也不用重新設計規(guī)劃圖，因而表現(xiàn)出了靈活性。 0 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 1 1 1 0 0 0 0 0 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 1 0 1 0 0 0 0 0 0 0 0 0 0 0。 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 1 1 1 0。]。P=biograph(G,[],39。,39。set(edges,39。4　粒子群優(yōu)化算法在機器人路徑規(guī)劃中的具體應用　問題描述與建模為了達到本論文的路徑規(guī)劃算法,在機器人運動環(huán)境建模時，我們作出了以下假設[20]：1) 智能機器人的運動環(huán)境空間為二維的；2) 在智能機器人的運行環(huán)境中存在著有限的已知靜態(tài)障礙物,我們能夠用多邊形表示障礙物。G矩陣中的每一個二進制值0或1就代表環(huán)境中一個位置。為了使得這個模型方便而且合理, 假定：在機器人從起始點到達目標位置的整個運行過程中, 所有在此環(huán)境模型中的障礙物的大小、幾何形狀均是靜止的和不變的。該論文中的微粒位置的更新以式(2)為標準，以下為本文采用的粒子位置更新策略:由PSO算法本身的特點，本篇論文中對微粒位置的更新事實上是對粒子位置向量中的某一個分量的更新，定義第i個微粒的位置向量為Xi=(Xi1,Xi2,Xi3,……,XiD)，那么定義更新后的位置分量為Xi39。但是上述位置分量的變化也許有可能使的更新后的位置分量Xi39。,Xi239。,Xi239。,Xi239。在此我選擇的是基于自然選擇的粒子群優(yōu)化算法。6　致謝歷經(jīng)了幾個月的忙碌學習，這一次艱難卻有意義的畢業(yè)設計將要馬上結(jié)束，作為一個本科生的畢業(yè)設計，由于經(jīng)驗的匱乏，所以不可避免存在許多考慮不周全的地方，因此，假設沒有導師的循循善誘的知道和督促，以及一起研究的同學們的幫助和支持，能夠這么順利的完成這個畢業(yè)設計簡直是非常難的。clc。 %學習因子2w=。 %隨機初始化速度 endend%先計算各個粒子的適應度，并初始化Pi和Pgfigure(3)for i=1:N P(i)=fitness2(x(i,:))。 end if P(i)fitness2(Pg) Pg=y(i,:)。 childx1(i,:)=pb*PoolX(seed1,:)+(1pb)*PoolX(seed2,:)。title(TempStr)。*************************************************************39。迭代次數(shù)39。endx(1:numPool,:)=childx1。if r1Pc %雜交概率 numPool=round(Sp*N)。endPg=x(N,:)。MaxDT=10000。%給定初始化條件c1=2。 所以，此時此刻我首先要感謝我的導師江祥奎老師給予我莫大的支持和幫助。通過父代位置進行算術交叉得到子代位置：child(x)=P*parent1(x)+(1P)* parent2(x) ()其中P是0到1之間的隨機數(shù)。,……,XiD39。,……,XiD39。,……,XiD39。,Xi239。,Xi239。依據(jù)改