基于免疫蟻群優(yōu)化算法的倉儲任務(wù)調(diào)度*

楊桂華，衛(wèi)嘉樂

(桂林理工大學機械與控制工程學院，桂林 541004)

0 引言

電子商業(yè)的快速發(fā)展帶動著物流行業(yè)的變革，傳統(tǒng)的“人到貨”模式的效率低下，不利于企業(yè)的良性發(fā)展[1]。利用倉儲機器人群協(xié)同工作實現(xiàn)“貨到人”的新揀選模式成為一種有效的解決方案[2]。倉儲機器人群解決方案的首要工作就是多機器人的調(diào)度問題，多機器人的任務(wù)調(diào)度問題就是確定系統(tǒng)中各個機器人在各個時刻應(yīng)該執(zhí)行哪些任務(wù)[3-4]，防止機器人之間的沖突和重復調(diào)用。

目前，有許多學者對群體調(diào)度問題進行了研究。王雷、趙賓鋒等[5-6]用改進免疫克隆選擇算法解決柔性作業(yè)車間的調(diào)度問題，秦新立等[7]引入局部優(yōu)化變異算子和融合改進模擬退火算法來改進蟻群算法，解決多機器人任務(wù)分配問題，同時采取改進共同進化遺傳算法理論求解自動導引小車(automatic guided vehicle，AGV)任務(wù)調(diào)度問題。但是近優(yōu)算法在求解過程中容易出現(xiàn)的快速收斂陷入局部優(yōu)值，以及種群迭代后期的多樣性下降導致的求解時間長、求解效率不高的問題。

針對上述問題，本文在研究傳統(tǒng)免疫算法的基礎(chǔ)上，提出了免疫蟻群優(yōu)化算法， 通過融合蟻群算法來代替免疫算法后期的求解工作，有效地加快了算法的求解效率。

1 物流倉庫環(huán)境

1.1 場地介紹

以小型智能物流儲存?zhèn)}庫建設(shè)為背景，當倉儲機器人群在倉庫中進行作業(yè)時，可以通過二維環(huán)境地圖描述當前的區(qū)域情況。倉庫環(huán)境如圖1所示，倉庫主要分為4個區(qū)域：入庫操作臺、出庫操作臺、倉儲區(qū)域和機器人存儲區(qū)域。其中入庫操作臺用于貨物入庫時檢測、登記以及入庫單的打印。倉儲區(qū)域用于貨物的存放。機器人存儲區(qū)用于機器人在沒有任務(wù)時的存放和補充能源。出庫操作臺用于貨物出庫時的登記。

圖1 物流倉庫平面示意圖

1.2 柵格法環(huán)境建模

在倉儲環(huán)境下，物流貨架較多，用拓撲圖法建立拓撲網(wǎng)絡(luò)地圖比較復雜。可視圖法雖然能直觀的體現(xiàn)環(huán)境情況，但是與拓撲網(wǎng)絡(luò)一樣，當?shù)貓D中的障礙物較多的時候，可視圖的構(gòu)建非常復雜，且當貨架位置進行變動的時候，需要重新構(gòu)建可視圖，靈活性不高[8]。相比之下柵格圖法在直觀的表示障礙物和自由空間的前提下，對于后續(xù)的更改只需要重新對柵格進行賦值就行了。所以綜合考慮下采用柵格圖方法。

利用柵格法建立的物流倉庫地圖如圖2所示。其中黑色柵格代表倉儲區(qū)域中的貨架，白色柵格是貨架之間可以移動的區(qū)域。其中每個柵格的邊長為1 m。

圖2 物流倉庫柵格地圖

柵格地圖構(gòu)建基于式(1)：

(1)

式中，(x,y)為圖2中柵格的橫坐標和縱坐標的數(shù)值；f(x,y)=0為倉儲區(qū)域中機器人可以移動的過道；f(x,y)=1為機器人不能移動的障礙物。

2 倉儲機器人群調(diào)度模型

2.1 問題描述

