粒子群蟻群混合優(yōu)化算法在船舶機艙布局優(yōu)化上的應用?

羅 云 唐麗晴

（武警海警學院計算機教研室 寧波 315801）

1 引言

機艙艙室設(shè)計是船舶總體設(shè)計的一個重要部分，其布局優(yōu)化需要兼顧船舶行駛安全、遇險疏散、增加空間利用率等多個目標。但由于機艙布局優(yōu)化問題的約束條件復雜且優(yōu)化目標之間相互制約，因而傳統(tǒng)的優(yōu)化算法難以精確地對其求解［1］。基于多種設(shè)備之間、設(shè)備與艙室之間的復雜的協(xié)調(diào)關(guān)系，盡可能地兼顧多種布局優(yōu)化的目的，需要給出一種高效的優(yōu)化算法以精確求得機艙設(shè)備的擺放位置。

目前，相關(guān)科研工作者已經(jīng)取得了大量的相關(guān)科研成果。韓洋［2］研究了船舶機艙的智能布局優(yōu)化設(shè)計方法。周發(fā)模［3］研究了粒子群算法及其在機艙布置優(yōu)化的應用研究。張國忠等［4］應用遺傳算法對機艙關(guān)鍵設(shè)備的布置進行優(yōu)化設(shè)計。吳先哲等［5］基于虛擬現(xiàn)實技術(shù)，通過運用Tribon、3DS Max 對船舶機艙及設(shè)備進行建模并運用Unity 3D進行虛擬裝配。該方法能使船舶機艙空間布局及主要設(shè)備進行優(yōu)化。管偉［6］從機裝生產(chǎn)設(shè)計的角度，結(jié)合53000DWT 散貨船機艙二層平臺綜合布置的優(yōu)化，進行實船三維建模對比分析，找出一套切實可行且具有可比性的優(yōu)化方案，為優(yōu)化類似船舶的機艙綜合布置提供一些思路，縮短設(shè)計周期。何海洋［7］以AutoCAD 為平臺，建立機艙模型，利用Multigen Creator和Vega實現(xiàn)其視覺仿真，依照船舶規(guī)范，結(jié)合人體工程學，應用虛擬技術(shù)，實現(xiàn)對艙室優(yōu)化布置。以上方法能夠有效地解決船舶艙室布局優(yōu)化問題，然而，很少文獻考慮利用能夠同時兼顧蟻群算法和粒子群算法的混合改進算法來解決船舶艙室布局優(yōu)化問題。

為將智能優(yōu)化算法研究的成果更好地應用于船舶艙室優(yōu)化布局，本文提出了一種結(jié)合粒子群算法和蟻群算法的優(yōu)化策略的混合優(yōu)化算法并應用于機艙布局優(yōu)化的具體實際問題中。在Matlab 平臺下采用幾種不同的優(yōu)化算法進行對比試驗，通過試驗結(jié)果說明了本文給出的粒子群蟻群混合優(yōu)化算法具有更佳的算法性能。

2 機艙布局優(yōu)化問題的約束目標模型

機艙布局優(yōu)化問題是一個二維布局優(yōu)化問題，旨在尋到一組機艙設(shè)備的擺放位置P ，使得機艙布局最為合理。其中n 為設(shè)備數(shù)量，( xi,yi)為第i 個設(shè)備的中心點坐標。

其約束條件有:

1）設(shè)備不靠近機艙艙壁的墻壁

式（1）表示設(shè)備與機艙之間必須留有一定的安全距離，L 為機艙長度，H 為機艙寬度，為第i 個設(shè)備的長度和寬度，a 為設(shè)備與機艙左、右墻壁之間的最小距離，b 為設(shè)備與機艙上、下墻壁之間的最小距離。

2）設(shè)備與設(shè)備之間不干涉

式（2）表示機艙內(nèi)任意兩個不同的設(shè)備之間不存在干涉的情況，也即第i 個設(shè)備區(qū)域內(nèi)的任一點不在其他設(shè)備的區(qū)域內(nèi)。

3）設(shè)備與設(shè)備之間不干涉

式（3）表示機艙內(nèi)任意兩個不同的設(shè)備之間不存在干涉的情況，也即第i 個設(shè)備區(qū)域內(nèi)的任一點不在其他設(shè)備的區(qū)域內(nèi)。

4）設(shè)備與預留通道之間不干涉

式（4）表示機艙設(shè)備區(qū)域內(nèi)的任一點( x′,y′)不在機艙內(nèi)的預留通道區(qū)域Ω 中，Ωi為第i 個預留通道，k 為預留通道的數(shù)目。

5）主機中心處于機艙的中軸線上

本文僅考慮機艙內(nèi)含一個主機的情況，此時主機的中心點位于機艙的中軸線上。

其目標函數(shù)有:

式（6）中，mi為第i 個設(shè)備的質(zhì)量。

2）人員流通距離f2( P )最小

人員流通距離即是各個設(shè)備區(qū)域到達樓梯口的距離，它直接描述了當火災等緊急情況發(fā)生時，人員可安全逃生的可能性。人員流通距離越小越好。

