改進(jìn)灰狼算法及其在港口泊位調(diào)度中的應(yīng)用

李長(zhǎng)安，謝宗奎，吳忠強(qiáng)，張立杰

(1. 先進(jìn)鍛壓成形技術(shù)與科學(xué)教育部重點(diǎn)實(shí)驗(yàn)室(燕山大學(xué))，河北 秦皇島 066004；2 .燕山大學(xué) 電氣工程學(xué)院，河北 秦皇島 066004；3. 河北省重型機(jī)械流體動(dòng)力傳輸與控制重點(diǎn)實(shí)驗(yàn)室(燕山大學(xué))，河北 秦皇島 066004；4.神華天津煤炭碼頭有限責(zé)任公司，天津 300457)

港口在全球經(jīng)濟(jì)貿(mào)易中發(fā)揮著重大作用，是海上運(yùn)輸?shù)臉屑~. 當(dāng)一個(gè)港口在進(jìn)行船舶貨物的裝卸與運(yùn)輸時(shí)，泊位直接面向船舶作業(yè)，其數(shù)量是有限的，因此如何合理安排泊位，提高港口裝卸效率，進(jìn)一步降低成本成為當(dāng)前的研究熱點(diǎn). Etsuko等[1]指出，傳統(tǒng)的泊位分配方法已阻礙大多數(shù)港口的發(fā)展，提出了以船舶停泊時(shí)間最少為目標(biāo)函數(shù)的非線性整數(shù)規(guī)劃模型，并將遺傳算法(Genetic Algorithm ，GA)引入泊位調(diào)度優(yōu)化中，通過(guò)大量的實(shí)驗(yàn)證明了GA算法的可行性. GA算法是一種較早的群集智能算法[2]，以其高效性和穩(wěn)定性的優(yōu)勢(shì)得到廣泛的應(yīng)用，同時(shí)也存在過(guò)早收斂以致求解精度低的不足.

為提高算法的尋優(yōu)精度和優(yōu)化效率，近年來(lái)研究人員提出多種群集智能算法. 黎成[3]在2010年通過(guò)模擬蝙蝠的捕食行為特征提出了蝙蝠算法(Bat-inspired Algorithm，BA). 2011年，劉長(zhǎng)平等[4]通過(guò)模擬螢火蟲(chóng)發(fā)光特性提出螢火蟲(chóng)算法(Firefly Algorithm，F(xiàn)A)；Pan等[5]通過(guò)模擬果蠅覓食行為提出果蠅算法(Fruit Fly Optimization Algorithm，F(xiàn)OA). 2012年Gandomi等[6]受磷蝦個(gè)體的群體特征啟發(fā)，提出磷蝦群算法(Krill Herd Algorithm，KH). 2014年 Mirjalili等[7]通過(guò)模擬灰狼捕食獵物的行為機(jī)制提出灰狼優(yōu)化算法(Gray Wolf Optimizer，GWO)； Cuevas等[8]通過(guò)模擬社會(huì)蜘蛛?yún)f(xié)作行為，提出蜘蛛群算法(Social Spider Optimization，SSO-C). 2015 年Meng 等[9]通過(guò)模擬鳥(niǎo)群的群體行為，提出鳥(niǎo)群算法( Bird Swarm Algorithm, BSA). 2016年 WU等[10]通過(guò)模擬海豚的群體捕食行為提出海豚群算法(Dolphin Swarm Algorithm，DSA). 2017年Mirjalili 等[11]提出樽海鞘群算法(Salp Swarm algorithm, SSA). 2018年劉生建等[12]模仿獅群捕食行為提出獅群算法(Lion Swarm Optimization, LSO). 這些算法已被廣泛應(yīng)用到各個(gè)領(lǐng)域[13-14].

