混合粒子群算法在ETV調(diào)度優(yōu)化中的應(yīng)用

丁 芳 宋小靜

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

0 引 言

近年來，隨著航空物流的快速發(fā)展，國內(nèi)的許多大型機場建立了自動化貨運站,其處理的貨物80%是集裝貨物。由于空中管制等原因，飛機通常在某個時間段內(nèi)進出港，導致進出庫任務(wù)較集中。目前國內(nèi)大型機場由ETV完成出入庫的任務(wù)，傳統(tǒng)ETV采用鏈式調(diào)度策略，制約了運行效率。因此，ETV調(diào)度算法的研究對提高機場貨運站物流過程的轉(zhuǎn)運效率具有重要的意義。

集裝貨物在航空貨運站的位置和平面示意圖如圖1所示。圖中，集裝貨物區(qū)位于貨運站空側(cè)和路側(cè)交接區(qū)域；集裝貨物區(qū)有多個IO口。

圖1 集裝貨物區(qū)位置

ETV是機場貨運區(qū)立體倉庫中轉(zhuǎn)運集裝貨物的主要設(shè)備，其功能與自動化立體倉庫中的堆垛機類似。近年來，許多學者針對機場貨運區(qū)ETV的優(yōu)化調(diào)度進行了研究。文獻[1]采用混合線性模型求解ETV調(diào)度問題，將調(diào)度過程中消耗最低總能量設(shè)為優(yōu)化目標，并考慮了裝載及容量限制等約束條件提高了ETV的工作效率，但是該規(guī)劃的方法建模困難，對參數(shù)敏感，求解大規(guī)模問題適應(yīng)性較差。郭春暉[2]基于五段S型運動模型,提出了改進遺傳算法對ETV的調(diào)度進行優(yōu)化,提高了全局尋優(yōu)能力，但是5段模型忽略了ETV在移動距離較短的情況下達不到最高速度的情況,誤差較大。文獻[3]在遺傳算法中引入小生境模型分析雙機ETV調(diào)度問題，使得立體倉庫的存取效率得到提高。但是改進的遺傳算法仍然存在收斂速度慢、需要迭代的次數(shù)較多且存在早熟問題。楊瑋等[4]采用改進的粒子群算法對多軌道多任務(wù)的出入庫任務(wù)進行優(yōu)化；邱建東[5]采用NLA-PSO算法對ETV調(diào)度系統(tǒng)進行了研究。這些學者[4-5]均采用粒子群算法求解ETV調(diào)度問題，但是算法迭代后期缺乏跳出策略，使粒子易陷入局部最優(yōu)?；煦缦到y(tǒng)是對初始值極其敏感的非線性動力系統(tǒng)，是介于確定系統(tǒng)和隨機系統(tǒng)之間的一種狀態(tài)，處于混沌狀態(tài)的粒子可以遍歷吸引子附近的所有點，利用混沌系統(tǒng)的偽隨機性、遍歷性和規(guī)律性的特點，混沌優(yōu)化算法有效地解決了組合優(yōu)化問題[6]。本文在標準粒子群算法的基礎(chǔ)上引入動態(tài)自適應(yīng)策略與混沌思想，以三者融合后的混合粒子群調(diào)度算法求解ETV控制系統(tǒng)的調(diào)度問題，從而提高了機場貨運區(qū)ETV的轉(zhuǎn)運效率。

1 ETV調(diào)度模型的建立

與傳統(tǒng)的立體倉庫相比，機場貨運區(qū)立體倉庫在貨架的底層分散設(shè)置了多個出入庫口，使ETV載物臺在取到ULD集裝貨物后不需要運動到巷道端口，就可以在立體貨架工作區(qū)域內(nèi)直接出庫。

