改進(jìn)遺傳算法的移動(dòng)機(jī)器人路徑規(guī)劃研究

摘" 要：針對(duì)遺傳算法應(yīng)用于移動(dòng)機(jī)器人路徑規(guī)劃時(shí)存在早熟和收斂慢的問(wèn)題，提出了一種改進(jìn)的遺傳算法。通過(guò)改良初始種群的生成方法，將八叉樹與引導(dǎo)函數(shù)結(jié)合，提高了初始種群的質(zhì)量；選擇操作中采用輪盤賭和精英保留策略相結(jié)合的方式，避免了精英個(gè)體的丟失而使算法陷入局部最優(yōu)；在遺傳操作中增加修正算子，在不影響進(jìn)化的同時(shí)保證進(jìn)化后個(gè)體的有效性。仿真實(shí)驗(yàn)表明，改進(jìn)遺傳算法相比于基本遺傳算法，收斂快，尋優(yōu)效率高，且不易陷入局部最優(yōu)，整體性能優(yōu)于基本遺傳算法。

關(guān)鍵詞：移動(dòng)機(jī)器人；路徑規(guī)劃；遺傳算法；改進(jìn)遺傳算法

中圖分類號(hào)：TP242.6" " " 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：2096-4706（2024）23-0180-05

Research on Mobile Robot Path Planning with Improved Genetic Algorithm

LI Zhonglin， JIA Yuting， JIANG Xiaoli

（Software Engineering Institute of Guangzhou， Guangzhou" 510990， China）

Abstract： Aiming at the exsiting problems of precocity and slow convergence when the Genetic Algorithm is applied to mobile robot path planning， an improved Genetic Algorithm is proposed. By improving the generation method of the initial population， the octree is combined with the bootstrap function to improve the quality of the initial population. The combination method of roulette and elite retention strategy is used in the selection operation to avoid the algorithm falling into the local optimum due to the loss of the excellent individuals， and the correction operator is added in the genetic operation to ensure the the individual validity after evolution" while not affecting the evolution. Simulation experiments show that the improved Genetic Algorithm， compared with the basic Genetic Algorithm， converges quickly， has high efficiency in finding the optimum， and is not easy to fall into the local optimum. It is better than the basic Genetic Algorithm in the overall performance.

Keywords： mobile robot; path planning; Genetic Algorithm; improved Genetic Algorithm

0" 引" 言

隨著移動(dòng)機(jī)器人技術(shù)的快速發(fā)展，其在各個(gè)領(lǐng)域的應(yīng)用日益廣泛，如物流、醫(yī)療、服務(wù)等領(lǐng)域。在這些應(yīng)用場(chǎng)景中，路徑規(guī)劃是移動(dòng)機(jī)器人的一個(gè)核心問(wèn)題，直接關(guān)系到機(jī)器人的工作效率和安全性。傳統(tǒng)的路徑規(guī)劃方法，如人工勢(shì)場(chǎng)法[1]、D*算法[2]、A*算法[3]等，雖然取得了一定的效果，但在處理復(fù)雜環(huán)境和實(shí)時(shí)規(guī)劃方面仍存在一定的局限性。因此，研究一種高效、穩(wěn)定的路徑規(guī)劃方法具有重要的實(shí)際意義。遺傳算法具有適應(yīng)性高和魯棒性強(qiáng)的特點(diǎn)，是一種優(yōu)良的全局優(yōu)化搜索算法，被廣泛應(yīng)用于復(fù)雜的優(yōu)化問(wèn)題[4-5]。然而，基本遺傳算法在搜索過(guò)程中易陷入局部最優(yōu)解和收斂慢[6]。為此，對(duì)遺傳算法進(jìn)行改進(jìn)，以提高其搜索效率和優(yōu)化能力以及適應(yīng)移動(dòng)機(jī)器人路徑規(guī)劃問(wèn)題。

1" 環(huán)境建模

