基于遺傳算法改進(jìn)的AGV 路徑規(guī)劃研究

馮 舒，劉 明

（云南民族大學(xué) 電氣信息工程學(xué)院，云南 昆明 650504）

0 引言

隨著人們環(huán)保意識(shí)的增強(qiáng)，節(jié)能減排在路徑規(guī)劃中的應(yīng)用被越來越多的研究者所關(guān)注，越來越多的學(xué)者開始關(guān)注物流體系中的碳排放問題[1]。尋找一條自動(dòng)引導(dǎo)搬運(yùn)車（Automated Guided Vehicle,AGV）綠色節(jié)能路徑的研究課題受到極大重視。

目前，針對(duì)AGV 路徑規(guī)劃這一領(lǐng)域，已有很多學(xué)者進(jìn)行研究。如：李健康等提出通過優(yōu)化狀態(tài)轉(zhuǎn)移概率以及信息素更新的方法對(duì)蟻群算法進(jìn)行改進(jìn)，再應(yīng)用于AGV 路徑規(guī)劃，獲得更短路徑[2]；熬國鑫等提出一種改進(jìn)的BI?RRT 算法，引入可變權(quán)重實(shí)現(xiàn)目標(biāo)導(dǎo)向，再對(duì)生成路徑作剪枝優(yōu)化，最后進(jìn)行平滑處理，得到更加平滑且較短的路徑[3]。

隨著各行各業(yè)對(duì)于節(jié)能減排的需求越來越迫切，學(xué)者們開始考慮AGV 路徑規(guī)劃的能耗問題，并且AGV 能耗指標(biāo)已得到工業(yè)界以及學(xué)術(shù)界的重視。為了實(shí)現(xiàn)節(jié)能減排與AGV 物流運(yùn)輸協(xié)同進(jìn)行，一些學(xué)者開展了相關(guān)的探索和研究。例如：郭亞銘等對(duì)結(jié)合AGV 的轉(zhuǎn)向和直行兩種模式下的運(yùn)動(dòng)進(jìn)行分析，建立單AGV 節(jié)能模型，利用Dijkstra 算法實(shí)現(xiàn)路徑規(guī)劃，得到距離短、能耗低的路徑；李俊蘭等提出一種結(jié)合改進(jìn)Dijkstra 算法和非支配排序遺傳法建立的AGV 節(jié)能模型來規(guī)劃路徑。但這些方法都存在一定程度的復(fù)雜性，并且很少考慮轉(zhuǎn)角數(shù)目以及拐彎角度的大小，而這些因素對(duì)于AGV 的運(yùn)動(dòng)能耗影響很大[4]。

本文提出一種改進(jìn)的遺傳算法。首先對(duì)地圖中的障礙物進(jìn)行規(guī)則化處理，忽略不必要的冗余角點(diǎn)，降低計(jì)算復(fù)雜度以提高算法效率；其次，以路徑長度為優(yōu)化目標(biāo)，且對(duì)遺傳算法中的變異算子進(jìn)行改進(jìn)，使得路徑總向?qū)δ繕?biāo)有利的方向進(jìn)行變異，尋找到一條最短、轉(zhuǎn)彎節(jié)點(diǎn)最少的路徑。

1 相關(guān)算法

遺傳算法是一種模擬生物遺傳進(jìn)化規(guī)律的原理來進(jìn)行尋優(yōu)的算法。它融合了“適者生存”“物競天擇”的擇優(yōu)方式以及遺傳基因交叉變異的特點(diǎn)，將需要求解的問題通過編碼形成染色體，模擬生物進(jìn)化的過程，再通過種群迭代和選擇、交叉、變異等步驟，并多次迭代和循環(huán)，篩選出最優(yōu)秀的染色體，最優(yōu)染色體對(duì)應(yīng)的解就是該問題的最優(yōu)解[5]。標(biāo)準(zhǔn)遺傳算法流程如圖1 所示。

2 算法描述

基于遺傳算法對(duì)AGV 路徑規(guī)劃進(jìn)行改進(jìn)。首先本文對(duì)地圖中的障礙物進(jìn)行簡化處理，改善角點(diǎn)過多的問題；再通過改進(jìn)的遺傳算法進(jìn)行路徑規(guī)劃，得到最優(yōu)路徑。

2.1 障礙物規(guī)則化處理

