梁金琳, 薛頌東, 趙 靜, 潘理虎

1(太原科技大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院, 太原 030024)

2(廣東機(jī)電職業(yè)技術(shù)學(xué)院, 廣州 510515)

以亞馬遜Kiva機(jī)器人為代表的智能倉(cāng)儲(chǔ)揀貨技術(shù), 將傳統(tǒng)的“人到貨”模式革命性地升級(jí)為“貨到人”模式, 極大適應(yīng)了現(xiàn)代物流配送發(fā)貨單位小型化的特點(diǎn)[1].倉(cāng)庫(kù)規(guī)模擴(kuò)大和訂單數(shù)激增, 進(jìn)一步要求提升揀貨效率, 由此提出了面向智能倉(cāng)儲(chǔ)調(diào)度的群機(jī)器人任務(wù)分配問(wèn)題[2].其屬于一類NP-Hard問(wèn)題[3], 通常采用啟發(fā)式算法解決.Azadnia等[4]借鑒旅行商問(wèn)題的求解思路,用遺傳算法對(duì)訂單任務(wù)進(jìn)行排序, 使分揀人員走過(guò)的路程最短, 但其復(fù)雜性隨任務(wù)量增加顯著提高.沈博文等[5]將機(jī)器人狀態(tài)設(shè)置為“忙”“閑”兩種, 通過(guò)修正A*算法實(shí)現(xiàn)特殊道路條件約束下的倉(cāng)儲(chǔ)調(diào)度, 但該法僅適合小規(guī)模任務(wù)情形.郭宇[6]提出一種基于市場(chǎng)拍賣思想的多機(jī)器人任務(wù)分配方法, 通過(guò)性能差值的直觀比較, 確定各機(jī)器人的競(jìng)標(biāo)價(jià)格, 生成較優(yōu)的任務(wù)分配方案.該法雖回避了組合和整數(shù)規(guī)劃中的復(fù)雜運(yùn)算,適合較大數(shù)量子系統(tǒng)之間的交互, 但對(duì)通信要求較高.蔣家志等[7]使用一種改進(jìn)的微粒群算法(PSO)解決訂單調(diào)度問(wèn)題, 主要優(yōu)化目標(biāo)為同一訂單中所有任務(wù)的完工時(shí)間與該訂單總完工時(shí)間的相聚程度, 提高了智能倉(cāng)儲(chǔ)的運(yùn)行效率, 但未考慮機(jī)器人的平均利用率, 可能導(dǎo)致部分機(jī)器人負(fù)擔(dān)過(guò)重.楊杰[8]引入訂單池概念,以訂單池中與分揀臺(tái)上訂單的適應(yīng)度為標(biāo)準(zhǔn), 使用離散PSO生成各分揀臺(tái)上的任務(wù)執(zhí)行順序.該法在處理大規(guī)模訂單時(shí), 容易產(chǎn)生早熟收斂現(xiàn)象, 且局部尋優(yōu)能力較差, 無(wú)法找到最優(yōu)分配規(guī)則.李功捷[9]引入虛擬任務(wù)概念和任務(wù)數(shù)分配思想, 通過(guò)智能優(yōu)化算法求解智能倉(cāng)儲(chǔ)調(diào)度的機(jī)器人任務(wù)分配問(wèn)題.

每種群體智能算法各有優(yōu)缺點(diǎn).發(fā)揮各自優(yōu)勢(shì),提高求解效率, 是不同算法融合的動(dòng)機(jī).作為經(jīng)典的啟發(fā)式算法, 許多學(xué)者對(duì)蟻群算法和遺傳算法的融合進(jìn)行了大量研究, 以克服或抑制各自缺陷, 實(shí)現(xiàn)優(yōu)勢(shì)互補(bǔ).融合算法大體上分為兩類: 一類是以蟻群算法為主體,利用遺傳算法產(chǎn)生的結(jié)果作為信息素進(jìn)行尋優(yōu)[10].該法雖能夠改善蟻群算法初期信息素匱乏的問(wèn)題, 但在遺傳算法階段一旦陷入局部最優(yōu), 后續(xù)的蟻群算法將很難跳出, 且蟻群算法本身也很可能因收斂速度過(guò)快陷入局部最優(yōu).為解決該問(wèn)題, 在固定次數(shù)迭代后又引入遺傳操作, 加大種群分布多樣性, 但花費(fèi)的時(shí)間代價(jià)高, 不適合實(shí)時(shí)應(yīng)用場(chǎng)景[11].另一類是以遺傳算法為主體, 利用蟻群算法快速收斂的特性進(jìn)行問(wèn)題求解[12], 提高了全局尋優(yōu)能力, 但主要用于求解旅行商問(wèn)題.