環(huán)境建模是實(shí)現(xiàn)路徑規(guī)劃的前提，首先要對(duì)移動(dòng)機(jī)器人的工作環(huán)境建模，常用的建模方法有柵格法、路標(biāo)法以及可視圖法[7]。其中，柵格法具有簡(jiǎn)單靈活易于處理的優(yōu)點(diǎn)[8]，選用柵格法建模。

1.1" 柵格法環(huán)境建模

柵格法是用等大的正方形柵格對(duì)移動(dòng)機(jī)器人的工作環(huán)境進(jìn)行分割。如圖1（a）所示，用等大的柵格以俯視的角度將工作環(huán)境柵格化，其中，黑色部分為障礙物，白色部分為可行路徑。其中，柵格的大小表征環(huán)境模型的精細(xì)程度，柵格越小，環(huán)境模型越精細(xì)，越接近真實(shí)環(huán)境，但柵格劃分過(guò)于精細(xì)，則對(duì)計(jì)算機(jī)算力要求高，影響路徑規(guī)劃速度[9]。一般地，以移動(dòng)機(jī)器人邊沿任意兩點(diǎn)連線的最大距離作為柵格的邊長(zhǎng)。

用柵格分割移動(dòng)機(jī)器人的工作環(huán)境后，如圖1（a）所示，會(huì)出現(xiàn)三種類型的柵格：柵格被障礙物完全覆蓋、柵格被障礙物部分覆蓋和柵格未被障礙物覆蓋。為避免移動(dòng)機(jī)器人與障礙物碰撞，將障礙物膨脹改進(jìn)，如圖1（b）所示，規(guī)定：被障礙物完全覆蓋的柵格記為障礙柵格，未被障礙覆蓋的柵格記為自由柵格，被障礙物不完全覆蓋的柵格，仍記為障礙柵格。障礙柵格移動(dòng)機(jī)器人不可行走，用黑色柵格表示，自由柵格移動(dòng)機(jī)器人可行走，用白色柵格表示。設(shè)工作環(huán)境分割得到M行N列柵格，（x0 y0）表示柵格的初始位置S，（xM yN）表示柵格的目標(biāo)位置G，全部柵格構(gòu)成的集合用A表示，如式（1）所示：

（1）

柵格（xy）所含的信息是障礙物還是可行柵格，用f（xy）表示，如式（2）所示，如該柵格為障礙柵格，則函數(shù)值為1，如該柵格為自由柵格，則函數(shù)值為0。

（2）

1.2" 柵格標(biāo)識(shí)

直角坐標(biāo)法[10]是常用的柵格標(biāo)識(shí)方法，其特點(diǎn)是直觀明了，但不利于染色體的形成及遺傳操作，故在此基礎(chǔ)上改進(jìn)為矩陣標(biāo)識(shí)法，如圖2所示。矩陣標(biāo)識(shí)法以柵格作為基本單位，將移動(dòng)機(jī)器人的工作環(huán)境橫向劃分為M個(gè)柵格，縱向劃分為N個(gè)柵格，橫向從左向右用阿拉伯?dāng)?shù)字標(biāo)注序號(hào)，縱向從下向上用阿拉伯?dāng)?shù)字標(biāo)注序號(hào)。根據(jù)柵格所處的橫縱柵格序號(hào)確定其矩陣坐標(biāo)，如柵格A所處位置是橫向第a個(gè)柵格和縱向第b個(gè)柵格，記作ab。為便于觀測(cè)與計(jì)算，給出矩陣坐標(biāo)與直角坐標(biāo)轉(zhuǎn)換公式，以柵格A為例，如式（3）所示：

（3）

其中，a、b分別表示柵格A橫軸和縱軸的柵格序號(hào)；xA、yA分別表示柵格A的直角坐標(biāo)。

1.3" 行走方式

