共享適應度粒子群在雙機ETV中的應用

，

(中國民航大學 電子信息與自動化學院，天津 300300)

0 引言

升降式轉運車(Elevating Transfer Vehicle，ETV)是機場貨運區運輸集裝貨物的轉運工具。許多大型機場在立體倉庫內配置了兩臺甚至更多的ETV同時作業。這些ETV運行在同一巷道內，不可避免的會出現碰撞。另外每個ETV通常擁有兩個貨位，立體倉庫內有兩排貨架，每個貨架有兩個貨位，這些情況都顯著提升了調度過程的復雜度。所以研究雙機雙貨位ETV控制系統對提高機場貨運區轉運效率和減少ETV磨損有著重要的意義。

近年來一些學者對雙機ETV調度算法進行了研究。宋宇博[1]等分析航空貨站AS/RS多端口出入庫的作業方式具有并發性和分布性特點,調度過程具有高密度和高柔性的特點，提出了一種兩階段禁忌搜索算法，并研究了ETV防沖突避讓算法，結果表明,此算法取得了良好的效果。季瓊[2]等使用分配法對專家系統進行改進，建立了雙ETV任務分配調度專家系統的知識庫，提升了機場貨運站的作業效率。YB[3]等使用帶約束的優化模型分析雙機ETV調度問題。以上方法均是基于任務集并結合ETV載物臺的狀態生成任務鏈，該過程建模復雜且不易實現。論文針對這個問題提出一種基于ETV載物臺狀態，結合下一任務屬性生成任務鏈的算法。該算法較基于任務的模型結構更加清晰，編程簡單易行。

標準粒子群算法易陷入局部最優，常見的優化算法采用調節權重、增加變異項等[4-6]。實驗仿真發現，這些優化算法在處理雙機ETV調度問題時雖然有一定的效果，但是跳出局部最優的能力依然較差且出現早熟現象。為了解決這個問題，引入共享適應度函數，改進了粒子群算法。

1 雙機ETV復合調度建模和粒子群算法

ETV所在的立體倉庫結構如圖1所示。

圖1 機場立體倉庫結構示意圖

圖中看出立體倉庫分為兩排，每排有n層m列貨位，ETV載物臺有A、B兩個貨位。每個貨位可裝載一個10號集裝器(Unit Load Device,ULD)，兩個貨位合并可裝載一個20號集裝器。為了描述方便，約定稱10號集裝器為小箱，稱20號集裝器為大箱，并且約定2、3號貨位所在排為內側貨位，1、4號貨位所在排為外側貨位。

機場貨運區立體貨架地址采用排-層-列的順序編碼。例如國內某機場擁有4排5層45列貨架。為了計算方便，將三維編碼按照公式(1)映射為一維編碼。

s=5(x-1)+y+20(z-1)

(1)

式中，s為地址，x為排，y為層，z為列。例如第1排第一層第一列的地址編碼為1，以此類推。

1.1 任務集和任務鏈分析

任務的合集稱之為任務集，任務的屬性包括出、入、倒、盤庫等。每個出/入庫任務選擇最近的出/入口作為其目的/源地址，每個倒/盤庫任務將下一個節點的地址作為其目的地址。每個任務映射為一個向量即C(i)=(srcadd(i),dstadd(i),size(i))，向量內元素依次為：源地址、目的地址、貨物大小。

任務集內的任務按照一定的先后順序組成一個任務序列，這些任務序列的源地址、目的地址首尾相連組成一個任務鏈。任務鏈節點是一個向量即L(i)=(add(i),dis(i))，向量內元素依次為：地址、x軸位移，其中任務鏈節點地址僅包含y、z兩個方向，x軸位移根據每個任務的源/目的地址和貨物大小綜合計算。任務鏈描述的是ETV載物臺在立體倉庫內運動的軌跡。例如任務鏈兩個相鄰節點(add1,-1)、(add2,1)，描述的是ETV載物臺在地址add1處獲取第三排貨位的ULD，然后運動到add2地址處向第三排卸載此ULD。

許多研究人員從任務的角度出發研究ETV的調度問題，分析復雜且易出錯。從任務鏈的角度出發將調度問題簡化為一個具有馬爾科夫性的過程，即：任務鏈的下一個節點狀態僅和當前任務狀態及下一個任務有關，而和任務鏈之前的節點無關。另外基于任務鏈的模型僅計算每個節點x軸方向運行時間和相鄰兩節點運行時間即可計算出總的運行時間，較基于任務的模型結構更加清晰。任務鏈生成步驟如圖2所示。

圖2 生成任務鏈步驟

1.2 按照任務序列生成任務鏈

