基于模擬退火遺傳算法的AGV調度系統研究

余星寶，楊慧斌，周玉鳳

(上海工程技術大學機械與汽車工程學院，上海 201620)

1 引言

我國正處于“中國制造2025”的關鍵階段[1]，航空航天領域一直處于國家戰略性地位，也代表了一個現代工業化國家的技術水平。為了提高裝配和加工效率，航空公司借鑒福特公司的汽車裝配流水線，改造出了“脈動生產線”，大大縮短了大型航空件如飛機的生產時間，同時對飛機零部件的裝配要求也更高。采用麥克納姆輪的自動引導車(AGV)可以全向移動，因此采用麥克納姆輪重載AGV應運而生，不僅可以靈活滿足普通的搬運任務，而且還可以在重載AGV的基礎上搭載具有其它功能的機器人對航空件進行各種工藝操作，提高生產效率。

對于重載AGV的研究，國內外對重載AGV的主要研究方向是機械結構方面和誤差方面的研究[2]，許多專家學者也對AGV的調度研究進行了大量研究。針對降低運輸時間、提高調度效率方面，采取現代優化算法，如遺傳算法[6]、模擬退火算法等[7]。曹有輝等[8]針對AGV局部極小值問題，提出一種基于虛擬目標的人工勢場的路勁規劃算法，羅哉等[9]利用積分分離PID糾偏算法來對AGV軌跡偏差進行糾正，楊瑋等[10]采用混合粒子群算法減低AGV調度過程中產生的鎖死現象；對于小車調度的評判方法，如模糊評價法[11]、數據包絡法[12]等。

本文結合某公司的重載鉆鉚AGV，對重載AGV的調度系統進行研究，針對調度系統的穩定性，提出理想解法對AGV進行實時評價建模，得到適應度函數。然后利用模擬退火遺傳算法對多AGV調度進行試驗和仿真，對本文所采用的方法的實用性和有效性進行驗證。

2 問題描述和建模

2.1 問題描述

本文研究的自動鉆鉚移動機器人，加工對象為飛機水平尾翼，加工部位如圖1所示，主要集中在上前壁板、上后壁板連接處；上后壁板與前梁連接部分；上前壁板外半側與后梁連接部分(綠色點集區域)。

圖1 加工對象

主要組成為重載AGV、鉆鉚外末端執行器、內頂執行器與制孔末端執行器，其模型如圖2所示。主要工藝流程是自動鉆孔、自動測量和自動鉚接等其它工藝如圖2和圖3所示，被加工部分即為固定工裝部分。

圖2 鉆鉚機器人工作模型

圖3 鉆鉚AGV實物

作業車間的調度問題可以描述為：有N臺鉆鉚機器人和M個工裝，每一個工裝所需工序時間相同。加工完一個工序之后AGV可以選擇繼續加工或者去下一個工裝進行加工。并且做如下假設：

1)AGV具有相同的運動速度，以避免AGV因速度不一致而產生同向碰撞沖突。

2)AGV的最短路徑已經規劃好，AGV數量固定，每個工裝的加工時間相同。

3)每個工裝AGV只加工一次，不允許重復加工。

2.2 基于理想解法建立目標函數

2.2.1 單AGV完成一項任務時間

首先計算出移動機器人完成一次鉆鉚所需的時間；然后利用理想解法的方式[13]，將AGV當前電量、鉚釘數量作為評價因素，計算出評價因子，目標函數即為評價因子與單個任務時間的乘積。本文建立模型來計算AGV移動至工裝的最短時間。一臺AGV在完成一次鉆鉚任務的總耗時T如式(1)所示

T=Te+Twl+Tij+Twg，Te≥0，Twl≥0，Tij≥0，Twg≥0

(1)

其中，T代表單AGV完成一次鉆鉚任務的總時間；AGV接受指令有兩種情況：1.當前時刻AGV無鉆鉚任務，Te表示AGV沒有任務的等待時間；2.AGV正在鉆鉚，耗時Twl之后AGV可以結束現階段的任務；Tij代表AGV從工裝i到達工裝j的時間；Twg代表AGV完成鉆鉚任務的時間。AGV結束所有鉆鉚任務需要的時間如式(2)所示