該文將障礙物分為三類，分別為1×n（n∈R）的矩形障礙物、b×m（b，m∈R）的矩形障礙物以及不規(guī)則多邊形障礙物。對(duì)于1×n的矩形障礙物，因?qū)挾戎粸橐粋€(gè)柵格，因此只在其尺寸為1 的柵格兩側(cè)旁各取一個(gè)角點(diǎn)即可，如圖2 所示，淺灰色部分為角點(diǎn)柵格。針對(duì)b×m的矩形障礙物，以其4 個(gè)凸角點(diǎn)為柵格角點(diǎn)，如圖3 所示。對(duì)于不規(guī)則多邊形障礙物，將其填補(bǔ)為多邊形的最小外接矩形，如圖4 所示，灰色部分為填充部分，淺灰色部分為角點(diǎn)柵格。對(duì)障礙物簡化后，在一定程度上減少了冗余節(jié)點(diǎn)，可為后續(xù)路徑搜索做準(zhǔn)備，有效提高搜索效率。

圖2 1×n 矩形障礙物取點(diǎn)

圖3 b×m 矩形障礙物取點(diǎn)

圖4 不規(guī)則障礙物取點(diǎn)

2.2 算法描述及其實(shí)現(xiàn)過程

首先，根據(jù)連通性矩陣可知角點(diǎn)ai與哪幾個(gè)角點(diǎn)連通，設(shè)從起始點(diǎn)ai到終點(diǎn)an之間，與ai連通的點(diǎn)有aj、ak、al、am，按角點(diǎn)順序連通，比如aj的順序排第一，則形成路徑a1→aj。

若a1與終點(diǎn)an有直接連通性，則跳過所有中間連通角點(diǎn)直接與終點(diǎn)連接。若在連通過程中出現(xiàn)與之前已連通過的角點(diǎn)重復(fù)的角點(diǎn)，為避免路徑出現(xiàn)死循環(huán)，則將兩角點(diǎn)之間的連通性斷開。

在連通過程中，如果某角點(diǎn)的所有連通角點(diǎn)在之前全部重復(fù)，則將連通關(guān)系全部取消，該角點(diǎn)無法到達(dá)終點(diǎn)。為了區(qū)別到達(dá)終點(diǎn)與未到達(dá)終點(diǎn)的路徑，設(shè)置懲罰函數(shù)將兩者區(qū)分，公式如下：

式中：Dall表示總路程長度；Df為已走完的路徑；Ddnf為未走的路徑；W為懲罰權(quán)重。本文將懲罰權(quán)重W設(shè)為5，將到達(dá)終點(diǎn)與未到達(dá)終點(diǎn)的路徑明顯區(qū)分開。

改進(jìn)遺傳算法的過程如下：

1）對(duì)角點(diǎn)種群進(jìn)行初始化處理，種群數(shù)目大小為popsize，個(gè)體的基因長度為poplength，并對(duì)初始種群采用輪盤賭的方式進(jìn)行選擇，確定每個(gè)個(gè)體被選擇的次數(shù)。

2）進(jìn)行交叉操作，本文采用前一個(gè)種群個(gè)體與后一個(gè)種群個(gè)體進(jìn)行交叉。

3）對(duì)種群個(gè)體進(jìn)行變異操作，產(chǎn)生隨機(jī)數(shù)rand，當(dāng)隨機(jī)數(shù)rand 小于變異概率Pm時(shí)，隨機(jī)確定變異位置并對(duì)基因進(jìn)行變異。

4）計(jì)算每個(gè)個(gè)體適應(yīng)度值并按大小排序。

5）判斷是否達(dá)到迭代次數(shù)最大值，達(dá)到則輸出排名前10 的個(gè)體；如果不滿足則返回步驟1）繼續(xù)進(jìn)行。

對(duì)于交叉變異，本文采用改進(jìn)策略。首先，要找到合適的變異概率，一般會(huì)取一個(gè)很小的值。但是變異概率不宜很小也不宜過大，因?yàn)檫^大會(huì)破壞種群中的優(yōu)良個(gè)體，過小則會(huì)使得種群過早收斂，這是由于在變異的過程中既會(huì)產(chǎn)生優(yōu)良個(gè)體也會(huì)產(chǎn)生劣質(zhì)個(gè)體[6]。本文針對(duì)這一問題對(duì)變異算子進(jìn)行改進(jìn)，過程如下：

1）設(shè)路徑為：

2）若變異點(diǎn)的位置與其前后基因位置滿足以下關(guān)系：當(dāng)Nn+1-Nn-1=10 且Nn+1-Nn-1=1 時(shí)，則Nn-1、Nn、Nn+1形成45°角，此時(shí)，把基因Nn刪除，形成新的路徑。

3）若變異點(diǎn)的位置與其前后基因位置滿足以下關(guān)系：當(dāng)Nn+1-Nn-1=11 時(shí)，Nn-1、Nn、Nn+1形成90°角，則把基因Nn刪除，形成新路徑。

4）如果變異點(diǎn)基因的位置與其前后基因位置滿足以下關(guān)系：當(dāng)Nn+1-Nn-1=12，Nn+1-Nn-1=21 時(shí)，Nn-1、Nn、Nn+1形成135°角，就把基因Nn刪除。此時(shí)新形成的路徑為：