GWO算法自出現(xiàn)起，就以其原理簡(jiǎn)單、易于實(shí)現(xiàn)、可調(diào)參數(shù)少等優(yōu)點(diǎn)受到研究者們的廣泛關(guān)注，在函數(shù)優(yōu)化方面具有很好的穩(wěn)定性和尋優(yōu)精度. 文獻(xiàn)[15]指出，在面對(duì)復(fù)雜的優(yōu)化問(wèn)題時(shí)，GWO算法與大多智能算法相似，也存在易早熟、收斂精度低等缺陷. 為進(jìn)一步提升GWO算法的收斂速度和尋優(yōu)精度，增強(qiáng)算法的可靠性，更好地解決港口泊位動(dòng)態(tài)調(diào)度問(wèn)題，本文提出一種改進(jìn)灰狼算法(Improved Gray Wolf Optimizer ，IGWO). 在生成初始種群時(shí)引入Sin混沌初始化[16]，增強(qiáng)初始種群的均勻性；引入頭狼引領(lǐng)策略，加快算法收斂，提高算法效率；引入合作競(jìng)爭(zhēng)機(jī)制，提高個(gè)體間有效信息的利用率；在灰狼種群位置更新時(shí)引入自適應(yīng)權(quán)值，以滿足不同時(shí)期的尋優(yōu)要求. 為驗(yàn)證IGWO算法的有效性，將IGWO算法與SSA算法、DSA算法、SSO-C算法、DSA算法、LSO算法及標(biāo)準(zhǔn)GWO算法進(jìn)行對(duì)比實(shí)驗(yàn)，并將IGWO應(yīng)用于港口泊位調(diào)度中，以證明該算法在港口泊位調(diào)度優(yōu)化中的實(shí)用性和有效性.

1 GWO算法

GWO算法的主要思想如下：從待尋優(yōu)空間的任意位置開(kāi)始，將具有最優(yōu)適應(yīng)度值的個(gè)體設(shè)置為頭狼α，適應(yīng)度值排第2和第3的個(gè)體設(shè)置為下屬狼β和普通狼δ，其余為底層狼ω. 在捕食過(guò)程中，首先由α、β和δ判斷獵物所在位置并進(jìn)行追捕；當(dāng)發(fā)現(xiàn)獵物所在位置時(shí)，α、β和δ帶領(lǐng)ω對(duì)獵物進(jìn)行圍剿，通過(guò)不斷迭代搜索得到最優(yōu)值.

在捕食的過(guò)程中，α、β和δ據(jù)獵物最近，首先要確定灰狼個(gè)體與α、β和δ之間的距離：

(1)

隨后，狼群其他個(gè)體利用α、β和δ之間的位置判斷獵物位置，對(duì)獵物進(jìn)行圍剿，該過(guò)程可描述為

(2)

2 改進(jìn)GWO算法

2.1 Sin混沌初始化

初始種群位置對(duì)算法的收斂速度和求解精度有很大的影響，甚至?xí)?dǎo)致尋優(yōu)的失敗. 在初始化的過(guò)程中，搜索空間的隨機(jī)分布會(huì)使種群個(gè)體分布不均，多樣性較差. 混沌映射是由確定性方程得到的具有隨機(jī)性的運(yùn)動(dòng)狀態(tài)，具有隨機(jī)性、遍歷性的特點(diǎn). Logistic映射和Sin映射是混沌學(xué)中常用的兩種映射，其映射表達(dá)式分別為

xn+1=μxn(1-xn),xn∈(0,1)，

(3)

xn+1=sin(2/xn),xn∈(-1,1)∩xn≠0.

(4)

式(3)中，μ的取值范圍是(0,4)，在>3.6時(shí)產(chǎn)生混沌現(xiàn)象，產(chǎn)生的xn+1的范圍為(0,1). 為比較上述兩種混沌映射的混沌特性，利用式(3)和式(4)分別產(chǎn)生區(qū)間(-1,1)上的2維混沌解，如圖1所示.

由圖1可知，Logistic映射產(chǎn)生的混沌解遍歷性較差，在空間中分布不均；與Logistic映射相比，Sin映射的混沌解在空間中分布均勻，具有更明顯的混沌特性. 為使初始種群具有更好的遍歷性和均勻性，引入Sin混沌映射進(jìn)行初始化，以加快算法的收斂.

·Sin映射 °Logistic映射

2.2 頭狼引領(lǐng)

