改進(jìn)遺傳算法在AGV路徑規(guī)劃的應(yīng)用

白云飛，胡大裟，蔣玉明，馮魯波

(1. 四川大學(xué)計(jì)算機(jī)學(xué)院，成都 610065；2. 四川省大數(shù)據(jù)分析與融合應(yīng)用技術(shù)工程實(shí)驗(yàn)室，成都 610065)

0 前言

隨著全球工業(yè)自動(dòng)化時(shí)代的到來，自動(dòng)導(dǎo)引小車(Automated Guided Vehicle，AGV)在工業(yè)生產(chǎn)中起到了中流砥柱的作用。AGV對(duì)于提高工業(yè)生產(chǎn)效率、減少工作人員負(fù)擔(dān)和降低生產(chǎn)成本具有重要意義。而路徑規(guī)劃是AGV完成工業(yè)生產(chǎn)過程中物料配送的前提。在過去的幾十年里，研究人員做了許多工作。其中重要的算法有Dijkstra算法、A*算法等經(jīng)典方法，以及智能優(yōu)化算法，如蟻群算法和遺傳算法[1]。

由于遺傳算法在路徑規(guī)劃問題中，可以通過需求設(shè)定不同的編碼方式，具有更好的魯棒性和全局搜索能力，因此被廣泛的應(yīng)用到AGV路徑規(guī)劃中。但算法本身卻有易陷入局部最優(yōu)和收斂速度慢等缺點(diǎn)，不少學(xué)者對(duì)此進(jìn)行了一些改進(jìn)。如文獻(xiàn)[2]利用自整定優(yōu)化策略改進(jìn)雙交叉算子，并引入靜態(tài)路徑繁忙程度改進(jìn)適應(yīng)度函數(shù)，使規(guī)劃后的路徑更符合實(shí)際情況。文獻(xiàn)[3]優(yōu)化傳統(tǒng)遺傳算法中的雙交叉算子和變異算子，提出一種利用地圖特征信息的改進(jìn)型遺傳算法；文獻(xiàn)[4]利用退火算法提高種群差異性，通過自整定策略提高算法收斂速度；文獻(xiàn)[5]通過隨機(jī)交叉的方式維持種群多樣性，從而防止算法早熟。綜上所述，雖然對(duì)傳統(tǒng)遺傳算法加以改進(jìn)，但是算法仍然存在一些缺點(diǎn)需要優(yōu)化：首先，還是使用傳統(tǒng)的雙交叉方式；其次對(duì)于適應(yīng)度的改進(jìn)依舊停留在靜態(tài)環(huán)境中[6-8]，而不能對(duì)每次迭代的解進(jìn)行動(dòng)態(tài)修正；而且并未考慮多AGV規(guī)劃可能會(huì)導(dǎo)致?lián)矶拢窂睫D(zhuǎn)彎數(shù)過多導(dǎo)致運(yùn)行耗時(shí)過長，降低工作效率。

本文結(jié)合AGV路徑規(guī)劃的特點(diǎn)，使用拓?fù)浞ń⒌貓D模型；采用三啟發(fā)交叉算子獲得更多父代信息保證個(gè)體多樣性，提高算法收斂速度，防止陷入局部最優(yōu)解；為了提高AGV的運(yùn)行效率，減少其轉(zhuǎn)彎次數(shù)，對(duì)規(guī)劃的路徑進(jìn)行平滑判斷；為了減少AGV間的碰撞和擁堵概率，根據(jù)路徑上AGV數(shù)量，進(jìn)行擁堵程度判斷；利用路徑平滑程度描述轉(zhuǎn)彎次數(shù)，擁堵系數(shù)表達(dá)路徑的擁堵程度。然后將二者作為規(guī)劃指標(biāo)加入到適應(yīng)度函數(shù)中，對(duì)每代最優(yōu)路徑進(jìn)行獎(jiǎng)勵(lì)，最差路徑進(jìn)行懲罰，從而尋找到符合實(shí)際的路徑。

