面向堆垛機路徑優化的局部搜索自適應遺傳算法①

史勤政,王 嵩,李冬梅,高 岑,田月

1(中國科學院大學,北京 100049)

2(中國科學院 沈陽計算技術研究所,沈陽 110168)

近年來,隨著物流行業的發展,現代倉儲物流企業對自動化倉庫AS/RS (Automated Storage and Retrieval System)的效率要求也越來越高,在AS/RS 中,出入庫貨物搬運任務完全由自動化巷道式堆垛機來負責完成,堆垛機作為AS/RS的核心設備,其調度問題對倉庫的管理效率起決定性作用,目前,倉庫的堆垛機調度路徑往往采用直接指派的方式,導致堆垛機的運行效率低、時間和能耗較高.良好的堆垛機存取路徑優化可以降低倉儲成本,提高AS/RS的利用率,對倉庫管理效率的提升具有很大的現實意義.

通過對堆垛機的運動模式和物理特性進行分析,發現其調度問題要考慮時間、能耗、作業效率等因素,這3 個因素顯然不能同時達到最佳,那么就需要一些方法來進行協調,傳統的方法是將多個目標函數通過權重分配的方式降維成單個目標函數,轉換成單目標優化的問題,這種方式存在權重量化設定困難和易于陷入局部最優等問題.本文采用多目標優化方式[1]來解決路徑優化問題,對多個無法同時達到最優的目標進行協調,產生一組Pareto 最優解[2]路徑,供倉庫控制系統自行選擇.

針對堆垛機調度問題,關榆君等[3]采用引入了交算子和交序列的貓群算法,但無法得到Pareto 最優解集,依舊是單目標優化的變種.針對多目標優化問題,Srinivas和Deb 在NSGA的基礎上提出了NSGA-Ⅱ算法[4]來求pareto 最優解集,NSGA-Ⅱ算法使用了快速非支配解排序算法降低復雜度、引進了精英策略來保證優良個體得以保留、采用擁擠度替代了共享適應度,NSGA-Ⅱ算法以運行速度快、解集收斂性好、簡單有效等特點在多目標優化領域得以廣泛應用,尤其對于低維多目標優化問題具有明顯優勢[5],但仍存在著容易陷入局部最小值、局部搜索能力不足等問題[6].因此,本文在NSGA-Ⅱ的基礎上進行改進與優化,對NSGA-Ⅱ算法易陷入局部最優的問題采用引入自適應遺傳算子的方式進行了改善,并新增了局部隨機搜索策略增強局部搜索能力.通過實驗證明了新方法對比NSGA-Ⅱ算法在堆垛機調度問題中的有效性.

1 堆垛機調度模型

1.1 問題描述

以連云港某家氨綸公司的自動化無人倉庫為研究對象,該倉庫為同端出/入布局,即入庫口與出庫口在巷道的同一側,貨架沿通道排列,堆垛機按指令沿通道運行,進行貨架上貨物的揀選作業.圖1為部分示意圖.

圖1 自動化無人倉庫部分示意圖

本文主要研究的是單一堆垛機面對多任務時,如何合理的設計調度路徑.從時間、能耗、批作業效率3 個方面考慮,這3 個指標不能同時達到最優,故運用算法產生一組Pareto 最優解,供倉庫控制系統自行選擇,從而節約堆垛機的使用費用,提高倉庫的搬運效率.

1.2 模型建立

堆垛機的運行可以歸類為TSP 問題,即機器從起點出發,一次性經過多個揀選點又回到起點的路徑問題.考慮到堆垛機在運行過程中的時間、能耗以及作業效率,對堆垛機的調度路徑進行建模.分別從時間、能耗、批作業效率3 個方面建立優化目標.

其中,ti(i+1)表示從堆垛機從第i個貨位點到第i+1 個貨位點的時間,ei(i+1)表示堆垛機從第i個貨位點到第i+1 個貨位點的能耗,t0i表示堆垛機從初始位到第i個貨位點的時間(即第i個貨位任務的等待時間),fi表示第i個貨位點貨物的優先級(數字越小表示優先級越高),T表示堆垛機完成一批次調度任務的總耗時,E表示堆垛機完成一批次調度任務的總耗能,Eff表示批作業的效率.

其中,(xi,yi)表示第i個貨位點在貨架中的坐標,L為一個貨位的長度,H為一個貨位的高度,ex為移動單位貨格長度的基礎能耗,ey為移動單位貨格高度的基礎能耗,V(x)為堆垛機變加速運動過程的平均速度,僅與移動距離有關.

2 基于局部隨機策略的自適應遺傳算法