由α、β、δ確定獵物所在位置后，底層狼ω隨即對(duì)獵物進(jìn)行圍捕. 此時(shí)，狼群中頭狼距獵物的距離最近，底層狼距頭狼位置較遠(yuǎn)，包圍過(guò)程中狼群圍捕速度較慢. 若能縮短獵物與整個(gè)種群之間的相對(duì)距離，則能夠加大獵捕的成功幾率，提高算法的尋優(yōu)速度，故引入頭狼引領(lǐng)策略. 種群中每一只狼在圍捕獵物前均按式(5)小步跟隨頭狼α進(jìn)行移動(dòng)，以縮短每只狼與獵物之間的距離.

(5)

2.3 合作競(jìng)爭(zhēng)機(jī)制

(6)

(7)

2.4 自適應(yīng)慣性權(quán)值

為滿足GWO算法在不同迭代周期的尋優(yōu)要求，提高收斂速度和尋優(yōu)精度，引入自適應(yīng)慣性權(quán)值w，且

隨著迭代次數(shù)的增大，w從1逐漸減小到0.

改進(jìn)后位置更新如式(8)所示:

(8)

2.5 算法步驟

步驟1. 設(shè)置算法參數(shù). 初始設(shè)置的參數(shù)主要有：種群數(shù)M，最大迭代次數(shù)T，維度D，求解空間的上限ub和下限lb.

步驟2. 進(jìn)行混沌初始化，按式(4)生成初始種群.

步驟3. 計(jì)算種群中每個(gè)個(gè)體的適應(yīng)度值，并選取適應(yīng)值最小的3個(gè)個(gè)體的位置分別作為α、β和δ.

步驟4. 按式(5)執(zhí)行頭狼引領(lǐng)策略.

步驟5. 除α、β、δ的灰狼個(gè)體按式(6)、式(7)執(zhí)行合作競(jìng)爭(zhēng)機(jī)制.

步驟6. 根據(jù)式(1)計(jì)算其他灰狼與α、β、δ的距離. 根據(jù)式(8)和式(2)更新其他灰狼的位置.

步驟7. 若達(dá)到最大迭代次數(shù)，轉(zhuǎn)至步驟9；否則轉(zhuǎn)至步驟8.

步驟8. 每隔一定迭代次數(shù)，重新排序，確定灰狼的位置，轉(zhuǎn)至步驟3.

步驟9. 輸出當(dāng)前最優(yōu)解，算法結(jié)束.

3 IGWO算法的收斂性分析

為證明IGWO算法的有效性，采用Markov鏈對(duì)該算法的收斂性進(jìn)行分析[18]. 設(shè)搜索空間為H，頭狼引領(lǐng)、狼群互動(dòng)和圍攻等行為均會(huì)引起狀態(tài)空間中的狀態(tài)轉(zhuǎn)移，設(shè)3個(gè)行為過(guò)程的轉(zhuǎn)移矩陣分別為S、M和W，則定義IGWO的Markov鏈轉(zhuǎn)移矩陣為

P=S×M×W.

首先,證明IGWO的優(yōu)化解序列是一個(gè)有限齊次Markov鏈. 設(shè)Qk={x1,x2,…,xN}為IGWO的第k代種群，N為灰狼種群大小，xi為第i只灰狼的狀態(tài). 因?yàn)榛依欠N群Qk是有限的，所以該算法的解序列是有限Markov鏈. 其次，由于IGWO算法中頭狼引領(lǐng)、狼群互動(dòng)和圍攻行為都是在獨(dú)立隨機(jī)過(guò)程中進(jìn)行的，每次個(gè)體更新具有優(yōu)勝選擇的繼承性，第k+1代種群的產(chǎn)生只與第k代群體有關(guān)，與各代群體之間的轉(zhuǎn)移概率無(wú)關(guān). 經(jīng)過(guò)種群的位置更新，可以得到一組優(yōu)化解序列. 因此，經(jīng)過(guò)IGWO一系列獨(dú)立隨機(jī)的變換處理得到的優(yōu)化解序列是一個(gè)有限齊次Markov鏈.

還需證明IGWO算法種群序列的Markov鏈?zhǔn)潜闅v鏈.

由于群體轉(zhuǎn)移概率矩陣Pij=P{Qk+1=j|Qk=i,k≥1}只與狀態(tài)i和j有關(guān)，且Qk>0，則群體轉(zhuǎn)移概率矩陣P為正定矩陣. 由定義1可得，IGWO算法的種群序列為不可約的Markov鏈.

