遺傳算法在AGV的路徑規(guī)劃中的應(yīng)用

扈先勤 李巍巍

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

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

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

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

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

1 遺傳算法的介紹

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

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

2 AGV環(huán)境建模

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

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

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

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

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

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

（1）

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

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

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

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

4 結(jié)語

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

參考文獻(xiàn)

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

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

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

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