式（7）中，F(xiàn) 為樓梯數(shù)目。

相關(guān)性反映了各個單元之間關(guān)系的密切程度，關(guān)系越密切的設(shè)備應當越靠近。

式（8）中，δi,j為第i 個設(shè)備和第j 個設(shè)備是相關(guān)性系數(shù)。

設(shè)備應當均勻布置在機艙中軸線的兩側(cè)。若集中于一側(cè)，設(shè)備正常工作時，設(shè)備內(nèi)會存在自由液面，會造成慣性矩不平衡，影響船舶平穩(wěn)運行。

式（9）中，nl 和nr 分別為中軸線左側(cè)的設(shè)備數(shù)目和右側(cè)的設(shè)備數(shù)目。

3 粒子群蟻群混合優(yōu)化改進算法

3.1 粒子群算法

粒子群優(yōu)化算法是1995 年由美國心理學家Kennedy 和電氣工程師Eberhart 受鳥群覓食行為的啟發(fā)下共同提出來的［8～10］。以下給出粒子群算法的更新迭代計算公式。設(shè)群體規(guī)模為N ，目標搜索空間的維度為D ，第i 個粒子的坐標位置向量為，速度向量為，個體極值為，粒子群全局極值記為。具體的基本粒子群群算法的更新迭代計算公式如下述式（10）所述。

式中i=1,2,…,N 為粒子序號，t 為粒子維度，d為迭代次數(shù)，w 為權(quán)重因子，c1,c2為加速隨機數(shù)，一般在0～2之間取值，rand 為0～1之間的隨機實數(shù)。采用粒子群算法在迭代計算的后期容易陷入局部最優(yōu)。

3.2 蟻群算法

蟻群算法由意大利學者M.Dorigo 于1992 年提出［11～12］。在蟻群算法中，每只螞蟻均在進行路徑搜索后獨立的產(chǎn)生一個可行解，并產(chǎn)生信息素。假設(shè)當前共有m 個節(jié)點等待螞蟻訪問及選擇，在t 時刻，第k 只螞蟻正處于節(jié)點i 處，即將選擇下一節(jié)點j 進行移動，其移動規(guī)則如下:

其中q0已在算法中給出，J 為隨機變量，并服從式（12）的概率分布:

每只螞蟻在構(gòu)建可行解的同時分泌信息素，局部信息素更新方式如式（13）所示。

當一次循環(huán)中的所有螞蟻均構(gòu)建了可行解后，對該次循環(huán)產(chǎn)生的最優(yōu)解與已知的最優(yōu)解進行比較，判斷是否產(chǎn)生了新的當前的最優(yōu)解，若產(chǎn)生，則對該解上的弧信息素進行更新，如式（14）所示。

式（11）～式（15）中，蟻群算法主要變量如下:τij為弧(i,j)上的螞蟻信息素密度，初始值為τ0；dij為弧(i,j)上的歐式長度；ηij為弧(i,j)上的啟發(fā)函數(shù)值，通常；α 為螞蟻信息素密度的相對重要性，α ≥0；β 為啟發(fā)函數(shù)的相對重要性，β ≥0；ρ 為螞蟻信息素的衰減參數(shù)，0 ＜ρ ＜1；Lbest為當前最優(yōu)解的路徑長度；Vbest為當前最優(yōu)解。

3.3 混合優(yōu)化算法改進策略

由于，粒子群算法使得全部粒子總是向全局極值和個體極值進行學習，因而，粒子群算法是一種尋優(yōu)模式相對單一的優(yōu)化算法。蟻群算法也有類似的特點，其最優(yōu)解對種群的進化方向的影響是很大的。為了克服采用單一的有相對固定尋優(yōu)指引方向的尋優(yōu)模式導致的算法容易陷入局部最優(yōu)的缺點，本文提出了一種同時混入蟻群優(yōu)化策略的粒子群優(yōu)化策略的混合優(yōu)化算法，記為IHOA。目的在于在保持原有粒子群算法和蟻群算法搜索性能的同時，防止算法因為尋優(yōu)模式單一而導致的陷入局部收斂的缺點。具體的改進的混合優(yōu)化算法流程圖如下所述。

具體的計算步驟如下所述:

Step 1 初始化混合優(yōu)化算法的各項參數(shù):種群規(guī)模m+N 、粒子群規(guī)模（粒子數(shù)量）N 、迭代次數(shù)d 、慣性權(quán)重w 、學習因子c1,c2、蟻群規(guī)模（螞蟻數(shù)量）m、啟發(fā)函數(shù)的相對重要性β 、螞蟻信息素的衰減參數(shù)ρ 等，其中的粒子群規(guī)模與蟻群規(guī)模相同m=N ；

圖1 改進的混合優(yōu)化算法流程圖

Step2 隨機生成m+N 種不同的機艙設(shè)備布局方案，也即生成初始種群，初始種群包含初始粒子群和初始蟻群；

Step3 計算N 種機艙設(shè)備布局方案的適應度函數(shù)值，并基于此對當前粒子群進行排序，以得到個體極值和全局極值；

Step4 采用粒子群算法的更新規(guī)則對粒子群中的所有粒子進行更新；