倉儲機器人群調(diào)度問題描述如下：有M個任務(wù)分配給K臺機器人去搬運完成，每個任務(wù)不指定特定機器人，但是一個任務(wù)只能由一臺機器人進行搬運，為了避免機器人任務(wù)不均衡，以提高效率為目的制定每臺機器人每次搬運不能少于m個任務(wù)，且任務(wù)根據(jù)重量和尺寸制定相應(yīng)的任務(wù)量，每臺機器人也對應(yīng)有最大搬運量，要求K臺機器人在完成M個任務(wù)的同時，每次機器人搬運的任務(wù)量要小于該機器人的最大搬運量，并且機器人群總行駛的距離應(yīng)達到最小。

2.2 模型建立

基于以上問題，建立如下模型。該模型是一個分配模型，在滿足調(diào)度任務(wù)距離損耗最小的情況下，保證機器人群能安全高效的運作。目標函數(shù)是各個機器人到需要搬運的任務(wù)點之間的距離。目標函數(shù)為：

(2)

約束條件為：

(3)

式中，F(xiàn)為目標函數(shù)，表示調(diào)度過程中機器人群到各個任務(wù)點的總的距離損耗；M={1,2,3,…,n}為所有的任務(wù)點的序號；dij為從機器人j到任務(wù)i的距離；wi為任務(wù)i的任務(wù)量；Tj為機器人j的最大搬運量；Zij為任務(wù)點和機器人之間的服務(wù)需求分配關(guān)系，當其為1的時候，表示任務(wù)點i由機器人j來進行搬運，否則為0；mindata為每臺機器人每次最少搬運任務(wù)的數(shù)量。

3 人工免疫系統(tǒng)及免疫算法

學者們受大自然中生物免疫系統(tǒng)的啟發(fā)，建立了人工免疫系統(tǒng)[9]，人工免疫系統(tǒng)通過模擬自然免疫系統(tǒng)識別抗原，產(chǎn)生抗體的過程生成了免疫算法來解決非線性規(guī)劃問題。免疫算法因其多樣性的抗體、自我調(diào)節(jié)功能、免疫記憶功能等優(yōu)秀特征克服了一般算法中尤其是多峰值函數(shù)尋優(yōu)過程中難處理的“早熟”問題[10]，最終求得全局最優(yōu)解。免疫算法的流程如圖3所示。

圖3 免疫算法流程圖

3.1 初始抗體種群的產(chǎn)生

根據(jù)任務(wù)數(shù)M和機器人數(shù)K生成初始抗體種群，此處采用編碼形式，每一個調(diào)度方案生成一個抗體，抗體包括了一個長度為M的任務(wù)序列和一個長度為K-1的間隔點序列，間隔點序列將任務(wù)序列從間隔點指示的位置處分為K段，每一段的序列對應(yīng)著一臺機器人的搬運任務(wù)。編碼的過程如圖4所示。

圖4 抗體編碼圖

任務(wù)序列為[13 2 7 22 6 4…]，每一個序號代表了一個任務(wù)，間隔序列為[3 6 12 18…]，間隔序列有最小間隔，由機器人每次搬運的最小任務(wù)數(shù)量m決定。則機器人1需要完成的任務(wù)為{13,2,7}，機器人2需要完成的任務(wù)為{22,6,4}，依此類推。

3.2 抗體多樣性評價

(1)抗體和抗原間的適應(yīng)度?？贵w與抗原間的親和度描述了抗體對抗原的識別程度，由適應(yīng)度函數(shù)A表達式為：

(4)

式中，F(xiàn)為目標函數(shù)，表達式如式(2)所示。

(2)抗體和抗體間的適應(yīng)度?？贵w間的適應(yīng)度描述了抗體之間的相似程度[11]，這里采用R位連續(xù)方法[12]來計算抗體間的適應(yīng)度。兩種個體編碼有超過連續(xù)R位的編碼相同，則表示這兩種抗體近似“相同”。

(5)

式中，M為任務(wù)數(shù)；ka,b為抗體a和抗體b中任務(wù)序列相同的位數(shù)。

(3)抗體濃度?？贵w濃度Cv表示一個抗體種群中，相似抗體所占的比例。

(6)

(4)期望繁殖概率?？贵w種群中，個體的期望繁殖概率P由式(4)計算出的抗體和抗原適應(yīng)度A和式(6)計算出的抗體濃度Cv兩部分共同決定。

(7)