本文在前人研究的基礎(chǔ)上, 根據(jù)智能倉(cāng)儲(chǔ)調(diào)度中多訂單任務(wù)動(dòng)態(tài)產(chǎn)生、任務(wù)由群機(jī)器人并發(fā)執(zhí)行的特點(diǎn), 將問(wèn)題建模成群機(jī)器人協(xié)同調(diào)度的多目標(biāo)優(yōu)化問(wèn)題.利用蟻群算法產(chǎn)生的較為優(yōu)秀的解集, 作為遺傳算法的初始種群, 以加快遺傳算法的收斂速度.在遺傳算法中采用多層編碼, 以適應(yīng)群機(jī)器人任務(wù)分配需求, 在輪盤賭算子后引入精英保留策略, 對(duì)選擇算子進(jìn)行改進(jìn), 并增加逆轉(zhuǎn)算子, 在保證種群多樣性的同時(shí), 使最優(yōu)個(gè)體能夠直接遺傳到下一代.通過(guò)多種技術(shù)手段的綜合運(yùn)用, 設(shè)計(jì)了一種新的蟻群-遺傳算法融合框架.仿真結(jié)果表明, 在本文提出的融合框架中求解, 較分別使用蟻群算法或遺傳算法求解, 能夠明顯發(fā)揮蟻群算法魯棒性好和遺傳算法全局搜索能力強(qiáng)的特點(diǎn), 且算法性能穩(wěn)定, 有效提高智能倉(cāng)庫(kù)的整體運(yùn)行效率.

1 問(wèn)題描述

如圖1所示, 由貨架、移動(dòng)機(jī)器人、分揀臺(tái)等組成智能倉(cāng)儲(chǔ)系統(tǒng), 設(shè)置有出入口與外界相通, 機(jī)器人能將訂單上商品對(duì)應(yīng)的貨架按照一定次序送至分揀臺(tái),由等候的倉(cāng)庫(kù)工作人員按系統(tǒng)指示從貨架上取出相應(yīng)數(shù)量的商品, 放入訂單對(duì)應(yīng)的包裝箱中打包配送.現(xiàn)有一批訂單, 包含貨物的品類數(shù)為n, 要求由m個(gè)成員機(jī)器人組成的群機(jī)器人處理.假設(shè)倉(cāng)庫(kù)為封閉的二維空間, 一個(gè)貨架上只存放一種商品, 則可用貨架位置表征特定品類商品對(duì)應(yīng)的任務(wù), 記任務(wù)集C= {1, 2, …,n}.設(shè)i,j為貨架(任務(wù))編號(hào),i,j∈C, 機(jī)器人從貨架i運(yùn)動(dòng)到j(luò)的距離為Dij, 倉(cāng)庫(kù)中空閑機(jī)器人的數(shù)量為r.規(guī)定成員機(jī)器人執(zhí)行的最少任務(wù)數(shù)為L(zhǎng).對(duì)環(huán)境進(jìn)行柵格化建模[13].考慮機(jī)器人避碰, 貨架間設(shè)置兩條通道, 供機(jī)器人相向通行.將各柵格設(shè)置的二維碼視為路標(biāo), 用于機(jī)器人定位.為簡(jiǎn)便起見, 追加如下假設(shè):

圖1 簡(jiǎn)化的智能倉(cāng)儲(chǔ)系統(tǒng)

(1) 每個(gè)機(jī)器人占據(jù)一個(gè)柵格, 以柵格為單位移動(dòng),運(yùn)動(dòng)方向限定為上、下、左、右.

(2) 為避免機(jī)器人碰撞, 貨架區(qū)域間由柵格組成的通道均為單行道.

(3) 機(jī)器人的感知、定位、交互、運(yùn)算、運(yùn)動(dòng), 以及托舉重物的能力相同.

