基于量子粒子群算法的船舶機艙布局方法

崔 奧，黃金娥，黃祥兵，江 杰，閔少松

(1. 海軍工程大學 艦船與海洋學院，湖北 武漢 430033；2. 中國人民解放軍92942部隊，北京 100161)

0 引 言

目前，大多數的布局算法都是啟發式與元啟發式相結合的方法。其中，啟發式算法的求解思路主要是根據問題特點，縮小搜索空間，進而得到最終解。這種算法雖能保證解的質量，但是通用性不強。元啟發式方法則是運用遺傳算法、粒子群算法等計算機智能優化算法，用隨機的方式搜索鄰域或者將多個解綜合成新解。這種算法通用性強，但是其結果受智能算法收斂性的影響較大，經常性出現結果不穩定的情況。因此，在布局優化中，2種方法經常被混合使用，以提高算法性能。

船舶機艙布局設計作為布局問題的一種，在滿足一般性布局問題要求的同時，還需要根據艙室環境的特殊性，結合船舶設計規范以及艙室設備布置要求，進行額外的約束，并在求解過程中，將各類約束轉化為罰函數的形式加入到目標函數中，進而利用計算機智能算法進行求解。但是求解思路主要集中在對算法的改進與優化上，未能對啟發式算法的優勢進行充分利用。此外，針對粒子群算法早收斂的特點，Sun J等提出了量子粒子群算法，并在各個領域作為粒子群算法的改進算法得到了廣泛應用，但是尚未應用于船舶艙室的布局問題。

本文借鑒啟發式布局的方式進行初始解的生成，運用量子粒子群算法對某型船舶機艙的設備進行布置，并與遺傳算法和粒子群算法進行對比，說明本文給出的基于量子粒子群算法的布局方法具備更佳的算法性能。

1 問題描述與模型建立

1.1 問題描述與模型的簡化

機艙布局優化問題分為三維布局與二維布局，本文主要在二維層面進行考慮，旨在求得機艙設備擺放位置的集合，使得船舶的機艙布局最為合理。可以表示為：={(,,),···,(x,y,α)}，其中(x,y)為設備的形心坐標，α為設備擺放的方向，為設備的數量。

為了合理表述這個復雜的問題，并建立相應的模型求解，本文進行以下簡化和假設：

1）在艙室布置時，主要考慮對艙室布局有較大影響的設施，管路、電纜以及壁掛式部件不做考慮。

2）將具有復雜形狀的設備簡化為規則的長方體。

3）通過垂直投影將三維布局問題簡化為以艙室甲板為平面的二維布局問題。

4）艙室內部一些大型設備在設計初期已經固定，如柴油機等。

5）艙室入口和可拆板以及吊裝通道的位置已經確定。

6）對不同設備、維修和操作位置可能會有所不同，但是每個設備的維修和操作位置相對為設備本身而言是固定的。

7）設備的擺放朝向問題僅考慮設備的長邊與船舶長度方向平行和垂直的2種情況，即α={0,1}。

1.2 數學模型的建立

一般情況下，船舶艙設備布置需考慮船舶艙室的設計規范及設備布置需求，因此該問題是一個帶復雜約束的多目標優化問題，可建立方程如下：

式中：為設計變量，包括設備的位置坐標及方向等參數，g()和h()分別為設備之間的功能性約束與幾何約束轉化的不等式約束與等式約束，為不等式約束個數，為等式約束個數，L和U則為設備布局的邊界。

1.3 目標函數

本文主要從滿足艙室設備基本布局的基礎上，便于設備維修保養的角度出發建立目標函數。主要從不平衡力矩、維修干涉、船員流通距離以及吊裝距離等方面進行艙室設備的布置。

1）不平衡力矩最小

相對于縱傾而言，船舶的橫傾對船舶的設計以及使用影響更大，因此本文主要考慮橫傾，盡量保證設備對船舶中縱剖面力矩的代數和最小?？啥x不平衡力矩函數為：

