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

苑光明 翟云飛 丁承君 張鵬

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

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

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

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

1問題描述

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

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

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

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

2改進(jìn)的遺傳算法

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

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

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

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

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

Fa>Fb>Fc>Fd。（1）

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

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

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

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

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

在遺傳算法中，適應(yīng)度函數(shù)是評(píng)判種群中個(gè)體存活能力的標(biāo)準(zhǔn)，它是依據(jù)目標(biāo)函數(shù)確定的。適應(yīng)度函數(shù)是非負(fù)的并且和目標(biāo)函數(shù)不完全對(duì)應(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ù)值呈負(fù)相關(guān)關(guān)系，一條路徑轉(zhuǎn)彎次數(shù)越多其目標(biāo)函數(shù)值越大，適應(yīng)度值越小，在進(jìn)行選擇操作時(shí)個(gè)體被保留下來的概率越小。目標(biāo)函數(shù)如式（4）：

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

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

3算法仿真及分析

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

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

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

4結(jié)束語

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