于佳喬，李巖

(長春工業(yè)大學電氣與電子工程學院，吉林長春 130012)

0 前言

隨著“中國制造2025”計劃的實施，制造業(yè)的生產(chǎn)模式發(fā)生了巨大變化，智能制造為傳統(tǒng)制造業(yè)開辟了一條新的道路。在新型智慧工廠中，柔性制造系統(tǒng)已應(yīng)用于大多數(shù)企業(yè)。柔性制造系統(tǒng)(Flexible Manufacturing System，F(xiàn)MS)是由統(tǒng)一的信息控制系統(tǒng)、物料儲運系統(tǒng)和數(shù)字控制加工設(shè)備組成，能適應(yīng)加工對象變換的自動化機械制造系統(tǒng)。其中自動導航小車(Automated Guided Vehicle，AGV)在柔性生產(chǎn)系統(tǒng)的物料搬運中發(fā)揮著越來越重要的作用。隨著AGV的廣泛應(yīng)用，隨之帶來的問題也不斷增加，其中路徑規(guī)劃是這一領(lǐng)域的重點問題。如何對AGV進行合理的規(guī)劃，以提高物料搬運效率和降低生產(chǎn)成本一直是企業(yè)關(guān)注的焦點。目前，國內(nèi)外已有許多學者對AGV路徑規(guī)劃問題進行研究：文獻[5]中采用改進的A*算法對智能車路徑進行優(yōu)化；文獻[6]中應(yīng)用多種群遺傳算法對路徑規(guī)劃進行研究;文獻[7]中提出了一種自適應(yīng)遺傳算法的路徑規(guī)劃方法,采用了人工勢場對種群初始化,提高了算法收斂速度；文獻[8]中應(yīng)用Voronoi圖法對移動機器人進行路徑規(guī)劃；文獻[9]中提出了一種混合算法解決移動機器人全局路徑規(guī)劃問題,提高AGV路徑的質(zhì)量；文獻[10]中將一種新的變異方法應(yīng)用到機器人動態(tài)路徑規(guī)劃中；文獻[11]中在遺傳算法中加入轉(zhuǎn)彎角度因素對移動機器人路徑規(guī)劃進行分析；文獻[12]中提出一種新的基于排序遺傳算法的多目標最優(yōu)路徑規(guī)劃；文獻[13]中提出了縱橫協(xié)同的多種群遺傳算法解決AGV調(diào)度問題；文獻[14]中采用了整數(shù)編碼和多參數(shù)編碼相結(jié)合的方式對遺傳算法進行改進，優(yōu)化AGV的任務(wù)排序列表以及行走路徑。

本文作者在傳統(tǒng)遺傳算法基礎(chǔ)上對編碼規(guī)則、變異算子以及交叉算子進行改進，在AGV數(shù)量及補料工位數(shù)量不同的情況下，擬優(yōu)化出任務(wù)最短路徑及排序，期望得到最優(yōu)方案。

1 問題描述

在柔性生產(chǎn)系統(tǒng)中，通常存在一個集中配料區(qū)，有序存放車間生產(chǎn)所需所有物料資源，當有工位加工物料低于存儲安全值時，就需要AGV及時為其補充物料。在生產(chǎn)過程中，可能出現(xiàn)多個工位同時需要AGV為其補充物料的情況，這時候就需要對AGV補料的順序及路徑進行優(yōu)化，使AGV在最短的時間內(nèi)為所有工位完成補料任務(wù)。本文作者在此基礎(chǔ)上以多個AGV 同時服務(wù)于多個工位為背景，對AGV路徑規(guī)劃進行研究，擬達到降低AGV運行成本及車間生產(chǎn)成本的目的。

對于AGV路徑規(guī)劃問題現(xiàn)做出如下假設(shè)：

(1)AGV出發(fā)點(物料存儲地)固定;

(2)上下料時間恒定且固定，故忽略不計;

(3)任何任務(wù)都可以分配給任何一臺AGV;

(4)AGV容量足夠大，且無差別;

(5)同一任務(wù)只能被一臺AGV所執(zhí)行。

2 數(shù)學模型

柔性生產(chǎn)車間AGV調(diào)度問題可描述為輛AGV服務(wù)個工位，AGV編號為:∈{1,2,3，…，}，工位編號為:∈{1,2,3,…,}，AGV任務(wù)編號為:∈{1,2,3,…,}。染色體用表示,現(xiàn)根據(jù)以上約束條件及假設(shè)，建立如下數(shù)學模型：

