遺傳算法在AGV的路徑規劃中的應用

扈先勤 李巍巍

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

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

關鍵詞：AGV 有向圖 路徑規劃 遺傳算法

中圖分類號：TP21/27 文獻標識碼：A 文章編號：1674-098X（2016）06（c）-0097-02

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

1 遺傳算法的介紹

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

遺傳算法（GA）是一類基于生物進化的隨機搜索算法，實現主要步驟：進化代數計數器初始化：t→0；隨機產生初始群體P（t）；評價群體P（t）的適應度；個體交叉運算；個體變異運算；評價群體P”（t）的適應度；對群體P（t）進行選擇運算；終止條件判斷。不滿足t+1→t轉到第4步，繼續進化過程，滿足輸出當前最優個體，算法結束。

2 AGV環境建模

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

3 AGV路徑中遺傳算法參數的設計與優化

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

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

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

對初始路徑進行復制操作首先確定各個路徑的適應度函數值，計算各個路徑被選擇的概率，計算公式如下：

（1）

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

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

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

遺傳算法的終止條件：（1）判別遺傳算法進化代數是否達到預定的最大代數；（2）判別染色體的適應度函數值是否已趨于穩定。整個遺傳算法的流程圖如圖4所示。

4 結語

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

參考文獻

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

[2] 賈建成.AGV視覺導引及其路徑規劃策略研究[D].秦皇島：燕山大學，2010.

[3] 蒲亮亮，張小棟.光導AGV智能循跡測控系統的建與仿真[J].測控技術，2011（5）：85-89.

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