新形成的路徑相較于改進(jìn)前長度更短，拐彎數(shù)量更少，因此，變異概率選較大一些。本文取變異概率Pm=0.3。

3 實(shí)驗(yàn)仿真及分析

為檢驗(yàn)改進(jìn)算法的可靠性，將改進(jìn)算法與遺傳算法從搜索時(shí)間、路徑長度、拐彎節(jié)點(diǎn)數(shù)、穿墻次數(shù)以及尋到的角點(diǎn)數(shù)等方面進(jìn)行分析對(duì)比。本文的仿真在Matlab上進(jìn)行驗(yàn)證。

首先對(duì)柵格圖中的障礙物進(jìn)行分類處理，用多邊形障礙物變換為最小外接矩形等一系列方法來減少搜索角點(diǎn)數(shù)，再對(duì)各角點(diǎn)之間的連通關(guān)系進(jìn)行判斷；其次，為減少穿墻次數(shù)，改進(jìn)算法將坐標(biāo)數(shù)值改為柵格中心點(diǎn)的位置。這種方法相較于原先的常規(guī)數(shù)值坐標(biāo)以柵格交點(diǎn)為中心點(diǎn)來說安全性更高，可以有效減少穿墻次數(shù)。坐標(biāo)位置圖如圖5所示。圖6為實(shí)際角點(diǎn)中心點(diǎn)連接圖。

圖5 坐標(biāo)位置圖

圖6 角點(diǎn)中心點(diǎn)連接圖

實(shí)驗(yàn)在100×100 的柵格中進(jìn)行，圖7 為改進(jìn)后尋到的角點(diǎn)圖，明顯可以看出，改進(jìn)后的角點(diǎn)相較于改進(jìn)前角點(diǎn)數(shù)減少了很多，這為后續(xù)階段的計(jì)算提高了效率，減少了計(jì)算量。圖8 為所有角點(diǎn)的連通路徑。

圖7 改進(jìn)角點(diǎn)圖

圖8 角點(diǎn)連接圖

圖9 為遺傳算法與改進(jìn)算法在同一地圖中的路徑圖，具體實(shí)驗(yàn)數(shù)據(jù)如表1 所示。由實(shí)驗(yàn)數(shù)據(jù)分析可看出：改進(jìn)算法尋到的角點(diǎn)數(shù)目相較于普通遺傳算法來說減少了68.8%，所用時(shí)間也略小于普通遺傳算法；并且改進(jìn)算法在速度方面能夠更快地得到最佳路徑，找到的路徑長度也比普通遺傳算法更短。改進(jìn)算法全程無穿墻事件發(fā)生，安全性更高，且拐彎角點(diǎn)也更少，有益于降低能耗。

表1 兩種算法實(shí)驗(yàn)數(shù)據(jù)對(duì)比

圖9 100×100 柵格地圖兩種算法路徑

圖10 為迭代次數(shù)與距離的收斂曲線。由圖10 可知，迭代次數(shù)為50 次，隨著迭代次數(shù)的增加，曲線收斂越快，尋找到的路徑距離更短，最終找到相對(duì)最優(yōu)的一條路徑。

圖10 迭代次數(shù)與距離的收斂曲線

4 結(jié)語

針對(duì)AGV 在自動(dòng)化生產(chǎn)線工作的過程中存在的拐彎節(jié)點(diǎn)過多，以及穿墻現(xiàn)象導(dǎo)致與障礙物摩擦的問題，本文通過簡化障礙物減少搜索角點(diǎn)，達(dá)到簡化計(jì)算、提高搜索效率的目的；并且改善了柵格地圖的坐標(biāo)系，在一定程度上減少了運(yùn)用遺傳算法時(shí)造成的穿墻事件，提高了AGV 的安全性。其次，本文的遺傳算法以路徑最短為優(yōu)化目標(biāo)，且對(duì)遺傳算法的變異算子進(jìn)行了改進(jìn)，并對(duì)種群個(gè)體進(jìn)行選擇、交叉、變異等操作，不僅找到的路徑更短，還能減少路徑的拐點(diǎn)數(shù)目，使得找到的路徑更加順滑，取得一系列優(yōu)化效果。

由仿真實(shí)驗(yàn)結(jié)果可看出：改進(jìn)算法相對(duì)于普通遺傳算法來說不僅在一定程度減少了搜索時(shí)間，縮短了路徑長度，還減少了穿墻次數(shù)，有效提高了路徑的安全系數(shù)；并且通過對(duì)變異算子的改進(jìn)，拐彎角點(diǎn)也有所減少，因此改進(jìn)算法使規(guī)劃的路徑更加合理有效。但是也存在一些不足，如拐彎處的路徑不夠圓滑，且無法直觀看到耗能量，因此在后續(xù)工作會(huì)加入節(jié)能模型來使算法更加完善。