Step5 將這m 只“螞蟻”置于起始結(jié)點0 上，采用蟻群算法的信息素更新規(guī)則對所有螞蟻進行更新；

Step6 粒子群和蟻群交換一定數(shù)目k 的個體，其交換數(shù)目要小于粒子群規(guī)模和蟻群規(guī)模k ＜min(m,N)；

Step4 查看是否達到最大迭代次數(shù)，如果是則轉(zhuǎn)步驟Step5，否則轉(zhuǎn)步驟Step2；

Step5 輸出計算得到的最優(yōu)解的最大完工時間。

4 仿真實驗

4.1 基于測試函數(shù)的仿真對比

為驗證本文提出的粒子群蟻群混合優(yōu)化算法相較于其他傳統(tǒng)優(yōu)化算法較優(yōu)。本文采用De jong測試函數(shù)對本文提出的粒子群蟻群混合優(yōu)化算法、遺傳粒子群算法和普通的粒子群算法進行測試。De jong 測試函數(shù)的最優(yōu)解為0.0，其函數(shù)公式如下所述。

具體的De jong 函數(shù)的仿真測試結(jié)果如圖2 所述。

圖2 采用De jong函數(shù)的仿真測試結(jié)果圖

圖2 中，本文提出的粒子群蟻群混合優(yōu)化算法最優(yōu)，求得的近似最優(yōu)解為(x1,x2)=(0.96441,0.99766)；最優(yōu)解函數(shù)值F(x1,x2)=0.4252。

通過算法對比可以發(fā)現(xiàn)，粒子群蟻群混合優(yōu)化算法的尋優(yōu)性能要優(yōu)于粒子群算法和蟻群算法。對于測試函數(shù)De jong 測試函數(shù)來說，粒子群蟻群混合優(yōu)化算法可以尋到精度更高的近似最優(yōu)解。

4.2 基于實際算例的仿真對比

基于實際的機艙設(shè)備布局優(yōu)化問題，為驗證本文提出的粒子群蟻群混合優(yōu)化算法相較于其他優(yōu)化算法更優(yōu)。本文采用機艙設(shè)備布局的實際算例對本文提出的粒子群蟻群混合優(yōu)化算法、粒子群算法和蟻群算法進行仿真測試。粒子群蟻群混合優(yōu)化算法、粒子群算法和蟻群算法分別記作IHOA、PSO 和ACO。機艙設(shè)備布局優(yōu)化實際算例選用規(guī)格為長8750mm、寬2500mm 的某個民用船的實際機艙，其機艙內(nèi)的設(shè)備尺寸如表1所述。

以下是具體的仿真運行結(jié)果。各個優(yōu)化算法機艙設(shè)備布局優(yōu)化結(jié)果得到的如圖3～5 所示，各個優(yōu)化算法機艙設(shè)備布局優(yōu)化結(jié)果評分表如表2 所示，各個優(yōu)化算法的迭代收斂性能如圖6所示。

表1 實際算例的機艙內(nèi)設(shè)備尺寸表

圖3 粒子群蟻群混合優(yōu)化算法的機艙設(shè)備布局優(yōu)化結(jié)果

圖4 粒子群算法的機艙設(shè)備布局優(yōu)化結(jié)果

表2 各個優(yōu)化算法得到的機艙設(shè)備布局優(yōu)化結(jié)果的評分表

由圖3～5 可知，本文提出的粒子群蟻群混合優(yōu)化算法的尋優(yōu)性能更佳，尋到的機艙設(shè)備布局優(yōu)化結(jié)果更合理，因此更適合于解決實際的機艙設(shè)備布局優(yōu)化問題。由表2 的評分表更能進一步地驗證上述結(jié)論。由圖6 可知，本文提出的粒子群蟻群混合優(yōu)化算法的收斂速度更快且尋優(yōu)精度更高。

圖5 蟻群算法的機艙設(shè)備布局優(yōu)化結(jié)果

圖6 各個優(yōu)化算法的迭代收斂性能圖

5 結(jié)語

粒子群算法和蟻群算法都是效率很高的優(yōu)化算法。然而，粒子群算法和蟻群算法都易于陷入局部收斂，因而不利于求解約束條件復雜和多目標之間存在沖突的機艙設(shè)備布局優(yōu)化問題。為此，本文提出了一種同時兼顧粒子群算法和蟻群算法尋優(yōu)模式的粒子群蟻群混合優(yōu)化的改進算法，其改進算法能夠有效克服單一尋優(yōu)模式的優(yōu)化算法容易陷入局部最優(yōu)。為驗證算法有效性，本文采用了De jong 測試函數(shù)和一個具體的機艙設(shè)備布局優(yōu)化問題的實際算例，其優(yōu)化算法的仿真結(jié)果表明粒子群蟻群混合優(yōu)化的改進算法優(yōu)于其他兩種優(yōu)化算法，可以用于機艙設(shè)備布局優(yōu)化問題的求解。因此，本文提出粒子群蟻群混合優(yōu)化的改進算法可以很好地用于機艙設(shè)備布局優(yōu)化問題的求解。