行走方式是指移動(dòng)機(jī)器人在柵格環(huán)境中移動(dòng)的規(guī)則，四叉樹和八叉樹是移動(dòng)機(jī)器人兩種基本的行走方式[11]。四叉樹行走方式如圖3（a）所示，移動(dòng)機(jī)器人從當(dāng)前柵格向下一個(gè)柵格移動(dòng)時(shí)，可選擇向左、向右、向上、向下四個(gè)方向。八叉樹行走方式如圖3（b）所示，移動(dòng)機(jī)器人除了選擇四叉樹中的四個(gè)方向外，還可以選擇四個(gè)斜行方向，左上、右上、左下、右下。因?yàn)榘瞬鏄湫凶叻较蚋?，又因其存在斜行方式，所形成的路徑更短，所以選用八叉樹的行走方式。

1.4" 行走規(guī)則

移動(dòng)機(jī)器人按照八叉樹的方式行走，在t時(shí)刻，移動(dòng)機(jī)器人的位置為（XtYt），在t-1時(shí)刻，移動(dòng)機(jī)器人的位置為（Xt-1Yt-1），兩位置坐標(biāo)應(yīng)符合以下規(guī)則：

（4）

（5）

（6）

移動(dòng)機(jī)器人行走的前后兩個(gè)時(shí)刻的位置坐標(biāo)必須滿足式（4）和式（6）或式（5）和式（6），即移動(dòng)機(jī)器人沿橫向坐標(biāo)移動(dòng)一個(gè)柵格或沿縱向坐標(biāo)移動(dòng)一個(gè)柵格或斜向行走一個(gè)斜向柵格。

移動(dòng)機(jī)器人的路徑規(guī)劃是為了獲取一條最短的安全路徑，路徑長(zhǎng)度用函數(shù)obj表示，即將每?jī)蓚€(gè)時(shí)刻之間路徑長(zhǎng)度累積，計(jì)算方法如式（7）所示：

（7）

其中，St表示連續(xù)兩步之間的距離。一個(gè)柵格的長(zhǎng)度記為單位1，移動(dòng)機(jī)器人沿坐標(biāo)軸移動(dòng)時(shí)，每移動(dòng)一次的路徑長(zhǎng)度為1，當(dāng)移動(dòng)機(jī)器人斜向移動(dòng)時(shí)，每移動(dòng)一次的路徑長(zhǎng)度為。

2" 改進(jìn)遺傳算法

基本遺傳算法是一種優(yōu)異的智能尋優(yōu)算法，但在使用基本遺傳算法規(guī)劃路徑時(shí)易出現(xiàn)收斂慢和早熟的現(xiàn)象，為此，需設(shè)計(jì)一種改進(jìn)遺傳算法，為移動(dòng)機(jī)器人路徑規(guī)劃提供一種新的思路和解決辦法。

2.1" 染色體編碼

染色體編碼采用二進(jìn)制編碼方式。在使用二進(jìn)制編碼時(shí)，首先將柵格坐標(biāo)依次序連接起來(lái)形成路徑，如ab，cd…mn。然后，將路徑中的每個(gè)柵格坐標(biāo)值用二進(jìn)制數(shù)表示，即為染色體，從而完成染色體編碼。其中，用二進(jìn)制數(shù)表示位置坐標(biāo)時(shí)所采用的二進(jìn)制位數(shù)以當(dāng)前環(huán)境模型中的終點(diǎn)坐標(biāo)所需用的最大二進(jìn)制位數(shù)為基準(zhǔn)，其他坐標(biāo)均按照該二進(jìn)制位數(shù)表示。

2.2" 初始化種群

初始化種群采用八叉樹與引導(dǎo)函數(shù)的相結(jié)合的方式。從起始柵格出發(fā)，按八叉樹原則選取與起始柵格相鄰的自由柵格作為下一個(gè)路徑柵格，當(dāng)可供選擇的自由柵格為多個(gè)時(shí)，需計(jì)算引導(dǎo)函數(shù)的值，引導(dǎo)函數(shù)如式（8）。將所有自由柵格的引導(dǎo)因子計(jì)算后，采用賭盤策略來(lái)選定柵格。規(guī)定在一條路徑中，當(dāng)柵格被選定后，標(biāo)記該柵格，在后續(xù)路徑規(guī)劃中不會(huì)被再次選擇，以避免產(chǎn)生循環(huán)路徑。

