共享適應(yīng)度粒子群在雙機(jī)ETV中的應(yīng)用

，

(中國(guó)民航大學(xué) 電子信息與自動(dòng)化學(xué)院，天津 300300)

0 引言

升降式轉(zhuǎn)運(yùn)車(Elevating Transfer Vehicle，ETV)是機(jī)場(chǎng)貨運(yùn)區(qū)運(yùn)輸集裝貨物的轉(zhuǎn)運(yùn)工具。許多大型機(jī)場(chǎng)在立體倉(cāng)庫(kù)內(nèi)配置了兩臺(tái)甚至更多的ETV同時(shí)作業(yè)。這些ETV運(yùn)行在同一巷道內(nèi)，不可避免的會(huì)出現(xiàn)碰撞。另外每個(gè)ETV通常擁有兩個(gè)貨位，立體倉(cāng)庫(kù)內(nèi)有兩排貨架，每個(gè)貨架有兩個(gè)貨位，這些情況都顯著提升了調(diào)度過(guò)程的復(fù)雜度。所以研究雙機(jī)雙貨位ETV控制系統(tǒng)對(duì)提高機(jī)場(chǎng)貨運(yùn)區(qū)轉(zhuǎn)運(yùn)效率和減少ETV磨損有著重要的意義。

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

標(biāo)準(zhǔn)粒子群算法易陷入局部最優(yōu)，常見(jiàn)的優(yōu)化算法采用調(diào)節(jié)權(quán)重、增加變異項(xiàng)等[4-6]。實(shí)驗(yàn)仿真發(fā)現(xiàn)，這些優(yōu)化算法在處理雙機(jī)ETV調(diào)度問(wèn)題時(shí)雖然有一定的效果，但是跳出局部最優(yōu)的能力依然較差且出現(xiàn)早熟現(xiàn)象。為了解決這個(gè)問(wèn)題，引入共享適應(yīng)度函數(shù)，改進(jìn)了粒子群算法。

1 雙機(jī)ETV復(fù)合調(diào)度建模和粒子群算法

ETV所在的立體倉(cāng)庫(kù)結(jié)構(gòu)如圖1所示。

圖1 機(jī)場(chǎng)立體倉(cāng)庫(kù)結(jié)構(gòu)示意圖

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

機(jī)場(chǎng)貨運(yùn)區(qū)立體貨架地址采用排-層-列的順序編碼。例如國(guó)內(nèi)某機(jī)場(chǎng)擁有4排5層45列貨架。為了計(jì)算方便，將三維編碼按照公式(1)映射為一維編碼。

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

(1)

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

1.1 任務(wù)集和任務(wù)鏈分析

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

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

許多研究人員從任務(wù)的角度出發(fā)研究ETV的調(diào)度問(wèn)題，分析復(fù)雜且易出錯(cuò)。從任務(wù)鏈的角度出發(fā)將調(diào)度問(wèn)題簡(jiǎn)化為一個(gè)具有馬爾科夫性的過(guò)程，即：任務(wù)鏈的下一個(gè)節(jié)點(diǎn)狀態(tài)僅和當(dāng)前任務(wù)狀態(tài)及下一個(gè)任務(wù)有關(guān)，而和任務(wù)鏈之前的節(jié)點(diǎn)無(wú)關(guān)。另外基于任務(wù)鏈的模型僅計(jì)算每個(gè)節(jié)點(diǎn)x軸方向運(yùn)行時(shí)間和相鄰兩節(jié)點(diǎn)運(yùn)行時(shí)間即可計(jì)算出總的運(yùn)行時(shí)間，較基于任務(wù)的模型結(jié)構(gòu)更加清晰。任務(wù)鏈生成步驟如圖2所示。

圖2 生成任務(wù)鏈步驟

1.2 按照任務(wù)序列生成任務(wù)鏈

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

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

1)m1、m2均為空。載入下一個(gè)任務(wù)。

①如果下一任務(wù)貨物類型為內(nèi)側(cè)小箱，將任務(wù)信息賦值給離此地址最近的載物臺(tái)。然后將任務(wù)鏈的下一節(jié)點(diǎn)賦值為載入任務(wù)的源地址和貨物類型。此時(shí)載物臺(tái)有一個(gè)小箱，任務(wù)鏈增加了一個(gè)節(jié)點(diǎn)。

②如果下一任務(wù)為外側(cè)小箱且目的地址為同側(cè)，將任務(wù)信息賦值給與任務(wù)貨位最近的載物臺(tái)貨位，將遠(yuǎn)離任務(wù)貨位的載物臺(tái)貨位的源、目的地址均賦值為與任務(wù)貨物相鄰的內(nèi)側(cè)貨位的地址。然后將任務(wù)鏈的下一節(jié)點(diǎn)賦值為載入任務(wù)的源地址和貨物類型。此時(shí)載物臺(tái)有兩個(gè)小箱，任務(wù)鏈增加了兩個(gè)節(jié)點(diǎn)。