1 改進(jìn)的遺傳算法路徑規(guī)劃

1.1 環(huán)境建模

本文采用拓?fù)浞ń⒌貓D環(huán)境，采用符號(hào)編碼方式，將拓?fù)涔?jié)點(diǎn)的序號(hào)對(duì)應(yīng)染色體的基因值。拓?fù)涞貓D如圖1所示[10]

圖1 AGV環(huán)境模擬拓?fù)鋱D

集合{V|V1，V2，V3，…，V9}為節(jié)點(diǎn)，表示現(xiàn)實(shí)工廠的工作機(jī)臺(tái)，M表示為接貨點(diǎn)。節(jié)點(diǎn)之間的數(shù)據(jù)是路徑權(quán)重，表示運(yùn)行路徑上的具體信息。擁堵系數(shù)由Dis_Jam(S，P)的形式表達(dá)，其中Dis_Jam為兩點(diǎn)之間的距離，S為路徑平滑程度，P為擁堵系數(shù)。

1.2 三交換啟發(fā)式交叉算子

傳統(tǒng)的雙交叉方式只繼承父代的基本特征，使得子代多樣性較低，無法繼承過多父代的優(yōu)良基因。導(dǎo)致交叉的概率減小，進(jìn)化受阻，收斂速度緩慢。而且當(dāng)子類多樣性偏低時(shí)，也會(huì)導(dǎo)致變異的概率減少，不易產(chǎn)生新樣本，從而陷入局部最優(yōu)解。

三交換啟發(fā)式交叉算子利用三個(gè)父代染色體間產(chǎn)生一個(gè)子代。與傳統(tǒng)的雙交叉方式相比，增加了產(chǎn)生子代染色體的信息，提高子代多樣性。

而對(duì)于四交叉、五交叉的情況，如圖2所示。在同樣目標(biāo)下，雖然父代染色體的增多，提高了繼承雙親優(yōu)良性狀的可能性，但交叉次數(shù)過多，會(huì)導(dǎo)致收斂速度過慢。

圖2 交叉次數(shù)對(duì)比圖

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

為了使規(guī)劃路徑符合實(shí)際，充分考慮真實(shí)路況和多AGV的影響，引入路徑平滑程度和擁堵系數(shù)優(yōu)化適應(yīng)度函數(shù)。

計(jì)算公式如下：

(1)

公式(1)中：f為目標(biāo)函數(shù)；dis(vk，vk+1)表示個(gè)體vk和個(gè)體vk+1之間的距離；Pk和S分別為的擁堵系數(shù)和路徑平滑程度。

其中若目標(biāo)函數(shù)越小，代表所耗路徑越短，規(guī)劃的路徑越優(yōu)秀。反之，目標(biāo)函數(shù)越大，代表所耗路徑越長，規(guī)劃的路徑越差。

1.3.1 路徑平滑程度

由于AGV易受到動(dòng)力學(xué)和運(yùn)動(dòng)學(xué)的約束，拐彎幅度不宜過大，且相對(duì)平滑的路徑更適合運(yùn)行。為保證規(guī)劃路徑的合理性，利用路徑平滑程度描述AGV的轉(zhuǎn)彎次數(shù)及轉(zhuǎn)彎的角度大小。

為方便計(jì)算，根據(jù)拐角大小對(duì)AGV的轉(zhuǎn)彎情況做4個(gè)層次劃分。假設(shè)AGV的正常轉(zhuǎn)彎速度為vr，arc為拐角角度，引入懲罰系數(shù)α。α計(jì)算公式如下：

路徑平滑程度計(jì)算公式如下：

(2)

其中vt為直線速度，vr為轉(zhuǎn)彎速度，速度勻速不變；R為轉(zhuǎn)彎半徑；num為整條路徑上拐角的個(gè)數(shù)。α為懲罰系數(shù)；

