基于改進遺傳算法的AGV路徑規劃

苑光明 翟云飛 丁承君 張鵬

[摘要]針對AGV在自動化生產線中原有路徑規劃算法存在路徑拐彎次數多，不利于AGV自動控制的問題，提出了一種改進遺傳算法。為提高AGV運行的效率，該算法引入了拐彎因素。針對在路徑規劃中傳統遺傳算法收斂速度慢的問題，結合分層方法，改進傳統的精英保留策略。在算法進化過程中，根據個體適應度的變化動態調整交叉概率和變異概率，加快算法的收斂速度。Matlab仿真實驗結果顯示：改進遺傳算法能夠規劃出一條更合理的路徑，相比較傳統方法減少了轉彎次數，改善了搜索路徑質量，表明該算法可以滿足自動化生產線AGV路徑規劃的要求。

[關鍵詞]自動導航車；路徑規劃；改進遺傳算法；轉彎次數

[中圖分類號]TP 273[文獻標志碼]A[文章編號]10050310（2018）01006505

AGV Path Planning Based on Improved Genetic Algorithm

Yuan Guangming， Zhai Yunfei， Ding Chengjun， Zhang Peng

（Institute of Mechanical Engineering，Hebei University of Technology，

Tianjin 300132，China）

Abstract： In order to solve the problem that the path planning algorithm in AGV automation production line has the number of turns， which is not conducive to the automatic control of AGV， an improved genetic algorithm is proposed. In order to improve the efficiency of AGV automatic control， the algorithm introduces the turning factor. Aiming at the problem of slow convergence of the path planning in the traditional genetic algorithm， the traditional elitism strategy is improved with hierarchical method. In the process of evolutionary algorithm， the crossover probability and mutation probability are dynamically adjusted according to the change of individual fitness， and the convergence speed of the algorithm is accelerated. Matlab simulation results show that the improved genetic algorithm can plan a more reasonable path， and the number of turns is reduced compared with the traditional methods， and the quality of the search path has been improved， which show that the algorithm can meet the requirements of automated production line AGV path planning.

Keywords：

Automated Guided Vehicle（AGV）； Path planning； Improved genetic algorithm； Turn times

0引言

隨著自動化技術的不斷發展，目前國內大部分制造業，尤其是在汽車制造、制藥等勞動力密集的制造企業，傳統的物料運輸方式效率低，柔性較差，且需要的人工量大，對于企業來說難以達到其高效生產的要求。為了克服這種現狀，相關領域積極引入AGV（Automated Guided Vehicle）自動導航車，達到物料運輸的目的[12]。AGV在實際應用中仍然有一些需要解決的問題，路徑規劃是其中比較重要的一個問題，當AGV收到調度系統下達的任務后，會自動規劃出1條從當前位置到達目標位置的路徑，該路徑需要優化的方面有行程時間、行程距離、所需能耗等[3]。AGV路徑規劃可以抽象建模成多目標優化問題，多目標通過懲罰函數使其成為單目標優化問題[4]。智能算法相比較傳統算法具有全局搜索能力強、搜索效率高、易于實施等優點，已經被應用在很多復雜問題的求解中[5]。遺傳算法是模仿自然界生物進化機制發展起來的隨機全局搜索優化方法，具有算法效率高、魯棒性強、可實現并行搜索等特點[6]，被廣泛用于解決人工智能、路徑規劃等領域的問題。

1問題描述

在自動化生產線的AGV路徑規劃中，從當前位置到目標位置需要找到一條最優路徑。大部分路徑規劃的最優路徑為最短路徑，也有部分路徑規劃考慮到路徑轉彎次數對 AGV運行的影響，并在傳統算法基礎上引入了轉彎因素[7]。但傳統算法搜索效率低，不能保證搜索到全局最優解。本文所研究的最優路徑具有路徑短、轉彎次數少等特點。

在生產車間AGV運行區域中，可以分為裝卸貨物區域、工位區和行走線路。圖1是車間的AGV運行環境地圖

（長度單位為m），本文將其簡化為無向的連接圖，該連接圖由工作站點、線路轉彎節點及行走線路組成。例如AGV收到任務從站點7到站點32，此時的最短路徑不止1條。

789101819203132是其中一條最短路徑，但路徑轉彎次數多，降低了AGV的運行效率，傳統的遺傳算法無法在多個最短路徑中得到轉彎次數更少的路徑。

2改進的遺傳算法

本文應用改進遺傳算法求解最優路徑，適應度函數包括路徑長度和懲罰函數。將分層算法應用到精英策略中，改進的精英策略確保種群多樣性的同時，優良個體能遺傳到下一代。種群的選擇操作采用改進的精英策略和輪盤賭規則[8]，根據適應度變化動態調整交叉概率和變異概率的取值，圖2是改進的遺傳算法流程圖。

21遺傳算法路徑規劃模型建立

遺傳算法中的每1條染色體，對應著遺傳算法的1個解決方案，在AGV路徑規劃中，基因是由起始點、目標點和AGV經過的若干個點組成。本文采用實數對基因進行編碼，相對于二進制編碼在求解過程中具有效率高、占用存儲空間少及編碼更加靈活等優點。如圖3所示，X1 Y1起點、Xn Yn目標點和n-2個中間點構成了1條攜帶從起點到目標點AGV路徑信息的染色體。