稱ETV需要在某個時間段內(nèi)處理多個任務(wù)組成的集合為任務(wù)集。ETV處理的任務(wù)類型分三種：入庫、出庫、倒庫。建立ETV調(diào)度模型的目的是求得一組作業(yè)時間最短的任務(wù)序列。一個確定的任務(wù)序列包括一組排列有序的任務(wù)，為便于研究，本文將每個任務(wù)的起始和目的貨位地址均映射為三維空間中的坐標點。任務(wù)序列中有序任務(wù)的坐標點依次相連形成的鏈狀結(jié)構(gòu)稱為任務(wù)鏈，其中坐標點稱為節(jié)點，節(jié)點間的線段代表ETV在節(jié)點間的運行路徑。

ETV在完成出入庫任務(wù)的過程中一般采用復合作業(yè)即完成一個任務(wù)后可運動到下一個任務(wù)的起始地址，而非運動到原點，如圖2所示。

圖2 ETV調(diào)度過程復合作業(yè)的方式

圖中假設(shè)IN為入庫口、OUT為出庫口、X軸為某貨架的列數(shù)，Y軸為對應(yīng)貨架的層數(shù)，A、B、C、D表示4個隨機的貨位。其中IN到A是入庫任務(wù)、B到C是倒庫任務(wù)、D到A是出庫任務(wù)。

設(shè)ETV在實際工況下的某個任務(wù)集為C={C1,C2,…,CN}，C中包含有N個任務(wù)，其中入庫任務(wù)的集合為Ar={Arj}，Arj=[ArajArbj]，Araj表示入庫任務(wù)的起始貨位、Arbj表示入庫任務(wù)的目的貨位；出庫任務(wù)的集合為Ac={Acj}，Acj=[AcajAcbj]，Acaj表示出庫任務(wù)的起始貨位、Acbj表示出庫任務(wù)的目的貨位；倒庫任務(wù)的集合為Ad={Adj}，Adj=[AdajAdbj]，Adaj表示倒庫任務(wù)的起始貨位、Adbj表示倒庫任務(wù)的目的貨位。令貨位的向量為ζ=[X，Y，Z，λ]，其中X為貨架的層數(shù)，Y為貨架的列數(shù)，Z為貨架的排數(shù)，λ表示貨位的載物情況，λ=1表示滿載，λ=0表示空載。令入庫口的集合為IN={INi},入庫口的集合為OUT={OUTi}。

設(shè)該任務(wù)集生成的某個任務(wù)序列映射的任務(wù)鏈節(jié)點的個數(shù)為M，任務(wù)序列的執(zhí)行時間如下式所示：

(1)

式中:Ti,i+1為任務(wù)鏈中ETV在相鄰兩個節(jié)點之間的行走時間，tM′和ti分別為任務(wù)鏈終節(jié)點和第i個節(jié)點處ETV載物臺與貨位間貨物轉(zhuǎn)運時間。

ETV的運動是水平方向和垂直方向的復合運動，因此ETV在兩貨位點間的行走時間應(yīng)是兩種運動時間的較大者：

ETV調(diào)度優(yōu)化問題的實質(zhì)是在眾多可行解的任務(wù)序列中，尋求運行時間最短的任務(wù)序列，則ETV調(diào)度優(yōu)化的目標函數(shù)為：

T=minTμμ=1,2,…,n

(3)

在實際工況下，還需滿足以下約束條件：

1) 任務(wù)鏈中入庫任務(wù)的源貨位點必須是入庫口，目的貨位點不能滿載。

Arj(ζa)∈IN且Arj(ζb(λ))≠1

(4)

2) 任務(wù)鏈中出庫任務(wù)的源貨位點不能為空，目的點必須是出庫口。

Acj(ζb)∈OUT且Acj(ζa(λ))≠0

(5)

3) 任務(wù)鏈中倒庫任務(wù)的源貨位點不能為空，目的貨位點不能滿載。

Adj(ζa(λ))≠0且Adj(ζb(λ))≠1

(6)

4) 任務(wù)序列中所有任務(wù)的合集等于任務(wù)集。

Ar∪Ac∪Ad=C

(7)

5) 任務(wù)序列中任意兩兩任務(wù)不相交。

