余星寶，楊慧斌，周玉鳳

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

1 引言

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

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

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

2 問題描述和建模

2.1 問題描述

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

圖1 加工對象

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

圖2 鉆鉚機器人工作模型

圖3 鉆鉚AGV實物

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

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

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

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

2.2 基于理想解法建立目標函數(shù)

2.2.1 單AGV完成一項任務時間

首先計算出移動機器人完成一次鉆鉚所需的時間；然后利用理想解法的方式[13]，將AGV當前電量、鉚釘數(shù)量作為評價因素，計算出評價因子，目標函數(shù)即為評價因子與單個任務時間的乘積。本文建立模型來計算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可以結(jié)束現(xiàn)階段的任務；Tij代表AGV從工裝i到達工裝j的時間；Twg代表AGV完成鉆鉚任務的時間。AGV結(jié)束所有鉆鉚任務需要的時間如式(2)所示

(2)

(3)

(4)

2.2.2 建立理想解法評價評價函數(shù)

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

表1 AGV當前狀態(tài)數(shù)據(jù)

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

(5)

數(shù)據(jù)經(jīng)過處理之后的結(jié)果如表2所示。

表2 數(shù)據(jù)經(jīng)標準化的屬性表

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

表3 加權(quán)標準化屬性表

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

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

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

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

3.2.1 編碼

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

AGV1：3-5-8

AGV2：2-4-1-6

AGV3：7-9

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

3.2.2 適應度函數(shù)

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

(12)

3.2.3 選擇算子

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

(13)

3.2.4 交叉算子

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

3.2.5 變異算子

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

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

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

3.2.6 模擬退火算子

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

-ΔF=Fmax-Fmin

(14)

(15)

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

(16)

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

4 實驗結(jié)果分析

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

表5 AGV當前狀態(tài)

表6 各個工裝之間距離

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

圖5 調(diào)度系統(tǒng)主頁

圖6 運行日志

通過試驗和MATLAB仿真得到最優(yōu)路徑分別為：

傳統(tǒng)遺傳算法最優(yōu)解：

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為試驗和仿真結(jié)果，由于AGV2的鉚釘數(shù)量缺乏，采用了理想解法的調(diào)度策略都使AGV2盡量少的進行加工，未采用理想解法的調(diào)度策略在鉚釘將要使用完的時候需要進行鉚釘補充，花費了一定時間，降低系統(tǒng)效率，而且采用了理想解法的算法計算時間更短，有效提高了系統(tǒng)效率和魯棒性。

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

本文提出的算法實際實驗時間比基于理想解法的遺傳算法時間減少11.2%，計算時間比模擬退火遺傳算法所需時間減少18.6%?？梢钥闯瞿M退火遺傳算法比傳統(tǒng)遺傳算法具有更好的全局最優(yōu)解查找能力，更好的避免了遺傳算法局部最優(yōu)解問題。

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

5 結(jié)論

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

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

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