(2)

(3)

(4)

2.2.2 建立理想解法評價評價函數

由于2.2.1章節的AGV調度模型只考慮了調度時間，并沒有考慮電量不足或者鉚釘數量不夠等情況，導致整個系統缺乏魯棒性。為了應對這些問題，本文提出理想解法評價模型(也稱TOPSIS法)。假設AGV當前狀態如表1所示。

表1 AGV當前狀態數據

1)數據預處理。將AGV當前電量和當前鉚釘數量相應數據放入矩陣aij中，向量標準化按照式(5)進行處理。

(5)

數據經過處理之后的結果如表2所示。

表2 數據經標準化的屬性表

2)設置權重系數。設權重向量為w=[0.6，0.4]，在設置權重系數之后，當前電量和鉚釘數量向量規范屬性如表3所示。

表3 加權標準化屬性表

3)確定正理想解C*和負理想解C0。

正理想解如式(6)

(6)

負理想解如式(7)：

(7)

由表3、式(6)和式(7)可知，正理想解C*=[0.4346，0.3274]，負理想解C0=[0.2562，0.1022]。

(8)

(9)

(10)

表4 各屬性距離值及評價值

(11)

3 模擬退火遺傳算法

3.1 模擬退火算法

模擬退火算法(SimulatedAnnealing，SA)[14]的基本原理如下。相關研究證明當物質進行退火的時時候，高溫下分子的活躍度高，自由運動熵增大，以致重新隨機排列。一段時間過后開始降低溫度，分子慢慢脫離不穩定狀況，利用概率的多變性可以在所有隨機解空間中找到全局最優解。從理論上來說，在整個算法流程中，最高溫度足夠高且合理且降溫時間充足，降溫緩慢，模擬退火算法能以接近100%的概率找到最優解。

3.2 融合模擬退火算法和遺傳算法

模擬退火遺傳算法(SA&GA)[15]是將模擬退火算法和遺傳算法相結合的一種優化選擇算法。它綜合了模擬退火的全局搜索能力和遺傳算法的局部搜索能力，提高了算法的精確性。本文實現模擬退火遺傳算法主要分為兩個部分，第一個部分利用遺傳算法對種群進行編碼，在適應度函數的基礎上進行選擇、交叉和變異操作，得到新的種群。第二部分在新種群的基礎上，用Metropolis算法來確定種群狀態變化，直至達到穩定。算法的執行過程如圖4所示。

圖4 混合模擬退火遺傳算法流程圖

3.2.1 編碼

定義染色體編碼是解決遺傳算法問題的第一步，根據本文實際場景，本文采取比較直觀的無起點自然數編碼，以工裝編號為基因，按照AGV加工順序組成染色體。假設一共3臺AGV，AGV的加工路線如下：

AGV1：3-5-8

AGV2：2-4-1-6

AGV3：7-9

將3臺AGV路線接連起來即為染色體編碼：358241679。每一個數字代表工裝編號，以此類題，直至加工完所有工裝。

3.2.2 適應度函數

遺傳算法對適應度函數的評價是進行選擇操作的依據，根據本文實際場景，模糊函數已由理想解法求出，見式(11)，本文以最小化時間為目標，適應度函數如式(12)

(12)

3.2.3 選擇算子

本文選擇算子的方式為計算適應度比例的方式。先計出單個個體的適應值占總群總適應度的比例，也就是單個個體被選中的概率。選擇過程以“物競天擇”的思想作為選擇依據。對于單個個體i，其被選中的概率如式(13)所示

(13)

3.2.4 交叉算子

交叉就是重組兩個父輩部分基因片段，以此增加基因的多樣性。運用次序交叉的方式進行交叉操作，以工裝相對次序為例，這種交叉方式在構造算子時會保存另一個父輩中基因的部分相對次序。

3.2.5 變異算子

遺傳算法中發揮主要遺傳作用的是交叉算子，變異算子輔助遺傳，主要目的是維持種群多樣性，產生少量變異個體。本文選取反轉變異的方法，在基因片段隨機選擇兩斷點，將兩斷點間的基因片段互換：

未變異：F1=(721|3489|56)