As∩Ap=?s,p∈N

(8)

2 粒子群優(yōu)化算法及改進

2.1 基本粒子群算法

基本粒子群算法中，假設(shè)目標搜索空間為D維空間，粒子群體大小為N，依據(jù)Eerhart[7]的帶慣性權(quán)重因子的改進算法，每個粒子的速度和位置更新的數(shù)學表達如下：

式中:w為慣性系數(shù)，c1、c2分別為認知系數(shù)和社會系數(shù)，Pid為單粒子最優(yōu)適應(yīng)度，Pig為所有粒子的最優(yōu)適應(yīng)度。ETV的適應(yīng)度函數(shù)為式1。

ETV所在立體倉庫貨位號的形式為：a-b-c。其中，a為貨架區(qū)域、b為貨位層數(shù)、c是貨位列數(shù)，將ETV任務(wù)排序形成任務(wù)集。為了使貨位號和粒子建立聯(lián)系，需要將三維立體倉庫貨位號映射為一維數(shù)字，按照先按區(qū)再按層最后按列的順序進行映射和逆映射，如下式所示：

nu=(a-1)×5+b+(c-1)×10

(10)

式中:floor為求最小整數(shù)計算。

映射后的任務(wù)序號按照任務(wù)集的順序排列成一個N維向量，將此向量看作一個工件加工次序，對應(yīng)N維粒子的一個坐標。粒子每次更新后各坐標分量按照降序排列，對應(yīng)一個新的加工次序。實例如表1所示。

表1 粒子SMC編碼

表1中，新的任務(wù)次序為1→6→3→2→5→4。每次更新后按照式(1)計算適應(yīng)度值，如果適應(yīng)度值比個體最佳適應(yīng)度更優(yōu)則更新個體最佳適應(yīng)度。如果所得適應(yīng)度比全局最佳適應(yīng)度更優(yōu)，則更新全局最佳適應(yīng)度。當?shù)螖?shù)達到最大設(shè)定值不再更新時停止運算，此時的全局最佳適應(yīng)度為粒子群算法的最優(yōu)解，對應(yīng)的序列為最優(yōu)ETV執(zhí)行序列。

2.2 算法改進

2.2.1加速因子自適應(yīng)調(diào)整策略

針對單機ETV的調(diào)度優(yōu)化問題，標準粒子群算法存在早熟收斂、易陷入局部極值的缺點。為提高粒子的全局與局部搜索的平衡能力，本文算法引入了加速因子的自適應(yīng)調(diào)整策略，使微粒能夠在迭代初期擴大整個解空間的搜索范圍，在后期增強局部最優(yōu)解的搜索能力。

認知因子c1和社會因子c2分別用于驅(qū)使粒子向自身及全局最佳位置運動。迭代初期c1取較大的值有利于突出自身優(yōu)勢避免早熟，迭代過程中c1值和算法的收斂速度有關(guān)，即c1減小得越快收斂速度越快；迭代后期c1減小得越慢越有利于局部挖掘。因此c1應(yīng)非線性遞減，其公式如下所示：

類似地，在迭代初期c2取較小的值可降低其他粒子的影響，提高整個解空間的搜索能力；迭代后期增加c2值可提高群體經(jīng)驗共享能力，有利于局部尋優(yōu)。因此c2應(yīng)非線性遞增，其公式如下所示：

式中：c1s、c2s分別為c1與c2的初值、c1e、c2e分別為c1與c2的終值。

2.2.2混沌映射

ETV模型為典型的多維PSO模型，多維PSO極易陷入局部尋優(yōu)且難以跳出?；煦缦到y(tǒng)是類似隨機的一種偽隨機運動，具有遍歷性、偽隨機性及規(guī)律性等特點，能在吸引子的鄰域不重復地遍歷所有的點。利用混沌變量對這些特性進行優(yōu)化搜索，保持粒子群體的多樣性，改善算法的全局尋優(yōu)能力。