（8）

H（xa yb）的值表示自由柵格的（xa yb）的引導(dǎo)因子，其值的大小反映了該自由柵格被選中的概率；（xM yN）為目標(biāo)柵格的坐標(biāo)。

2.3" 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)以路徑總長(zhǎng)的倒數(shù)作為適應(yīng)度函數(shù)，記作F，如式（9）。對(duì)于路徑規(guī)劃，路徑總長(zhǎng)度越短越好，即F越大越好。

（9）

式中i為示路徑的序號(hào)，St為t時(shí)刻和t-1時(shí)刻之間的歐式距離。

2.4" 遺傳操作

遺傳操作包括選擇、交叉、變異和修正操作，其中選擇操作使用輪盤賭和精英保留策略相結(jié)合的方式，交叉操作使用單點(diǎn)交叉算子，變異操作使用基本位變異算子，修正操作用于判斷和修復(fù)個(gè)體。

2.4.1" 選擇算子

選擇算子采用輪盤賭和精英保留策略相結(jié)合的方式[12]。在輪盤賭選擇中，個(gè)體被選擇的概率與其適應(yīng)度成正比，種群中適應(yīng)度高的個(gè)體易被保留，適應(yīng)度低的個(gè)體易被淘汰。當(dāng)種群中產(chǎn)生最優(yōu)個(gè)體時(shí)，如僅使用輪盤賭選擇，存在最優(yōu)個(gè)體參與下一輪進(jìn)化時(shí)而被破壞的現(xiàn)象，可能使算法收斂于局部最優(yōu)解，因此輪盤賭選擇需結(jié)合精英保留策略使用。種群的每次進(jìn)化時(shí)均使用精英保留策略將最優(yōu)個(gè)體保存，同時(shí)保證該個(gè)體繼續(xù)參與進(jìn)化，當(dāng)有適應(yīng)度更高的染色體出現(xiàn)時(shí)，將原保留的個(gè)體用該個(gè)體替換，以保證最優(yōu)個(gè)體不丟失且始終保持最優(yōu)，彌補(bǔ)輪盤賭選擇的不足。

2.4.2" 交叉算子

交叉操作選用單點(diǎn)交叉[13]的方式。按照設(shè)定的交叉概率，首先選擇兩個(gè)父代個(gè)體，在它們之間對(duì)應(yīng)位置隨機(jī)選擇一個(gè)點(diǎn)，利用該點(diǎn)將兩父代個(gè)體的基因序列一分為二；然后將這兩個(gè)父代個(gè)體的后半部分基因交換，從而形成兩個(gè)新的個(gè)體，完成交叉操作。通過(guò)交叉算子能夠生成新個(gè)體，新個(gè)體來(lái)自上一代種群，而不同于上一代種群中的個(gè)體，從而實(shí)現(xiàn)算法的全局搜索。

2.4.3" 變異算子

交叉操作采用基本位變異[14]的方法。交叉操作按照較小的概率進(jìn)行，按照設(shè)定的變異概率，將選中個(gè)體的某位基因由零變一或由一變零，以改變?cè)撐坏幕蛑?，從而產(chǎn)生新的個(gè)體。通過(guò)變異操作也可以產(chǎn)生新的個(gè)體，但因變異操作的概率較小且染色體變動(dòng)不大，完成了在遺傳進(jìn)化過(guò)程中進(jìn)行局部搜索的作用。

2.4.4" 修正算子