群機(jī)器人的任務(wù)分配流程為: 中央處理器接收到訂單任務(wù), 查表得到商品所在貨架位置, 生成機(jī)器人的調(diào)度方案; 機(jī)器人運(yùn)動(dòng)到相應(yīng)貨架并將其托舉至分揀臺(tái); 分揀臺(tái)處等候的工作人員按訂單要求取下貨架上的商品; 機(jī)器人將貨架送回原位置, 該次任務(wù)完成.

對(duì)于一個(gè)訂單任務(wù), 由于商品種類及貨架位置均已確定, 故機(jī)器人在貨架與分揀臺(tái)間的行走距離也已確定.這便意味著, 群機(jī)器人任務(wù)分配的優(yōu)化目標(biāo), 為機(jī)器人完成相應(yīng)于時(shí)序相連的兩個(gè)任務(wù)(貨架)的過(guò)程.由于機(jī)器人只能沿柵格移動(dòng), 記柵格位置坐標(biāo)(x,y),故貨架之間的距離用曼哈頓距離計(jì)算, 見式(1):

其中,xi,yi和xj,yj分別為第i, j個(gè)任務(wù)對(duì)應(yīng)貨架在柵格地圖中的橫坐標(biāo)和縱坐標(biāo).

根據(jù)智能倉(cāng)儲(chǔ)系統(tǒng)的優(yōu)化目標(biāo), 將任務(wù)分配評(píng)價(jià)指標(biāo)定義為路徑代價(jià)和時(shí)間代價(jià)的綜合.其中, 路徑代價(jià)為機(jī)器人在目標(biāo)任務(wù)間行走的距離.構(gòu)造如式(2)所示的適應(yīng)度函數(shù), 作為評(píng)價(jià)指標(biāo):

其中,PAC為路徑代價(jià), 即完成所有任務(wù)全部機(jī)器人走過(guò)的距離之和;TAC為時(shí)間代價(jià), 即全部機(jī)器人完成所有任務(wù)花費(fèi)的時(shí)間;A,B是路徑代價(jià)和時(shí)間代價(jià)的權(quán)重.由于完成任務(wù)花費(fèi)的時(shí)間與機(jī)器人的行走距離有關(guān), 故將完成任務(wù)時(shí)行走距離最大的機(jī)器人走過(guò)的距離值作為時(shí)間代價(jià).為避免誤解, 同時(shí)作距離量綱到時(shí)間量綱的處理.可見, 適應(yīng)度函數(shù)值越小, 表明完成任務(wù)的代價(jià)越小, 即全部機(jī)器人完成任務(wù)走過(guò)的距離越短, 任務(wù)分配越合理.

2 蟻群算法求解任務(wù)分配問(wèn)題

用蟻群算法[14]建模并求解任務(wù)分配問(wèn)題.螞蟻之間通過(guò)覓食過(guò)程中釋放的“信息素”進(jìn)行間接通信, 選擇較優(yōu)路徑, 形成正反饋, 經(jīng)過(guò)多次迭代找到最優(yōu)路徑.

表示任務(wù)數(shù)和機(jī)器人數(shù)的符號(hào)意義保持不變.將其轉(zhuǎn)化為(n+m-1)個(gè)任務(wù)的單機(jī)器人問(wèn)題.由于機(jī)器人的能力相對(duì)有限, 故限定機(jī)器人執(zhí)行的最大任務(wù)數(shù)為lr.首先給每只螞蟻隨機(jī)分配一個(gè)初始任務(wù), 待初始任務(wù)完成, 將其加入禁忌表, 然后從未完成的任務(wù)中選擇一個(gè).當(dāng)?shù)趓個(gè)機(jī)器人完成的任務(wù)數(shù)等于最大任務(wù)數(shù)lr時(shí), 螞蟻選擇下一個(gè)機(jī)器人執(zhí)行其余任務(wù), 直到所有任務(wù)完成為止.t時(shí)刻螞蟻k由任務(wù)i到j(luò)的狀態(tài)轉(zhuǎn)移概率見式(3):

其中, τij(t)表示任務(wù)i和j之間的信息素強(qiáng)度, ηij表示任務(wù)i和j間啟發(fā)式因子的強(qiáng)度, α、 β 分別是信息素重要程度因子和啟發(fā)函數(shù)重要程度因子, 用于調(diào)節(jié)τij(t)和 ηij之間的作用, σ表示機(jī)器人還未完成的任務(wù), 即不在禁忌表中的任務(wù).t+n時(shí)刻螞蟻釋放的信息素濃度,按式(4)所示規(guī)律更新:

其中, ρ為信息素?fù)]發(fā)因子, ( 1 -ρ)則為信息素殘留因子, Δ τij為本次循環(huán)任務(wù)i到j(luò)的信息素增量, 見式(5):

其中,Q為信息素強(qiáng)度系數(shù),Lk表示第k只螞蟻本次循環(huán)所走過(guò)的路徑長(zhǎng)度.群機(jī)器人任務(wù)分配求解的蟻群算法流程見算法1.

算法1.蟻群算法解決任務(wù)分配開始參數(shù)初始化隨機(jī)產(chǎn)生m只螞蟻的初始位置當(dāng)不滿足終止要求:對(duì)于每一只螞蟻k:根據(jù)式(3)計(jì)算狀態(tài)轉(zhuǎn)移概率選擇任務(wù)更新禁忌表結(jié)束當(dāng)m只螞蟻搜索完畢:記錄本次迭代最佳路線按式(4)-式(6)更新信息素禁忌表清零結(jié)束結(jié)束

3 遺傳算法求解任務(wù)分配問(wèn)題

用遺傳算法[15]求解群機(jī)器人任務(wù)分配問(wèn)題.為解決收斂速度慢和封閉競(jìng)爭(zhēng)問(wèn)題, 定義虛擬任務(wù)并加入列表.為了使虛擬任務(wù)不影響代價(jià)計(jì)算, 規(guī)定虛擬任務(wù)間的關(guān)聯(lián)代價(jià)為無(wú)窮, 虛擬任務(wù)與真實(shí)任務(wù)間的代價(jià)以及虛擬任務(wù)的自身代價(jià)為0.群機(jī)器人任務(wù)分配的遺傳算法求解流程見算法2.

算法2.遺傳算法解決任務(wù)分配開始初始化參數(shù)初始化種群中m條染色體編碼當(dāng)不滿足終止要求:計(jì)算個(gè)體適應(yīng)度值遺傳操作結(jié)束解碼輸出最優(yōu)結(jié)果結(jié)束

4 蟻群-遺傳融合框架及其求解

4.1 基本思想

蟻群算法具有較強(qiáng)的魯棒性, 對(duì)初始路線要求不高, 求解結(jié)果不依賴于初始路線選擇, 但收斂速度慢,易陷入局部最優(yōu), 且計(jì)算開銷大.遺傳算法全局搜索能力強(qiáng), 不會(huì)陷入局部最優(yōu)解的快速下降陷阱, 但搜索速度較慢, 對(duì)初始種群依賴性強(qiáng), 局部搜索能力差.為發(fā)揮兩種算法各自的優(yōu)勢(shì), 提高收斂速度和執(zhí)行效率, 提出一個(gè)蟻群-遺傳算法融合框架.基于該框架的群機(jī)器人任務(wù)分配算法流程見算法3.

算法3.蟻群-遺傳算法融合框架內(nèi)的群機(jī)器人任務(wù)分配開始初始化參數(shù)隨機(jī)產(chǎn)生m只螞蟻的初始位置對(duì)于每一個(gè)螞蟻k:根據(jù)式(3)計(jì)算狀態(tài)轉(zhuǎn)移概率選擇任務(wù)更新禁忌表結(jié)束當(dāng)m只螞蟻搜索完畢:將蟻群算法一次迭代所得解集作為遺傳算法初始種群種群編碼當(dāng)不滿足終止要求:根據(jù)式(2)計(jì)算個(gè)體適應(yīng)度值do{輪盤賭法從種群中選擇一定比例父代精英保留策略選出最佳父代直接保存其余個(gè)體分別進(jìn)行交叉、變異、逆轉(zhuǎn)操作}結(jié)束獲得任務(wù)分配最優(yōu)解結(jié)束

不難看出, 融合框架的設(shè)計(jì)思路為, 利用蟻群算法,經(jīng)過(guò)一次迭代后產(chǎn)生一個(gè)較為優(yōu)秀的解集, 將其作為遺傳算法的初始種群, 以有效減少遺傳算法的尋優(yōu)次數(shù), 快速找到最優(yōu)解.

4.2 操作要點(diǎn)

