《電子技術(shù)應(yīng)用》
您所在的位置:首頁 > 其他 > 設(shè)計應(yīng)用 > 基于混沌遺傳算法的機器人路徑規(guī)劃方法研究
基于混沌遺傳算法的機器人路徑規(guī)劃方法研究
來源:微型機與應(yīng)用2011年第13期
任偉建,劉世聰,孫 超
(東北石油大學 電氣信息工程學院,黑龍江 大慶 163318)
摘要: 針對機器人路徑規(guī)劃中,應(yīng)用遺傳算法時容易陷入局部最優(yōu)解以及收斂速度較慢等問題,設(shè)計出一種基于混沌遺傳算法的路徑規(guī)劃方法。在基本遺傳算法的基礎(chǔ)上采用自適應(yīng)調(diào)整的選擇概率,并引入混沌操作,從而增強移動機器人路徑規(guī)劃算法的魯棒性,解決一般遺傳算法的早熟和收斂速度慢問題。經(jīng)MATLAB仿真,證明該方法具有良好的避障性能。
Abstract:
Key words :

摘  要: 針對機器人路徑規(guī)劃中,應(yīng)用遺傳算法時容易陷入局部最優(yōu)解以及收斂速度較慢等問題,設(shè)計出一種基于混沌遺傳算法的路徑規(guī)劃方法。在基本遺傳算法的基礎(chǔ)上采用自適應(yīng)調(diào)整的選擇概率,并引入混沌操作,從而增強移動機器人路徑規(guī)劃算法的魯棒性,解決一般遺傳算法的早熟和收斂速度慢問題。經(jīng)MATLAB仿真,證明該方法具有良好的避障性能。
關(guān)鍵詞: 混沌;遺傳算法;路徑規(guī)劃

 路徑規(guī)劃是按照某一性能指標搜索一條從起始狀態(tài)到目標狀態(tài)的最優(yōu)或近似最優(yōu)的無碰路徑,機器人的路徑規(guī)劃是一個非線性問題,遺傳算法GA(Genetic Algorithm)可以求解此類問題。但對于復(fù)雜的大型系統(tǒng),GA仍然有一些缺陷[1-3]。為了避免這些問題,不少人對遺傳算法的編碼方式和算法結(jié)構(gòu)等進行了改進[4]。Hussein A. Abdullah等[5]采用直角坐標法編碼,將浮點數(shù)表示的坐標點鏈接成染色體,染色體為不定長,這種方法具有良好的全局搜索性能,但路徑個體中途點坐標的可取值范圍過大,路徑拐點多;周明等[6]提出一種連續(xù)空間下基于遺傳算法的機器人路徑規(guī)劃方法,該方法先建立連通圖,然后再使用遺傳算法逐步得到較優(yōu)的路線,但對于復(fù)雜環(huán)境、障礙物數(shù)目較多的情況,建立連通圖會有一定的困難;羅熊[7]等設(shè)計了一種基于隨機指導式搜索策略的初始種群的快速有效生成方法,用于具有大量不規(guī)則障礙物的環(huán)境下的機器人路徑規(guī)劃,取得很好的仿真效果;馮琦[8]等提出了一種在極坐標環(huán)境下應(yīng)用遺傳算法求解機器人路徑規(guī)劃問題的方法,該方法采用簡捷有效的路徑染色體編碼方法和快速的個體適應(yīng)度計算方法,并對生成的初始路徑點集進行提煉處理,以剔除其中含有的不必要拐點。
 本文結(jié)合混沌優(yōu)化方法,在基本遺傳算法的搜索機制上,利用混沌優(yōu)化的遍歷性和遺傳算法優(yōu)化的反演性,提出了一種混沌遺傳算法CGA(Chaos Genetic Algorithm)。本算法通過設(shè)計編碼方式、選擇概率以及加入操作算子來改進基本遺傳算法,并在遺傳算法中引入混沌操作,將本算法運用于機器人路徑規(guī)劃中,經(jīng)MATLAB仿真實驗,證明此算法能夠有效的進行機器人路徑規(guī)劃。
1 混沌遺傳算法
 CGA的基本思想是利用混沌優(yōu)化策略的遍歷性生成較優(yōu)良的初始種群,根據(jù)適者生存的原則,對其進行選擇、雜交、變異遺傳操作,同時加入刪除和插入操作加快遺傳算法收斂速度,然后利用混沌的隨機性在種群中加入擾動,避免遺傳算法的早熟收斂現(xiàn)象,增強算法的魯棒性,通過不斷繁衍進化,最后得到適合環(huán)境的較優(yōu)個體。算法流程圖如圖1所示。


