丁家會 冒宇露 顧立博 戴彥楚 吳雪倩

摘 要：針對傳統(tǒng)路徑規(guī)劃算法存在路徑不可達、尋優(yōu)計算規(guī)模大等缺陷導致算法的計算量大、收斂精度低等問題，本文提出采用改進遺傳算法優(yōu)化中間節(jié)點，結(jié)合Dijkstra算法求最短路徑算法補齊節(jié)點間的路徑形成一條完整路徑的方式，保證遺傳操作中的路徑全部為可行路徑。與傳統(tǒng)遺傳算法作對比，試驗結(jié)果表明改進后的算法在收斂精度和尋優(yōu)能力上都取得了明顯的效果。

關(guān)鍵詞：遺傳算法;路徑規(guī)劃;中間節(jié)點

中圖分類號：TP301.6 ? ? 文獻標識碼：A ? ? ? 文章編號：1003-5168（2021）27-0006-03

Abstract： In view of the problems of traditional path planning algorithms such as unreachable paths and large-scale optimization calculations， which lead to large calculations and low convergence accuracy， this paper proposes an improved genetic algorithm to optimize intermediate nodes， combined with Dijkstra's shortest path algorithm to fill in the path between nodes to form a complete path， to ensure that all paths in the genetic operation are feasible paths. Compared with the traditional genetic algorithm， the experimental results show that the improved algorithm has achieved obvious results in convergence accuracy and optimization ability.

Keywords： genetic algorithm; path planning; intermediate node

路徑規(guī)劃研究已經(jīng)進行了很多年，研究者們提出多種方法來解決此問題，不同的方法適用范圍也各不相同，沒有一種路徑規(guī)劃方法適用于所有環(huán)境信息。其中，人工勢場法[1]、網(wǎng)格法[2]、粒子群算法[3]等是路徑規(guī)劃中的典型方法。但一些傳統(tǒng)的優(yōu)化算法在非線性、離散的路徑規(guī)劃問題中受局限較大，優(yōu)化效果并不太好。因此，遺傳算法憑借其較強的全局尋優(yōu)能力而被廣泛地應(yīng)用于路徑規(guī)劃問題，本文提出一種基于Dijkstra算法的改進遺傳算法用于求解機器人路徑規(guī)劃問題。

1 算法介紹

1.1 遺傳算法

遺傳算法實時性能良好，應(yīng)用于移動機器人路徑規(guī)劃的基本思想是：將路徑個體表示為路徑中的一系列中間點，然后通過編碼將其轉(zhuǎn)化為數(shù)學問題。具體而言，它包括初始化路徑種群，然后執(zhí)行一系列遺傳運算，如選擇、交叉、變異等，在滿足終止條件后停止進化，并輸出當前的最優(yōu)個體[4]。

1.2 Dijkstra算法

1959年，荷蘭科學家Dijkstra提出并命名了一種求解單源點到其余頂點的最短路徑問題的算法——Dijkstra算法，其思想是按路徑長度遞增的次序一步一步并入來求取，是貪婪算法的一個應(yīng)用[5]。

2 改進算法的原理及步驟

研究發(fā)現(xiàn)，傳統(tǒng)遺傳算法解決路徑規(guī)劃問題存在以下缺陷：（1）路徑個體編碼設(shè)計不合理，導致進化過程中產(chǎn)生不可行路徑;（2）遺傳算子的設(shè)置參數(shù)應(yīng)能在線調(diào)整。

本文中的解決方法為：對于問題（1），采用遺傳算法優(yōu)化中間節(jié)點，隨機生成n個非障礙物的中間節(jié)點，中間節(jié)點和路徑起始點間用Dijkstra算法求最短路徑補齊;針對問題（2），采用改進遺傳算法[6]中的自適應(yīng)調(diào)節(jié)方法，從而在線調(diào)節(jié)算法中的交叉和變異概率。

改進算法進行路徑規(guī)劃的主要步驟：①建立柵格環(huán)境，標明障礙物、路徑點與非障礙物的序列號;②確定起始和終點位置、種群數(shù)量sizepop、迭代次數(shù)itermax等初始化參數(shù)及中間節(jié)點數(shù)量n;③隨機生成sizepop*n個路徑節(jié)點作為初始化種群pop，采用Dijkstra求最短路算法生成完整的可行路徑集合path;④將路徑集合中的個體代入目標函數(shù)，根據(jù)適應(yīng)度值選擇個體進行下一步遺傳操作;⑤對中間節(jié)點進行交叉、變異操作，直到生成新的節(jié)點種群，并得到新的路徑集;⑥判斷是否滿足終止條件，若不滿足返回④;若滿足，輸出最優(yōu)節(jié)點和路徑。

3 算法的設(shè)定

本文選用實數(shù)編碼[7]方式根據(jù)path中每條路徑的適應(yīng)度對pop中對應(yīng)的中間節(jié)點進行優(yōu)化，保證算法運行過程中參與運算的路徑全部都是可行解。

