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

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

0 引 言

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

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

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

1 問題描述與模型建立

1.1 問題描述與模型的簡化

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

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

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

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

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

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

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

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

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

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

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

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

1.3 目標(biāo)函數(shù)

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

1）不平衡力矩最小

相對(duì)于縱傾而言，船舶的橫傾對(duì)船舶的設(shè)計(jì)以及使用影響更大，因此本文主要考慮橫傾，盡量保證設(shè)備對(duì)船舶中縱剖面力矩的代數(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è)備維修干涉的目標(biāo)函數(shù)為：

3）人員流通距離最小

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

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

4）吊裝距離最小

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

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

1.4 約束條件

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

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

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

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

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

3）其他約束

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

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

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

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

2.1 遺傳算法和粒子群算法

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

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

2.2 量子粒子群算法

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

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

2.3 初始解的生成

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

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

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

圖2 依次選取設(shè)備進(jìn)行布置并更新剩余空間編號(hào)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 計(jì)算步驟

運(yùn)用量子粒子群算法求解布局問題，其計(jì)算步驟如下：

1 初始化量子粒子群算法的各項(xiàng)參數(shù)：種群規(guī)模、進(jìn)化代數(shù)。

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

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

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

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

3 實(shí)例分析與算法比較

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

設(shè)置種群=800，最大迭代次數(shù)=2 000，運(yùn)用量子粒子群算法，對(duì)艙室的布置進(jìn)行優(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 基于量子粒子群算法的機(jī)艙設(shè)備布局結(jié)果Fig. 4 Layout results of cabin equipment based on quantum particle swarm optimization algorithm

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

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

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

圖6 基于粒子群算法的機(jī)艙設(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）研究船舶艙室的布局問題時(shí)，并不能單純得出某種智能算法更優(yōu)的結(jié)論，需要將啟發(fā)式算法與元啟發(fā)式算法相結(jié)合，得到計(jì)算結(jié)果，進(jìn)而討論算法的優(yōu)劣性。

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

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

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