修正算子用于判斷個(gè)體是否為有效路徑及修復(fù)個(gè)體。當(dāng)種群完成交叉和變異操作后，所生成的新種群中部分個(gè)體可能會(huì)存在障礙柵格，即為無(wú)效路徑。無(wú)效路徑如被隨意刪除將影響種群的多樣性，不利于算法的收斂，此時(shí)需使用修正算子對(duì)個(gè)體進(jìn)行修復(fù)。當(dāng)個(gè)體中存在一個(gè)障礙柵格時(shí)，對(duì)障礙柵格相鄰的兩個(gè)自由柵格分別使用八叉樹行走方式確定交叉柵格，如交叉柵格只有一個(gè)，則用其替代障礙柵格，如交叉柵格有多個(gè)，每個(gè)交叉柵格對(duì)應(yīng)一個(gè)有效路徑，此時(shí)需計(jì)算每個(gè)有效路徑的適應(yīng)度值，選擇適應(yīng)度值最高的個(gè)體代替原個(gè)體，如適應(yīng)度相同，則隨機(jī)選擇一個(gè)個(gè)體。當(dāng)個(gè)體中存在多個(gè)障礙柵格時(shí)，則自左向右依次按照一個(gè)障礙柵格的方法來(lái)處理。

3" 實(shí)驗(yàn)與分析

改進(jìn)算法的可行性和有效性需通過(guò)實(shí)驗(yàn)驗(yàn)證。使用MATLAB 2015b在配置為2.4 GHz、酷睿i5處理器、Windows 11家庭中文版的戴爾Inspiron 15 3511計(jì)算機(jī)平臺(tái)上，對(duì)其進(jìn)行計(jì)算機(jī)仿真實(shí)驗(yàn)，并與基本遺傳算法進(jìn)行比較。工作環(huán)境為20×20的柵格環(huán)境，改進(jìn)算法與原算法主要參數(shù)設(shè)置如下：種群規(guī)模M = 200，交叉操作的概率Pc = 0.6，變異操作的概率Pm = 0.05，最大進(jìn)化代數(shù)T = 100。

圖4、圖5分別為兩種算法的收斂曲線，圖6、圖7分別為兩種算法的路徑規(guī)劃圖，對(duì)比可得：基本遺傳算法在第37代收斂，規(guī)劃路徑長(zhǎng)度為32.8，陷入局部最優(yōu)解，改進(jìn)遺傳算法在第10代收斂，規(guī)劃路徑長(zhǎng)度為28.63，搜索到全局最優(yōu)解。在相同的工作環(huán)境和參數(shù)設(shè)定情況下，改進(jìn)遺傳算法的收斂的更早，并且沒(méi)有陷入局部最優(yōu)解。

單次實(shí)驗(yàn)具有隨機(jī)性和不確定性，為確保改進(jìn)算法的有效性，按照原參數(shù)對(duì)兩種算法分別進(jìn)行50次實(shí)驗(yàn)，計(jì)算其平均收斂代數(shù)和最優(yōu)路徑比例，實(shí)驗(yàn)結(jié)果如表1所示。從表中可以看到，50次實(shí)驗(yàn)中，改進(jìn)遺傳算法平均收斂代數(shù)為12.5，小于基本遺傳算法的43.6，尋到最優(yōu)路徑的比例為98%，高于基本遺傳算法的76%。因此，改進(jìn)遺傳算法相比于基本遺傳算法在規(guī)劃路徑時(shí)收斂更快，尋優(yōu)效率更高，且不易陷入局部最優(yōu)，能有效地解決了基本遺傳算法早熟和收斂慢的問(wèn)題。

4" 結(jié)" 論

為解決基本遺傳算法的早熟和收斂慢及對(duì)移動(dòng)機(jī)器人路徑規(guī)劃的適應(yīng)性，對(duì)基本遺傳算法進(jìn)行了改進(jìn)。在種群初始化時(shí)將八叉樹與引導(dǎo)函數(shù)結(jié)合，提高了初始化種群質(zhì)量；選擇操作中采用輪盤賭和精英保留策略相結(jié)合的方式，能避免精英個(gè)體的丟失而使算法陷入局部最優(yōu)；在遺傳操作中增加修正算子，能在不影響進(jìn)化的同時(shí)保證進(jìn)化后個(gè)體的有效性。改進(jìn)遺傳算法在規(guī)劃路徑時(shí)收斂更快，尋優(yōu)效率更高，且不易陷入局部最優(yōu)，能有效地解決基本遺傳算法存在的問(wèn)題。

