改進灰狼算法及其在港口泊位調度中的應用

李長安，謝宗奎，吳忠強，張立杰

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

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

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

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

1 GWO算法

GWO算法的主要思想如下：從待尋優空間的任意位置開始，將具有最優適應度值的個體設置為頭狼α，適應度值排第2和第3的個體設置為下屬狼β和普通狼δ，其余為底層狼ω. 在捕食過程中，首先由α、β和δ判斷獵物所在位置并進行追捕；當發現獵物所在位置時，α、β和δ帶領ω對獵物進行圍剿，通過不斷迭代搜索得到最優值.

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

(1)

隨后，狼群其他個體利用α、β和δ之間的位置判斷獵物位置，對獵物進行圍剿，該過程可描述為

(2)

2 改進GWO算法

2.1 Sin混沌初始化

初始種群位置對算法的收斂速度和求解精度有很大的影響，甚至會導致尋優的失敗. 在初始化的過程中，搜索空間的隨機分布會使種群個體分布不均，多樣性較差. 混沌映射是由確定性方程得到的具有隨機性的運動狀態，具有隨機性、遍歷性的特點. Logistic映射和Sin映射是混沌學中常用的兩種映射，其映射表達式分別為

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時產生混沌現象，產生的xn+1的范圍為(0,1). 為比較上述兩種混沌映射的混沌特性，利用式(3)和式(4)分別產生區間(-1,1)上的2維混沌解，如圖1所示.

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

·Sin映射 °Logistic映射

2.2 頭狼引領

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

(5)

2.3 合作競爭機制

(6)

(7)

2.4 自適應慣性權值

為滿足GWO算法在不同迭代周期的尋優要求，提高收斂速度和尋優精度，引入自適應慣性權值w，且

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

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

(8)

2.5 算法步驟

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

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

步驟3. 計算種群中每個個體的適應度值，并選取適應值最小的3個個體的位置分別作為α、β和δ.

步驟4. 按式(5)執行頭狼引領策略.

步驟5. 除α、β、δ的灰狼個體按式(6)、式(7)執行合作競爭機制.

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

步驟7. 若達到最大迭代次數，轉至步驟9；否則轉至步驟8.

步驟8. 每隔一定迭代次數，重新排序，確定灰狼的位置，轉至步驟3.

步驟9. 輸出當前最優解，算法結束.

3 IGWO算法的收斂性分析

為證明IGWO算法的有效性，采用Markov鏈對該算法的收斂性進行分析[18]. 設搜索空間為H，頭狼引領、狼群互動和圍攻等行為均會引起狀態空間中的狀態轉移，設3個行為過程的轉移矩陣分別為S、M和W，則定義IGWO的Markov鏈轉移矩陣為

P=S×M×W.

首先,證明IGWO的優化解序列是一個有限齊次Markov鏈. 設Qk={x1,x2,…,xN}為IGWO的第k代種群，N為灰狼種群大小，xi為第i只灰狼的狀態. 因為灰狼種群Qk是有限的，所以該算法的解序列是有限Markov鏈. 其次，由于IGWO算法中頭狼引領、狼群互動和圍攻行為都是在獨立隨機過程中進行的，每次個體更新具有優勝選擇的繼承性，第k+1代種群的產生只與第k代群體有關，與各代群體之間的轉移概率無關. 經過種群的位置更新，可以得到一組優化解序列. 因此，經過IGWO一系列獨立隨機的變換處理得到的優化解序列是一個有限齊次Markov鏈.

還需證明IGWO算法種群序列的Markov鏈是遍歷鏈.

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

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

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

綜上所述，IGWO算法的Markov鏈是遍歷鏈.

文獻[17]已經證明，若一個進化算法滿足以下條件：1)對可行解空間中任意2點x1和x2，x2是x1由算法中各種算子可達的； 2)若種群序列Q1,Q2,…,QT是單調的，則此進化算法以概率1收斂于問題的全局最優解. 由于IGWO算法種群序列的Markov鏈是遍歷鏈，條件1)顯然是成立的. 由于IGWO算法中頭狼引領、狼群互動和圍捕行為的位置狀態更新都體現出優秀解的保持策略，所以IGWO優化解序列是一個有限齊次Markov鏈，并且每次種群個體位置只有遇到更優解時才會更新. 因此，IGWO算法產生的子代Qk+1中的任意解都非劣于Qk，由此可得種群序列Q1,Q2,…,QT是單調的. 綜上所述，IGWO算法以概率1收斂于問題的全局最優解.

4 仿真測試

為檢驗IGWO 算法的尋優能力，將本算法與SSA、BSA、SSO-C、LSO、DSA和標準GWO算法在同樣的環境下進行仿真比較. 所使用電腦的詳細設置：CPU為Intel(R)Pentium(R)CPUG2020;頻率為2.90 GHz；內存為4.00 GB. 操作系統windows7，仿真軟件為MATLAB2015b.

4.1 標準測試函數

實驗選取5個標準測試函數進行測試，如表1所示.

表1 標準測試函數

4.2 參數設置

BSA算法中,c1=c2=1.5，a1=a2=1，FQ=10；SSO-C算法中，PF=0.65；LSO算法中成年獅的占比β=2%；DSA算法中，T1=3，T2=1 000，速度為1，A=5,M=3,e=4. 為保證測試的公平性，6種算法的種群數量均為100，最大迭代次數M=200，為避免單次運行的隨機性帶來的影響，各算法獨立運行20次，取平均值和標準差. 5個測試函數分別在D=2、D=30和D=100這三種維度下進行仿真.

4.3 實驗分析

為驗證IGWO算法的有效性，對各算法的尋優精度和收斂速度進行比較分析. 表2為7種算法對5個標準測試函數的尋優結果.

表2 7種算法的對比測試結果

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

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

(a)f1 (b)f2

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

5 IGWO算法在港口泊位調度中的應用

5.1 優化模型的建立

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

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

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

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

由所有船舶在港停泊時間相加，即可得到泊位l上所有船舶的在港停泊時間，將所有泊位的時間相加則為所有船舶總在港停泊時間. 目標函數是使所有在港船舶的總在港作業時間最短，即

約束條件:

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

2)每個泊位服務的船舶數應該等于總船舶數:

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

(9)

5.2 算例分析

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

按經驗調度可根據船舶到港時間進行，安排1號、4號、7號船?？?3號泊位，2號、5號船停靠14號泊位，3號、6號船?？?5號泊位. 根據式(9)可得3個泊位總停時間為451.6 h.

現采用IGWO算法對該問題求解. 將第一條船到港的時間記為0:00時刻，則根據船舶在港口的時刻表可得表3、4.

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

表4 2018.12.20某煤炭碼頭船舶在港服務時間分布表

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

6 結 論

本文針對GWO算法存在的缺陷，提出一種改進灰狼算法(IGWO)，經測試函數驗證后應用到港口泊位調動中.

1)采用Sin混沌序列進行初始化，并引入頭狼引領策略、合作競爭機制和自適應權值，增強了個體間的信息交流，提高了信息利用率，從而加快了算法的收斂速度.

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

3)在港口泊位調度中的應用，取得了滿意的應用效果，結果表明，經過IGWO算法優化后，所有船舶停留總時間較優化前縮短了14.7%，大幅度縮短了船舶的在港時間，提高了生產效率，為實現船舶優化調度提供了有效方法.