沙勇

基于遺傳算法機(jī)器人路徑規(guī)劃研究

沙勇

（齊齊哈爾大學(xué)學(xué)報(bào)（自然科學(xué)版）編輯部，黑龍江 齊齊哈爾 161006）

針對(duì)傳統(tǒng)的機(jī)器人算法不是線性路徑優(yōu)化而導(dǎo)致不能較好地解決實(shí)際問題情況，介紹了采取遺傳算法處理路徑規(guī)劃的方法解決路徑規(guī)劃問題的方案。

遺傳算法；路徑規(guī)劃；機(jī)器人

目前，在機(jī)器人的路徑規(guī)劃研究領(lǐng)域，對(duì)于處理路徑的優(yōu)化方式一般有可視圖法和人工勢(shì)場法，對(duì)于傳統(tǒng)的算法處理不是線性的路徑優(yōu)化問題的缺點(diǎn)[1]，遺傳算法因其自身優(yōu)勢(shì)在機(jī)器人路徑規(guī)劃上就得到了應(yīng)有的重視[2]。本文主要介紹了采取遺傳算法處理路徑規(guī)劃的方法解決路徑規(guī)劃問題的方案。

1 構(gòu)建環(huán)境模型

環(huán)境模型是根據(jù)傳感器搜索到的全局環(huán)境信息進(jìn)行環(huán)境的模型構(gòu)建。該模型應(yīng)該具有種群進(jìn)行操作時(shí)可以保證初始條件不變的能力的穩(wěn)定性，具有種群本身對(duì)外界干擾自身的保持能力魯棒性。本文運(yùn)用柵格法搭建環(huán)境模型地圖。

柵格地圖用大小均勻的柵格劃分機(jī)器人所處的二維空間環(huán)境，柵格大小可以滿足機(jī)器人的運(yùn)動(dòng)范圍，對(duì)于2D的柵格地圖，環(huán)境依次劃分為均勻的柵格，每個(gè)柵格只有兩種形態(tài)，包括二進(jìn)制數(shù)0和1，對(duì)于占據(jù)狀態(tài)，通常用1代表，對(duì)于空閑狀態(tài)，通常用0代表；當(dāng)處理3D的環(huán)境模型時(shí)，柵格的密集信息由每個(gè)單元格表示，用這些柵格來代表全局的環(huán)境模型。

2 初始化設(shè)置

2.1 路徑編碼

路徑編碼是一種把路徑的可行解問題模擬為一種對(duì)遺傳算法相對(duì)于進(jìn)行全局搜索的空間進(jìn)行的替換。編碼的機(jī)理是算法進(jìn)化過程里的前提，算法的效果主要取決于編碼的合理性。本文采用標(biāo)記序列號(hào)的方法進(jìn)行編碼，對(duì)于表示的一個(gè)個(gè)體，一般是在路徑的初始位置上不出現(xiàn)重復(fù)與障礙物的序列號(hào)，這些路徑才是合理的路徑。例如，每一條染色體都是一列柵格序列號(hào)組成，它代表了機(jī)器人的路徑，如圖1所示。

圖1 路徑與相應(yīng)的染色體

2.2 種群初始化

本文規(guī)劃首先對(duì)種群初始化是對(duì)種群的初始化，對(duì)種群進(jìn)行選擇、交叉等操作，實(shí)現(xiàn)算法的快速性也取決于種群的初始化。在未知最優(yōu)解的情況下，解決好初始化種群進(jìn)而實(shí)現(xiàn)其優(yōu)化是十分重要的。種群初始化的方法很多，在研究遺傳算法時(shí)，基本遺傳算法利用隨機(jī)的方式初始種群，這就造成了算法的不確定性，人們對(duì)這方面的研究也越來越多，如何構(gòu)造好的初始化種群成為遺傳算法的一個(gè)熱點(diǎn)[3-5]。本文運(yùn)用隨機(jī)操作和啟發(fā)式結(jié)合的方法初始化種群，既可以加快路徑規(guī)劃的速度也可以有效地表示空間的信息。初始化一般包括兩步。（1）為了保證路徑長度的不變，在進(jìn)行選擇路徑的時(shí)候，隨機(jī)生成在中間點(diǎn)和對(duì)應(yīng)位置的坐標(biāo)之間的路徑；（2）因?yàn)槁窂降钠鹗嘉恢靡阎?，進(jìn)行全局的路徑搜索過程時(shí)，選擇一條路徑中不出現(xiàn)障礙物的一條，保證了算法的速度和路徑的最優(yōu)，由此獲得其他的居中點(diǎn)。采用的主要方式是啟發(fā)式。

為了避免安全性與平滑性對(duì)路徑的干擾，從圖1可以看出，這種方法的起始位置的連線上集合了生成的路徑，可以得出路徑不是最優(yōu)的路徑，需要進(jìn)行進(jìn)一步的優(yōu)化，減少盲目性地生成種群。

3 適應(yīng)度函數(shù)設(shè)計(jì)