參考文獻(xiàn)：

[1] 梅藝林，崔立堃，胡雪巖，等.基于人工勢(shì)場(chǎng)法的復(fù)雜環(huán)境下多無(wú)人車避障與編隊(duì)控制 [J/OL].工程科學(xué)學(xué)報(bào)，2024：1-14[2024-12-03].http：//kns.cnki.net/kcms/detail/10.1297.TF.20240830.1126.002.html.

[2] 秦旭，黃曉華，馬東明，等.基于改進(jìn)D*算法的巡檢機(jī)器人路徑規(guī)劃 [J].組合機(jī)床與自動(dòng)化加工技術(shù)，2022（6）：10-13.

[3] 王慧婷，余萌，李昱葉，等.月面南極巡視器自主導(dǎo)航路徑規(guī)劃算法 [J].深空探測(cè)學(xué)報(bào)：中英文，2023，10（6）：598-607.

[4] HART P E，NLSSON N J，RAPHEL B. A Formal Basis for the Heuristic Determination of Minimum Cost Paths [J].IEEE Transactions on Systems Science and Cybernetics，1968，4（2））：100-107.

[5] 閆永權(quán).基于注意力機(jī)制的云數(shù)據(jù)中心資源消耗預(yù)測(cè) [J/OL].武漢大學(xué)學(xué)報(bào)：理學(xué)版，2024：1-10[2024-11-28].https：//doi.org/10.14188/j.1671-8836.2024.0031.

[6] ZHUANG X Q，ZHUANG S Q，SU D M，DU S，et al. TPS-Genetic Algorithm for Real-Time Sailing Route Planning based on Potential Field Theory [J].European Journal of Engineering and Technology Research，2023，8（3）：86-99.

[7] 許赫威，戴曉強(qiáng)，王瑩，等.改進(jìn)分布估計(jì)算法的AUV全局路徑規(guī)劃 [J].傳感器與微系統(tǒng)，2024，43（7）：47-50.

[8] 韓書豪.基于實(shí)時(shí)分布式模式的多機(jī)器人協(xié)同運(yùn)動(dòng)控制 [D].西安：西安電子科技大學(xué)，2021.

[9] 周雷.基于改進(jìn)鯨魚優(yōu)化算法的無(wú)人機(jī)航跡規(guī)劃技術(shù)研究 [D].南昌：華東交通大學(xué)，2023.

[10] 龔銘凡，徐海祥，馮輝，等.基于改進(jìn)蟻群算法的智能船舶路徑規(guī)劃 [J].武漢理工大學(xué)學(xué)報(bào)：交通科學(xué)與工程版，2020，44（6）：1072-1076.

[11] 楊朝棚.海流環(huán)境下的無(wú)人艇路徑規(guī)劃研究 [D].廈門：集美大學(xué)，2024.

[12] 黃榮杰，王亞剛.基于可視圖與改進(jìn)遺傳算法的機(jī)器人平滑路徑規(guī)劃 [J].控制工程，2024，31（4）：678-686.

[13] 楊寅澤，柯俊.基于GA優(yōu)化神經(jīng)網(wǎng)絡(luò)的變剛度復(fù)合材料板簧剛強(qiáng)度預(yù)測(cè)研究 [J].軟件工程，2024，27（7）：17-21.

[14] 張滕飛，金曉輝，朱汗青.基于改進(jìn)樸素貝葉斯的武器裝備性能預(yù)測(cè) [J].軍事交通學(xué)院學(xué)報(bào)，2021，23（5）：23-27.

作者簡(jiǎn)介：李忠林（1990—），男，漢族，江蘇連云港人，助教，碩士，研究方向：智能控制與算法。