基于改進遺傳算法的自動導航小車路徑規劃調度
2022-09-19 06:02:56于佳喬李巖
機床與液壓 2022年5期
于佳喬，李巖
(長春工業大學電氣與電子工程學院，吉林長春 130012)
0 前言
隨著“中國制造2025”計劃的實施，制造業的生產模式發生了巨大變化，智能制造為傳統制造業開辟了一條新的道路。在新型智慧工廠中，柔性制造系統已應用于大多數企業。柔性制造系統(Flexible Manufacturing System，FMS)是由統一的信息控制系統、物料儲運系統和數字控制加工設備組成，能適應加工對象變換的自動化機械制造系統。其中自動導航小車(Automated Guided Vehicle，AGV)在柔性生產系統的物料搬運中發揮著越來越重要的作用。隨著AGV的廣泛應用，隨之帶來的問題也不斷增加，其中路徑規劃是這一領域的重點問題。如何對AGV進行合理的規劃，以提高物料搬運效率和降低生產成本一直是企業關注的焦點。目前，國內外已有許多學者對AGV路徑規劃問題進行研究：文獻[5]中采用改進的A*算法對智能車路徑進行優化；文獻[6]中應用多種群遺傳算法對路徑規劃進行研究;文獻[7]中提出了一種自適應遺傳算法的路徑規劃方法,采用了人工勢場對種群初始化,提高了算法收斂速度；文獻[8]中應用Voronoi圖法對移動機器人進行路徑規劃；文獻[9]中提出了一種混合算法解決移動機器人全局路徑規劃問題,提高AGV路徑的質量；文獻[10]中將一種新的變異方法應用到機器人動態路徑規劃中；文獻[11]中在遺傳算法中加入轉彎角度因素對移動機器人路徑規劃進行分析；文獻[12]中提出一種新的基于排序遺傳算法的多目標最優路徑規劃；文獻[13]中提出了縱橫協同的多種群遺傳算法解決AGV調度問題；文獻[14]中采用了整數編碼和多參數編碼相結合的方式對遺傳算法進行改進，優化AGV的任務排序列表以及行走路徑。
本文作者在傳統遺傳算法基礎上對編碼規則、變異算子以及交叉算子進行改進，在AGV數量及補料工位數量不同的情況下，擬優化出任務最短路徑及排序，期望得到最優方案。
1 問題描述
在柔性生產系統中，通常存在一個集中配料區，有序存放車間生產所需所有物料資源，當有工位加工物料低于存儲安全值時，就需要AGV及時為其補充物料。在生產過程中，可能出現多個工位同時需要AGV為其補充物料的情況，這時候就需要對AGV補料的順序及路徑進行優化，使AGV在最短的時間內為所有工位完成補料任務。本文作者在此基礎上以多個AGV 同時服務于多個工位為背景，對AGV路徑規劃進行研究，擬達到降低AGV運行成本及車間生產成本的目的。
對于AGV路徑規劃問題現做出如下假設：
(1)AGV出發點(物料存儲地)固定;
(2)上下料時間恒定且固定，故忽略不計;
(3)任何任務都可以分配給任何一臺AGV;
(4)AGV容量足夠大，且無差別;
(5)同一任務只能被一臺AGV所執行。
2 數學模型
柔性生產車間AGV調度問題可描述為輛AGV服務個工位，AGV編號為:∈{1,2,3，…，}，工位編號為:∈{1,2,3,…,}，AGV任務編號為:∈{1,2,3,…,}。染色體用表示,現根據以上約束條件及假設，建立如下數學模型：
(1)
(2)
0=0 ?,
(3)
=1 ?
(4)
其中：式(1)表示總路徑長度為各AGV路徑長度總和；式(2)表示每輛AGV的每個任務只為一個工位進行補料；式(3)表示每輛AGV執行任務前統一在初始位置集合；式(4)表示每輛AGV可裝載量足夠且固定。
3 改進的遺傳算法
遺傳算法(Genetic Algorithm)是模擬達爾文生物進化論的自然選擇和遺傳學機制的生物進化過程的計算模型，是一種通過模擬自然進化過程搜索最優解的方法。傳統的遺傳算法雖能尋找到最優解，但是在求解速度以及局部最優解問題的處理上并不理想。本文作者在傳統的遺傳算法基礎上對編碼、解碼、變異算子及交叉算子進行改進，應用改進的遺傳算法求解問題，以達到準確、快速、高效解決問題的目的。
3.1 編碼設計
傳統的遺傳算法中編碼方法有二進制編碼、浮點數編碼、實數編碼。針對文中所研究的內容，提出一種雙層實數編碼方式：將染色體分為前后兩部分：前一部分代表工位編號(工位編號先后即AGV補料順序先后)；后一部分為AGV編號。例如：一條染色體為“2354113213”，其含義如圖1所示。
圖1 染色體編碼
基于以上染色體編碼方式其讀取方式為：第一輛AGV補料任務地點為工位1、工位4；第二輛AGV補料任務地點為工位3；第三輛AGV補料地點為工位2、工位5。
染色體編碼后按上述讀取規則對AGV行走路徑進行解碼，通過讀取AGV行走路徑及搬運順序記錄染色體目標值。個體的適應度函數()定義如下：
式中：()為第輛AGV行走總路徑之和。將所有AGV行走路徑之和加在一起組成個體的適應度函數。根據上述定義可知，個體適應度值越大，目標值越小。當目標值最小時，得出最優解。
3.2 初始種群的生成
由于文中在染色體生成時使用雙層編碼方式，同時滿足兩個變量要求：工位數和AGV數，所以傳統的種群生成方式不適用。文中初始種群的生成具體步驟如下：
(1)根據工位的數量確定第一層工位編碼范圍[1,…,]；
(2)根據可調用AGV數量確定第二層AGV編碼范圍[1,…,]；
(3)將第一層與第二層組成一條完整的染色體序列；
(4)重復步驟3、4，生成一組含有多個染色體的初始種群。
3.3 變異算子
變異操作是遺傳算法中一個重要的過程，變異算子的主要作用是改善系統的全局搜索能力，維持種群的多樣性。過小的變異率會導致新生成的種群產生新個體的能力較弱，抑制早熟現象的能力變差；過大的變異率會使系統隨機性更大，增加不必要的計算。本文作者在綜合考慮其影響因素后，提出一種變異方法：雙層編碼多次變異。多次的變異過程不僅增大了解的空間，而且維持了種群的多樣性，降低了算法陷入局部最優解的概率。具體步驟如圖2所示。
圖2 變異過程
改進的變異操作在第一層編碼的兩點變異后加入了逆轉變異以及滑動變異來增大解的空間，增強算法的搜索能力，可以更好地找到最優解。逆轉變異及滑動變異具體原理如圖3—圖4所示(由于只對第一層編碼有效，示例僅編寫第一層編碼)：
(1)逆轉變異。在變異前產生隨機數<，例如=4，即染色體前4位進行逆轉變異，由原始“53214”變為“12354”，如圖3所示。
圖3 逆轉變異
(2)滑動變異。首先將原始染色體復制，組成一條新的染色體=[,]，長度為二倍；其次生成隨機數<，取的第位到第+-1位為新染色體,如圖4所示。
圖4 滑動變異
3.4 交叉操作
交叉算子是遺傳算法中控制全局搜索的一種算子，算子大小的調試對整個算法有重要影響：較大的交叉算子會增強算法開辟新的搜索區域的能力，但是過大的算子會增加不必要的計算成本；當交叉算子過小時，系統會陷入遲鈍狀態，在搜索新個體時速度變慢，導致運行停滯，增大運行時間。基于雙層編碼方式對染色體進行雙層兩點交叉，即對染色體第一、二層同時進行兩點交叉。首先將所有染色體分為兩兩一組，組成若干個染色體對，為每個染色體對分配隨機數，當
圖5 染色體修補過程
圖6 交叉過程
3.5 迭代終止條件
迭代終止條件在遺傳算法中控制著算法運行時間長短：過小的終止條件會讓算法在未尋找到最優值時停止，而沒有完成任務；過大則會增加算法不必要的過程，增加程序運行成本。在遺傳算法中終止迭代有多種方法：(1)人為設置種群在迭代多次后強行終止，這種情況一般設置迭代次數為20～500之間；(2)當種群在多次迭代后目標值沒有發生變化時停止迭代；(3)當迭代后的結果小于人為設定的值時，程序停止運行。文中選用第一種：當迭代次數為20～500代時，終止程序。這種方法會讓程序變得更加可控，在不斷觀察運行結果時調整參數，以達到最優的效果。
4 仿真實驗與分析
環境地圖中最多有20個工位，將各工位置于-坐標系中并計算其坐標，結果如圖7所示。
圖7 工位點坐標
以此坐標作為地圖，應用改進的遺傳算法分別對相同工位數量、不同AGV數量以及相同AGV數量、不同工位數量在不同節拍要求下進行仿真實驗，通過對比計算出約束下的最優方案。此算法中基本參數設置如下：種群數量=100；選擇方式：輪盤賭選擇；變異率：PM=0.1；交叉率：PC=0.7。迭代次數：當工位數量較多時=500，工位數低于10時=300。部分仿真結果如圖8所示。
圖8 20工位4車優化結果
以20個工位為例：當車間共有20個工位需要補料時，應用改進的遺傳算法即可優化出在固定節拍要求下的最優路徑及最優AGV數量，當節拍允許范圍為100 s以下時，評估車輛成本及時間差成本選擇最優車輛為4輛，由圖8可知AGV1運輸路徑為：16→18→1→2；AGV2運輸路徑為：12→5；AGV3運輸路徑為：17→11→9→20→15→6→14→19；AGV4運輸路徑為：8→10→7→4→13→3。圖9只是其中一種結果。如表1所示：完成任務時總運行距離為399.6 m；平均節拍為99.9 s。相對于傳統算法AGV行走路徑長度縮短了74.8 m，平均節拍減少了18.7 s，在節約成本的同時縮短了完成任務的工期，證明了文中算法的實用性。
圖9 20工位4車仿真結果
表1 不同工位-AGV組合比較
5 結束語
本文作者在不同條件背景下對多AGV多任務模式調度問題進行研究，應用改進的遺傳算法對模型進行優化，當任務較多時，改進的遺傳算法無論從AGV行走距離、任務完成時間、迭代次數等方面都優于傳統遺傳算法，從而證明了算法的有效性；隨后應用于模型中并達到了預期效果，也證明改進算法的實用性。通過算法對AGV進行調度，使工廠變得更加數字化、智能化、科學化，同時響應智慧工廠發展趨勢。