③如果下一任務(wù)為外側(cè)小箱且目的地址為對(duì)側(cè)，按照距離下一任務(wù)的目的地址最節(jié)省時(shí)間且在對(duì)側(cè)的空閑貨位為中轉(zhuǎn)貨位；任務(wù)完成后，載物臺(tái)上只剩中轉(zhuǎn)貨物，源地址為中轉(zhuǎn)貨位地址，目的地址為中轉(zhuǎn)貨位的原始地址。任務(wù)鏈增加了3個(gè)節(jié)點(diǎn)。第一個(gè)節(jié)點(diǎn)的地址為中轉(zhuǎn)貨位地址，貨物類型為1；第二個(gè)節(jié)點(diǎn)的地址為任務(wù)的目的地址，貨物類型為1；第三個(gè)節(jié)點(diǎn)的地址為中轉(zhuǎn)貨位地址，貨位類型為1。

③如果下一任務(wù)鏈貨物類型為大箱，將任務(wù)信息賦值給載物臺(tái)所有貨位。將任務(wù)鏈的下一節(jié)點(diǎn)地址賦值為載入任務(wù)的源地址，貨物類型為2。

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

2)m1、m2有一個(gè)為空。

如果是下一任務(wù)貨物類型為大箱，按照死鎖避免策略應(yīng)當(dāng)首先清空載物臺(tái)再進(jìn)行裝載，裝載完成時(shí)，載物臺(tái)上只有一個(gè)大箱，載物臺(tái)兩貨位信息為大箱的源地址、目的地址和貨物類型。按順序增加兩個(gè)任務(wù)鏈節(jié)點(diǎn)：1、當(dāng)前任務(wù)的目的地址，貨物類型為1；2、下一任務(wù)的源地址，貨物類型為2。最后更新立體貨架存貨信息。

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

①m1有貨，目的地址為同側(cè)，直接載入下一任務(wù)。當(dāng)下一任務(wù)源地址和m1同側(cè)時(shí)，將m1賦值給m2，將下一任務(wù)的信息賦值給m1。此時(shí)載物臺(tái)上有兩個(gè)貨物。當(dāng)下一任務(wù)源地址和m1異側(cè)時(shí)，將下一任務(wù)信息賦值給m2。

任務(wù)鏈增加一個(gè)：節(jié)點(diǎn)為下一任務(wù)的源地址，貨物類型為1。

②m1有貨，目的地址為異側(cè)。如果下一任務(wù)源地址為m1同側(cè)，將m1賦值給m2，下一任務(wù)信息賦值給m1，此時(shí)載物臺(tái)上有兩個(gè)貨物。如果下一任務(wù)源地址為m1異側(cè)目的地址m1異側(cè)，將下一任務(wù)信息賦值給m2。

任務(wù)鏈增加一個(gè)：節(jié)點(diǎn)為下一任務(wù)的源地址，貨物類型為1。

如果下一任務(wù)源地址為m1異側(cè)目的地址m1同側(cè)，此時(shí)產(chǎn)生死鎖。使用撤銷策略避免死鎖，首先完成當(dāng)前任務(wù)，然后裝載下一任務(wù)，完成時(shí)載物臺(tái)有一個(gè)m2貨物，m2屬性為下一任務(wù)屬性，

任務(wù)鏈增加兩個(gè)：第1節(jié)點(diǎn)為當(dāng)前任務(wù)的目的地址，貨物類型為1；第二節(jié)點(diǎn)為下一任務(wù)的源地址。

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

3)m1、m2均有貨。

如果ETV載物臺(tái)兩貨物均為小箱，選擇離m1、m2目的地址耗時(shí)最短的貨位為下一任務(wù)鏈節(jié)點(diǎn)。①下一任務(wù)是卸載m1，將m2賦值給m1，清空m2，增加一個(gè)任務(wù)鏈節(jié)點(diǎn)：m1目的地址。②下一任務(wù)是卸載m2，將m1賦值給m2，清空m1，增加一個(gè)任務(wù)鏈節(jié)點(diǎn)：m2目的地址。完成后m1、m2有一個(gè)為空。

如果ETV載物臺(tái)為一個(gè)大箱，下一任務(wù)是卸載m1和m2，任務(wù)完成后清空m1和m2，任務(wù)鏈增加一個(gè)節(jié)點(diǎn)：地址為m1或m2的目的地址，貨物類型為2。

1.3 使用粒子群算法求任務(wù)序列