式中，?為比例常數(shù)，通過式(7)不難看出個體期望繁殖概率隨著個體適應(yīng)度的增加而增加，反之亦然。通過這樣的方式，抑制高濃度的個體，同時也保護了對抗原適應(yīng)度高的個體，避免免疫算法求解過程中陷入局部極值的問題。

免疫算法在迭代求解的過程中，抑制高濃度的抗體的同時也會存在抑制高適應(yīng)度抗體的問題，所以需要采取精英保留策略[13]，將一個種群中與抗原適應(yīng)度最高的幾個抗體按照期望繁殖概率存入記憶庫中，保留至下一次種群。

3.3 免疫操作

(1)選擇：采用輪盤賭的方法，根據(jù)式(7)得出的個體期望繁殖概率進行選擇。

(2)交叉：尋常的交叉方法一般選擇兩個抗體，在相同的一個或者兩個位置進行序列數(shù)的交換[14]，但是在此次調(diào)度問題中考慮到此類操作會導致有些任務(wù)被重復調(diào)度，所以改進為一個抗體的隨機兩個位置任務(wù)序號進行交換。

(3)變異：隨機生成新的間隔點序列，然后在一個抗體中選擇兩個插入點，插入點之間的序列先做翻轉(zhuǎn)變異，例如原變異序列[1 2 3 4 5]翻轉(zhuǎn)變異后為[5 4 3 2 1]，然后做滑動變異，變異后序列為[4 3 2 1 5]。

3.4 免疫算法調(diào)度實驗

任務(wù)調(diào)度實驗中，假設(shè)總?cè)蝿?wù)數(shù)為32，任務(wù)從貨架中隨機選取，共有4臺機器人協(xié)同完成。每臺機器人最少搬運5個任務(wù)，每個任務(wù)對應(yīng)的任務(wù)量設(shè)定為10～70間的隨機整數(shù)，任務(wù)量和機器人群的搬運量如表1和表2所示，任務(wù)點位置和機器人的位置如圖5所示。其中每個塊中白色的位置表示任務(wù)點的位置，灰色的位置則是機器人所在位置。

圖5 倉儲機器人群調(diào)度場景設(shè)定 圖6 免疫算法的調(diào)度方案

表1 任務(wù)量數(shù)據(jù)

表2 機器人的最大搬運量

在上述調(diào)度情景的設(shè)定下，在MATLAB軟件中進行仿真實驗，表3是免疫算法中有關(guān)的參數(shù)設(shè)定。

表3 免疫算法的參數(shù)設(shè)置

圖6是利用免疫算法得到的調(diào)度方案示意圖。

可以看出，每一條軌跡都是機器人對應(yīng)搬運路線，路線僅代表了機器人搬運自己分配到的調(diào)度任務(wù)的順序。對應(yīng)的調(diào)度方案數(shù)據(jù)如表4所示。

表4 免疫算法的調(diào)度結(jié)果

圖7是人工免疫算法的收斂曲線。

圖7 免疫算法收斂曲線

可以看出適應(yīng)度值隨著迭代次數(shù)的增加而收斂，適應(yīng)度在迭代次數(shù)500次左右達到了穩(wěn)定。

4 免疫蟻群優(yōu)化算法

4.1 算法改進

分析上述實驗結(jié)果，免疫算法雖然可以得到結(jié)果，但是需要迭代多次才能得到較好結(jié)果。免疫算法在運行過程中會產(chǎn)生很多的冗余信息，所以收斂速度不高，效率低下。為了改善這一情況，通過結(jié)合免疫算法和蟻群算法對原算法進行改進。蟻群算法通過信息素的累計和更新進行搜索最優(yōu)解[15]，式(8)是蟻群算法[16]的計算過程：

(8)

蟻群算法初期信息素的積累時間較長，速度較慢。因此，先通過免疫算法得到較優(yōu)抗體種群，將其轉(zhuǎn)化為蟻群算法的初始信息素，利用蟻群算法對種群的每條抗體進行求解。免疫蟻群優(yōu)化算法的流程圖如圖8所示。

圖8 改進免疫算法流程圖

以上述免疫算法調(diào)度實驗結(jié)果為較優(yōu)解作為蟻群算法的初始信息素，然后利用蟻群算法對種群的每個抗體的任務(wù)序列分段求解，形成新的抗體組。其中適應(yīng)度最小的抗體為新算法的最優(yōu)解。具體步驟如圖9所示。