對(duì)于給定的k>0，由IGWO是不可約的Markov鏈可知，?j∈H，使得Pij>0，又由定義2知k=1. 因此集合U的最大公約數(shù)為1，則IGWO為非周期不可約的Markov鏈.

Pij為狀態(tài)i經(jīng)歷各行為達(dá)到狀態(tài)j的轉(zhuǎn)移概率，由于轉(zhuǎn)移矩陣S、M和W都處于(0,1)之間，則0

綜上所述，IGWO算法的Markov鏈?zhǔn)潜闅v鏈.

文獻(xiàn)[17]已經(jīng)證明，若一個(gè)進(jìn)化算法滿足以下條件：1)對(duì)可行解空間中任意2點(diǎn)x1和x2，x2是x1由算法中各種算子可達(dá)的； 2)若種群序列Q1,Q2,…,QT是單調(diào)的，則此進(jìn)化算法以概率1收斂于問(wèn)題的全局最優(yōu)解. 由于IGWO算法種群序列的Markov鏈?zhǔn)潜闅v鏈，條件1)顯然是成立的. 由于IGWO算法中頭狼引領(lǐng)、狼群互動(dòng)和圍捕行為的位置狀態(tài)更新都體現(xiàn)出優(yōu)秀解的保持策略，所以IGWO優(yōu)化解序列是一個(gè)有限齊次Markov鏈，并且每次種群個(gè)體位置只有遇到更優(yōu)解時(shí)才會(huì)更新. 因此，IGWO算法產(chǎn)生的子代Qk+1中的任意解都非劣于Qk，由此可得種群序列Q1,Q2,…,QT是單調(diào)的. 綜上所述，IGWO算法以概率1收斂于問(wèn)題的全局最優(yōu)解.

4 仿真測(cè)試

為檢驗(yàn)IGWO 算法的尋優(yōu)能力，將本算法與SSA、BSA、SSO-C、LSO、DSA和標(biāo)準(zhǔn)GWO算法在同樣的環(huán)境下進(jìn)行仿真比較. 所使用電腦的詳細(xì)設(shè)置：CPU為Intel(R)Pentium(R)CPUG2020;頻率為2.90 GHz；內(nèi)存為4.00 GB. 操作系統(tǒng)windows7，仿真軟件為MATLAB2015b.

4.1 標(biāo)準(zhǔn)測(cè)試函數(shù)

實(shí)驗(yàn)選取5個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)進(jìn)行測(cè)試，如表1所示.

表1 標(biāo)準(zhǔn)測(cè)試函數(shù)

4.2 參數(shù)設(shè)置

BSA算法中,c1=c2=1.5，a1=a2=1，F(xiàn)Q=10；SSO-C算法中，PF=0.65；LSO算法中成年獅的占比β=2%；DSA算法中，T1=3，T2=1 000，速度為1，A=5,M=3,e=4. 為保證測(cè)試的公平性，6種算法的種群數(shù)量均為100，最大迭代次數(shù)M=200，為避免單次運(yùn)行的隨機(jī)性帶來(lái)的影響，各算法獨(dú)立運(yùn)行20次，取平均值和標(biāo)準(zhǔn)差. 5個(gè)測(cè)試函數(shù)分別在D=2、D=30和D=100這三種維度下進(jìn)行仿真.

4.3 實(shí)驗(yàn)分析

為驗(yàn)證IGWO算法的有效性，對(duì)各算法的尋優(yōu)精度和收斂速度進(jìn)行比較分析. 表2為7種算法對(duì)5個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)的尋優(yōu)結(jié)果.

表2 7種算法的對(duì)比測(cè)試結(jié)果