2 路徑規(guī)劃方法
2.1 基于地理信息的編碼

 如何將問題的解轉(zhuǎn)換為編碼表達的染色體,在xoy坐標系中表示障礙物信息,并利于后續(xù)約束條件下的優(yōu)化操作是遺傳算法的關(guān)鍵問題。在遺傳算法中,對于固定的適應(yīng)度函數(shù),編碼的長度和搜索空間的大小直接決定了在線的計算時間。因此必須設(shè)計一種簡捷實用的編碼技術(shù),才能縮短規(guī)劃時間,實現(xiàn)實時控制。在實際運動中,路徑點是二維的,如果能對路徑坐標點進行降維處理,必將大大提高計算速度。因此本文采用了簡化編碼長度的技術(shù),即把路徑的二維編碼簡化為一維編碼。編碼形式如圖2所示。

 在xoy坐標系中,機器人運動的起始點是(X1,Y1),目標點是(Xn,Yn),把起始點和目標點按x坐標等分成n段,則每個點的坐標可表示為(Xi,Yi)(i=1,2,…,n)。在初始化種群時,由于x坐標被等分,所以每個個體表示的路徑的區(qū)別僅僅是路徑的縱坐標不同,縱坐標y的改變可以使機器人避開障礙物并按照不同的路徑運動到目標點。

2.3 基于約束條件的適應(yīng)度函數(shù)
 根據(jù)以上分析,在機器人路徑規(guī)劃中適應(yīng)度函數(shù)需要滿足兩個條件:避障和路徑最短。假設(shè)障礙物的位置信息可由機器人的超聲波傳感器檢測到,由此信息計算出機器人與障礙物的距離和夾角,然后進行編碼,以直角坐標的形式表示在以機器人位置為原點的直角坐標系中,若種群中個體包含障礙物坐標越多則適應(yīng)度越小,反之就比較大,適應(yīng)度函數(shù)為f1。評價路徑最短的適應(yīng)度函數(shù)為個體的前后基因的距離和,距離越大則適應(yīng)度越小,反之就比較大,適應(yīng)度函數(shù)為f2。遺傳算法的適應(yīng)度函數(shù)可用如下關(guān)系表示:
 
其中(Xi,Yi)為個體基因,n為基因個數(shù),(xj,yj)為障礙物坐標,m為障礙物個數(shù)。F是把2個約束條件有機結(jié)合起來的綜合適應(yīng)度函數(shù),a和b為加權(quán)系數(shù)。
2.4 路徑規(guī)劃方法步驟
 (1)初始化參數(shù)。設(shè)定種群大小為npop,交叉概率為pc,變異概率為pm,最大迭代次數(shù)為counter。
 (2)環(huán)境建模。此地圖信息建立在xoy坐標下的柵格,將機器人傳感器獲得外界地理信息轉(zhuǎn)化為柵格坐標,包括障礙物的坐標點和非障礙物的坐標點。柵格大小以機器人自由轉(zhuǎn)身來確定,若障礙物大小不滿一個柵格也占據(jù)一個柵格的坐標。
 (3)種群初始化。首先隨機生成一維編碼的種群,然后把此種群每個個體分別進行Logistic混沌映射,產(chǎn)生的新個體的適應(yīng)值若大于原個體,則新個體替換原個體,否則保留原個體,經(jīng)混沌優(yōu)化后得到初始種群Gi(i=1,2,…,npop)。
 (4)進入循環(huán)。判斷循環(huán)次數(shù)是否滿足終止條件,若滿足,則跳轉(zhuǎn)到步驟9,否則執(zhí)行下一步。
 (5)將種群進行混沌擾動。
?、俪跏蓟河秒S機方法產(chǎn)生新的種群Ci(i=1,2,…,cpop),種群數(shù)量為cpop=pch×npop,其中pch為混沌擾動概率。
?、趯⑸傻幕煦缧蛄蠧i映射到區(qū)間[0,1]內(nèi),設(shè)mx為種群中最大基因值,mi為種群中最小基因值,則01映射公式為CHi(Ci-mi)/(mx-mi)。
 ③以CHi為初始值,用Logistic映射得到序列CSi,Logistic映射公式為CSi=μ×CHi×(1-CHi),μ為混沌算子中的吸引算子。
?、芨鶕?jù)01映射公式作逆映射得到基因序列,將此基因序列替換掉Gi種群中適應(yīng)度較高的個體,形成新的Gi種群。
 (6)以混沌擾動后的個體為基準進行遺傳操作。