式中：為設備數量，m為設備的質量，y為設備形心到中縱剖面的距離，為船舶的初穩性高。

2）維修干涉最小

式中：D為設備的最小維修距離要求，D為設備的最大距離需求，dc為設備與的距離。在考慮維修干涉的過程中，還應該考慮設備的作業頻率f，因此定義船舶艙室設備維修干涉的目標函數為：

3）人員流通距離最小

良好的設備布局應當滿足艙室人員快速出艙的需求，以便在緊急情況下船員能夠迅速撤出工作艙室。定義船員的流通距離函數為：

式中：L為設備到出口的距離，為艙室除艙口外的設備數量，為艙口數量，為艙室的對角線長度。

4）吊裝距離最小

在對船舶艙室設備進行維修的過程中，需要將部分設備吊裝出艙外進行維修，因此需要考慮設備的吊裝距離?？啥x吊裝函數為：

式中：為需要吊裝設備數量；T為設備到吊裝出口的距離，T= |x-x|+|y-y|；T為設備在艙室中的頂角布置時，到吊裝口的距離。

1.4 約束條件

1）設備之間不干涉

式中：l為設備的長，h為設備的寬。

2）設備在艙室內

在設備布置的過程中，設備應當全部在艙室區域以內，即()={A?}。

式中：為艙室長，為艙室寬，α為設備的方向。

3）其他約束

在布置過程中，還需要考慮設備的距離要求以及布置區域等其他類因素，記為：

式中，為布局過程中的其他約束要求。則最后的適應度函數可定義為：

式中：f為目標函數；ω為目標函數的權重，本文取ω=0.2；為違反約束條件的懲罰值。

2 基于量子粒子群算法的布局優化

2.1 遺傳算法和粒子群算法

遺傳算法(GA)是一種基于種群的啟發式算法，是當前最流行的進化算法之一。該算法是一種全局收斂性的算法，它通過遺傳、變異的方式實現種群內部的信息交換，使擁有較高適應度的染色體得以保留，通過多次迭代進化，進而得到最優解。

粒子群算法(PSO)是一種基于群體智能的進化計算方法，具有較強的局部搜索能力。該算法受到鳥類覓食行為的啟發，將種群中的每個粒子均視當前的候選解，在迭代過程中，通過種群中的粒子在多維空間搜索過程中的競爭和合作，進而尋找最優解。

2.2 量子粒子群算法

粒子群算法雖然有較強的局部搜索能力和一定的全局搜索能力，但是其本身存在一定的局限性，并且已經被學者Van den Bergh證明，該算法不是一個全局收斂的算法。對此Sun等在粒子群算法的基礎上，將PSO算法公式進行改進，提出了量子粒子群優化算法(QPSO)，并對其全局收斂的性質進行證明，其算法公式如下：

式中：和是0～1均勻分布的隨機數；P為第個粒子所經歷的最佳位置，P=(p,···,p)；P為全部粒子所經歷的最佳位置，P=(,···,g)；是粒子 群的中間位 置向量；為和之間的隨機點；為收斂系數，隨迭代次數的變化而變化，取=0.5+0.5×(-)，其中，為迭代代數，為當前迭代代數。

2.3 初始解的生成

在布局問題中，為了得到更好的求解結果和效率，設計出了大量的基于不同策略的算法，較為經典的如BL(bottom-left)和BLF(bottom-left-fill)等。這種算法對于二維裝箱問題有較強的適用性，但是對于船舶的艙室布局而言，其布置的原則不是以艙室設備的最小占用面積為主要考慮指標，此外在布局過程中還需考慮設備之間的復雜約束以及某些設備必須安裝在特殊區域，因此，需要探索適用于船舶艙室布局問題的方法，以提高初始解的生成質量。

