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

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

0 引言

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

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

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

1 物流倉(cāng)庫(kù)環(huán)境

1.1 場(chǎng)地介紹

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

圖1 物流倉(cāng)庫(kù)平面示意圖

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

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

利用柵格法建立的物流倉(cāng)庫(kù)地圖如圖2所示。其中黑色柵格代表倉(cāng)儲(chǔ)區(qū)域中的貨架，白色柵格是貨架之間可以移動(dòng)的區(qū)域。其中每個(gè)柵格的邊長(zhǎng)為1 m。

圖2 物流倉(cāng)庫(kù)柵格地圖

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

(1)

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

2 倉(cāng)儲(chǔ)機(jī)器人群調(diào)度模型

2.1 問(wèn)題描述

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

2.2 模型建立

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

(2)

約束條件為：

(3)

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

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

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

圖3 免疫算法流程圖

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

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

圖4 抗體編碼圖

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

3.2 抗體多樣性評(píng)價(jià)

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

(4)

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

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

(5)

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

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

(6)

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

(7)

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

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

3.3 免疫操作

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

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

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

3.4 免疫算法調(diào)度實(shí)驗(yàn)

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

圖5 倉(cāng)儲(chǔ)機(jī)器人群調(diào)度場(chǎng)景設(shè)定 圖6 免疫算法的調(diào)度方案

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

表2 機(jī)器人的最大搬運(yùn)量

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

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

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

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

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

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

圖7 免疫算法收斂曲線

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

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

4.1 算法改進(jìn)

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

(8)

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

圖8 改進(jìn)免疫算法流程圖

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

圖9 改進(jìn)免疫算法操作示意圖

在算法融合過(guò)程中存在著一個(gè)最佳融合點(diǎn)的問(wèn)題，免疫算法迭代到多少代的時(shí)候?yàn)樽罴讶诤宵c(diǎn)。通?？捎擅庖咚惴ǖ氖諗啃试u(píng)價(jià)函數(shù)來(lái)確定[17]，它由免疫算法的適應(yīng)度函數(shù)來(lái)決定，表達(dá)式如式(9)所示：

(9)

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

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

(10)

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

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

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

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

其中，一個(gè)抗體的解的數(shù)目r=ants/N，N為倉(cāng)儲(chǔ)機(jī)器人的數(shù)量。

圖10是利用免疫優(yōu)化算法得到的調(diào)度方案示意圖。對(duì)比圖6和圖10兩種算法得到的調(diào)度方案示意圖可以直觀地看出，免疫優(yōu)化算法在機(jī)器人任務(wù)分配上面更加趨于合理。對(duì)應(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)化算法通過(guò)免疫算法進(jìn)行確定初始信息素后，使得蟻群算法能更快的收斂趨于穩(wěn)定，大大減少了蟻群算法前期信息素沉淀的時(shí)間。并且對(duì)比表5和表6的數(shù)據(jù)，免疫蟻群優(yōu)化算法在運(yùn)行時(shí)間和機(jī)器人群的搬運(yùn)距離上都有一定的改善。

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

圖12 對(duì)比實(shí)驗(yàn)數(shù)據(jù)柱狀圖

表7 對(duì)比實(shí)驗(yàn)數(shù)據(jù)

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

5 結(jié)論

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