(1)

(2)

0=0 ?,

(3)

=1 ?

(4)

其中：式(1)表示總路徑長度為各AGV路徑長度總和；式(2)表示每輛AGV的每個任務(wù)只為一個工位進行補料；式(3)表示每輛AGV執(zhí)行任務(wù)前統(tǒng)一在初始位置集合；式(4)表示每輛AGV可裝載量足夠且固定。

3 改進的遺傳算法

遺傳算法(Genetic Algorithm)是模擬達爾文生物進化論的自然選擇和遺傳學機制的生物進化過程的計算模型，是一種通過模擬自然進化過程搜索最優(yōu)解的方法。傳統(tǒng)的遺傳算法雖能尋找到最優(yōu)解，但是在求解速度以及局部最優(yōu)解問題的處理上并不理想。本文作者在傳統(tǒng)的遺傳算法基礎(chǔ)上對編碼、解碼、變異算子及交叉算子進行改進，應(yīng)用改進的遺傳算法求解問題，以達到準確、快速、高效解決問題的目的。

3.1 編碼設(shè)計

傳統(tǒng)的遺傳算法中編碼方法有二進制編碼、浮點數(shù)編碼、實數(shù)編碼。針對文中所研究的內(nèi)容，提出一種雙層實數(shù)編碼方式：將染色體分為前后兩部分：前一部分代表工位編號(工位編號先后即AGV補料順序先后)；后一部分為AGV編號。例如：一條染色體為“2354113213”，其含義如圖1所示。

圖1 染色體編碼

基于以上染色體編碼方式其讀取方式為：第一輛AGV補料任務(wù)地點為工位1、工位4；第二輛AGV補料任務(wù)地點為工位3；第三輛AGV補料地點為工位2、工位5。

染色體編碼后按上述讀取規(guī)則對AGV行走路徑進行解碼，通過讀取AGV行走路徑及搬運順序記錄染色體目標值。個體的適應(yīng)度函數(shù)()定義如下：

式中：()為第輛AGV行走總路徑之和。將所有AGV行走路徑之和加在一起組成個體的適應(yīng)度函數(shù)。根據(jù)上述定義可知，個體適應(yīng)度值越大，目標值越小。當目標值最小時，得出最優(yōu)解。

3.2 初始種群的生成

由于文中在染色體生成時使用雙層編碼方式，同時滿足兩個變量要求：工位數(shù)和AGV數(shù)，所以傳統(tǒng)的種群生成方式不適用。文中初始種群的生成具體步驟如下：

(1)根據(jù)工位的數(shù)量確定第一層工位編碼范圍[1,…,]；

(2)根據(jù)可調(diào)用AGV數(shù)量確定第二層AGV編碼范圍[1,…,]；

(3)將第一層與第二層組成一條完整的染色體序列；

(4)重復步驟3、4，生成一組含有多個染色體的初始種群。

3.3 變異算子

變異操作是遺傳算法中一個重要的過程，變異算子的主要作用是改善系統(tǒng)的全局搜索能力，維持種群的多樣性。過小的變異率會導致新生成的種群產(chǎn)生新個體的能力較弱，抑制早熟現(xiàn)象的能力變差；過大的變異率會使系統(tǒng)隨機性更大，增加不必要的計算。本文作者在綜合考慮其影響因素后，提出一種變異方法：雙層編碼多次變異。多次的變異過程不僅增大了解的空間，而且維持了種群的多樣性，降低了算法陷入局部最優(yōu)解的概率。具體步驟如圖2所示。

圖2 變異過程

改進的變異操作在第一層編碼的兩點變異后加入了逆轉(zhuǎn)變異以及滑動變異來增大解的空間，增強算法的搜索能力，可以更好地找到最優(yōu)解。逆轉(zhuǎn)變異及滑動變異具體原理如圖3—圖4所示(由于只對第一層編碼有效，示例僅編寫第一層編碼)：

(1)逆轉(zhuǎn)變異。在變異前產(chǎn)生隨機數(shù)<，例如=4，即染色體前4位進行逆轉(zhuǎn)變異，由原始“53214”變?yōu)椤?2354”，如圖3所示。

圖3 逆轉(zhuǎn)變異

(2)滑動變異。首先將原始染色體復制，組成一條新的染色體=[,]，長度為二倍；其次生成隨機數(shù)<，取的第位到第+-1位為新染色體,如圖4所示。

圖4 滑動變異