在迭代初期，用混沌序列對種群粒子進行初始化，保證粒子在搜索空間較均勻地遍歷性分布[8]，同時，利用混沌算子替代引入動態(tài)自適應(yīng)調(diào)整的粒子群算法中的隨機數(shù)，改善算法的隨機性以提高粒子的搜素效率；在迭代中后期，為解決粒子早熟的問題，本文借助混沌算子對粒子的位置擾動對算法進行改進，從而保持群體多樣性，克服算法易陷入局部極值的缺點。

不同的混沌系統(tǒng)有著不同的最大lyapunov指數(shù)，因此有著不同的對初值的敏感程度，文獻[9]中指出Tent映射比Logistic映射具有更好的遍歷均勻性和更高的搜索效率。Tent混沌映射算子的迭代公式如下所示：

本文將映射算子嵌入到全局最優(yōu)Pig中對早熟的粒子進行擾動，得到下式：

Pig=Pig×(rn)s

(15)

式中：Pig為全局最優(yōu)，rn為n次迭代的混沌迭代算子。s為自適應(yīng)項，當全局最優(yōu)值超過累加器設(shè)定的最大值MAX粒子仍未更新時s=1，否則s=0。通過引入混沌變異，使得陷入局部最優(yōu)的粒子跳出局部解。

圖3為隨機與混沌兩種方法獨自生成范圍為0～1的初始粒子，由圖可知: 混沌序列法生成的微粒更均勻地分布在整個解空間，有利于提高粒子的搜索效率，更快地獲取最優(yōu)解。

圖3 混沌與隨機序列初始化粒子對比圖

2.2.3粒子不改進及早熟判別機制

粒子群算法在迭代過程中，種群中每個粒子均追隨自身歷史最優(yōu)和全局歷史最優(yōu)兩個極值點。如果某一粒子搜索到了新的全局最優(yōu)點，那么其他粒子會迅速地靠近該點，種群的多樣性收到影響。如果該點為解空間的局部最優(yōu)點，各粒子將聚集在該點，產(chǎn)生不改進現(xiàn)象。因此可用種群各粒子之間的離散程度描述粒子不改進現(xiàn)象。本文結(jié)合了粒子的平均粒距、適應(yīng)度方差以及漢明距離作為粒子不改進判斷機制，采用粒子連續(xù)不改進次數(shù)的最大值作為早熟的判別機制，當粒子出現(xiàn)早熟時，利用混沌擾動更新微粒的位置使其跳出當前局部最優(yōu)，進而搜索解空間的其他區(qū)域。

文獻[10]使用平均粒距從空間角度描述了粒子之間分布離散程度，其定義如下：

(16)

式中:M為種群大小，L為解空間維數(shù)，由式(14)可知平均粒距和種群大小、粒子維數(shù)獨立，且平均粒距越小粒子越集中。

文獻[11-12]使用種群適應(yīng)度方差從函數(shù)值角度描述粒子間個體的聚集程度，其定義如下：

式中:M為種群大小，fi為某粒子適應(yīng)度，f′為全部粒子適應(yīng)度的均值，f為歸一化因子用來限制適應(yīng)度方差范圍，其定義如下：

當粒子聚集于兩個或多個適應(yīng)度相差不大的極值點時，適應(yīng)度方差可能小于閾值ε但是平均粒距卻不收斂。所以粒子群算法中單獨判斷粒子聚散不夠充分，應(yīng)當討論收斂在單極值點附近時粒子的聚散程度，即在滿足適應(yīng)度方差收斂的前提下滿足平均粒距收斂。

由于ETV最優(yōu)解是一維數(shù)組，而搜索空間卻是連續(xù)的，因此可能會出現(xiàn)適應(yīng)度方差、平均粒距收斂但是ETV解卻不收斂的情況。例如ETV的兩個粒子坐標及對應(yīng)的解如表2所示。

表2 粒子編碼

表2中兩粒子的粒距很小，但此時ETV的解并不收斂。因此針對本文ETV調(diào)度序列求解問題時引入漢明距離[13-14]在粒子適應(yīng)度方差及平均粒距均收斂的情況下，判定序列的相似度，從而判斷粒子是否不改進。

