基于遺傳算法的工廠AGV路徑優(yōu)化研究

黨宏社 孫心妍

摘要：針對工廠AGV行駛路徑復(fù)雜、應(yīng)用局限性等問題，vRAGV配送物料行駛路徑最短為目標(biāo)，采用遺傳算法進(jìn)行AGV路徑規(guī)劃，并加入物料類型選擇的循環(huán)套，通過多次實(shí)驗(yàn)確定最合理的控制參數(shù)，從而產(chǎn)生AGV運(yùn)輸多種類型物料的最優(yōu)路徑結(jié)果。使用Maflab軟件對算法進(jìn)行仿真，結(jié)果表明：該算法是有效的，能夠直接實(shí)現(xiàn)ACV在輸多種類型物料時(shí)所產(chǎn)生的不同種路徑的優(yōu)化。

關(guān)鍵詞：自動(dòng)導(dǎo)引車;路徑規(guī)劃;遺傳算法

0引言

隨著社會(huì)生產(chǎn)技術(shù)的發(fā)展和自動(dòng)化程度的提高，很多工廠為了提升運(yùn)輸工作效率，引入了自動(dòng)導(dǎo)引小車AGV（Automatic Guided Vehicle）進(jìn)行物流運(yùn)輸。據(jù)相關(guān)資料統(tǒng)計(jì)，在制造業(yè)中不足5%的時(shí)間用于加工裝配，而超過95%的時(shí)間用于物流配送，因此物料的及時(shí)準(zhǔn)確供應(yīng)直接關(guān)系到生產(chǎn)線的流暢性。節(jié)約車間生產(chǎn)成本，減少物料運(yùn)輸時(shí)間，提升單臺(tái)AGV搬運(yùn)效率，一直以來AGV的路徑規(guī)劃問題，即尋找AGV的最優(yōu)路徑是工廠所關(guān)注的焦點(diǎn)。

目前國內(nèi)外很多學(xué)者都對于AGV的路徑規(guī)劃問題做了相應(yīng)的研究。遺傳算法是模仿自然界生物進(jìn)化機(jī)制發(fā)展起來的隨機(jī)全局搜索優(yōu)化方法，具有算法效率高、魯棒性強(qiáng)、可實(shí)現(xiàn)并行搜索等特點(diǎn)，被廣泛用于解決路徑規(guī)劃等領(lǐng)域的問題。G.Jeon和William等人用混合遺傳算法求解車輛路徑規(guī)劃問題：李青欣進(jìn)行了AGV路徑規(guī)劃的遺傳算法研究，根據(jù)運(yùn)行環(huán)境信息復(fù)雜度和數(shù)量的不同分別分析了幾種不同類型的路徑規(guī)劃。

當(dāng)前國內(nèi)外學(xué)者在AGV的路徑規(guī)劃問題上取得了諸多成果，但是實(shí)際的工廠生產(chǎn)情況多變，機(jī)器所需的物料并不相同，因而AGV的運(yùn)輸路徑也有差異。多類型物料的運(yùn)輸與AGV路徑的優(yōu)化相結(jié)合的研究目前并不多見也不夠完善。

針對遺傳算法解決路徑規(guī)劃問題時(shí)只能完成單任務(wù)、實(shí)現(xiàn)單次運(yùn)輸路徑規(guī)劃的不足，為提升規(guī)劃效率，擴(kuò)大應(yīng)用面，本文在路徑規(guī)劃以前，加入對于物料的選擇情況，構(gòu)建路徑規(guī)劃數(shù)學(xué)模型，設(shè)計(jì)遺傳算法并進(jìn)行數(shù)據(jù)仿真，一次得到AGV運(yùn)輸多種物料的行駛路徑。仿真結(jié)果表明本文提出的基于遺傳算法的AGV路徑規(guī)劃方案對于解決此類運(yùn)輸問題是有效的。

1工廠AGV路徑規(guī)劃的模型

1.1問題描述

某工廠的AGV運(yùn)輸物料模型一般可以描述為：工廠的生產(chǎn)車間共有20臺(tái)工作機(jī)器，需要5種物料，當(dāng)AGV運(yùn)輸不同物料時(shí)，途經(jīng)的機(jī)器坐標(biāo)和數(shù)量不同，行駛路徑有很多種。本文將研究如何運(yùn)用遺傳算法高效直接的產(chǎn)生AGV運(yùn)輸多種物料時(shí)的不同路徑優(yōu)化結(jié)果。鑒于AGV運(yùn)輸物料的過程比較復(fù)雜，且為了便于本文的模型建立及研究，現(xiàn)做如下規(guī)定和假設(shè)：

1）單臺(tái)AGV只可運(yùn)輸一種物料：

2）AGV初始位置均在物料配送中心：

3）AGV行駛路徑是指從物料配送中心坐標(biāo)為起點(diǎn)，途經(jīng)所有需要此種類型物料的機(jī)器，最后回到起點(diǎn);

2遺傳算法的流程

