丁家會(huì) 冒宇露 顧立博 戴彥楚 吳雪倩

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

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

中圖分類號(hào)：TP301.6 ? ? 文獻(xiàn)標(biāo)識(shí)碼：A ? ? ? 文章編號(hào)：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)進(jìn)行了很多年，研究者們提出多種方法來解決此問題，不同的方法適用范圍也各不相同，沒有一種路徑規(guī)劃方法適用于所有環(huán)境信息。其中，人工勢(shì)場(chǎng)法[1]、網(wǎng)格法[2]、粒子群算法[3]等是路徑規(guī)劃中的典型方法。但一些傳統(tǒng)的優(yōu)化算法在非線性、離散的路徑規(guī)劃問題中受局限較大，優(yōu)化效果并不太好。因此，遺傳算法憑借其較強(qiáng)的全局尋優(yōu)能力而被廣泛地應(yīng)用于路徑規(guī)劃問題，本文提出一種基于Dijkstra算法的改進(jìn)遺傳算法用于求解機(jī)器人路徑規(guī)劃問題。

1 算法介紹

1.1 遺傳算法

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

1.2 Dijkstra算法

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

2 改進(jìn)算法的原理及步驟

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

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

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

3 算法的設(shè)定

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

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

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

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

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

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

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

式中，pop表示變異后的個(gè)體，pop（a，：）表示當(dāng)前變異的個(gè)體，popmax表示終點(diǎn)的實(shí)數(shù)序號(hào)，nvar表示當(dāng)前變異個(gè)體的長(zhǎng)度，根據(jù)公式（4）隨機(jī)生成一個(gè)新個(gè)體。

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

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

4 仿真實(shí)驗(yàn)與分析

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

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

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

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

5 結(jié)語

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

參考文獻(xiàn)：

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

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

[3] 賈會(huì)群，魏仲慧，何昕，等.基于改進(jìn)粒子群算法的路徑規(guī)劃[J].農(nóng)業(yè)機(jī)械學(xué)報(bào)，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] 丁家會(huì)，張兆軍.基于個(gè)體排序的自適應(yīng)遺傳算法[J].電子科技，2020，33（3）：6-11，32.

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