漢明距離統(tǒng)計的是兩個等長數(shù)列之間對應(yīng)位置出現(xiàn)不同數(shù)值的次數(shù)用來描述序列之間的相似程度s[15-16]。通過與設(shè)定閾值ε相比較，判斷序列是否相似，相似度公式如下所示：

評判早熟有多種方法，本文采用粒子連續(xù)不改進次數(shù)的最大值MAX作為早熟的判別機制，為每個粒子設(shè)定一個累加器，迭代過程中粒子不更新則累加器加1，否則置0。當粒子不更新的次數(shù)小于累加器設(shè)定的最大值時，粒子進行正常搜索；當粒子不更新的次數(shù)超過累加器設(shè)定的最大值時，對該粒子進行混沌擾動，并對累加器進行復位。

2.2.4改進算法流程

Step1初始化參數(shù)。主要有：種群數(shù)量M，維度L，加速因子c1、c2，最大迭代次數(shù)Nmax，適應(yīng)度方差閾值d，平均粒距閾值σ，漢明距離閾值ε，累加器最大計次數(shù)O，混沌映射初始化粒子。跳轉(zhuǎn)到Step2。

Step2判斷是否滿足停止條件，如果未達到則跳轉(zhuǎn)到Step3，如果達到則跳轉(zhuǎn)到Step8。

Step3判斷粒子有無改進。按照式(6)計算粒子適應(yīng)度，確定該次迭代的個體、全局最優(yōu)位置和對應(yīng)的個體、全局最優(yōu)值。按照適應(yīng)度方差、平均粒距、漢明距離公式判斷各粒子是否有改進，如果有改進則跳轉(zhuǎn)到Step4，如果無改進則跳轉(zhuǎn)到Step5。

Step4累加器置零，跳轉(zhuǎn)到Step6。

Step5累加器加一，如果累加器數(shù)字小于最大計次O則跳轉(zhuǎn)到Step6，否則累加器置零跳轉(zhuǎn)到Step7。

Step6非線性位置更新。按照式(10)-式(11)進行迭代，然后跳轉(zhuǎn)到Step2。

Step7混沌擾動。按照式(13)進行迭代，然后跳轉(zhuǎn)到Step2。

Step8結(jié)束并輸出最優(yōu)結(jié)果。

3 實例仿真與結(jié)果分析

某機場ETV設(shè)計參數(shù)為：Vimax=2 m/s、Vjmax=0.33 m/s、aimax=0.5 m/s2、ajmax=0.3 m/s2、Ji=1 m/s3、Jj=0.5 m/s3、ULD貨位長度和高度均為3.75 m、共有45列5層貨位。空側(cè)I/O口有7個，路側(cè)I/O口為6個。模型以空側(cè)為入口，路側(cè)為出口為例進行研究。以式3為目標函數(shù)，選取文獻[5]中的樣本調(diào)度任務(wù)集如表3所示。

表3 任務(wù)集

為盡可能地弱化比較結(jié)果的隨機性和提高比較結(jié)果的可信度,目標函數(shù)用本文及對比算法分別計算10次并將10次結(jié)果的平均值作為評價指標進行對比，如下式所示：

式中:record記錄了10次平均結(jié)果。

針對ETV的調(diào)度問題，首先將標準粒子群算法與遺傳算法、模擬退火及蟻群算法三中經(jīng)典的調(diào)度算法進行對比，尋優(yōu)曲線如圖4所示。

圖4 粒子群算法與其他經(jīng)典算法的迭代尋優(yōu)曲線

由對比圖可知遺傳算法、模擬退火、蟻群算法在求解ETV調(diào)度問題的過程中都存在易早熟、易陷入局部最優(yōu)的缺陷，且遺傳算法收斂速度太慢。標準粒子群算法相比其他幾種算法收斂速度快、尋優(yōu)效果好，因此本文在標準粒子群算法的基礎(chǔ)上研究改進的調(diào)度算法能夠最大化地提高ETV的轉(zhuǎn)運效率。

