扈先勤 李巍巍

DOI：10.16660/j.cnki.1674-098X.2016.18.097

摘 要：使用有向圖對(duì)AGV路徑進(jìn)行建模，在求解最優(yōu)路徑問(wèn)題上采用了遺傳算法和相關(guān)的遺傳算子及終止條件。根據(jù)遺傳算法的進(jìn)行過(guò)程，首先對(duì)AGV路徑進(jìn)行建模、編碼和確定適應(yīng)度函數(shù)，其次設(shè)計(jì)選擇、交叉及變異算子和遺傳算法的終止條件。其中對(duì)不同的長(zhǎng)度染色體采用禁止交叉策略，以便更好地適應(yīng)AGV復(fù)雜的工作路徑。

關(guān)鍵詞：AGV 有向圖 路徑規(guī)劃 遺傳算法

中圖分類(lèi)號(hào)：TP21/27 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1674-098X（2016）06（c）-0097-02

AGV（自動(dòng)導(dǎo)引小車(chē)）是現(xiàn)代物流系統(tǒng)中的關(guān)鍵設(shè)備之一。AGV路徑優(yōu)化問(wèn)題，就是尋找一條從起點(diǎn)到終點(diǎn)能夠防止AGV之間無(wú)碰撞的最短路徑。傳統(tǒng)方法是將路徑考慮成一系列的路徑點(diǎn)，進(jìn)行規(guī)劃并行實(shí)現(xiàn)，這種方法雖然在實(shí)時(shí)性方面有很大的優(yōu)勢(shì)，但對(duì)于全局最優(yōu)解的尋找卻無(wú)能為力。因此，可引入遺傳算法來(lái)幫助尋找全局最優(yōu)解。

1 遺傳算法的介紹

進(jìn)化計(jì)算是計(jì)算機(jī)里模擬進(jìn)化，它包括遺傳算法、進(jìn)化策略和遺傳編程，其中遺傳算法是使用比較普遍的一種方法。

遺傳算法（GA）是一類(lèi)基于生物進(jìn)化的隨機(jī)搜索算法，實(shí)現(xiàn)主要步驟：進(jìn)化代數(shù)計(jì)數(shù)器初始化：t→0；隨機(jī)產(chǎn)生初始群體P（t）；評(píng)價(jià)群體P（t）的適應(yīng)度；個(gè)體交叉運(yùn)算；個(gè)體變異運(yùn)算；評(píng)價(jià)群體P”（t）的適應(yīng)度；對(duì)群體P（t）進(jìn)行選擇運(yùn)算；終止條件判斷。不滿足t+1→t轉(zhuǎn)到第4步，繼續(xù)進(jìn)化過(guò)程，滿足輸出當(dāng)前最優(yōu)個(gè)體，算法結(jié)束。

2 AGV環(huán)境建模

在建模過(guò)程中，假設(shè)AGV是工作在二維空間中的運(yùn)動(dòng)，用折線表示AGV可通過(guò)的所有路徑，AGV抽象為質(zhì)點(diǎn)；AGV在每個(gè)節(jié)點(diǎn)的停留時(shí)間長(zhǎng)都一定且相等。對(duì)AGV的路徑簡(jiǎn)化，將相對(duì)應(yīng)的節(jié)點(diǎn)及路徑可得到相對(duì)應(yīng)的有向圖，如圖1所示。

3 AGV路徑中遺傳算法參數(shù)的設(shè)計(jì)與優(yōu)化

采用遺傳算法對(duì)AGV路徑規(guī)劃，要求設(shè)置部分遺傳算法的參數(shù)和相關(guān)技術(shù)，有解碼與編碼、適應(yīng)度函數(shù)、復(fù)制、交叉、變異算子以及控制參數(shù)的設(shè)定。

對(duì)上述路徑簡(jiǎn)化有向圖進(jìn)行順序編碼，如圖2所示，圖中的數(shù)字是編碼的基因。圖中的線段長(zhǎng)度不代表實(shí)際長(zhǎng)度。

從圖中可以看出路徑染色體的基因編碼及遺傳算法的種群初始化，如2359、1369、136789等。鑒于AGV的路徑規(guī)劃中，適應(yīng)度函數(shù)采用距離公式，同時(shí)規(guī)定路徑中染色體基因中，前一個(gè)基因編號(hào)必須比后面的一個(gè)基因編號(hào)小。

對(duì)初始路徑進(jìn)行復(fù)制操作首先確定各個(gè)路徑的適應(yīng)度函數(shù)值，計(jì)算各個(gè)路徑被選擇的概率，計(jì)算公式如下：

（1）

式子中的Fi為第i路徑的適應(yīng)度值，Pi為正比例選擇概率，N為子代和父代的總體個(gè)數(shù)。在使用遺傳算法對(duì)AGV路徑進(jìn)行選擇時(shí)，分析Pi值的大小，選擇Pi越大的個(gè)體進(jìn)行后續(xù)的交叉和變異。

由于之前單模式路徑問(wèn)題中的遺傳算子針對(duì)的路徑編碼是同質(zhì)的，各個(gè)位置的基因性質(zhì)對(duì)等，可以進(jìn)行任意交叉及變異。設(shè)置對(duì)等染色體之間進(jìn)行交叉和變異計(jì)算，在各個(gè)同等基因的染色體交叉算子統(tǒng)一采用單點(diǎn)交叉策略，如圖3所示，4基因父類(lèi)（A、B）不能與5基因父類(lèi)（1，2，4，5，9）進(jìn)行交叉。

在遺傳算法中通常將變異概率設(shè)定為一個(gè)已知的數(shù)，而且值也很小，由于AGV路徑比較簡(jiǎn)單，因此變異概率選擇0.01或者更小，使整個(gè)遺傳算法體系的染色體處于正常狀態(tài)，同時(shí)變異的方法選擇位置變異。

遺傳算法的終止條件：（1）判別遺傳算法進(jìn)化代數(shù)是否達(dá)到預(yù)定的最大代數(shù)；（2）判別染色體的適應(yīng)度函數(shù)值是否已趨于穩(wěn)定。整個(gè)遺傳算法的流程圖如圖4所示。

4 結(jié)語(yǔ)

對(duì)AGV的工作空間采用有向圖進(jìn)行建模，在一定程度上簡(jiǎn)化了AGV路徑規(guī)劃的難度，同時(shí)將遺傳算法運(yùn)用到AGV路徑規(guī)劃中，可以適應(yīng)更加復(fù)雜多變的AGV工作環(huán)境。分別對(duì)不同長(zhǎng)度路徑中交叉與變異算子進(jìn)行設(shè)計(jì)，使遺傳算法能夠更加準(zhǔn)確高效地把握進(jìn)化方向。

參考文獻(xiàn)

[1] 張曉萍.現(xiàn)代生產(chǎn)物流及仿真（修訂版）[M].北京：清華大學(xué)出版社，2011：105-235.

[2] 賈建成.AGV視覺(jué)導(dǎo)引及其路徑規(guī)劃策略研究[D].秦皇島：燕山大學(xué)，2010.

[3] 蒲亮亮，張小棟.光導(dǎo)AGV智能循跡測(cè)控系統(tǒng)的建與仿真[J].測(cè)控技術(shù)，2011（5）：85-89.

[4] 周明，孫樹(shù)棟.遺傳算法原理及應(yīng)用[M].北京：國(guó)防工業(yè)出版社，2014.