ETV載物臺有兩個貨位，理論上可以同時載入兩個小箱，但是如果兩個小箱目的地址有競爭，ETV會產生死鎖。解除死鎖的方法主要有4種：①撤銷全部有關任務；②依次撤銷最后加入的任務，直到死鎖消失；③強制剝奪陷入死鎖進程的資源，直到死鎖消失；④調用更多的資源分配給死鎖進程。具體到ETV調度問題有兩種策略避免死鎖：①撤銷最后一個任務；②尋找中轉貨位。文獻[7]證明多數情況下采用中轉貨位策略花費時間長于撤銷最后一個任務策略，為了減少ETV的磨損且減少運行時間,論文采用第二種ETV死鎖避免策略生成任務鏈。

按照任務序列順序，以ETV的兩個載物臺貨位狀態為條件并加入死鎖避免策略，生成任務鏈。假設ETV載物臺的兩個貨位用m1、m2表示，分以下幾種情況：

1)m1、m2均為空。載入下一個任務。

①如果下一任務貨物類型為內側小箱，將任務信息賦值給離此地址最近的載物臺。然后將任務鏈的下一節點賦值為載入任務的源地址和貨物類型。此時載物臺有一個小箱，任務鏈增加了一個節點。

②如果下一任務為外側小箱且目的地址為同側，將任務信息賦值給與任務貨位最近的載物臺貨位，將遠離任務貨位的載物臺貨位的源、目的地址均賦值為與任務貨物相鄰的內側貨位的地址。然后將任務鏈的下一節點賦值為載入任務的源地址和貨物類型。此時載物臺有兩個小箱，任務鏈增加了兩個節點。

③如果下一任務為外側小箱且目的地址為對側，按照距離下一任務的目的地址最節省時間且在對側的空閑貨位為中轉貨位；任務完成后，載物臺上只剩中轉貨物，源地址為中轉貨位地址，目的地址為中轉貨位的原始地址。任務鏈增加了3個節點。第一個節點的地址為中轉貨位地址，貨物類型為1；第二個節點的地址為任務的目的地址，貨物類型為1；第三個節點的地址為中轉貨位地址，貨位類型為1。

③如果下一任務鏈貨物類型為大箱，將任務信息賦值給載物臺所有貨位。將任務鏈的下一節點地址賦值為載入任務的源地址，貨物類型為2。

最后更新立體貨架存貨信息。

2)m1、m2有一個為空。

如果是下一任務貨物類型為大箱，按照死鎖避免策略應當首先清空載物臺再進行裝載，裝載完成時，載物臺上只有一個大箱，載物臺兩貨位信息為大箱的源地址、目的地址和貨物類型。按順序增加兩個任務鏈節點：1、當前任務的目的地址，貨物類型為1；2、下一任務的源地址，貨物類型為2。最后更新立體貨架存貨信息。

如果不是大箱，分幾種情況分析：

①m1有貨，目的地址為同側，直接載入下一任務。當下一任務源地址和m1同側時，將m1賦值給m2，將下一任務的信息賦值給m1。此時載物臺上有兩個貨物。當下一任務源地址和m1異側時，將下一任務信息賦值給m2。

任務鏈增加一個：節點為下一任務的源地址，貨物類型為1。

②m1有貨，目的地址為異側。如果下一任務源地址為m1同側，將m1賦值給m2，下一任務信息賦值給m1，此時載物臺上有兩個貨物。如果下一任務源地址為m1異側目的地址m1異側，將下一任務信息賦值給m2。

任務鏈增加一個：節點為下一任務的源地址，貨物類型為1。

如果下一任務源地址為m1異側目的地址m1同側，此時產生死鎖。使用撤銷策略避免死鎖，首先完成當前任務，然后裝載下一任務，完成時載物臺有一個m2貨物，m2屬性為下一任務屬性，

任務鏈增加兩個：第1節點為當前任務的目的地址，貨物類型為1；第二節點為下一任務的源地址。

③m2有貨，分析方法和第二類m1有貨相似。

3)m1、m2均有貨。

如果ETV載物臺兩貨物均為小箱，選擇離m1、m2目的地址耗時最短的貨位為下一任務鏈節點。①下一任務是卸載m1，將m2賦值給m1，清空m2，增加一個任務鏈節點：m1目的地址。②下一任務是卸載m2，將m1賦值給m2，清空m1，增加一個任務鏈節點：m2目的地址。完成后m1、m2有一個為空。

如果ETV載物臺為一個大箱，下一任務是卸載m1和m2，任務完成后清空m1和m2，任務鏈增加一個節點：地址為m1或m2的目的地址，貨物類型為2。