為驗證本文改進粒子群算法的有效性，將本文算法的結(jié)果與標準的粒子群算法(PSO)、非對稱線性調(diào)節(jié)粒子群算法(NsLF-PSO)[17]、非線性學習因子粒子群算法(NLA-PSO)[5]、混沌粒子群算法(IACPSO)[18]對比。本文改進算法各參數(shù)設(shè)置為：種群規(guī)模M=40；慣性權(quán)重w=0.9；認知因子c1的初值為c1s=2.5，終值為c1e=1；社會因子c2的初值為c2s=0.5，終值為c2e=2.25；k1和k2均為π/4，k為1；最大迭代次數(shù)為3 000。標準PSO的慣性權(quán)重w=0.9，c1、c2為2。NsLF-PSO的最大粒子速度Vmax為1。NLA-PSO的c1s為2.5、c1e為1、c2s為0.5、c2e為2.25，k1和k2均為π/4，k為1。為保證比較結(jié)果更加客觀公正，對比算法的種群規(guī)模與最大迭代次數(shù)分別設(shè)定為40和3 000。所有算法均使用表3所示任務(wù)集實驗10次并求取平均值作為一次最優(yōu)解。其結(jié)果如表4和圖5、圖6所示。

表4 不同算法尋優(yōu)結(jié)果對比

圖5 ETV目標函數(shù)不同算法的迭代尋優(yōu)曲線

圖6 改進PSO與鏈式調(diào)度最優(yōu)解對比圖

由表4可以看出，和標準的粒子群算法、非對稱線性調(diào)節(jié)粒子群算法、非線性學習因子粒子群算法及混沌粒子群算法相比，本文算法在求解ETV調(diào)度問題時最優(yōu)解的平均值最小，表明改進的的粒子群算法尋優(yōu)效果最好；最優(yōu)解標準差最小，說明改進算法穩(wěn)定性最好。由圖5可以看出，相比其他算法，本文算法收斂速度快，且在迭代中后期其他算法陷入停滯而本文算法持續(xù)更新，說明本文算法能夠較好地防止早熟收斂，具有較強的全局搜索能力。由圖6可以明顯看出，本文改進算法的最優(yōu)解很大幅度上優(yōu)于傳統(tǒng)鏈式調(diào)度算法，且由表4數(shù)據(jù)可以計算出，本文改進算法相比傳統(tǒng)鏈式調(diào)度平均最優(yōu)解的任務(wù)調(diào)度時間縮短了15.6%，說明本文算法在實際應(yīng)用中能夠較好地解決ETV轉(zhuǎn)運效率低的問題。

4 結(jié) 語

研究機場貨運區(qū)ETV調(diào)度算法對于提高機場貨運站貨物處理能力具有重要意義，是滿足日益增長的航空貨運量的有效途徑。本文對機場貨運區(qū)ETV的調(diào)度問題進行了研究，建立了ETV的調(diào)度模型并提出了混合粒子群調(diào)度算法。引入非線性自適應(yīng)策略對參數(shù)進行自適應(yīng)調(diào)整，利用混沌系統(tǒng)的偽隨機性、遍歷性和規(guī)律性的特點對粒子進行初始化使粒子能夠均勻分布，提高粒子的搜索效率。通過改進的粒子早熟判別機制并利用混沌擾動使陷入局部最優(yōu)的粒子能夠進行位置更新，增加了粒子種群迭代末期的多樣性，有效地避免粒子早熟收斂，提高了算法的全局搜索能力，加快了算法的收斂速度。最后經(jīng)過實例仿真驗證了本文算法對比其他算法在求解ETV調(diào)度問題上具有較好的收斂性、穩(wěn)定性、尋優(yōu)性，相比傳統(tǒng)調(diào)度能夠更大化的提高ETV的轉(zhuǎn)運效率。