3.4 交叉操作

交叉算子是遺傳算法中控制全局搜索的一種算子，算子大小的調(diào)試對整個算法有重要影響：較大的交叉算子會增強算法開辟新的搜索區(qū)域的能力，但是過大的算子會增加不必要的計算成本；當交叉算子過小時，系統(tǒng)會陷入遲鈍狀態(tài)，在搜索新個體時速度變慢，導致運行停滯，增大運行時間?；陔p層編碼方式對染色體進行雙層兩點交叉，即對染色體第一、二層同時進行兩點交叉。首先將所有染色體分為兩兩一組，組成若干個染色體對，為每個染色體對分配隨機數(shù)，當0.5時，對染色體第二層進行交叉，交換兩染色體AGV編號，產(chǎn)生新的染色體。相較于原染色體，新染色體為相同補料工位使用不同的AGV來完成任務(wù)，增加了補料工位分配任務(wù)的解空間。交叉完成后對于第一層染色體片段工位編碼部分，可能會出現(xiàn)重復工位的可能，因此在交叉后會對交叉后的染色體進行修補：取交叉片段補集隨機排列到非交叉片段。具體過程如圖5—圖6所示。

圖5 染色體修補過程

圖6 交叉過程

3.5 迭代終止條件

迭代終止條件在遺傳算法中控制著算法運行時間長短：過小的終止條件會讓算法在未尋找到最優(yōu)值時停止，而沒有完成任務(wù)；過大則會增加算法不必要的過程，增加程序運行成本。在遺傳算法中終止迭代有多種方法：(1)人為設(shè)置種群在迭代多次后強行終止，這種情況一般設(shè)置迭代次數(shù)為20～500之間；(2)當種群在多次迭代后目標值沒有發(fā)生變化時停止迭代；(3)當?shù)蟮慕Y(jié)果小于人為設(shè)定的值時，程序停止運行。文中選用第一種：當?shù)螖?shù)為20～500代時，終止程序。這種方法會讓程序變得更加可控，在不斷觀察運行結(jié)果時調(diào)整參數(shù)，以達到最優(yōu)的效果。

4 仿真實驗與分析

環(huán)境地圖中最多有20個工位，將各工位置于-坐標系中并計算其坐標，結(jié)果如圖7所示。

圖7 工位點坐標

以此坐標作為地圖，應(yīng)用改進的遺傳算法分別對相同工位數(shù)量、不同AGV數(shù)量以及相同AGV數(shù)量、不同工位數(shù)量在不同節(jié)拍要求下進行仿真實驗，通過對比計算出約束下的最優(yōu)方案。此算法中基本參數(shù)設(shè)置如下：種群數(shù)量=100；選擇方式：輪盤賭選擇；變異率：PM=0.1；交叉率：PC=0.7。迭代次數(shù)：當工位數(shù)量較多時=500，工位數(shù)低于10時=300。部分仿真結(jié)果如圖8所示。

圖8 20工位4車優(yōu)化結(jié)果

以20個工位為例：當車間共有20個工位需要補料時，應(yīng)用改進的遺傳算法即可優(yōu)化出在固定節(jié)拍要求下的最優(yōu)路徑及最優(yōu)AGV數(shù)量，當節(jié)拍允許范圍為100 s以下時，評估車輛成本及時間差成本選擇最優(yōu)車輛為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只是其中一種結(jié)果。如表1所示：完成任務(wù)時總運行距離為399.6 m；平均節(jié)拍為99.9 s。相對于傳統(tǒng)算法AGV行走路徑長度縮短了74.8 m，平均節(jié)拍減少了18.7 s，在節(jié)約成本的同時縮短了完成任務(wù)的工期，證明了文中算法的實用性。

圖9 20工位4車仿真結(jié)果

表1 不同工位-AGV組合比較

5 結(jié)束語

本文作者在不同條件背景下對多AGV多任務(wù)模式調(diào)度問題進行研究，應(yīng)用改進的遺傳算法對模型進行優(yōu)化，當任務(wù)較多時，改進的遺傳算法無論從AGV行走距離、任務(wù)完成時間、迭代次數(shù)等方面都優(yōu)于傳統(tǒng)遺傳算法，從而證明了算法的有效性；隨后應(yīng)用于模型中并達到了預期效果，也證明改進算法的實用性。通過算法對AGV進行調(diào)度，使工廠變得更加數(shù)字化、智能化、科學化，同時響應(yīng)智慧工廠發(fā)展趨勢。