改進遺傳算法的移動機器人路徑規劃研究

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

關鍵詞：移動機器人；路徑規劃；遺傳算法；改進遺傳算法

中圖分類號：TP242.6" " " 文獻標識碼：A 文章編號：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" 引" 言

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

1" 環境建模

環境建模是實現路徑規劃的前提，首先要對移動機器人的工作環境建模，常用的建模方法有柵格法、路標法以及可視圖法[7]。其中，柵格法具有簡單靈活易于處理的優點[8]，選用柵格法建模。

1.1" 柵格法環境建模

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

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

（1）

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

（2）

1.2" 柵格標識

直角坐標法[10]是常用的柵格標識方法，其特點是直觀明了，但不利于染色體的形成及遺傳操作，故在此基礎上改進為矩陣標識法，如圖2所示。矩陣標識法以柵格作為基本單位，將移動機器人的工作環境橫向劃分為M個柵格，縱向劃分為N個柵格，橫向從左向右用阿拉伯數字標注序號，縱向從下向上用阿拉伯數字標注序號。根據柵格所處的橫縱柵格序號確定其矩陣坐標，如柵格A所處位置是橫向第a個柵格和縱向第b個柵格，記作ab。為便于觀測與計算，給出矩陣坐標與直角坐標轉換公式，以柵格A為例，如式（3）所示：

（3）

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

1.3" 行走方式

行走方式是指移動機器人在柵格環境中移動的規則，四叉樹和八叉樹是移動機器人兩種基本的行走方式[11]。四叉樹行走方式如圖3（a）所示，移動機器人從當前柵格向下一個柵格移動時，可選擇向左、向右、向上、向下四個方向。八叉樹行走方式如圖3（b）所示，移動機器人除了選擇四叉樹中的四個方向外，還可以選擇四個斜行方向，左上、右上、左下、右下。因為八叉樹行走方向更多，又因其存在斜行方式，所形成的路徑更短，所以選用八叉樹的行走方式。

1.4" 行走規則

移動機器人按照八叉樹的方式行走，在t時刻，移動機器人的位置為（XtYt），在t-1時刻，移動機器人的位置為（Xt-1Yt-1），兩位置坐標應符合以下規則：

（4）

（5）

（6）

移動機器人行走的前后兩個時刻的位置坐標必須滿足式（4）和式（6）或式（5）和式（6），即移動機器人沿橫向坐標移動一個柵格或沿縱向坐標移動一個柵格或斜向行走一個斜向柵格。

移動機器人的路徑規劃是為了獲取一條最短的安全路徑，路徑長度用函數obj表示，即將每兩個時刻之間路徑長度累積，計算方法如式（7）所示：

（7）

其中，St表示連續兩步之間的距離。一個柵格的長度記為單位1，移動機器人沿坐標軸移動時，每移動一次的路徑長度為1，當移動機器人斜向移動時，每移動一次的路徑長度為。

2" 改進遺傳算法

基本遺傳算法是一種優異的智能尋優算法，但在使用基本遺傳算法規劃路徑時易出現收斂慢和早熟的現象，為此，需設計一種改進遺傳算法，為移動機器人路徑規劃提供一種新的思路和解決辦法。

2.1" 染色體編碼

染色體編碼采用二進制編碼方式。在使用二進制編碼時，首先將柵格坐標依次序連接起來形成路徑，如ab，cd…mn。然后，將路徑中的每個柵格坐標值用二進制數表示，即為染色體，從而完成染色體編碼。其中，用二進制數表示位置坐標時所采用的二進制位數以當前環境模型中的終點坐標所需用的最大二進制位數為基準，其他坐標均按照該二進制位數表示。

2.2" 初始化種群

初始化種群采用八叉樹與引導函數的相結合的方式。從起始柵格出發，按八叉樹原則選取與起始柵格相鄰的自由柵格作為下一個路徑柵格，當可供選擇的自由柵格為多個時，需計算引導函數的值，引導函數如式（8）。將所有自由柵格的引導因子計算后，采用賭盤策略來選定柵格。規定在一條路徑中，當柵格被選定后，標記該柵格，在后續路徑規劃中不會被再次選擇，以避免產生循環路徑。

（8）

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

2.3" 適應度函數

適應度函數以路徑總長的倒數作為適應度函數，記作F，如式（9）。對于路徑規劃，路徑總長度越短越好，即F越大越好。

（9）

式中i為示路徑的序號，St為t時刻和t-1時刻之間的歐式距離。

2.4" 遺傳操作

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

2.4.1" 選擇算子

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

2.4.2" 交叉算子

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

2.4.3" 變異算子

交叉操作采用基本位變異[14]的方法。交叉操作按照較小的概率進行，按照設定的變異概率，將選中個體的某位基因由零變一或由一變零，以改變該位的基因值，從而產生新的個體。通過變異操作也可以產生新的個體，但因變異操作的概率較小且染色體變動不大，完成了在遺傳進化過程中進行局部搜索的作用。

2.4.4" 修正算子

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

3" 實驗與分析

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

圖4、圖5分別為兩種算法的收斂曲線，圖6、圖7分別為兩種算法的路徑規劃圖，對比可得：基本遺傳算法在第37代收斂，規劃路徑長度為32.8，陷入局部最優解，改進遺傳算法在第10代收斂，規劃路徑長度為28.63，搜索到全局最優解。在相同的工作環境和參數設定情況下，改進遺傳算法的收斂的更早，并且沒有陷入局部最優解。

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

4" 結" 論

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

參考文獻：

[1] 梅藝林，崔立堃，胡雪巖，等.基于人工勢場法的復雜環境下多無人車避障與編隊控制 [J/OL].工程科學學報，2024：1-14[2024-12-03].http：//kns.cnki.net/kcms/detail/10.1297.TF.20240830.1126.002.html.

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

[3] 王慧婷，余萌，李昱葉，等.月面南極巡視器自主導航路徑規劃算法 [J].深空探測學報：中英文，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] 閆永權.基于注意力機制的云數據中心資源消耗預測 [J/OL].武漢大學學報：理學版，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] 許赫威，戴曉強，王瑩，等.改進分布估計算法的AUV全局路徑規劃 [J].傳感器與微系統，2024，43（7）：47-50.

[8] 韓書豪.基于實時分布式模式的多機器人協同運動控制 [D].西安：西安電子科技大學，2021.

[9] 周雷.基于改進鯨魚優化算法的無人機航跡規劃技術研究 [D].南昌：華東交通大學，2023.

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

[11] 楊朝棚.海流環境下的無人艇路徑規劃研究 [D].廈門：集美大學，2024.

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

[13] 楊寅澤，柯俊.基于GA優化神經網絡的變剛度復合材料板簧剛強度預測研究 [J].軟件工程，2024，27（7）：17-21.

[14] 張滕飛，金曉輝，朱汗青.基于改進樸素貝葉斯的武器裝備性能預測 [J].軍事交通學院學報，2021，23（5）：23-27.

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