由表2可知，在求解單峰f1、f2函數(shù)時(shí)，7種算法在D=2時(shí)均能找到精度較高的解，IGWO算法和LSO算法直接找到了最優(yōu)解， DSA算法求解值精度相對(duì)較低；當(dāng)維度增大到30或100時(shí)，IGWO算法和BSA算法依然能找到最優(yōu)解，GWO算法和LSO算法隨著求解維度的增大求解精度有所下降，SSA算法、DSA算法和SSO-C算法所得解誤差較大，甚至找不到精度較高的解. 對(duì)于多峰f3、f4和f5函數(shù)，IGWO算法在幾個(gè)函數(shù)上均得到了最優(yōu)值，表明了該算法在低維和高維求解時(shí)都有很好的性能，適合求解多峰函數(shù)；GWO算法在D=2時(shí)能找到精度較高的解，但當(dāng)求解維度增大時(shí)，求解性能有不同程度的下滑，甚至找不到精度較高的解，表明GWO算法不宜求解高維多峰函數(shù)；LSO算法在求解f5函數(shù)時(shí)，低維和高維情況下均取得了最優(yōu)值，而在其他多峰函數(shù)的測(cè)試中表現(xiàn)一般，高維求解時(shí)所得結(jié)果偏差較大. DSA算法和SSO-C算法表現(xiàn)最差，求解精度相對(duì)較低，表明DSA算法、SSO-C算法存在一定缺陷，易陷入局部最優(yōu)，不宜求解多峰函數(shù). 此外，IGWO算法獨(dú)立運(yùn)行20次取得解的標(biāo)準(zhǔn)差均為0，表明該算法對(duì)不同維度的求解問(wèn)題均具有很好的抗擾性.

圖2為各算法在5個(gè)函數(shù)上的部分尋優(yōu)曲線. 由圖2可知，IGWO算法在單峰和多峰函數(shù)的尋優(yōu)中，均具有較快的收斂速度，優(yōu)于其他6種算法； GWO算法收斂速度較IGWO算法速度較慢，在f1、f2函數(shù)的尋優(yōu)中，與IGWO算法相比收斂速度和收斂精度上都有很大的差距，但優(yōu)于其他5種算法；BSA算法有較快的收斂速度，但差于GWO和IGWO；SSA算法在迭代前期收斂較慢，迭代后期收斂速度有所提升；LSO算法、DSA算法、SSO-C算法收斂速度較慢，在多峰函數(shù)的求解中很明顯陷入了局部最優(yōu).

(a)f1 (b)f2

(c)f3 (d)f4 (e)f5

5 IGWO算法在港口泊位調(diào)度中的應(yīng)用

5.1 優(yōu)化模型的建立

采用文獻(xiàn)[18]中的港口為研究對(duì)象，引入如下符號(hào)：B為泊位集合；l=1,2,3∈B，表示泊位；V為計(jì)劃期內(nèi)預(yù)計(jì)到港船舶集合；m=1,2,3,4…，表示船舶；O為每個(gè)泊位上船舶靠泊次序集合；n=1,2,3,4…，表示靠泊次序；Am為船舶到達(dá)港口的時(shí)刻；Blm為船舶開(kāi)始靠泊位時(shí)的時(shí)刻；Clm為船舶在泊位上的待裝時(shí)間；Wlm為船舶在泊位上的裝卸時(shí)間. 船m的在港時(shí)間可以描述為：船舶開(kāi)始靠泊時(shí)刻-到港時(shí)刻+泊位待裝時(shí)間+裝船時(shí)間. 即：Blm-Am+Clm+Wlm，所有泊位上船舶總的在港時(shí)間為

以船舶總的在港時(shí)間作為泊位調(diào)度問(wèn)題的目標(biāo)函數(shù). 為得到優(yōu)化目標(biāo)的實(shí)際應(yīng)用形式，令：xlmn={0,1},xlmn=1表示船舶m是在泊位l上的第n條被服務(wù)的船,xlmn=0,表示船舶m還在等待空閑泊位.ylmn表示在泊位l上第n條被服務(wù)的船到港時(shí)刻與同一泊位上第n-1條被服務(wù)的船離開(kāi)時(shí)刻，如果ylmn<0，則讓ylmn=0，即如果第n條被服務(wù)的船在第n-1條被服務(wù)的船離開(kāi)之前到港，則它在第n-1條被服務(wù)的船離開(kāi)時(shí)刻開(kāi)始被服務(wù). 假設(shè)在l泊位上有Pl條船被服務(wù)，Tl表示優(yōu)化所選定的一段時(shí)間內(nèi)泊位l變空閑的時(shí)刻，ms表示泊位l上第s條靠泊船的船號(hào)(s

Wlm1+Wlm2+···+WlmPl+Tl-AmPl+ylm11+ylm22+

···+ylmPlPl+Clm1+Clm2+···+ClmPl.

由所有船舶在港停泊時(shí)間相加，即可得到泊位l上所有船舶的在港停泊時(shí)間，將所有泊位的時(shí)間相加則為所有船舶總在港停泊時(shí)間. 目標(biāo)函數(shù)是使所有在港船舶的總在港作業(yè)時(shí)間最短，即

約束條件:

1)每條船必須在某一泊位上被服務(wù)一次,即

