【文章內容簡介】 自身的知識庫或自身的組織結構進行再組織，從而實現算法求解能力的進化?；鞠伻核惴ǖ牧鞒蘙1415]如圖32所示。N開始結束滿足終止條件設置參數，初始化評價蟻群信息素更新概率選擇移動方向n=n+1Y輸出最短路徑圖32 基本蟻群算法流程圖4 基于蟻群算法的機器人路徑規(guī)劃 環(huán)境建模為了實現移動機器人的路徑規(guī)劃，首先使用柵格法對機器人工作空間進行建模，如圖41，黑格表示為障礙柵格，其余白色柵格為自由柵格。并且，假設在柵格數組中用1表示為障礙物，0為自由空間。因此，圖41可轉化為以數據形式存儲地圖信息的01矩陣，如圖42所示。圖41 機器人工作環(huán)境的柵格模型圖42 機器人工作環(huán)境的柵格數組表示 算法的描述每只人工螞蟻并不是像我們想象的需要知道整個環(huán)境的信息，它們其實只關心很小范圍內的信息，而且根據這些局部信息利用幾條簡單的規(guī)則（如下）進行決策。1）覓食規(guī)則：在每只人工螞蟻能感知的范圍內尋找是否有食物，實驗中它能觀察到的范圍是33個柵格，如果發(fā)現食物就直接過去。否則判斷是否有信息素，并且比較在能感知的范圍內哪一點的信息素最多，這樣，它就向信息素多的地方移動。同時，每只人工螞蟻會以一定的小概率犯錯誤，概率越大，說明人工螞蟻越具創(chuàng)新性，避免了陷入過早的局部收斂。2）選擇節(jié)點規(guī)則：每只人工螞蟻朝信息素多的方向移動，為了防止人工螞蟻原地轉圈，可以通過建立禁忌表的方式將訪問過的節(jié)點放入禁忌表中，以此判斷是否朝該方向移動，如果發(fā)現要走的下一節(jié)點已經存在禁忌表中，它就會盡量避開。這也是人工螞蟻優(yōu)于實際螞蟻之處，因為人工螞蟻具有記憶特性。3）避障規(guī)則：如果人工螞蟻要移動的方向有障礙物擋住，它會隨機選擇另一個方向，并且在信息素指引下，按照前兩條規(guī)則繼續(xù)移動。4）信息素更新規(guī)則：人工螞蟻每移動到一個節(jié)點，都會撒播一定量的信息素，以指引后面的同伴。然而，為避免殘留信息素過多引起殘留信息淹沒啟發(fā)信息，在每只人工螞蟻走完一步或者完成一次迭代后，需對殘留信息進行揮發(fā)更新處理。根據這幾條規(guī)則，人工螞蟻之間并沒有直接的關系，但是每只人工螞蟻都和環(huán)境發(fā)生交互，而通過信息素這個紐帶，實際上把各個人工螞蟻聯系起來了。比如，當一只人工螞蟻找到了食物，它并沒有直接告訴伙伴這兒有食物，而是向環(huán)境撒播信息素，當其它的人工螞蟻經過它附近的時候，就會感覺到信息素的存在，進而根據信息素的指引找到了食物。機器人路徑規(guī)劃的蟻群算法可簡單描述為：第1輪派出m只螞蟻從節(jié)點S出發(fā)，對于每只螞蟻以當前節(jié)點為中心，按一定的策略選擇并移動到下一個節(jié)點。當第一只螞蟻到達目標節(jié)點E，因為這只螞蟻最先到達，用時最少，所以它得到的路徑在蟻群本輪尋優(yōu)中是最優(yōu)的，保存該路徑為當前最優(yōu)路徑，并在該路徑上進行信息素更新。然后，另外派出m只螞蟻繼續(xù)尋優(yōu)。若螞蟻得到新的路徑，則將新路徑與當前最優(yōu)路徑進行比較，若新路徑優(yōu)于當前最優(yōu)路徑，則將新路徑更新保存為當前最優(yōu)路徑，并對新的當前最優(yōu)路徑進行信息素更新。如此往復，直到規(guī)定的代數完成或滿足設定的其他條件結束[16]。 算法的步驟Step1：初始化。每一代螞蟻的數目為m，將螞蟻放置在出發(fā)點S，并把S加入到禁忌表中(k=1,2,3,…,m)。列表記錄了每一代螞蟻k當前所走過的節(jié)點。 表示t時刻在（i,j）邊上殘留的信息激素量，令初始時刻各條邊上的信息量為同一常數，（為常數）。設置實驗迭代次數NG=1，最大代數為。Step2：根據策略選擇下一節(jié)點j 。在時刻t，螞蟻從節(jié)點i轉移到節(jié)點j的概率為 （41）其中，表示螞蟻k下一步允許選擇的所有節(jié)點。和分別表示路徑上信息量和啟發(fā)式因子的重要程度。是一個啟發(fā)式因子，表示螞蟻從節(jié)點i轉移到節(jié)點j的期望程度，通常取 （42）表示節(jié)點i和節(jié)點j之間的距離。螞蟻從當前柵格轉移到下一柵格，如果總是在可選擇的柵格中選取轉移概率的最大者，就會使算法失去隨機性，從而陷入局部最優(yōu)解。為解決此問題，采用“輪盤賭”[17]方法選擇節(jié)點j，并將j加入禁忌表中。輪盤賭選擇是一常用的隨機選擇方法，類似于博彩游戲中的輪盤賭。根據節(jié)點轉移概率（j=1, 2,…,n）將一個圓盤分成n份，其中第j個扇形的中心角為 。在進行選擇時，轉動一下圓盤，待圓盤停穩(wěn)后，若某參照點落入到第j個扇形內，則選擇節(jié)點j ?？梢姡∩刃蔚闹行慕窃酱?，其扇形區(qū)域的面積越大，則它所代表的節(jié)點的轉移概率也越大，從而該節(jié)點被選擇到的機會也越多。Step3：信息素更新。經過時間后，各條路徑上的信息素按式(43)進行調整。 (43)其中，表示信息素的揮發(fā)系數，表示信息素的殘留因子，為了防止信息素的無限積累，的取值范圍為：。表示經過時間路徑（i,j）上信息素的增量，初始時刻。 (44)式中，表示第k只螞蟻經過時間路徑（i,j）上信息素的增量。根據信息素更新策略的不同，[12]，分別稱之為AntCycle模型、AntQuantity模型及AntDensity模型，其差別在于求法不同。在AntCycle模型中， (45)式中，Q表示信息素強度，它在一定程度上影響算法的收斂速度；表示第k只螞蟻在本次循環(huán)中所走路徑的總長度。在AntQuantity模型中， (46)在AntDensity模型中， (47)式(46)和(47)中利用的是局部信息，即螞蟻每完成一步后就更新路徑上的信息素；而式(45)中利用的是整體信息，即螞蟻完成一次迭代后再更新所有路徑上的信息素，在求解TSP時性能較好。由于本課題與TSP原理類似，因此，也采用式(45)作為蟻群算法的基本模型。Step4：NG++，若NG，則停止，否則轉到Step2。Step5：輸出最優(yōu)路徑，算法結束。5 仿真實驗及結果分析 仿真實驗，程序文件共有三個，完成蟻群算法的路徑規(guī)劃功能。首先將三個文件復制到Matlab的當前路徑下，程序調用格式如下：load DATA[ROUTES,PL,Tau]=RPPACA(G,ones(400,400),50,30,1,400,1,10,1)。全部螞蟻爬過的軌跡如圖51所示，圖52是大多數螞蟻選擇前往目標點的一條路徑，這條路徑就是所要的最優(yōu)路徑，即機器人的移動路徑。圖51 全部螞蟻爬過的軌跡圖52 最短路徑的螞蟻爬行圖 結果分析圖53為收斂曲線圖，從圖可知算法執(zhí)行到第8代時已得到收斂的路徑解，并且在以后的迭代過程中沒有得到更好的解，算法的收斂已趨于穩(wěn)定。而平均路徑長度也隨著螞蟻搜索路徑的迭代次數增加而變短，收斂逐漸趨于最短路徑的收斂值。最后。圖53 收斂曲線仿真實驗表明該算法簡單、快速及高效，在路徑客觀存在的情況下，能在已知給定的環(huán)境中迅速規(guī)劃出一條最短路徑。文章在蟻群算法的基礎上提出了一種適用于柵格式路徑規(guī)劃問題的啟發(fā)式算法，由于蟻群算法的簡單有效性，可將其應用于多機器人、多路徑規(guī)劃，這有待進一步的研究。這種算法的優(yōu)勢在于，避免了冗長的編程和籌劃，程序本身是基于一定規(guī)則的隨機運行來尋找最佳配置。也就是說，當程序最開始找到目標的時候，路徑幾乎不可能是最優(yōu)的，甚至可能是包含了無數錯誤的選擇而極度冗長的。但是，程序可以根據人工螞蟻尋找目標點時的信息素更新策略，不斷地去修正原來的路線，使整個路線越來越短，也就是說，程序執(zhí)行的時間越長，所獲得的路徑就越可能接近最優(yōu)路徑。這種優(yōu)化過程的本質在于：選擇機制：信息素越多的路徑，被選擇的概率越大。更新機制：路徑上面的信息素會隨螞蟻的經過而增多，同時也會隨時間的推移逐漸揮發(fā)消失。協調機制：螞蟻間實際上是通過分泌物來互相通信、協同工作的。蟻群算法正是充分利用了選擇、更新和協調的優(yōu)化機制，即通過個體之間的信息交流與相互協作最終找到最優(yōu)解，使它具有很強的發(fā)現較優(yōu)解的能力。雖然蟻群算法是一種來自大自然的隨機搜索尋優(yōu)方法，和傳統的算法相比，具有更好的適應性。但就目前階段來說，在蟻群算法中，信息素啟發(fā)因子α、期望啟發(fā)因子β和信息衰減系數會嚴重影響到算法的收斂性，同時，蟻群算法的參數也是影響其求解性能和效率的關鍵因素。但由于蟻群算法參數空間的龐大性和各參數之間的關聯性，如何確定最優(yōu)組合參數使蟻群算法求解性能最佳一直是一個極其復雜的優(yōu)化問題，目前尚沒有完善的理論依據，大多數情況下都是基于經驗而定。6 結束語機器人技術作為20世紀人類最偉大的發(fā)明之一，從某種意義上講，反映了這個國家綜合技術實力的高低。目前，機器人已在工業(yè)領域得到了廣泛應用，并且正在極快的速度不斷向軍事、醫(yī)療、服務、娛樂等非工業(yè)領域擴展。毋庸質疑，2l世紀機器人技術必將得到更大的發(fā)展，成為各國必爭的知識經濟制高點。移動機器人的路徑規(guī)劃是一種比較典型的優(yōu)化問題，本身具有復雜性、約束性、非線性、建模規(guī)范等特點[18]，目前對路徑規(guī)劃算法的研究方興未艾，尤其是新型的蟻群算法。蟻群算法的正反饋性、協同性和隱含的并行性使其具有極強的發(fā)展?jié)摿?，靈活性使其在解決組合優(yōu)化問題上具有良好的適應性，因此將蟻群算法應用于智能移動機器人避障的路徑規(guī)劃問題研究，能夠探索與改進一種新的路徑優(yōu)化算法，促進優(yōu)化理論與實踐的發(fā)展，并且為經濟領域以及工程領域的優(yōu)化問題提供借鑒。但是蟻群算法也有許多不足之處，如容易陷入局部最優(yōu)解等。但在空間復雜度上與傳統算法相比，是有優(yōu)勢可言的。同時，此算法是一種基于種群的魯棒性較強的模擬進化算法。針對這些特點，可以利用蟻群算法進一步解決實際動態(tài)路徑規(guī)劃問題，這將是我們繼續(xù)深入研究的重點。參考文獻[1] 李士勇,陳永強,[M].哈爾濱:哈爾濱工業(yè)大學出版社,.[2] [M].北京:科學出版社,.[3] 朱明華,王霄,[J].機床與液壓,2006(3):58.[4] 李彩虹,張景元,[J].淄博學院學報(自然科學與工程版),2001,3(3):2730.[5] 莊曉東,孟慶春,殷波,[J].機器人,2001,23(5):397399,458.[6] 禹建麗,[J].燕山大學學報,2002,26(3):258260.[7] 劉成良,張凱,付莊,[J].機械科學與技術（西安）,2003,22(2):226228,331.[8] 岳富占,崔平遠,[J].控制與決策,2006,21(12):14371438.[9] Tan Guanzheng,He Huan,Sloman Colony System Algorithm for Realtime Globally Optimal Path Planning of Mobile Robots[J].Acta Automatica Sinica, 2007,33(3): 279285.[10] [D].天津:天津財經大學,2006:2126,39.[11] [D].武漢:武漢理工大學,2007:4850.[12] 多里戈,[M].張軍,胡曉敏,羅旭耀,:清華大學出版社,.[13] 、理論及其應用研究[D].重慶:重慶大學,2004:98101.[14] [D].武漢:武漢科技大學,2007:2528,3235.[15] 謝園園,[J].南京師范大學學報,2006,6(3):45,17.[16] [D].上海:上海交通大學,2007:2733.[17] 夏桂梅,[J].計算機工程與科學,2007,29(6):52.[18] [D].南京:南京師范大學,2005:24,915.致謝 請您刪除一下內容，O(∩_∩)O謝謝！??！Many people have the same mixed feelings when planning a trip during Golden Week. With heaps of time, the sevenday Chinese請您刪除一下內容，O(∩_∩)O謝謝?。?！National Day holiday could be the best occasion to enjoy a destination. However, it can also be the easiest way to ruin how you feel about a place and you may bee more fatigued after the holiday, due to battling the large crowds. During peak season, a dream about a place can turn to nightmare without careful planning, especially if you travel with children and older people. As most Chinese people will take the holiday to visit domestic tourist destinations, crowds and busy traffic are inevitable at most places. Also to be expected are increasing transport and acmodation prices, with the possibility that there will be no rooms available. It is also mon that you39。llwait in the line for one hour to get a ticket, and another two hou