1.3 使用粒子群算法求任務序列

國內某機場某立體倉庫內擁有一個巷道兩個ETV，雙機ETV調度問題屬于并行調度問題(ParallelMachineShopSchedulingProblem,PMSP)，PMSP是NP完全問題[8]。隨著啟發算法的深入研究，NP完全問題得到了很好的解決。其中粒子群算法結構簡單易行得到了廣泛的應用。

雙機ETV調度問題是帶有約束條件的優化問題，它的適應度函數為式(2)：

pi=max(T1i,T2i)

(2)

式中，T1i、T2i分別表示1號ETV和2號ETV執行任務鏈所用時間。

約束條件如式(3)所示：

(3)

式(3)中，第一行約束條件保證一號ETV運行的區間在第1～40列，第二行約束條件保證二號ETV運行的區間在第5～45列，第三行約束條件保證相同時刻兩ETV之間的距離大于等于4列，第四行和第五行保證兩個任務鏈均屬于任務集，第六行保證兩個子任務集內任意元素不屬于對方任務集。

1.4 雙ETV調度問題粒子編碼

雙機ETV調度要解決的是任務分配問題，將任務、ETV序號映射為粒子的位置，這個過程叫做編碼。相對應的，將粒子位置映射為任務、ETV序號的過程稱之為解碼。

設有40個出入庫任務，則一個粒子需要40個維數，將粒子的每個維數和每個任務一一對應，根據粒子每個維度的坐標確定任務的序列。首先將粒子每個維度的坐標值按照從大到小的順序排列。將坐標值大于0的維度對應的任務分配給1號ETV，將坐標值小于0的維度對應的任務分配給2號ETV。并且每個ETV分配的任務執行順序為粒子坐標值的順序。例如10個粒子分配情況如表1所示。

表1 粒子編碼示例

表中，1號ETV執行的任務序列為8、1、5、7、4；2號ETV執行的任務序列為6、3、2、10、9。

1.5 標準粒子群算法

在一個N維空間中有M個粒子，每個粒子的位置記為xi=(x1,x2,…,xn)，速度記為vi=(v1,v2,…,vn)。在基本粒子群算法中，計算每個粒子的適應度，如果第i個粒子在某次迭代中適應度比以前更優，則更新第i個粒子的最優值并記做pid；選出這些粒子的最優值記做全局最優值并記做pig。按照公式(4)進行位置的迭代。

(4)

式中，w為慣性系數，w等于0.9；c1、c2分別為認知系數和社會系數，c1、c2均等于2；Pid為單粒子最優值；Pig為所有粒子的最優值；r1和r2屬于U(0,1)均勻分布；

繼續迭代，直至滿足停止條件，全局最優解Pig即為模型最優解，對應的粒子位置xig即為最優位置。

1.6 混沌粒子群算法

許多改進的粒子群算法利用復雜的函數調節速度迭代算式，但是仿真結果發現在求解本文問題時容易陷入局部最優。Khare[9]等提出一種混沌迭代粒子群算法，王[10]等增加了一種變異因子。這些算法均提高了跳出局部最優的能力。受此啟發對認知系數和全局系數進行非線性優化。為了提高迭代后期樣本的多樣性，利用混沌算子可以不重復的遍歷吸引域內的所有點的特性，引入Tent混沌算子進行變異。

混沌優化粒子群算法中，位置更新算式如式5所示。

(5)

(6)

2 共享適應度改進粒子群算法

改進的粒子群算法雖然加快了收斂速度，而且在一定程度上提高了收斂效果，但是仍然易出現早熟現象。為了解決這個問題，論文在混沌粒子群算法的基礎上，采用共享函數改進粒子群算法，提高算法的收斂效果。共享適應度算法來源于多峰函數的遺傳算法求解，其思想是將某個小生境內的所有個體的適應度值除以一個和個體數目相關的函數值，用來鼓勵較少個體物種的繁殖。論文借用這個思想在混沌粒子群算法的基礎上，劃定了一個共享半徑，通過共享適應度的方式驅離重新初始化的粒子。

共享函數描述的是兩個粒子之間的相互關系，它的值由此粒子和其他粒子之間的關系決定。增加了共享函數的粒子適應度為式(7)：

(7)

兩個粒子位置向量差值的1范數記做兩個粒子之間的距離，即公式(8)：

(8)

當粒子群陷入到局部最優時隨機選擇一部分粒子重新初始化，新舊兩個粒子群相對獨立。為了防止新粒子群回到原粒子群的局部最優附近，選取早熟區范圍是距離全局最優解最近的20%的粒子，這些粒子中離全局最優解最遠的粒子距離設為共享半徑ds，當新粒子進入到共享半徑時，它的適應度函數應當急劇增加，以促使其遠離這個區域。基于以上思想設計共享適應度函數為公式9：

