基于模擬退火遺傳算法的AGV調(diào)度系統(tǒng)研究

余星寶，楊慧斌，周玉鳳

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

1 引言

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

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

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

2 問題描述和建模

2.1 問題描述

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

圖1 加工對(duì)象

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

圖2 鉆鉚機(jī)器人工作模型

圖3 鉆鉚AGV實(shí)物

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

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

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

3)每個(gè)工裝AGV只加工一次，不允許重復(fù)加工。

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

2.2.1 單AGV完成一項(xiàng)任務(wù)時(shí)間

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

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

(1)

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

(2)

(3)

(4)

2.2.2 建立理想解法評(píng)價(jià)評(píng)價(jià)函數(shù)

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

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

1)數(shù)據(jù)預(yù)處理。將AGV當(dāng)前電量和當(dāng)前鉚釘數(shù)量相應(yīng)數(shù)據(jù)放入矩陣aij中，向量標(biāo)準(zhǔn)化按照式(5)進(jìn)行處理。

(5)

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

表2 數(shù)據(jù)經(jīng)標(biāo)準(zhǔn)化的屬性表

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

表3 加權(quán)標(biāo)準(zhǔn)化屬性表

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

正理想解如式(6)

(6)

負(fù)理想解如式(7)：

(7)

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

(8)

(9)

(10)

表4 各屬性距離值及評(píng)價(jià)值

(11)

3 模擬退火遺傳算法

3.1 模擬退火算法

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

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

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

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

3.2.1 編碼

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

AGV1：3-5-8

AGV2：2-4-1-6

AGV3：7-9

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

3.2.2 適應(yīng)度函數(shù)

遺傳算法對(duì)適應(yīng)度函數(shù)的評(píng)價(jià)是進(jìn)行選擇操作的依據(jù)，根據(jù)本文實(shí)際場(chǎng)景，模糊函數(shù)已由理想解法求出，見式(11)，本文以最小化時(shí)間為目標(biāo)，適應(yīng)度函數(shù)如式(12)

(12)

3.2.3 選擇算子

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

(13)

3.2.4 交叉算子

交叉就是重組兩個(gè)父輩部分基因片段，以此增加基因的多樣性。運(yùn)用次序交叉的方式進(jìn)行交叉操作，以工裝相對(duì)次序?yàn)槔?，這種交叉方式在構(gòu)造算子時(shí)會(huì)保存另一個(gè)父輩中基因的部分相對(duì)次序。

3.2.5 變異算子

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

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

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

3.2.6 模擬退火算子

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

-ΔF=Fmax-Fmin

(14)

(15)

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

(16)

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

4 實(shí)驗(yàn)結(jié)果分析

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

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

表6 各個(gè)工裝之間距離

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

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

圖6 運(yùn)行日志

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

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

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

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

5 結(jié)論

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

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

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