(1) 種群初始化.遺傳算法的初始種群通常是隨機(jī)生成的, 雖然保證了個(gè)體的多樣性, 但隨機(jī)生成的初始種群在迭代過(guò)程中收斂速度緩慢, 導(dǎo)致遺傳算法尋優(yōu)速度慢.本文將蟻群算法經(jīng)過(guò)一次迭代后產(chǎn)生的解集作為遺傳算法的初始種群, 使遺傳算法獲得較為優(yōu)秀的初始種群, 有效減少遺傳算法的尋優(yōu)次數(shù).

(2) 編碼.遺傳算法采用多層編碼方式, 第1層編碼為任務(wù)的執(zhí)行順序, 第2層編碼為機(jī)器人之間執(zhí)行任務(wù)中斷點(diǎn)的位置.

(3) 選擇算子.采用輪盤賭法選擇一定比例的父代,再通過(guò)精英保留策略, 挑選出最佳父代, 直接保存在下一代中.采用這種方法可以在保證個(gè)體多樣性的同時(shí),還可以使最佳個(gè)體直接遺傳到下一代中.

(4) 交叉算子.采用部分映射交叉方式, 在染色體編碼串中隨機(jī)選擇兩個(gè)交叉點(diǎn), 然后進(jìn)行部分基因的交換, 得到新的個(gè)體.

(5) 變異算子.采用互換變異的方式, 隨機(jī)選擇兩個(gè)基因位置, 然后將這兩個(gè)基因位置的編碼交換, 獲得一個(gè)新的個(gè)體.染色體中基因互換過(guò)程見圖2.

圖2 變異算子操作過(guò)程

(6) 逆轉(zhuǎn)操作.為加速進(jìn)化加入逆轉(zhuǎn)操作, 這里的逆轉(zhuǎn)操作具有單向性, 即加入逆轉(zhuǎn)操作后產(chǎn)生的個(gè)體更優(yōu)才會(huì)進(jìn)行.隨機(jī)產(chǎn)生兩個(gè)隨機(jī)數(shù)n1和n2(n1,n2∈n,n1≠n2), 將n1與n2間的基因反向排序, 得到新個(gè)體.以n=8,n1=3,n2=6為例的逆轉(zhuǎn)操作見圖3.

圖3 逆轉(zhuǎn)操作過(guò)程

5 仿真

仿真在Matlab 2018b的平臺(tái)上進(jìn)行.將尺寸為100 m×102 m的實(shí)驗(yàn)環(huán)境建模為柵格地圖, 單位長(zhǎng)度為 1m.貨架的位置坐標(biāo)設(shè)置后, 任務(wù)隨機(jī)生成.設(shè)置螞蟻數(shù)=80, 信息素重要程度因子α=1, 啟發(fā)函數(shù)重要程度因子β=5, 遺傳算法種群數(shù)=80, 最大迭代次數(shù)=5000.

考慮到倉(cāng)庫(kù)存在空閑期和繁忙期, 分別用蟻群算法、遺傳算法和本文所提的融合算法, 針對(duì)小任務(wù)量和中大任務(wù)量情形, 進(jìn)行任務(wù)分配實(shí)驗(yàn).

5.1 小任務(wù)量情形

設(shè)置空閑移動(dòng)機(jī)器人數(shù)量=4, 隨機(jī)生成任務(wù)數(shù)=20,每個(gè)機(jī)器人執(zhí)行5個(gè)任務(wù), 分別使用蟻群算法、遺傳算法和融合算法, 對(duì)群機(jī)器人任務(wù)分配進(jìn)行控制, 收斂過(guò)程見圖4.

圖4顯示, 融合算法在迭代300次左右時(shí), 適應(yīng)度函數(shù)值趨于穩(wěn)定; 而蟻群算法和遺傳算法分別在在迭代4000和2000次后, 適應(yīng)度函數(shù)值逐漸穩(wěn)定于200左右.表明融合算法的收斂速度較蟻群算法和遺傳算法快, 且結(jié)果也優(yōu)于其他兩種算法.究其原因, 融合算法在迭代開始時(shí)就有較為優(yōu)秀的種群, 在迭代過(guò)程中可以快速跳出局部最優(yōu), 收斂性強(qiáng), 適應(yīng)度函數(shù)值接近于最終穩(wěn)定的結(jié)果.因此, 對(duì)于小規(guī)模的任務(wù)分配, 本文所提融合算法能夠快速尋求較優(yōu)的任務(wù)分配結(jié)果,進(jìn)而提高智能倉(cāng)庫(kù)的整體運(yùn)行效率.