22基于分層方法的選擇算子設計

為了選出優秀的個體，使優良的基因得以延續，要采用精英選擇策略。傳統的精英選擇策略是將適應度高的個體（一般是適應度排名為前10%的個體）直接復制到下一代，由于這種方法只是保留了適應度最高的一小部分個體，隨著迭代次數的增加，種群多樣性會快速降低，容易得到局部最優解而非全局最優解[9]。本文將種群以適應度函數為標準分成4個層次a、b、c、d，處在4個層次中的個體其適應度滿足（1）式，Fi是個體的適應度值。

Fa>Fb>Fc>Fd。（1）

其中a、b、c這3個層次的個體直接復制到下一代，保證種群基因的多樣性，原則上a層次個體的數量少于b層次的，b層次個體數量少于c層次的。本文初始種群數50，分別取a、b、c層次個體數量為1、2、3個，種群中剩下的個體為d層次。每次迭代更新種群后，先按分層方法操作a、b、c這3個層次個體，再按輪盤賭規則選擇個體復制到下一代。

23交叉算子和變異算子設計

交叉操作是對自然界的基因重組過程進行模擬，是遺傳算法產生新個體的主要方法。本文采用部分映射方式進行染色體的交叉操作，生成兩個隨機數m、n，將x、y染色體位于m和n之間的基因片段互換。變異操作模擬自然界基因突變的過程，迭代過程中染色體上的基因會隨機發生突變來產生新個體。

在算法進化過程中，交叉和變異概率影響著算法的局部和全局搜索能力，固定的交叉概率和變異概率無法保證算法較快地收斂并搜索到全局最優解[10]。本文根據算法進化過程中個體適應度的變化，動態調整Pc和Pm，交叉和變異概率公式如（2）和（3）：

Pc=Pcmax-（Pcmax-Pcmin）（Fc-Fmin）Fmax-Fmin，（2）

Pm=Pmmax-（Pmmax-Pmmin）（Fm-Fmin）Fmax-Fmin。（3）

式中：Pcmax和Pmmax分別表示交叉概率和變異概率的最大值；Pcmin和Pmmin分別表示交叉概率和變異概率的最小值；Fmax和Fmin分別表示種群中最大適應度值和最小適應度值，Fc表示兩個要交叉個體中較大的適應度值，Fm表示要變異個體的適應度值。

24適應度函數設計

在遺傳算法中，適應度函數是評判種群中個體存活能力的標準，它是依據目標函數確定的。適應度函數是非負的并且和目標函數不完全對應，在問題求解中適應度函數的值越大越好。在AGV路徑規劃中，適應度函數的首要指標是路徑長度，除此之外還有路徑能耗等指標[11]。本文的AGV路徑規劃目標是路徑最短和更少的轉彎次數，因此引入了懲罰系數α，在這里適應度函數值和目標函數值呈負相關關系，一條路徑轉彎次數越多其目標函數值越大，適應度值越小，在進行選擇操作時個體被保留下來的概率越小。目標函數如式（4）：

f=n-1i=1d（pi，pi+1）+αm（v-vt）π2rvt。（4）

式中：f為目標函數；d（pi，pi+1）表示基因點pi和pi+1連接形成線段的距離；α為懲罰系數，一般取α≥1；m為路徑染色體上全部節點連接起來時的轉彎次數，m=0時路徑為直線；v是AGV直線行走時的速度，vt是AGV轉彎時的速度，假設v和vt大小恒定，vt小于v；r是AGV轉彎半徑。

3算法仿真及分析

在Matlab 2013環境下對算法進行仿真，參數設置如下：α=2，v=15，r=1。分別采用傳統遺傳算法和本文改進的遺傳算法，去搜索站點7到站點32的最優路徑，得到遺傳算法的收斂曲線，在不同的初始化種群條件下進行多次仿真，絕大多數能得到如圖4所示的結果，可以看出改進的遺傳算法相比于傳統的遺傳算法迭代次數少，收斂速度較快，提高了搜索效率；在極少數情況下出現了如圖5所示的結果，可以看出傳統遺傳算法陷入了局部最優，改進的遺傳算法具有更好的全局搜索能力。

將A*算法、傳統的遺傳算法和改進的遺傳算法的搜索結果進行對比，如表1所示，可以看出3種算法都能搜索到最短路徑，但從起始點到目標點有多條最短路徑時，3種算法搜索出來的路徑會有不同。

為了進一步驗證改進遺傳算法的有效性，去搜索站點27到站點13的最優路徑，得到路徑272823178910111213，轉彎次數為2次，成功地從長度相同最大轉彎次數為5次的最短路徑集合中找到了轉彎次數最少的路徑，算法收斂曲線如圖6所示，可以看出改進遺傳算法的收斂速度更快。改進的遺傳算法能夠高效地搜索到轉彎次數更少的路徑，相比于其他路徑更有利于AGV的自動控制，具有明顯的優勢。

4結束語

針對AGV在自動化生產線中原有路徑規劃算法存在路徑轉彎次數多，不利于AGV自動控制的問題，本文將規劃路徑的拐