在遺傳算法之中，下一代的群體概率由上一代的適應(yīng)度函數(shù)決定，遺傳算法的設(shè)計(jì)取決于適應(yīng)度函數(shù)的選擇和設(shè)計(jì)，它是制約算法獲得最優(yōu)解的關(guān)鍵所在。算法的效率和質(zhì)量都由適應(yīng)度函數(shù)影響。適應(yīng)度的函數(shù)為

式中，代表個(gè)體路徑中的柵格數(shù)目，代表個(gè)體路徑長度。由式(1)可知，函數(shù)與機(jī)器人運(yùn)動(dòng)的距離成正函數(shù)，所以，把函數(shù)作為適應(yīng)度函數(shù)。路徑的總長度，是初始位置間所有轉(zhuǎn)向點(diǎn)之間的距離之和，用式(2)表示：

4 遺傳算子操作

在本文中利用輪盤法的具體做法如下：（1）依據(jù)上面的適應(yīng)度的函數(shù)逐次算出群體中的個(gè)體適應(yīng)度，得到對(duì)應(yīng)累積值Q，最終死亡累積值Q；（2）在[0, Q]間得到平均的隨機(jī)數(shù)；（3）把Q與進(jìn)行比較，第一個(gè)Q的個(gè)體被作為復(fù)制對(duì)象；（4）重復(fù)（2）,（3）項(xiàng)，直到得到滿足的復(fù)制個(gè)體數(shù)。

由上面的方式即滿足適者生存的法則，產(chǎn)生種群適應(yīng)度最大的個(gè)體進(jìn)行遺傳可以獲得新種群合適的路徑數(shù)目。

4.1 交叉算子

交叉操作是指選擇兩個(gè)個(gè)體P1和P2作為父母體，將兩者的部分碼值進(jìn)行交叉，假設(shè)有如下8位長的2個(gè)體：生成一個(gè)在1～7之間的隨機(jī)的數(shù)，如果生成的數(shù)為3，把P1與P2的低3位進(jìn)行交換：P1中高5位和P2中低3位構(gòu)成數(shù)串二進(jìn)制10001001，得到P1與P2的一個(gè)子代個(gè)體Q；P2中高5位和P1中低3位構(gòu)成數(shù)串的二進(jìn)制為11011110，得到P1與P2的一個(gè)子代個(gè)體2。

4.2 變異算子

變異算子的操作簡單的過程就是修改數(shù)碼串中某個(gè)位置中的數(shù)碼，下面介紹簡單的二進(jìn)制編碼形式。二進(jìn)制中的數(shù)碼只有0和1兩種形式，以下面的二進(jìn)制數(shù)碼為例表示：它的碼長是8，隨機(jī)生成一個(gè)1至8里的數(shù)值，假如現(xiàn)在=5，對(duì)從右向左的第5位做變異操作，把原來的0變成1。二進(jìn)制編碼就是簡單的將0與1互換：0變異為1，1變異為0。TSP變異操作：隨機(jī)生成一個(gè)1至里的數(shù)，開始對(duì)回路中的第個(gè)的代碼作變異操作，又生成一個(gè)1至之間的數(shù)，代替，12，注意數(shù)在數(shù)串里出現(xiàn)了重復(fù)，刪除和相重復(fù)的即可獲得合法染色體。

本文采用最佳適應(yīng)度值過半的方法，它的意思就是當(dāng)種群中包含一半以上的染色體達(dá)到相同的適應(yīng)度，且種群平均適應(yīng)值保持不變，終止種群就確定下來了。

[1] 肖南峰. 智能機(jī)器人[M]. 廣州：華南理工大學(xué)出版社，2008: 12-15.

[2] 劉天孚，程如意. 基于遺傳算法的移動(dòng)機(jī)器人路徑規(guī)劃[J]. 計(jì)算機(jī)工程，2008, 34(17): 214-215．

[3] 張洪. 移動(dòng)機(jī)器人動(dòng)態(tài)路徑規(guī)劃方法研究[D]. 無錫：江南大學(xué)，2011: 25-28.

[4] 呂微. 基于混沌免疫遺傳算法的優(yōu)化問題研究[D]. 大慶：大慶石油學(xué)院，2010.

[5] 張雷，王道波，段海濱. 基于粒子群優(yōu)化算法的無人戰(zhàn)斗機(jī)路徑規(guī)劃方法[J]. 系統(tǒng)工程與電子技術(shù)，2008, 30(3): 506-510.

Research on robot path planning based on genetic algorithm

SHA Yong

(Journal of Qiqihar University(Natural Science Edition) Editorial Department, Heilongjiang Qiqihar 161006, China)

For the problem that the traditional robot algorithm is not linear path optimization and can not solve the problem well, this paper introduces the solution of path planning using genetic algorithm to solve the problem.

genetic algorithm；path planning；robot

2021-04-20

齊齊哈爾市科技局工業(yè)公關(guān)項(xiàng)目（440036）

沙勇（1963-），男，黑龍江齊齊哈爾人，副編審，本科，主要從事編輯工程、自動(dòng)化應(yīng)用研究，shayong10@163.com。

TP242;TP18

A

1007-984X(2021)05-0055-02