設(shè)置適應(yīng)度函數(shù)如公式（1）所示：

其中，T表示機器人經(jīng)過的路徑點的數(shù)目，L表示起點與終點間所有路徑點的距離之和，即一條路徑的完整長度，用公式（2）表示：

其中，L（Pi，Pi+1）表示相鄰兩個端點間的距離。L越大，說明個體效果越差，因此將適應(yīng)度值小的個體作為優(yōu)秀個體，不斷尋優(yōu)直到找到全局最優(yōu)解。

另外，采用算術(shù)交叉方式對個體進行交叉操作，交叉方式如公式（3）所示：

式中，pop表示交叉后的個體，pop1和pop2分別表示較優(yōu)父代個體和較差父代個體，k取[0，0.5]區(qū)間內(nèi)的任意數(shù)，使得新個體較大概率繼承優(yōu)秀父代。

變異方式如公式（4）所示：

式中，pop表示變異后的個體，pop（a，：）表示當前變異的個體，popmax表示終點的實數(shù)序號，nvar表示當前變異個體的長度，根據(jù)公式（4）隨機生成一個新個體。

另外，交叉率和變異率的確定以文獻[6]中的自適應(yīng)公式為依據(jù)，如公式（5）和公式（6）所示。

其中，N1表示父代適應(yīng)度值中較大者的排序號，N2為平均適應(yīng)度值的排序號，N3為最大適應(yīng)度值的排序號。

4 仿真實驗與分析

為驗證算法有效性，在靜態(tài)柵格環(huán)境中對該算法進行仿真，相同環(huán)境下與傳統(tǒng)遺傳算法作對比，設(shè)置種群規(guī)模sizepop=60，最大進化代數(shù)itermax=100，自適應(yīng)調(diào)整參數(shù)Pc1=0.9，Pc2=0.6，Pm1=0.1，Pm2=0.05。傳統(tǒng)遺傳算法中隨機生成初始化種群，采用輪盤賭選擇法，設(shè)置交叉率Pc=0.6，變異率Pm=0.1，種群規(guī)模為60，最大進化代數(shù)為100。

在10*10和15*15柵格環(huán)境中，改進后的尋優(yōu)路徑及最大適應(yīng)度曲線對比圖分別如圖1和圖2所示。

對比發(fā)現(xiàn)，改進算法找到的路徑優(yōu)于傳統(tǒng)遺傳算法，證明了改進算法的優(yōu)越性。從最大適應(yīng)度曲線圖中可以看到傳統(tǒng)遺傳算法的收斂精度低于改進算法，推測由于自適應(yīng)策略的加入使得改進算法的交叉率和變異率在進化中后期變大，幫助種群跳出局部最優(yōu)。

試驗結(jié)果表明改進算法規(guī)劃的路徑比傳統(tǒng)遺傳算法規(guī)劃的效率更高，其收斂速度和收斂精度都優(yōu)于傳統(tǒng)遺傳算法，節(jié)約了實際工作時間。

5 結(jié)語

本文主要介紹了移動機器人在靜態(tài)環(huán)境下基于改進的遺傳算法實現(xiàn)的路徑規(guī)劃問題，主要工作包括構(gòu)建柵格地圖作為機器人的環(huán)境模型，采用改進遺傳算法優(yōu)化中間節(jié)點，再用Dijkstra算法求最短路算法補齊節(jié)點間的路徑，這種方式得到的路徑都是可行解，將離散化問題轉(zhuǎn)化為連續(xù)問題。設(shè)置最短距離為適應(yīng)度函數(shù)，提出算數(shù)交叉方式和隨機變異策略，交叉率、變異率的設(shè)定采用自適應(yīng)策略。最后仿真驗證改進算法的有效性和可行性。

參考文獻：

[1] 梁獻霞，劉朝英，宋雪玲，等.改進人工勢場法的移動機器人路徑規(guī)劃研究[J].計算機仿真，2018， 35（04）：291-294，361.

[2] 林巍凌.引入導航網(wǎng)格的室內(nèi)路徑規(guī)劃算法[J].測繪科學，2016，41（02）：39-43.

[3] 賈會群，魏仲慧，何昕，等.基于改進粒子群算法的路徑規(guī)劃[J].農(nóng)業(yè)機械學報，2018，49（12）：371-377.

[4] HOLLAND J H. Adaptation in natural and artificial systems[M]. Cambridge City： MIT Press， 1975.

[5] KAZUO M， AKIYOSHI S. Dijkstra's algorithm and L-concave function maximization[J]. Mathematical Programming， 2014，145（1-2）：163-177.

[6] 丁家會，張兆軍.基于個體排序的自適應(yīng)遺傳算法[J].電子科技，2020，33（3）：6-11，32.

[7] 林丹，李敏強，寇紀凇，等.基于實數(shù)編碼的遺傳算法的收斂性研究[J].計算機研究與發(fā)展，2000（11）：1321-1327.