國(guó)內(nèi)某機(jī)場(chǎng)某立體倉(cāng)庫(kù)內(nèi)擁有一個(gè)巷道兩個(gè)ETV，雙機(jī)ETV調(diào)度問(wèn)題屬于并行調(diào)度問(wèn)題(ParallelMachineShopSchedulingProblem,PMSP)，PMSP是NP完全問(wèn)題[8]。隨著啟發(fā)算法的深入研究，NP完全問(wèn)題得到了很好的解決。其中粒子群算法結(jié)構(gòu)簡(jiǎn)單易行得到了廣泛的應(yīng)用。

雙機(jī)ETV調(diào)度問(wèn)題是帶有約束條件的優(yōu)化問(wèn)題，它的適應(yīng)度函數(shù)為式(2)：

pi=max(T1i,T2i)

(2)

式中，T1i、T2i分別表示1號(hào)ETV和2號(hào)ETV執(zhí)行任務(wù)鏈所用時(shí)間。

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

(3)

式(3)中，第一行約束條件保證一號(hào)ETV運(yùn)行的區(qū)間在第1～40列，第二行約束條件保證二號(hào)ETV運(yùn)行的區(qū)間在第5～45列，第三行約束條件保證相同時(shí)刻兩ETV之間的距離大于等于4列，第四行和第五行保證兩個(gè)任務(wù)鏈均屬于任務(wù)集，第六行保證兩個(gè)子任務(wù)集內(nèi)任意元素不屬于對(duì)方任務(wù)集。

1.4 雙ETV調(diào)度問(wèn)題粒子編碼

雙機(jī)ETV調(diào)度要解決的是任務(wù)分配問(wèn)題，將任務(wù)、ETV序號(hào)映射為粒子的位置，這個(gè)過(guò)程叫做編碼。相對(duì)應(yīng)的，將粒子位置映射為任務(wù)、ETV序號(hào)的過(guò)程稱之為解碼。

設(shè)有40個(gè)出入庫(kù)任務(wù)，則一個(gè)粒子需要40個(gè)維數(shù)，將粒子的每個(gè)維數(shù)和每個(gè)任務(wù)一一對(duì)應(yīng)，根據(jù)粒子每個(gè)維度的坐標(biāo)確定任務(wù)的序列。首先將粒子每個(gè)維度的坐標(biāo)值按照從大到小的順序排列。將坐標(biāo)值大于0的維度對(duì)應(yīng)的任務(wù)分配給1號(hào)ETV，將坐標(biāo)值小于0的維度對(duì)應(yīng)的任務(wù)分配給2號(hào)ETV。并且每個(gè)ETV分配的任務(wù)執(zhí)行順序?yàn)榱Ｗ幼鴺?biāo)值的順序。例如10個(gè)粒子分配情況如表1所示。

表1 粒子編碼示例

表中，1號(hào)ETV執(zhí)行的任務(wù)序列為8、1、5、7、4；2號(hào)ETV執(zhí)行的任務(wù)序列為6、3、2、10、9。

1.5 標(biāo)準(zhǔn)粒子群算法

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

(4)

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

繼續(xù)迭代，直至滿足停止條件，全局最優(yōu)解Pig即為模型最優(yōu)解，對(duì)應(yīng)的粒子位置xig即為最優(yōu)位置。

1.6 混沌粒子群算法

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

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

(5)

(6)

2 共享適應(yīng)度改進(jìn)粒子群算法

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

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

(7)

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

(8)

當(dāng)粒子群陷入到局部最優(yōu)時(shí)隨機(jī)選擇一部分粒子重新初始化，新舊兩個(gè)粒子群相對(duì)獨(dú)立。為了防止新粒子群回到原粒子群的局部最優(yōu)附近，選取早熟區(qū)范圍是距離全局最優(yōu)解最近的20%的粒子，這些粒子中離全局最優(yōu)解最遠(yuǎn)的粒子距離設(shè)為共享半徑ds，當(dāng)新粒子進(jìn)入到共享半徑時(shí)，它的適應(yīng)度函數(shù)應(yīng)當(dāng)急劇增加，以促使其遠(yuǎn)離這個(gè)區(qū)域。基于以上思想設(shè)計(jì)共享適應(yīng)度函數(shù)為公式9：

(9)

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

改進(jìn)算法流程如下。

Step1：初始化粒子群。

Step2：在滿足約束條件的基礎(chǔ)上計(jì)算各個(gè)粒子的適應(yīng)度，判斷是否到達(dá)迭代次數(shù)的最大值，如果是則跳轉(zhuǎn)到Step6，如果否繼續(xù)。

Step3：判斷收斂條件，如果收斂說(shuō)明陷入局部最優(yōu)，跳轉(zhuǎn)至步驟5，如果否繼續(xù)。

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

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

Setp6：迭代停止，得到最優(yōu)解。

3 實(shí)驗(yàn)和結(jié)果

國(guó)內(nèi)某機(jī)場(chǎng)ETV倉(cāng)庫(kù)擁有7個(gè)路側(cè)I/O口和6個(gè)空側(cè)I/O口，設(shè)路側(cè)為入口、空側(cè)為出口，則出入口分布如表2所示。

