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

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

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

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

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

　基于混沌遺傳算法的移動(dòng)機(jī)器人路徑規(guī)劃方法，把遺傳算法和混沌優(yōu)化方法各自優(yōu)點(diǎn)結(jié)合起來，可以克服遺傳算法在求解可行解空間巨大的大范圍優(yōu)化問題時(shí)容易陷入局部最優(yōu)值的局限，對(duì)提高路徑規(guī)劃的質(zhì)量和效率有較好的效果。仿真結(jié)果說明混沌遺傳算法在移動(dòng)機(jī)器人路徑規(guī)劃中的可行性和有效性。但在移動(dòng)機(jī)器人運(yùn)動(dòng)過程中，運(yùn)動(dòng)精度還有待提高。
參考文獻(xiàn)
[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] 孫樹棟，曲彥賓．遺傳算法在機(jī)器人路徑規(guī)劃中的應(yīng)用研究[J]．西北工業(yè)大學(xué)學(xué)報(bào)，1998，16(1)：79-83．
[3] 陳剛，沈林成．復(fù)雜環(huán)境下路徑規(guī)劃問題的遺傳路徑規(guī)劃方法[J]．機(jī)器人，2001，23(1)：40-44．
[4] 章敬東，劉小輝，鄧飛其，等．混沌優(yōu)化與遺傳算法的智能集成[J]．計(jì)算機(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ī)劃移動(dòng)機(jī)器人路徑[J]．西北工業(yè)大學(xué)學(xué)報(bào)，1998，16(4)：581-583．
[7] 羅熊，樊曉平，易最，等．具有大量不規(guī)則障礙物的環(huán)境下機(jī)器人路徑規(guī)劃的一種新型遺傳算法[J]．機(jī)器人，2004，26：23-24．
[8] 馮琦，周德云．極坐標(biāo)系下基于遺傳算法的路徑規(guī)劃方法[J]．機(jī)械科學(xué)與技術(shù)，2004，23(5)：45-48．