楊增鋼，閆 明，雷 蕾 YANG Zenggang, YAN Ming, LEI Lei

（沈陽工業(yè)大學(xué) 機(jī)械工程學(xué)院，遼寧 沈陽 110870）

目前在使用遺傳算法解決路徑優(yōu)化問題方面，主要分為兩個(gè)維度。一是橫向維度：多算法結(jié)合；二是縱向維度：將遺傳算法升級(jí)。本文從橫向、縱向兩個(gè)維度同時(shí)對(duì)現(xiàn)有算法進(jìn)行改進(jìn)。在縱向維度，將現(xiàn)有自適應(yīng)遺傳算法中交叉、變異公式進(jìn)行改進(jìn)，形成IAGA 算法，以解決AGA 在進(jìn)化早期出現(xiàn)“停滯”的問題。在橫向維度，將IAGA 與SA 結(jié)合形成ASAGA 算法，以提高算法的精確度和收斂速度。

1 堆垛機(jī)調(diào)度建模

1.1 復(fù)合作業(yè)模式

復(fù)合作業(yè)方式工作過程為：從出入庫(kù)站臺(tái)O 點(diǎn)出發(fā)運(yùn)行到第一個(gè)貨位點(diǎn)進(jìn)行入庫(kù)操作，然后直接運(yùn)行到第二個(gè)貨位點(diǎn)，進(jìn)行出貨操作回到出入庫(kù)站臺(tái)，如此便完成了一組出入庫(kù)作業(yè)。如圖1 所示。

1.2 建立數(shù)學(xué)模型

考慮復(fù)合作業(yè)的實(shí)際工作情況，為使研究更方便，提出假設(shè)：

（1） 忽略堆垛機(jī)起速、降速時(shí)間；

（2） 堆垛機(jī)運(yùn)動(dòng)分解成兩個(gè)正交方向的運(yùn)動(dòng)；

（3） 堆垛機(jī)收到一組指令，其中入庫(kù)與出庫(kù)指令數(shù)量均為k。堆垛機(jī)一次出入庫(kù)作業(yè)時(shí)間為：

其中：tOA為入庫(kù)運(yùn)行時(shí)間，tAB空載運(yùn)行時(shí)間，tOB出庫(kù)運(yùn)行時(shí)間。

由圖1 可知，任意一組出入庫(kù)組合任務(wù)中，無論其處于哪一個(gè)順序位置上，OA 與OB 的距離是固定的，即tOA、tOB固定，而tAB（即空載時(shí)間） 卻會(huì)因?yàn)橄噜彽娜霂?kù)與出庫(kù)貨位點(diǎn)的不同選擇而發(fā)生變化，所以選擇合適的出入庫(kù)順序使空載運(yùn)行時(shí)間最短才是問題的關(guān)鍵。

采用單向配對(duì)的方式進(jìn)行出入庫(kù)任務(wù)處理，設(shè)A= ｛A1,A2,…,Ak｝，B= ｛B1,B2,…,Bk｝兩個(gè)有序序列，Ak表示第k 個(gè)入庫(kù)貨位，Bk表示第k 個(gè)出庫(kù)貨位，則復(fù)合作業(yè)運(yùn)行路徑為：O→A1→B1→O→A2→B2→O→…→Ak→Bk。作業(yè)簡(jiǎn)化成如下方式：入庫(kù)貨位點(diǎn)集合A 按照訂單自然順序排列，作為待配對(duì)位置點(diǎn)，對(duì)出庫(kù)貨位點(diǎn)進(jìn)行排序，使得總運(yùn)行時(shí)間最小。

設(shè)A 中第i 個(gè)入庫(kù)貨位點(diǎn)的坐標(biāo)為（xi, yi），重新排序后的B 中的第i 個(gè)出庫(kù)貨位點(diǎn)坐標(biāo)為）。數(shù)學(xué)模型為：

式中：Vx、Vy為堆垛機(jī)水平、豎直方向運(yùn)行速度，L 為貨格的寬度。

2 自適應(yīng)模擬退火遺傳算法

2.1 自適應(yīng)遺傳算法設(shè)計(jì)步驟

（1） 編 碼

采用順序編碼，整數(shù)的不同排列順序即表示基因在染色體上的不同排列。

（2） 選擇算子

本文采用輪盤賭法?；舅枷耄簩€(gè)體適應(yīng)度值占全部個(gè)體適應(yīng)度總值的比例作為進(jìn)入下一代的概率，概率公式為：

式中：f （xi）為個(gè)體i 的適應(yīng)度值，為當(dāng)代所有個(gè)體適應(yīng)度值總和。

（3） 交叉、變異算子

a.交叉、變異方式：

采用兩點(diǎn)交叉方式：隨機(jī)選擇兩個(gè)交叉點(diǎn)的位置，兩個(gè)交叉點(diǎn)之間的染色體片段即為交叉片段，兩個(gè)父代交換交叉片段，其他位置上的基因按原來順序且不重復(fù)原則排列在染色體上。

例如：

父代A （1,3,5,2,6,4 ）→子代A （3,5,2,1,6,4）

父代B （4,5,2,1,6,3 ）→子代B （4,3,5,2,1,6）

變異方式：隨機(jī)選取兩個(gè)基因位置進(jìn)行交換。

例如： （1,3,5,2,6,4 ）→（1,6,5,2,3,4）

b.交叉、變異概率：

在Srinivasa[1]提出的自適應(yīng)交叉、變異概率公式基礎(chǔ)上做出改進(jìn)，改進(jìn)后公式如下：