結(jié)合公式(1-2)可看出，若路徑平滑程度越高，表示懲罰越大，使得目標(biāo)函數(shù)f增大。根據(jù)遺傳算法輪盤賭機(jī)制，易拋棄f值較大路徑，從而防止算法得到轉(zhuǎn)彎次數(shù)過多的路徑。

1.3.2 擁堵系數(shù)

由于運(yùn)行過程中可能發(fā)生多AGV擁堵或者碰撞的情況，通過定義擁堵系數(shù)，對(duì)擁堵程度較高的路徑懲罰，避開較擁堵路段。其中擁堵系數(shù)是表達(dá)T時(shí)段內(nèi)，該節(jié)點(diǎn)經(jīng)過的次數(shù)對(duì)于總節(jié)點(diǎn)數(shù)的比重。擁堵系數(shù)計(jì)算流程圖如圖3。

圖3 擁堵系數(shù)計(jì)算流程圖

計(jì)算公式如下：

(3)

(4)

n為節(jié)點(diǎn)號(hào)；k為已使用的節(jié)點(diǎn)號(hào)；HK表示時(shí)間周期T內(nèi)k節(jié)點(diǎn)使用頻率；集合M表示節(jié)點(diǎn)k出現(xiàn)的次數(shù)；集合A為當(dāng)前節(jié)點(diǎn)AGV出現(xiàn)的次數(shù)；MAX為小車總數(shù)。Pk表示路段k的擁堵系數(shù)。

結(jié)合公式(1)、(4)可看出，若擁堵系數(shù)越大，表示懲罰程度越大，導(dǎo)致目標(biāo)函數(shù)f增大。

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

利用軟件VS2015和C#語言對(duì)圖1所示的地圖環(huán)境進(jìn)行路徑規(guī)劃測(cè)試，運(yùn)行速度：vt=0.5m/s，vr=0.2m/s；小車數(shù)量：4輛；為增加合理性對(duì)比驗(yàn)證，分別對(duì)傳統(tǒng)遺傳算法、Dijkstra、蟻群算法和本文改進(jìn)遺傳算法進(jìn)行多次實(shí)驗(yàn)。

2.1 遺傳算法和改進(jìn)遺傳算法的對(duì)比

基本遺傳算法中，選擇方式為輪盤賭選擇，使用二交換啟發(fā)交叉算子，適應(yīng)度只考慮路徑長度。終止條件為迭代次數(shù)500次；耗時(shí)：242.5813；路徑長度：147.9752；

利用三交換啟發(fā)算子改進(jìn)的遺傳算法中，選擇方式為輪盤賭選擇，使用三交換啟發(fā)交叉算子，適應(yīng)度考慮路徑長度。終止條件為迭代次數(shù)500次；耗時(shí)：126.7127；路徑長度：120.9981；

利用三交換啟發(fā)算子，并引入路徑平滑程度和動(dòng)態(tài)擁堵系數(shù)改進(jìn)的遺傳算法中，選擇方式為輪盤賭選擇，使用三交換啟發(fā)交叉算子，適應(yīng)度考慮路徑長度，路徑平滑程度，動(dòng)態(tài)擁堵系數(shù)。終止條件為迭代次數(shù)500次；耗時(shí)：116.7127；路徑長度：118.9981；

在不同的初始化種群條件下進(jìn)行多次仿真，通過分析遺傳算法收斂曲線，最終得到如圖4、5所示的結(jié)果。

從圖4可以看出利用三交換啟發(fā)算子和適應(yīng)度優(yōu)化的遺傳算法和傳統(tǒng)的遺傳算法對(duì)比，迭代次數(shù)少，且加快了收斂速度；

圖4 對(duì)比收斂曲線