圖4 小任務(wù)量分配情形典型迭代過(guò)程(任務(wù)數(shù)=20, 機(jī)器人數(shù)=4)

5.2 中大規(guī)模任務(wù)量情形

(1) 固定任務(wù)數(shù)=100, 分別令機(jī)器人數(shù)=10, 20, 30,40, 50, 每組實(shí)驗(yàn)重復(fù)執(zhí)行30次, 統(tǒng)計(jì)結(jié)果見圖5.

圖5 不同規(guī)模群機(jī)器人完成100個(gè)任務(wù)的代價(jià)

結(jié)果顯示, 隨著機(jī)器人數(shù)量增加, 群機(jī)器人完成任務(wù)花費(fèi)的路徑代價(jià)和時(shí)間代價(jià)逐漸降低.通過(guò)折線圖可以直觀看出, 本文提出的融合算法無(wú)論是走過(guò)的路程還是花費(fèi)的時(shí)間, 都明顯優(yōu)于單獨(dú)采用蟻群算法和遺傳算法時(shí)的任務(wù)分配效果, 體現(xiàn)出較高效率.在執(zhí)行固定數(shù)量的任務(wù)時(shí), 采用融合算法進(jìn)行任務(wù)分配, 機(jī)器人完成全部任務(wù)花費(fèi)的時(shí)間比單獨(dú)采用蟻群算法和遺傳算法少50%以上, 融合算法具有明顯優(yōu)勢(shì), 大大提高了智能倉(cāng)庫(kù)的整體工作效率.在機(jī)器人數(shù)=10, 20, 30,40時(shí), 融合算法的路徑代價(jià)呈現(xiàn)線性下降的趨勢(shì); 當(dāng)機(jī)器人數(shù)=50時(shí), 下降趨勢(shì)減緩.其原因可能是, 隨機(jī)器人數(shù)增多, 倉(cāng)庫(kù)中逐漸變得擁擠; 當(dāng)執(zhí)行任務(wù)的機(jī)器人過(guò)多時(shí), 會(huì)導(dǎo)致每個(gè)機(jī)器人分配的任務(wù)數(shù)過(guò)少, 無(wú)法充分發(fā)揮機(jī)器人的價(jià)值, 造成資源浪費(fèi).

(2) 固定機(jī)器人數(shù)=10, 分別令任務(wù)數(shù)=50, 100, 150,200, 每組實(shí)驗(yàn)重復(fù)執(zhí)行30次, 統(tǒng)計(jì)結(jié)果見圖6.

圖6 10個(gè)機(jī)器人分別完成不同數(shù)量任務(wù)的代價(jià)

不難發(fā)現(xiàn), 群機(jī)器人數(shù)不變時(shí), 隨著任務(wù)增加, 花費(fèi)的路徑代價(jià)和時(shí)間代價(jià)都隨之增加.

使用融合算法和單獨(dú)使用蟻群算法進(jìn)行任務(wù)分配,雖然在路徑代價(jià)上沒(méi)有明顯差別, 但前者的時(shí)間代價(jià)遠(yuǎn)小于后者.在任務(wù)數(shù)超過(guò)150后, 采用遺傳算法進(jìn)行任務(wù)分配花費(fèi)的路徑代價(jià)和時(shí)間代價(jià)增加速度變快,完成任務(wù)機(jī)器人所走的路程以及花費(fèi)的時(shí)間變大, 而融合算法則在任務(wù)數(shù)超過(guò)150后, 花費(fèi)的路徑代價(jià)和時(shí)間代價(jià)增加趨勢(shì)減緩.

使用融合算法進(jìn)行任務(wù)分配, 路徑代價(jià)和時(shí)間代價(jià)均優(yōu)于單獨(dú)使用遺傳算法.

本組實(shí)驗(yàn)結(jié)果表明, 本文提出的融合算法在中大規(guī)模智能倉(cāng)儲(chǔ)系統(tǒng)的任務(wù)分配效率更高.