由改進(jìn)后的公式，避免了出現(xiàn)交叉、變異概率為0 的現(xiàn)象，進(jìn)化早期保證當(dāng)前最優(yōu)個(gè)體能夠繼續(xù)進(jìn)化，保證了全局收斂性。式中，fi表示要進(jìn)行交叉運(yùn)算的兩個(gè)較大個(gè)體的適應(yīng)度，K1、K2、K3、K4為常數(shù)，fmax為當(dāng)代最大適應(yīng)度值，favg為適應(yīng)度平均值。

2.2 模擬退火算法

模擬退火算法具有跳突性，在于其Metropolis 準(zhǔn)則：當(dāng)個(gè)體A 為當(dāng)前最優(yōu)解時(shí)，算法不會(huì)將其直接輸出為最終解，而是在其鄰域隨機(jī)擾動(dòng)產(chǎn)生一新個(gè)體B。若B 適應(yīng)度大于等于當(dāng)前最大適應(yīng)度fi，則直接接受該個(gè)體，并將B賦予A；若B 的適應(yīng)度小于fi，則將根據(jù)Metropolis 準(zhǔn)則：隨機(jī)產(chǎn)生一個(gè)數(shù)Z∈（0,1 ），若Z≤exp （Δf/KT ）則接受B；反之，則不接受。其中，K為物理學(xué)常量，T 為當(dāng)前溫度。

2.3 自適應(yīng)模擬退火遺傳算法

為了徹底克服遺傳算法過早收斂的問題，將改進(jìn)后的自適應(yīng)遺傳算法（IAGA） 與SA 結(jié)合。結(jié)合方式如圖2 所示：

圖2 ASAGA 流程圖

結(jié)合方式：將遺傳算法經(jīng)交叉變異后，將新種群中每一個(gè)體均進(jìn)行模擬退火操作，然后求解出每一個(gè)體的適應(yīng)度Fi，并將這些個(gè)體組成新的組合F=max （F1,F2,…,Fn），當(dāng)作本代一組最優(yōu)解，作為下一代的初始種群。

3 仿真分析

3.1 參數(shù)設(shè)置

參數(shù)：貨架：長(zhǎng)100m，高30m，單元貨格高度1m，寬度1m，共3 000 個(gè)貨位；堆垛機(jī)：水平速度Vx=1.5m/s，豎直速度Vy=0.5m/s；隨機(jī)生成40 條貨單，30 條入庫(kù)貨單，30 條出庫(kù)貨單。

入庫(kù)貨單坐標(biāo)： （2,1 8 ）（5,3 ）（20,16 ）（28,23 ）（35,12 ）（36 ,9 ）（42,28 ）（50,26 ）（58,24 ）（63,10 ）（64,15 ）（9,2 0 ）（12,20 ）（18,16）（29,13 ）（44 ,2 ）（59,17 ）（70,23 ）（72,15 ）（75 ,7 ）（79 ,1 ）（82 ,8 ）（84,30 ）（84 ,8 ）（89 ,2 ）（92,30 ）（98,21 ）（93 ,3 ）（99 ,8 ）（100,28 ）；

出庫(kù)貨單坐標(biāo)： （3,5 ）（12,14 ）（17,21 ）（24,29 ）（29 ,7 ）（35,28 ）（43 ,6 ）（53,13 ）（60 ,2 ）（64,30 ）（66 ,2 ）（6,1 9 ）（14,25 ）（14,14）（26,30 ）（37,28 ）（38 ,2 ）（44,10 ）（47 ,9 ）（54,29 ）（65,18 ）（71,17 ）（76,13 ）（79,20 ）（80 ,5 ）（81,21 ）（88,10 ）（90 ,1 ）（93,30 ）（95 ,9 ）。

將出庫(kù)貨單依次編號(hào)1~30。種群規(guī)模N=100，初始溫度T0=100，最終溫度Tf=0.01，降溫速率k=0.98，內(nèi)部循環(huán)次數(shù)取50。

3.2 結(jié)果分析

使用Matlab 軟件分別對(duì)各種算法運(yùn)行20 次，分別取四種算法中最能代表結(jié)果平均值的一組數(shù)據(jù)，如圖3 所示。

圖3 四種算法最大適應(yīng)度迭代曲線

由圖3 看出，ASAGA 求解結(jié)果最接近理論最優(yōu)值，適應(yīng)度為0.000 92，即堆垛機(jī)最短作業(yè)時(shí)間為1 117s，貨位出庫(kù)順序?yàn)?2→1→2→4→18→7→16→6→20→19→8→3→13→14→5→17→21→24→22→23→9→25→15→27→11→10→26→28→30→29。

從縱向角度分析。IAGA 能夠在算法進(jìn)化初期避免出現(xiàn)陷入局部最優(yōu)的現(xiàn)象，收斂速度有明顯的提升，精確度也有一定幅度的提高。從橫向角度分析。ASAGA 吸取了IAGA 全局搜索性強(qiáng)和SA 局部最優(yōu)跳脫性的優(yōu)點(diǎn)，在精確度和收斂速度上均有所提高。

4 結(jié)束語

本文研究自動(dòng)化立體倉(cāng)庫(kù)堆垛機(jī)復(fù)合作業(yè)路徑優(yōu)化問題，建立數(shù)學(xué)模型，并使用SA、AGA、IAGA、ASAGA 四種算法求解，得到了最佳路徑優(yōu)化方案。并通過結(jié)果分析，證實(shí)了IAGA 能夠解決AGA 在進(jìn)化早期陷入局部最優(yōu)的問題，ASAGA 能夠在算法精確度、收斂速度兩方面較SA、IAGA 均有一定提高，進(jìn)而提高了倉(cāng)庫(kù)效率，降低了成本。