借鑒文獻 [14]中對三維空間分割進行初始解生成的思路，本文對二維艙室進行分割，根據艙室布置要求，對艙室某個設備放置后，將剩余空間進行分割，如圖1所示。對空間進行分割后，依次選擇待布置設備，判斷分割后的空間能否滿足待布置設備的布設；在滿足裝備能夠布置的區域中隨機選擇某個區域，并在該區域中將待布置設備隨機布放，完成設備的布置后，對剩余可布置空間進行更新，如圖2所示。依次選取剩余設備，進行設備的布置，直至全部設備布放完畢。艙室設備的布置流程如圖3所示。

圖1 空間分割示意圖Fig. 1 Schematic diagram of space division

圖2 依次選取設備進行布置并更新剩余空間編號Fig. 2 Select the equipment in turn for layout and update the number of remaining space

圖3 初始解生成流程圖Fig. 3 Flow chart of initial solution generation

2.4 計算步驟

運用量子粒子群算法求解布局問題，其計算步驟如下：

1 初始化量子粒子群算法的各項參數：種群規模、進化代數。

2 隨機生成種不同的機艙設備布局方案，根據建立的數學模型，求解種群中粒子的適應度。

3 根據步驟2中所得結果，利用量子粒子群算法對粒子進行更新，并檢驗所得粒子中的各設備之間是否存在干涉，若存在干涉，則執行步驟4，否則跳到步驟5。

4 若存在干涉，找出干涉設備并尋找區域重新布置，若無法布置，則生成新的粒子并加入種群中進行迭代

5 若不存在干涉，計算新的粒子適應度，并執行粒子的更新操作，直到迭代結束。最終得到優化后的最優解。

3 實例分析與算法比較

選用某型船舶機艙為例，進行算法的驗證。已知該型船長為6.75 m，寬為3 m，初穩性高為0.8 m，艙室設備原始布置情況及維修需求如表1所示。根據相關規范與標準，設備的布置類約束如表2所示。

設置種群=800，最大迭代次數=2 000，運用量子粒子群算法，對艙室的布置進行優化，其優化后的結果與適應度變化曲線分別如圖4所示。

表1 艙室設備原始布置及維修需求表Tab. 1 Original layout and maintenance requirements of cabin equipment

表2 設備關聯性要求Tab. 2 Equipment relevance requirements

圖4 基于量子粒子群算法的機艙設備布局結果Fig. 4 Layout results of cabin equipment based on quantum particle swarm optimization algorithm

同樣條件下，分別運用遺傳算法（設置遺傳算法的=0.8，=0.01）和粒子群算法（設置慣性權重=0.8，學習因子均設置為0.8）對上述案例進行優化，所得的布局結果如圖5和圖6所示。將3種算法的適應度變化進行對比，如圖7所示。從優化的效果看，量子粒子群算法＞遺傳算法＞粒子群算法。各算法的目標函數值如表3所示。

圖5 基于遺傳算法的機艙設備布局結果Fig. 5 Engine room equipment layout results based on genetic algorithm

此外，文獻 [4]中的粒子群算法的優化效果優于遺傳算法效果的結論，在本文中并不成立。因此，對于船舶艙室的布局問題，需要針對具體算法與初始解的生成方式進行具體分析，進而得到相應的結論。

圖6 基于粒子群算法的機艙設備布局結果Fig. 6 Layout results of cabin equipment based on particle swarm optimization algorithm

圖7 不同算法的適應度變化Fig. 7 Fitness changes of different algorithms

表3 不同算法下的優化效果比較Tab. 3 Comparison of optimization effects under different algorithms

4 結 語

1）研究船舶艙室的布局問題時，并不能單純得出某種智能算法更優的結論，需要將啟發式算法與元啟發式算法相結合，得到計算結果，進而討論算法的優劣性。

2）對于機艙布局，在運用本文初始解生成方式的前提下，量子粒子群算法的計算結果優于遺傳算法和粒子群算法。

本文研究結果可為船舶機艙的布置與優化提供參考方案。

在后續研究中，主要從3個方面進一步研究：一是布局問題初始解生成的生成與規劃的問題；二是各類智能算法的改進與優化在布局算法中的應用；三是布局問題的元啟發式算法與啟發式算法相結合與匹配的問題。