原因在于傳統(tǒng)遺傳算法受自身的交叉變異機(jī)制，很容易造成種群差異性小，且相對(duì)于其他群智能算法收斂速度較慢。再加上使用輪盤賭的方法，有極高的概率破壞優(yōu)良個(gè)體，使算法易陷入局部最優(yōu)。而改進(jìn)的遺傳算法采用三交叉方式提高了子代多樣性，降低了輪盤賭的不良影響。從而使算法能較快收斂且不易“早熟”。

在僅改進(jìn)交叉算子和同時(shí)優(yōu)化適應(yīng)度和交叉算子的對(duì)比中，如圖5可以看出，同時(shí)優(yōu)化適應(yīng)度和交叉算子的曲線能較快收斂。原因是采用三交叉算法雖然能使種群差異性提高，但同時(shí)增加了較差子代的概率。而且傳統(tǒng)算法的適應(yīng)度設(shè)計(jì)過于簡單，對(duì)于較差子代也能擁有很高的適應(yīng)度，從而使算法不能較快收斂。通過對(duì)適應(yīng)度的優(yōu)化可以融入更多的信息，加強(qiáng)適應(yīng)度函數(shù)的判斷能力，加快算法收斂。

圖5 對(duì)比收斂曲線

2.2 蟻群算法和改進(jìn)遺傳算法的對(duì)比

將傳統(tǒng)蟻群算法與改進(jìn)的遺傳算法進(jìn)行比較，實(shí)驗(yàn)結(jié)果如圖6所示。從圖中可以明顯看出，雖然蟻群

圖6 對(duì)比收斂曲線

算法能更快地找到最優(yōu)解，有較好的收斂性。但蟻群算法具有正反饋的特點(diǎn)，初始時(shí)刻環(huán)境中的信息素完全相同，算法幾乎按隨機(jī)方式完成解的構(gòu)建，這些解必然會(huì)存在優(yōu)劣之分，且容易陷入局部最優(yōu)。而在迭代數(shù)20～60之間，改進(jìn)遺傳算法曲線發(fā)生波動(dòng)，證明此時(shí)種族差異性大，跳出局部最優(yōu)解的可能性增大。

2.3 多AGV路徑規(guī)劃比較

將Dijkstra算法、蟻群算法、傳統(tǒng)的遺傳算法和改進(jìn)的遺傳算法的搜索結(jié)果進(jìn)行對(duì)比，并加入路徑平滑和擁堵系數(shù)，測(cè)試在多AGV和考慮道路狀況的情況下三種算法的計(jì)算效率。

通過表1算法仿真結(jié)果對(duì)比，改進(jìn)的遺傳算法所規(guī)劃的路徑長度更短，耗時(shí)更少。而且對(duì)于路徑平滑程度的考慮，改進(jìn)的遺傳算法選擇到了最優(yōu)路徑，而Dijkstra和傳統(tǒng)遺傳算法并未選擇到平滑程度最高的路線，即轉(zhuǎn)彎次數(shù)最少。對(duì)于蟻群算法，雖然耗時(shí)很短，但很容易陷入局部最優(yōu)解。

表1 算法仿真結(jié)果對(duì)比

3 結(jié)語

針對(duì)遺傳算法在規(guī)劃AGV路徑時(shí)，存在易陷入局部最優(yōu)，收斂速度慢的問題，將路徑的長度，路徑平滑程度，擁堵系數(shù)，作為評(píng)價(jià)指標(biāo)對(duì)適應(yīng)度函數(shù)進(jìn)行改進(jìn)；采用三交叉啟發(fā)式算子代替?zhèn)鹘y(tǒng)的二交叉模式，使子類個(gè)體獲得更多的父類信息。根據(jù)仿真結(jié)果證明，改進(jìn)的遺傳算法和傳統(tǒng)遺傳算法相比具有全局搜索能力強(qiáng)、收斂性能好的優(yōu)點(diǎn)；與其他路徑規(guī)劃算法相比，能獲得更優(yōu)秀的解。