圖9 改進免疫算法操作示意圖

在算法融合過程中存在著一個最佳融合點的問題，免疫算法迭代到多少代的時候為最佳融合點。通?？捎擅庖咚惴ǖ氖諗啃试u價函數(shù)來確定[17]，它由免疫算法的適應(yīng)度函數(shù)來決定，表達式如式(9)所示：

(9)

式中，R(n)為迭代過程中第n代種群的進化率；A(n)為第n代種群與抗原的最優(yōu)親和度；N為種群大小。

但由于免疫算法在迭代的過程中導致最優(yōu)適應(yīng)度浮動較大，實際應(yīng)用中并不能很好的確定最佳融合點。本文在式(9)基礎(chǔ)上進行改進，如式(10)所示：

(10)

式中，Ri(n)為免疫算法第n代種群的第i個抗體的進化率；Ai(n)為免疫算法第n代種群第i個抗體與抗原的親和度；R(n)為免疫算法第n代種群的平均進化率；N為種群大小。假設(shè)子代群體的最小進化率Rmin，并統(tǒng)計連續(xù)出現(xiàn)R≤Rmin的次數(shù)，如果次數(shù)小于設(shè)定的閥值，說明免疫算法已經(jīng)變得低效冗余，可以終結(jié)免疫算法進入蟻群算法。

4.2 免疫蟻群優(yōu)化算法調(diào)度實驗

在上述調(diào)度情景下進行免疫蟻群優(yōu)化算法的倉儲機器人調(diào)度實驗。免疫算法的參數(shù)設(shè)置如表3所示，蟻群算法的參數(shù)設(shè)置如表5所示。

表5 蟻群算法的參數(shù)設(shè)置

其中，一個抗體的解的數(shù)目r=ants/N，N為倉儲機器人的數(shù)量。

圖10是利用免疫優(yōu)化算法得到的調(diào)度方案示意圖。對比圖6和圖10兩種算法得到的調(diào)度方案示意圖可以直觀地看出，免疫優(yōu)化算法在機器人任務(wù)分配上面更加趨于合理。對應(yīng)的調(diào)度方案數(shù)據(jù)如表6所示。

圖10 免疫蟻群優(yōu)化算法的調(diào)度方案 圖11 免疫蟻群優(yōu)化算法收斂曲線

表6 免疫蟻群優(yōu)化算法調(diào)度結(jié)果

圖11是蟻群算法的收斂曲線。

從圖11可以看出，免疫蟻群優(yōu)化算法通過免疫算法進行確定初始信息素后，使得蟻群算法能更快的收斂趨于穩(wěn)定，大大減少了蟻群算法前期信息素沉淀的時間。并且對比表5和表6的數(shù)據(jù)，免疫蟻群優(yōu)化算法在運行時間和機器人群的搬運距離上都有一定的改善。

為了充分測試改進算法的可行性，設(shè)置4個場景，隨機產(chǎn)生任務(wù)點位置，再用免疫算法和免疫蟻群優(yōu)化算法分別進行調(diào)度測試，統(tǒng)計算法的運行時間和完成調(diào)度的倉儲機器人群所用的距離。圖12是對比實驗數(shù)據(jù)的柱狀圖，表7是實驗數(shù)據(jù)。

圖12 對比實驗數(shù)據(jù)柱狀圖

表7 對比實驗數(shù)據(jù)

分析表7數(shù)據(jù)，可以看出免疫蟻群優(yōu)化算法無論在運行時間上，還是倉儲機器人群的移動距離上都有所改善，但是有時候由于免疫算法結(jié)束時的較優(yōu)解存在參差性，與極優(yōu)點存在著一定的差異。

5 結(jié)論

本文針對免疫算法存在著迭代次數(shù)長，運行過程中冗余信息多的問題，設(shè)計了免疫蟻群優(yōu)化算法，通過免疫算法提供蟻群算法的初始信息素，利用蟻群算法進一步迭代尋優(yōu)，通過對比實驗，從距離和時間上驗證了免疫蟻群優(yōu)化算法在求解效率和質(zhì)量上都有提升，表明了本文算法的可行性。