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

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

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

0 引 言

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

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

1 問(wèn)題描述與模型建立

1.1 問(wèn)題描述與模型的簡(jiǎn)化

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

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

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

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

3）通過(guò)垂直投影將三維布局問(wèn)題簡(jiǎn)化為以艙室甲板為平面的二維布局問(wèn)題。

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

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

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

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

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

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

式中：為設(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ù)和最小。可定義不平衡力矩函數(shù)為：

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

2）維修干涉最小

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

3）人員流通距離最小

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

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

4）吊裝距離最小

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

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

1.4 約束條件

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

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

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

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

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

3）其他約束

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

式中，為布局過(guò)程中的其他約束要求。則最后的適應(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)化算法之一。該算法是一種全局收斂性的算法，它通過(guò)遺傳、變異的方式實(shí)現(xiàn)種群內(nèi)部的信息交換，使擁有較高適應(yīng)度的染色體得以保留，通過(guò)多次迭代進(jìn)化，進(jìn)而得到最優(yōu)解。

粒子群算法(PSO)是一種基于群體智能的進(jìn)化計(jì)算方法，具有較強(qiáng)的局部搜索能力。該算法受到鳥(niǎo)類覓食行為的啟發(fā)，將種群中的每個(gè)粒子均視當(dāng)前的候選解，在迭代過(guò)程中，通過(guò)種群中的粒子在多維空間搜索過(guò)程中的競(jìng)爭(zhē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 初始解的生成

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

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

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

選用某型船舶機(jī)艙為例，進(jìn)行算法的驗(yàn)證。已知該型船長(zhǎng)為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ì)于船舶艙室的布局問(wèn)題，需要針對(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é) 語(yǔ)

1）研究船舶艙室的布局問(wèn)題時(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)一步研究：一是布局問(wèn)題初始解生成的生成與規(guī)劃的問(wèn)題；二是各類智能算法的改進(jìn)與優(yōu)化在布局算法中的應(yīng)用；三是布局問(wèn)題的元啟發(fā)式算法與啟發(fā)式算法相結(jié)合與匹配的問(wèn)題。