(9)

式中，ds為共享半徑，di為粒子到原全局最優解的距離，M是懲罰系數，為定值100。

改進算法流程如下。

Step1：初始化粒子群。

Step2：在滿足約束條件的基礎上計算各個粒子的適應度，判斷是否到達迭代次數的最大值，如果是則跳轉到Step6，如果否繼續。

Step3：判斷收斂條件，如果收斂說明陷入局部最優，跳轉至步驟5，如果否繼續。

Step4：按照公式(2)更新位置和速度，然后跳轉到Step2。

Step5：按照1.5章所述算法確定共享半徑，選出部分粒子重新初始化，并且計算這部分粒子的共享適應度并排序，判斷所有粒子是否均在共享半徑外。如果有粒子在共享半徑內，繼續初始化這些共享半徑內的粒子，直到所有新粒子均在共享半徑外，然后跳轉到Step2。

Setp6：迭代停止，得到最優解。

3 實驗和結果

國內某機場ETV倉庫擁有7個路側I/O口和6個空側I/O口，設路側為入口、空側為出口，則出入口分布如表2所示。

表2 出入口位置

實驗樣本選用20個入庫任務和20個出庫任務，如表3所示。

表中，任務號格式為X-X-X，以此表示為任務類型、任務號、大小箱類型。其中大小箱類型分別表示‘1’為小箱和‘2’為大箱。

表3 任務庫

3.1 算法步驟

算法步驟如Step1～5所示。

Step1：選擇距離最近的出/入口作為出/入庫任務的目的/起始坐標生成只含有源/目的地址的任務集。

Step2：判斷是否達到停止條件。如果是，跳轉到Setp5；如果否，繼續。

Step3：按照標準PSO算法、混沌優化粒子群算法、共享適應度粒子群算法分別迭代生成新的編碼順序

Setp4：根據粒子群算法生成的編碼順序生成任務鏈，并按照公式(2)計算粒子群的適應度。然后跳轉到Step2。

Step5：迭代停止，得到最優解。

3.2 仿真結果和分析

3種粒子群算法的最大迭代次數均為200次。粒子群規模均為20個。為了測試算法的有效性，分別運行10次并記錄。10次迭代結果分別如圖3～5所示。

圖3 標準PSO迭代結果

圖4 混沌優化PSO迭代結果

圖5 共享適應度PSO迭代結果

從圖3～5可以看出，該樣本有3個局部最優解區域，分別在1 500 s、1 650 s、1 800 s左右。標準粒子群算法易出現早熟現象。混沌粒子群算法雖然加快了運行速度而且在一定程度上提高了跳出局部最優的能力。從圖5可以看出，在迭代后期有一些粒子到達了1 500 s左右區域，共享適應度粒子群算法在增加少量迭代次數的情況下有較強的跳出局部最優的能力，全局尋優能力更強。

計算10次任務鏈的平均時間如圖6所示。

圖6 平均任務鏈時間對比

圖中可以看出，共享適應度粒子群算法所得任務鏈時間最短。

使用公式(10)計算第i次迭代中10次結果的標準差，如圖7所示。

(10)

圖7 標準差對比

圖中可以看出迭代初期標準PSO的標準差最低，共享適應度粒子群算法標準差波動最大。迭代后期混沌優化粒子群算法標準差最大，共享適應度粒子群算法標準差最小。結果說明迭代初期共享適應度粒子群算法頻繁的執行粒子重初始化程序，使粒子跳出局部最優；迭代后期共享適應度粒子群算法所得結果更穩定。

圖8是共享函數改進粒子群算法獲得的最優序列的位置-時刻圖。

圖8 最優位置時刻圖

圖中可以看出，最優序列下兩個ETV大部分時間在各自的半區運行，且運行軌跡較平滑，進一步驗證了算法的有效性。

4 結束語

針對從任務的角度出發生成雙機ETV任務序列較困難的問題，提出一種基于ETV載物臺貨位生成任務鏈的算法。和文獻[7]所述算法相比，不僅降低了模型的復雜程度，而且可以方便的計算每個時刻載物臺貨位的狀態和任務序列的執行時間。針對雙機ETV求解最優序列過程中極易陷入局部最優的問題，將共享適應度概念應用到了模型的求解。仿真結果表明，和標準PSO、混沌優化粒子群算法相比，改進的共享適應度粒子群算法所得結果更優，穩定性更好。