表2 出入口位置

實(shí)驗(yàn)樣本選用20個(gè)入庫(kù)任務(wù)和20個(gè)出庫(kù)任務(wù)，如表3所示。

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

表3 任務(wù)庫(kù)

3.1 算法步驟

算法步驟如Step1～5所示。

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

Step2：判斷是否達(dá)到停止條件。如果是，跳轉(zhuǎn)到Setp5；如果否，繼續(xù)。

Step3：按照標(biāo)準(zhǔn)PSO算法、混沌優(yōu)化粒子群算法、共享適應(yīng)度粒子群算法分別迭代生成新的編碼順序

Setp4：根據(jù)粒子群算法生成的編碼順序生成任務(wù)鏈，并按照公式(2)計(jì)算粒子群的適應(yīng)度。然后跳轉(zhuǎn)到Step2。

Step5：迭代停止，得到最優(yōu)解。

3.2 仿真結(jié)果和分析

3種粒子群算法的最大迭代次數(shù)均為200次。粒子群規(guī)模均為20個(gè)。為了測(cè)試算法的有效性，分別運(yùn)行10次并記錄。10次迭代結(jié)果分別如圖3～5所示。

圖3 標(biāo)準(zhǔn)PSO迭代結(jié)果

圖4 混沌優(yōu)化PSO迭代結(jié)果

圖5 共享適應(yīng)度PSO迭代結(jié)果

從圖3～5可以看出，該樣本有3個(gè)局部最優(yōu)解區(qū)域，分別在1 500 s、1 650 s、1 800 s左右。標(biāo)準(zhǔn)粒子群算法易出現(xiàn)早熟現(xiàn)象。混沌粒子群算法雖然加快了運(yùn)行速度而且在一定程度上提高了跳出局部最優(yōu)的能力。從圖5可以看出，在迭代后期有一些粒子到達(dá)了1 500 s左右區(qū)域，共享適應(yīng)度粒子群算法在增加少量迭代次數(shù)的情況下有較強(qiáng)的跳出局部最優(yōu)的能力，全局尋優(yōu)能力更強(qiáng)。

計(jì)算10次任務(wù)鏈的平均時(shí)間如圖6所示。

圖6 平均任務(wù)鏈時(shí)間對(duì)比

圖中可以看出，共享適應(yīng)度粒子群算法所得任務(wù)鏈時(shí)間最短。

使用公式(10)計(jì)算第i次迭代中10次結(jié)果的標(biāo)準(zhǔn)差，如圖7所示。

(10)

圖7 標(biāo)準(zhǔn)差對(duì)比

圖中可以看出迭代初期標(biāo)準(zhǔn)PSO的標(biāo)準(zhǔn)差最低，共享適應(yīng)度粒子群算法標(biāo)準(zhǔn)差波動(dòng)最大。迭代后期混沌優(yōu)化粒子群算法標(biāo)準(zhǔn)差最大，共享適應(yīng)度粒子群算法標(biāo)準(zhǔn)差最小。結(jié)果說(shuō)明迭代初期共享適應(yīng)度粒子群算法頻繁的執(zhí)行粒子重初始化程序，使粒子跳出局部最優(yōu)；迭代后期共享適應(yīng)度粒子群算法所得結(jié)果更穩(wěn)定。

圖8是共享函數(shù)改進(jìn)粒子群算法獲得的最優(yōu)序列的位置-時(shí)刻圖。

圖8 最優(yōu)位置時(shí)刻圖

圖中可以看出，最優(yōu)序列下兩個(gè)ETV大部分時(shí)間在各自的半?yún)^(qū)運(yùn)行，且運(yùn)行軌跡較平滑，進(jìn)一步驗(yàn)證了算法的有效性。

4 結(jié)束語(yǔ)

針對(duì)從任務(wù)的角度出發(fā)生成雙機(jī)ETV任務(wù)序列較困難的問(wèn)題，提出一種基于ETV載物臺(tái)貨位生成任務(wù)鏈的算法。和文獻(xiàn)[7]所述算法相比，不僅降低了模型的復(fù)雜程度，而且可以方便的計(jì)算每個(gè)時(shí)刻載物臺(tái)貨位的狀態(tài)和任務(wù)序列的執(zhí)行時(shí)間。針對(duì)雙機(jī)ETV求解最優(yōu)序列過(guò)程中極易陷入局部最優(yōu)的問(wèn)題，將共享適應(yīng)度概念應(yīng)用到了模型的求解。仿真結(jié)果表明，和標(biāo)準(zhǔn)PSO、混沌優(yōu)化粒子群算法相比，改進(jìn)的共享適應(yīng)度粒子群算法所得結(jié)果更優(yōu)，穩(wěn)定性更好。