在解決多目標優化問題時,NSGA-Ⅱ算法作為較為經典的一種算法一直得到廣泛的應用,但將其應用到堆垛機調度問題中時,發現NSGA-Ⅱ算法容易陷入局部最優,并在搜索能力上有所不足,因此,本文在NSGA-Ⅱ算法的基礎上從遺傳算子著手進行了改進,并加入了局部隨機搜索策略,得到了一種加入局部搜索策略的自適應遺傳算法(IMOGA).

2.1 染色體編碼

本文采用對堆垛機的貨位點揀選順序進行編碼的方式,染色體由多個基因組成,每個基因表示貨架上的貨格編號,以25 列20 行的貨架為例,采用行優先的方式對貨格進行編號,第1 行第1 列編號為0,第1 行第2 列編號為1,依次類推,一直到編號4999.以長度為5的染色體為例,染色體[43,54,2,386,123]表示堆垛機共經過5 個點,依次為43,54,2,386,123 號貨位.

2.2 自適應遺傳算子

在進化過程中,出現堆垛機路徑序列部分貨位點相鄰的情況,以25 列20 行的貨架為例,對于55 號貨位,20、54、56、80 號貨位都與它相鄰,如圖2所示.為了保證堆垛機的運行效率,對于這樣的相鄰貨位點序列,在交叉變異過程中,應當保證相鄰貨位點序列不被破壞.出于以上考慮,對交叉、變異操作進行了改進.

圖2 貨位示意圖

交叉操作采用改進的基于位置的交叉,首先根據染色體長度L與隨機位置數z的關系公式z=,隨機生成z個隨機交叉位置,在初始待優化序列中找到對應位置的基因,作為保留位置基因,并在基因的左右位置上進行探測,是否存在該基因對應的臨近貨位編碼基因,若存在,擴展進保留位置基因中,父代兩個個體間保留位置基因依序交換,然后依次在未保留位插入剩余基因.譬如,對于初始待優化序列[45,287,2,467,3642,264,2182,20,466,9],隨機生成3 個位置1、4、10,對應保留位置基因45、467、9,對于兩個父代[264,466,9,2,45,20,3642,2182,467,287]和[2,9,20,2182,3642,466,467,287,264,45],搜索臨近位置基因,發現存在相鄰貨位點基因序列[45,20]和[466,467],拓展保留基因為[45,46][466,467][9],基于交叉位置進行交換,依次在未保留位插入剩余基因,得到子代,如圖3所示.

圖3 改進后的交叉操作

變異操作采用隨機位置的互換操作,根據染色體長度L與變異點z的關系公式z=,隨機生成z個變異點,若變異點左右位置上存在該變異點基因對應的臨近貨位基因,則將變異點進行延拓,循環交換這z個變異點的基因段.譬如,對于父代[264,45,20,9,2,466,467,287,2182,3642],隨機生成3 個變異點2、7、9,對應基因45、467、2182,在變異點臨近位置上進行探測,發現存在相鄰貨位點基因序列[45,20]和[466,467],延拓變異點基因段為[45,20][466,467][2182],循環交換基因段,如圖4所示.

圖4 改進后的變異操作

在研究過程中發現,遺傳算子的交叉、變異概率對在很大程度上將影響算法的結果.對于適應度較差的個體,應當給予更高的交叉變異概率,而對于適應度較高的優秀個體,應當給予較低的交叉變異概率[7],因此,根據自適應的思想,使交叉率變異率按照適應度的Sigmoid 曲線進行調整[8],盡力保留優秀個體的同時跳出局部收斂,將遺傳交叉變異概率做如下改進.

其中,pc為交叉概率,pm為變異概率,Pcmax為最大交叉概率,Pcmin為最小交叉概率,favg表示種群的平均適應度,fmax表示種群最大適應度,f′表示待交叉個體中較大的適應度,Pmmax為最大變異概率,Pmmin為最小變異概率,f表示待變異個體的適應度,A=9.903 438,依據Sigmoid曲線特性得來.

2.3 基于模擬退火算法的局部隨機搜索策略

遺傳算法在前期的搜索過程中主要是對解空間進行全局尋優搜索,能夠搜索到最優解集的大致范圍,到了迭代的后期,解集較為集中,就需要考驗算法的局部搜索能力,由于NSGA-Ⅱ算法局部搜索能力不足,難以得到問題的真正解集.出于以上的考慮,本文針對NSGA-Ⅱ遺傳算法局部搜索能力不足的問題,進行了改進,采用了局部隨機搜索策略來幫助算法改善搜索過程.

模擬退火是一種隨機尋優的算法,具有比較強的局部搜索能力,其Metropolis 準則允許一定的概率上接受劣于原解的新解,從而使算法能夠跳離局部最優的陷阱[9],理論上,只要迭代次數足夠,就能夠搜索到全局最優.因此,本文采用基于模擬退火思想的局部隨機搜索策略.模擬退火算法依據Metropolis 準則來判斷是否接受搜索過程中得到的被原始解所支配的新解,新解的接受概率公式為:

其中,f(x1)為新解的目標函數值,f(x0)為原始解的目標函數值,k為Boltzmann 常數,T為進化代對應的熱度,由上式可以看出,接受概率P與熱度T有關,T熱度越高,對被支配解的接受概率越大,T熱度越低,對被支配解的接受概率越小,熱度T的迭代公式為:

其中,T0為模擬退火的初始狀態溫度,t為迭代次數,可以看出,T熱度隨著迭代次數的增加而降低,使得算法迭代前期能夠保留一些“潛力解”,使解空間具有更多的可能性,增加了全局搜索能力,在算法迭代后期,熱度降低,接受被支配解的概率降低,避免丟失較優解,并有一定的概率讓陷入局部最優陷阱的解進行“自救”.基于模擬退火的局部隨機搜索策略步驟如下:

Step 1.設置初始參數:初始狀態溫度T0,迭代次數上限n,鄰域內搜索次數m,鄰域內搜索上限M次.

Step 2.遺傳算法進化得到非劣解集S,非劣解集S中解用xi表示.

Step 3.若在解xi的一定鄰近范圍內隨機搜索得到新解yi,計算ΔE=f(yi)?f(xi),若ΔE<0,則接受新解yi取代xi,跳至Step6;若ΔE≥0,則隨機生成概率r,跳至Step 4.

Step 4.按照新解接受概率公式,若r

Step 5.若m

Step 6.更新溫度T,迭代次數若超過最大次數,終止.否則,返回Step 2.

3 實驗分析

為了驗證本文所述的改進算法IMOGA的性能,針對具體的調度序列,分別采用NSGA-Ⅱ和IMOGA算法進行求解.以連云港某氨綸公司的自動化無人倉庫為例,貨架有11 排,每排有25 列20 層,單個貨位的長和高均為1 m,一臺堆垛機負責一個巷道內的出入庫操作,依照貨位點依次揀選作業,堆垛機貨位揀選點坐標測試數據如下:

針對上述貨位揀選點,分別使用NSGA-Ⅱ、IMOGA算法對堆垛機路徑進行優化.算法參數:初始種群大小100,最大迭代數200,NSGA-Ⅱ的pc=0.8;pm=0.05.IMOGA 算法的M=10;pcmax=0.9;pcmin=0.5;pmmax=0.1;pmmin=0.01;T0=700,兩算法迭代過程如圖5～圖7所示.

圖5 時間原則算法迭代過程

圖6 能耗原則算法迭代過程

圖7 作業效率原則算法迭代過程

由圖5～圖7可見,IMOGA 較NSGA-Ⅱ收斂速度更快,趨于穩定的代數更早,在各個目標函數上的值最優,IMOGA 在收斂過程中存在一些拐點,證明IMOGA在局部隨機搜索策略幫助下,能在一定概率上接受劣解來跳出局部最優.IMOGA 算法求得測試數據(圖8)的一組路徑坐標Pareto 解如圖9～圖11所示.

圖8 初始序列路徑圖

圖9 Pareto 解1 路徑圖

圖10 Pareto 解2 路徑圖

圖11 Pareto 解3 路徑圖

采用Knowles,Corne 提出的解集與參考集的距離指標DIR[10]來衡量解的質量,DIR越小,解的質量越高,DIR公式如下:其中,S j為求得的解集,S?為參考解集,dxy為解y在N維目標空間中到解x的距離,fi?(·)表示解·的第i個目標函數值.dxy公式如下:

分別用NSGA-Ⅱ、IMOGA 算法相同條件下運行20 次得到各自的解集,合并并去除非劣解,得到非劣解集作為參考集S?.得到趨于穩定的平均迭代次數和DIR指標如表1所示.

表1 算法平均性能比較

由表1可以看出,在堆垛機調度問題中,IMOGA算法的DIR與趨于穩定的平均迭代次數均少于NSGA-Ⅱ算法,證明IMOGA 算法的解集質量更高,具有更快的收斂速度,針對堆垛機路徑優化問題具有更強的有效性.

4 結語

本文對同端出入立體倉庫中的堆垛機調度問題進行建模,針對NSGA-Ⅱ算法容易陷入局部搜索能力不足的問題進行了改進,并引入了一種局部隨機搜索策略來幫助算法跳出局部最優,提出了一種根據自適應遺傳算子和局部搜索策略進行改進后的遺傳算法IMOGA.通過實驗分析表明,在堆垛機調度問題上,IMOGA 相較于NSGA-Ⅱ,不論是解的質量還是收斂速度,都具有一定的優勢,證明了算法的有效性.