?、佥啽P賭法選擇操作。選擇操作采用自適應(yīng)調(diào)整的選擇概率ps進行操作,根據(jù)適應(yīng)度函數(shù)計算種群適應(yīng)度的平均值fmean和最優(yōu)個體的適應(yīng)值ftop。ftop-fmean越大則表明個體適應(yīng)值差別較大,ftop-fmean越小則表明個體之間的適應(yīng)值差別較小,說明此種群容易達到局部最優(yōu),過早收斂的可能性越大。因此可以近似地用最優(yōu)個體的適應(yīng)值和平均適應(yīng)值之差來反映種群的收斂程度。這樣選擇概率ps的自適應(yīng)計算公式表示為ps=c(ftop-fmean)/k,其中k為算法迭代次數(shù),c為比例系數(shù)。
 ②交叉操作。以設(shè)定好的交叉概率pc進行個體的交叉操作,適應(yīng)度高的個體和適應(yīng)度低的個體進行交叉。首先找到兩個交叉?zhèn)€體的交叉點,即相同的基因值,然后從此基因開始交換兩個個體后面的基因。
?、圩儺惒僮?。變異操作目的是在個體結(jié)構(gòu)一定的前提下,加入隨機擾動,以尋找最優(yōu)解,以此來避免丟失一些有用的遺傳因子。具體操作是隨機產(chǎn)生一個[0,1]空間的數(shù)值與Pm進行比較,若小于Pm,則進行變異操作,將變異后的個體替代原個體;若隨機產(chǎn)生的隨機數(shù)大于Pm,則不做變換。
 (7)對種群進行刪除和插入操作。刪除操作通過刪除個體中包含的障礙物基因,可以使不可行路徑變?yōu)橐粭l可行的路徑。插入操作即在不連續(xù)的路徑處插入基因使路徑成為一條連續(xù)可行的路徑。
 (8)計算終止條件。終止條件包括迭代次數(shù)和適應(yīng)值,其中迭代次數(shù)加一,并計算當前種群的適應(yīng)度函數(shù)值,然后跳轉(zhuǎn)到步驟(4)。
 (9)進行輸出,終止此次機器人行走的路徑規(guī)劃。
3 仿真結(jié)果
 為了驗證本文提出的基于混沌遺傳算法的路徑規(guī)劃方法的有效性和正確性,在MATLAB7.0中對算法進行了仿真試驗,仿真試驗的主要參數(shù)設(shè)置為:9×9矩形場地,種群規(guī)模為50,交叉概率為0.8,變異概率為0.1,最大迭代次數(shù)為100,混沌吸引算子為4。
 設(shè)定移動機器人運動的起始點為左下角柵格,目標點為右上角柵格,這里用圓圈表示移動機器人走過的柵格,用矩形表示障礙物,SGA仿真實驗分別對基本遺傳算法(Simple Genetic Algorithm)和本文所設(shè)計的CGA進行仿真實驗,圖4給出其中一次應(yīng)用CGA的仿真結(jié)果。


 基于混沌遺傳算法的移動機器人路徑規(guī)劃方法,把遺傳算法和混沌優(yōu)化方法各自優(yōu)點結(jié)合起來,可以克服遺傳算法在求解可行解空間巨大的大范圍優(yōu)化問題時容易陷入局部最優(yōu)值的局限,對提高路徑規(guī)劃的質(zhì)量和效率有較好的效果。仿真結(jié)果說明混沌遺傳算法在移動機器人路徑規(guī)劃中的可行性和有效性。但在移動機器人運動過程中,運動精度還有待提高。
參考文獻
[1] ASHIRU I, CZARNECKI C, ROUTENT. Characteristics of a genetic based approach to path planning for mobile robots[J]. Journal of Network and Computer Applications, 1996,19: 149-159.
[2] 孫樹棟,曲彥賓.遺傳算法在機器人路徑規(guī)劃中的應(yīng)用研究[J].西北工業(yè)大學學報,1998,16(1):79-83.
[3] 陳剛,沈林成.復(fù)雜環(huán)境下路徑規(guī)劃問題的遺傳路徑規(guī)劃方法[J].機器人,2001,23(1):40-44.
[4] 章敬東,劉小輝,鄧飛其,等.混沌優(yōu)化與遺傳算法的智能集成[J].計算機工程與應(yīng)用,2003(17):17-20.
[5] ABDULLAH H A, AREIBI S. Mobile robots path planning optimization in static and dynamic environments[J]. Ahmed ELSHAMLI, 2004, 12-15.
[6] 周明,孫樹棟,彭炎午.使用遺傳算法規(guī)劃移動機器人路徑[J].西北工業(yè)大學學報,1998,16(4):581-583.
[7] 羅熊,樊曉平,易最,等.具有大量不規(guī)則障礙物的環(huán)境下機器人路徑規(guī)劃的一種新型遺傳算法[J].機器人,2004,26:23-24.
[8] 馮琦,周德云.極坐標系下基于遺傳算法的路徑規(guī)劃方法[J].機械科學與技術(shù),2004,23(5):45-48.

此內(nèi)容為AET網(wǎng)站原創(chuàng),未經(jīng)授權(quán)禁止轉(zhuǎn)載。