變異后：G1=(721|9843|56)

3.2.6 模擬退火算子

遺傳算法得到不同的個體之后，對個體編碼進行解碼的操作。該種群的最大適應度函數值為Fmax，最小適應度函數值為Fmin。

-ΔF=Fmax-Fmin

(14)

(15)

式(15)中，t0是初始溫度；p0為接受劣解的概率，(0Ej，分子狀態j即為當前時刻狀態；否則就用概率pr代替當前時刻分子狀態，如式(15)。多次循環直至退火系統達到平衡。

(16)

根據模擬退火算法的收斂速度和優化性能，算法的終止條件即為遺傳算法最大進化次數。實際操作中，當進化代數過大，則認為模擬退火算法溫度足夠低，可以終止算法。

4 實驗結果分析

3臺重載AGV，編號為AGV1、AGV2和AGV3；8個工裝，編號依次從1至8；行駛速度v=0.25m/s；由于工裝加工時間均相同，計算過程中均忽略加工時間；AGV當前電量，鉚釘數量的權重分別為：0.6和0.4；AGV當前狀態如表5所示，工裝之間的距離如表6所示。

表5 AGV當前狀態

表6 各個工裝之間距離

本文采取的算法相關參數為：初始種群個數為100個；進化代數為200；交叉概率為pc=0.85；變異概率為pm=0.15；退火系統中劣解的概率p0=0.95；衰減系數α=0.85。分別利用實驗和仿真對傳統遺傳算法和模擬退火遺傳算法進行比較，以及使用了理想解法的優化算法和未使用理想解法的優化算法進行計較。通過Visual Studio 2017設計出調度系統，其主頁如圖5所示，部分運行日志如圖6所示。

圖5 調度系統主頁

圖6 運行日志

通過試驗和MATLAB仿真得到最優路徑分別為：

傳統遺傳算法最優解：

3-8-7，2-5， 1-4-6

未使用理想解法的模擬退火遺傳算法：

1-2，3-7-8，4-6-5

基于理想解法的模擬退火遺傳算法：

1-2-6， 4-5， 3-8-7

表7為試驗和仿真結果，由于AGV2的鉚釘數量缺乏，采用了理想解法的調度策略都使AGV2盡量少的進行加工，未采用理想解法的調度策略在鉚釘將要使用完的時候需要進行鉚釘補充，花費了一定時間，降低系統效率，而且采用了理想解法的算法計算時間更短，有效提高了系統效率和魯棒性。

表7 不同算法條件下試驗和仿真結果

本文提出的算法實際實驗時間比基于理想解法的遺傳算法時間減少11.2%，計算時間比模擬退火遺傳算法所需時間減少18.6%。可以看出模擬退火遺傳算法比傳統遺傳算法具有更好的全局最優解查找能力，更好的避免了遺傳算法局部最優解問題。

圖7 遺傳算法(GA)和模擬退火遺傳算法(SA&GA)優化過程

5 結論

針對重載AGV的調度問題，本文以AGV當前電量和鉚釘數量為評價指標，利用理想解法建立評價函數，此種方法更能體現實時性，更符合實際生產需求。自適應函數以最小化鉆鉚機器人調度時間為依據，然后實現多AGV對多個工位的合理調度，在理想解法生成的自適應函數基礎上，利用遺傳算法對基因進行選擇、交叉和變異操作，最后再利用模擬退火算法對新種群進行退火操作，使得遺傳算法的解具有更高的全局性，使得算法更精確完善，已達到航空航天裝配的高精度需求。

相較于不使用理想解法，本文提出的基于理想解法的模擬退火遺傳算法能針對具體場景和具體要求得到最佳的調度策略，實際調度時間更短，而且降低計算量，提高了調度系統的想以速度，增強了系統的魯棒性，可以達到航空航天加工裝配要求。

將理想解法計算得到的適應度函數帶入遺傳算法中更具有實際意義，在理論對模擬退火遺傳算法的每個流程都給出了細致的解答。融合了模擬退火算法的遺傳算法的選擇全局最優解的能力也有所提升。根據實驗和仿真結果，本文提出的混合優化算法能對多AGV的調度系統設計具有一定參考和實用價值。