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

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

0 引 言

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

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

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

1 問題描述與模型建立

1.1 問題描述與模型的簡化

機艙布局優(yōu)化問題分為三維布局與二維布局，本文主要在二維層面進行考慮，旨在求得機艙設(shè)備擺放位置的集合，使得船舶的機艙布局最為合理?？梢员硎緸椋?{(,,),···,(x,y,α)}，其中(x,y)為設(shè)備的形心坐標，α為設(shè)備擺放的方向，為設(shè)備的數(shù)量。

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

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

2）將具有復雜形狀的設(shè)備簡化為規(guī)則的長方體。

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

4）艙室內(nèi)部一些大型設(shè)備在設(shè)計初期已經(jīng)固定，如柴油機等。

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

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

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

1.2 數(shù)學模型的建立

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

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

1.3 目標函數(shù)

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

1）不平衡力矩最小

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

式中：為設(shè)備數(shù)量，m為設(shè)備的質(zhì)量，y為設(shè)備形心到中縱剖面的距離，為船舶的初穩(wěn)性高。

2）維修干涉最小

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

3）人員流通距離最小

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

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

4）吊裝距離最小

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

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

1.4 約束條件

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

式中：l為設(shè)備的長，h為設(shè)備的寬。

2）設(shè)備在艙室內(nèi)

在設(shè)備布置的過程中，設(shè)備應(yīng)當全部在艙室區(qū)域以內(nèi)，即()={A?}。

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

3）其他約束

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

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

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

2 基于量子粒子群算法的布局優(yōu)化

2.1 遺傳算法和粒子群算法

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

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

2.2 量子粒子群算法

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

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

2.3 初始解的生成

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

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

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

圖2 依次選取設(shè)備進行布置并更新剩余空間編號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 初始化量子粒子群算法的各項參數(shù)：種群規(guī)模、進化代數(shù)。

2 隨機生成種不同的機艙設(shè)備布局方案，根據(jù)建立的數(shù)學模型，求解種群中粒子的適應(yīng)度。

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

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

5 若不存在干涉，計算新的粒子適應(yīng)度，并執(zhí)行粒子的更新操作，直到迭代結(jié)束。最終得到優(yōu)化后的最優(yōu)解。

3 實例分析與算法比較

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

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

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

表2 設(shè)備關(guān)聯(lián)性要求Tab. 2 Equipment relevance requirements

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

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

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

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

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

圖7 不同算法的適應(yīng)度變化Fig. 7 Fitness changes of different algorithms

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

4 結(jié) 語

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

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

本文研究結(jié)果可為船舶機艙的布置與優(yōu)化提供參考方案。

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