本文采用遺傳算法進(jìn)行路徑的優(yōu)化。算法的具體流程圖如下圖1所示：

采用1-N的數(shù)字隨機(jī)排列的方式進(jìn)行編碼，可以省去解碼環(huán)節(jié)，提高了算法的運(yùn)行效率，其中一條染色體就代表AGV在車間內(nèi)運(yùn)輸物料的一種行駛路徑。

3.2初始群體的設(shè)定

本文中考慮一般情況下，在編碼空間內(nèi)均勻采樣，對于Ⅳ臺(tái)工作機(jī)器，隨機(jī)生成一定數(shù)目的個(gè)體（一般為機(jī)器數(shù)量的2倍，即2N），每個(gè)個(gè)體代表AGV運(yùn)輸特定類型物料的路線。傳統(tǒng)的算法解決路徑規(guī)劃問題時(shí)，初始群體都是固定值，算法只產(chǎn)生適用一種情況的最優(yōu)路徑，本文在算法的前端加入了物料類型選擇的循環(huán)套。當(dāng)AGV運(yùn)輸A、B、C、D、E這5種不同類型的物料時(shí)，初始群體的規(guī)模也不相同，具體數(shù)值如下表所示：

選擇過程體現(xiàn)了自然界生物進(jìn)化過程中“適者生存”的思想，并且能夠確保適應(yīng)度強(qiáng)的優(yōu)良基因遺傳到下一代的個(gè)體。

3.4.2交叉操作

本文中，假設(shè)隨機(jī)選擇兩個(gè)已經(jīng)被復(fù)制的個(gè)體分別為：A=35749，B=46285，確定交叉點(diǎn)，A=35I 749，B=46I 285，在對應(yīng)位置交換基因片段，同時(shí)保證每個(gè)個(gè)體依然是1-N的隨機(jī)排列，防止進(jìn)入局部收斂，交叉過程后則產(chǎn)生=46749，=35285兩個(gè)新個(gè)體。

3.4.3變異操作

本文中，在已經(jīng)被選擇的個(gè)體中，隨機(jī)選取1個(gè)個(gè)體，同時(shí)隨機(jī)選取個(gè)體的兩個(gè)基因進(jìn)行交換，實(shí)現(xiàn)變異操作。假設(shè)隨機(jī)選取個(gè)體A=3576289，選取該個(gè)體上的“3”“7“兩個(gè)基因進(jìn)行位置互換，可以得到新的個(gè)體=7536289。通過變異操作，可增加種群的多樣性，有效地防止了遺傳算法過早的收斂，出現(xiàn)“早熟”現(xiàn)象。

3.5控制參數(shù)的設(shè)定以及循環(huán)終止條件

遺傳算法中關(guān)鍵的參數(shù)為：交叉概率、變異概率和迭代次數(shù)C。交叉概率控制著交叉算子的應(yīng)用頻率，變異操作是保持群體多樣性的最有效手段，迭代次數(shù)決定了遺傳操作的執(zhí)行次數(shù)。為了確保參數(shù)設(shè)置的有效性和合理性，做了如下實(shí)驗(yàn)。

3.5.1交叉概率

選擇將AGV運(yùn)輸C類物料的路徑作為研究對象，遍歷機(jī)器數(shù)目為N=13，AGV行駛路徑個(gè)數(shù)也即群體規(guī)模為2N=26，迭代次數(shù)C為50次，設(shè)定變異概率，改變交叉概率的數(shù)值，每種情況實(shí)驗(yàn)15次，求出不同數(shù)值下的平均路徑長度，發(fā)現(xiàn)當(dāng)交叉概率時(shí)，平均路徑長度最短。因此，本文中遺傳算法的交叉概率取值為0.6為宜。

3.5.2變異概率

遍歷機(jī)器數(shù)目、AGV行駛路徑個(gè)數(shù)、迭代次數(shù)保持不變，設(shè)定交叉概率，改變交叉概率的數(shù)值，每種情況實(shí)驗(yàn)15次，求出不同數(shù)值下的平均路徑長度。發(fā)現(xiàn)當(dāng)變異概率時(shí)，平均路徑長度最短。因此，本文中遺傳算法的變異概率取值為0.08為宜。

3.5.3迭代次數(shù)

本文將AGV運(yùn)輸不同類型的物料時(shí)算法迭代次數(shù)設(shè)為不同的值，當(dāng)遍歷機(jī)器數(shù)目為N時(shí)，迭代次數(shù)C為4N，從而提高了算法的運(yùn)行效率。

3.5.4循環(huán)終止條件

本文迭代終止條件連續(xù)4代最優(yōu)解不發(fā)生變化則迭代停止，輸出最優(yōu)解。

4實(shí)驗(yàn)仿真與結(jié)果分析

在Matlab2016環(huán)境下運(yùn)用改進(jìn)后的遺傳算法進(jìn)行路徑的優(yōu)化，可以一次性得到AGV分別運(yùn)輸車間要求的5種物料時(shí)的優(yōu)化路徑，仿真結(jié)果如下圖3所示：