苑光明 翟云飛 丁承君 張鵬

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

[關(guān)鍵詞]自動導(dǎo)航車；路徑規(guī)劃；改進遺傳算法；轉(zhuǎn)彎次數(shù)

[中圖分類號]TP 273[文獻標(biāo)志碼]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引言

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

1問題描述

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

在生產(chǎn)車間AGV運行區(qū)域中，可以分為裝卸貨物區(qū)域、工位區(qū)和行走線路。圖1是車間的AGV運行環(huán)境地圖

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

789101819203132是其中一條最短路徑，但路徑轉(zhuǎn)彎次數(shù)多，降低了AGV的運行效率，傳統(tǒng)的遺傳算法無法在多個最短路徑中得到轉(zhuǎn)彎次數(shù)更少的路徑。

2改進的遺傳算法

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

21遺傳算法路徑規(guī)劃模型建立

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

22基于分層方法的選擇算子設(shè)計

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

Fa>Fb>Fc>Fd。（1）

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

23交叉算子和變異算子設(shè)計

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

在算法進化過程中，交叉和變異概率影響著算法的局部和全局搜索能力，固定的交叉概率和變異概率無法保證算法較快地收斂并搜索到全局最優(yōu)解[10]。本文根據(jù)算法進化過程中個體適應(yīng)度的變化，動態(tài)調(diào)整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分別表示種群中最大適應(yīng)度值和最小適應(yīng)度值，F(xiàn)c表示兩個要交叉?zhèn)€體中較大的適應(yīng)度值，F(xiàn)m表示要變異個體的適應(yīng)度值。

24適應(yīng)度函數(shù)設(shè)計

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

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

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

3算法仿真及分析

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

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

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

4結(jié)束語

針對AGV在自動化生產(chǎn)線中原有路徑規(guī)劃算法存在路徑轉(zhuǎn)彎次數(shù)多，不利于AGV自動控制的問題，本文將規(guī)劃路徑的拐