2)每個(gè)泊位服務(wù)的船舶數(shù)應(yīng)該等于總船舶數(shù):

3)每條船必須在達(dá)到之后才能靠泊,即

(9)

5.2 算例分析

在文獻(xiàn)[19]的基礎(chǔ)上，本文考慮7艘船的優(yōu)化調(diào)度問(wèn)題. 已知煤炭碼頭港口在2018年12月20日共有7艘船(A1、A2、A3、A4、A5、A6、A7)到港，到港時(shí)間分別為： 6:00、 8:00、 12:30、 17:30、18:00、 19:00、21:00; 港口有3個(gè)泊位可接待這些船舶：13號(hào)泊位12月21日23：00開(kāi)始處于空閑；14號(hào)泊位12月20日20：12開(kāi)始處于空閑；15號(hào)泊位12月21日16:36開(kāi)始處于空閑.

按經(jīng)驗(yàn)調(diào)度可根據(jù)船舶到港時(shí)間進(jìn)行，安排1號(hào)、4號(hào)、7號(hào)船?？?3號(hào)泊位，2號(hào)、5號(hào)船停靠14號(hào)泊位，3號(hào)、6號(hào)船?？?5號(hào)泊位. 根據(jù)式(9)可得3個(gè)泊位總停時(shí)間為451.6 h.

現(xiàn)采用IGWO算法對(duì)該問(wèn)題求解. 將第一條船到港的時(shí)間記為0:00時(shí)刻，則根據(jù)船舶在港口的時(shí)刻表可得表3、4.

表3 2018.12.20某煤炭碼頭船舶到港時(shí)間順序表

表4 2018.12.20某煤炭碼頭船舶在港服務(wù)時(shí)間分布表

相應(yīng)的13#、14#、15#泊位從第一條船到港至處于空閑的等待時(shí)間為41.0 、14.2、34.6 h. 采用IGWO算法求解，得到最佳靠泊方案為：(3、5、8、4、2、1、9、6、7)，所有船舶在港停留總時(shí)間為385.3 h，較原來(lái)的451.6 h縮短了66.3 h. 可見(jiàn)利用IGWO算法求解能夠得出相對(duì)較佳的調(diào)度方案，可實(shí)現(xiàn)泊位停靠最優(yōu)化.

6 結(jié) 論

本文針對(duì)GWO算法存在的缺陷，提出一種改進(jìn)灰狼算法(IGWO)，經(jīng)測(cè)試函數(shù)驗(yàn)證后應(yīng)用到港口泊位調(diào)動(dòng)中.

1)采用Sin混沌序列進(jìn)行初始化，并引入頭狼引領(lǐng)策略、合作競(jìng)爭(zhēng)機(jī)制和自適應(yīng)權(quán)值，增強(qiáng)了個(gè)體間的信息交流，提高了信息利用率，從而加快了算法的收斂速度.

2) IGWO算法在求解低維函數(shù)和高維函數(shù)時(shí)均能得到精度較高的解，且收斂速度明顯快于GWO算法、LSO算法、DSA算法、BSA算法、SSO-C算法和SSA算法，說(shuō)明該算法具有較快的收斂速度和較高的尋優(yōu)精度.

3)在港口泊位調(diào)度中的應(yīng)用，取得了滿意的應(yīng)用效果，結(jié)果表明，經(jīng)過(guò)IGWO算法優(yōu)化后，所有船舶停留總時(shí)間較優(yōu)化前縮短了14.7%，大幅度縮短了船舶的在港時(shí)間，提高了生產(chǎn)效率，為實(shí)現(xiàn)船舶優(yōu)化調(diào)度提供了有效方法.