通過(guò)兩組實(shí)驗(yàn)可以發(fā)現(xiàn), 蟻群算法收斂速度慢, 易陷入局部最優(yōu), 且計(jì)算開銷大.遺傳算法搜索速度較慢,對(duì)初始種群依賴性強(qiáng), 局部搜索能力差.采用融合算法進(jìn)行任務(wù)分配, 相較單獨(dú)使用蟻群算法或遺傳算法, 時(shí)間代價(jià)明顯為少.隨著任務(wù)數(shù)增加, 融合算法體現(xiàn)出更高的效率.

計(jì)算兩種變量固定情形下的路徑相對(duì)誤差SP和時(shí)間相對(duì)誤差ST.計(jì)算方法見式(7)和式(8):

其中,RiP,RiT分別是第i次實(shí)驗(yàn)的路徑代價(jià)和時(shí)間代價(jià),分別是n次實(shí)驗(yàn)路徑代價(jià)和時(shí)間代價(jià)的平均值, 結(jié)果見表1和表2中, ACO_GA_P, ACO_GA_T為融合算法分別對(duì)應(yīng)的路徑代價(jià)和時(shí)間代價(jià), GA_P,GA_T為遺傳算法分別對(duì)應(yīng)的路徑代價(jià)和時(shí)間代價(jià),ACO_P, ACO_T為蟻群算法分別對(duì)應(yīng)的路徑代價(jià)和時(shí)間代價(jià).

表1 不同數(shù)量機(jī)器人完成100個(gè)任務(wù)的相對(duì)誤差

表2 10個(gè)機(jī)器人完成不同數(shù)量任務(wù)的相對(duì)誤差

結(jié)果顯示, 任務(wù)量確定時(shí), 隨著機(jī)器人數(shù)增加, 相對(duì)誤差逐漸變小; 機(jī)器人數(shù)確定時(shí), 隨著執(zhí)行的任務(wù)數(shù)增加, 相對(duì)誤差逐漸變大.可見, 作為啟發(fā)式算法, 不同組合條件下都存在隨機(jī)性.但本文所提融合算法的代價(jià), 其相對(duì)誤差均較單獨(dú)使用蟻群算法和遺傳算法更小, 表明融合算法的性能較為穩(wěn)定.

6 討論

本文針對(duì)智能倉(cāng)儲(chǔ)調(diào)度中群機(jī)器人任務(wù)分配問(wèn)題,提出了一個(gè)適用于不同任務(wù)規(guī)模的蟻群-遺傳算法融合框架, 通過(guò)仿真實(shí)驗(yàn)得到以下結(jié)論:

(1) 蟻群算法具有較強(qiáng)的魯棒性, 采用蟻群算法解決群機(jī)器人任務(wù)分配問(wèn)題時(shí)對(duì)初始路線要求不高, 求解結(jié)果不受初始路線的影響, 局部搜索能力強(qiáng).但蟻群算法收斂速度慢, 易陷入局部最優(yōu), 且計(jì)算開銷大, 故采用蟻群算法解決群機(jī)器人任務(wù)分配問(wèn)題效率較低.

(2) 單獨(dú)使用遺傳算法解決任務(wù)分配問(wèn)題, 全局搜索能力強(qiáng), 不會(huì)陷入局部最優(yōu)的快速下降陷阱, 但搜索速度較慢, 對(duì)初始種群依賴性強(qiáng), 局部搜索能力差, 故單獨(dú)使用遺傳算法解決該類問(wèn)題執(zhí)行效率較低.

(3) 蟻群-遺傳算法融合框架下, 蟻群算法和遺傳算法各自優(yōu)點(diǎn)得到發(fā)揮, 全局搜索能力強(qiáng), 不會(huì)陷入局部最優(yōu)解, 收斂速度快, 完成任務(wù)的路程代價(jià)和時(shí)間代價(jià)較小, 尋優(yōu)結(jié)果更好, 提高了智能倉(cāng)儲(chǔ)系統(tǒng)的運(yùn)行效率.

(4) 本文提出的融合框架雖可有效提升智能倉(cāng)儲(chǔ)系統(tǒng)任務(wù)分配的效率, 但仍存在不足.主要是, 成員機(jī)器人一次只能執(zhí)行一個(gè)訂單任務(wù)、未考慮動(dòng)態(tài)訂單分配等.未來(lái)研究將圍繞倉(cāng)庫(kù)動(dòng)態(tài)訂單分配進(jìn)行, 以不斷接近智能倉(cāng)儲(chǔ)系統(tǒng)的實(shí)際工作情形.