陸　煊，崔　玫，宋　劭，曹洪波

(中國(guó)艦船研究設(shè)計(jì)中心，武漢 430064)

?

基于災(zāi)變遺傳算法的船舶火災(zāi)探測(cè)報(bào)警系統(tǒng)電纜線路設(shè)計(jì)

陸煊，崔玫，宋劭，曹洪波

(中國(guó)艦船研究設(shè)計(jì)中心，武漢 430064)

摘要：針對(duì)火災(zāi)探測(cè)報(bào)警系統(tǒng)電纜線路的優(yōu)化問(wèn)題，首先分析火災(zāi)探測(cè)報(bào)警系統(tǒng)結(jié)構(gòu)，把電纜線路優(yōu)化抽象為TSP問(wèn)題，在遺傳算法的基礎(chǔ)上引入災(zāi)變的概念，對(duì)該問(wèn)題進(jìn)行求解，介紹災(zāi)變遺傳算法的實(shí)現(xiàn)，證明遺傳算法在火災(zāi)探測(cè)報(bào)警系統(tǒng)電纜線路設(shè)計(jì)中的優(yōu)勢(shì)。

關(guān)鍵詞：火災(zāi)探測(cè)報(bào)警系統(tǒng)；線路優(yōu)化；遺傳算法；災(zāi)變

船舶內(nèi)的空間狹小，布滿電力、機(jī)械設(shè)備，使船舶上的火源密集，火災(zāi)易發(fā)，施救困難?；馂?zāi)初期不易發(fā)現(xiàn)，但蔓延速度又十分迅速，一旦火災(zāi)初期不能得到有效控制，過(guò)高的溫度和無(wú)法排出的煙氣使得救援工作極為困難，會(huì)造成無(wú)可估量的人員、經(jīng)濟(jì)損失[1]。所以，目前絕大多數(shù)船舶設(shè)置有火災(zāi)探測(cè)報(bào)警系統(tǒng)，對(duì)火災(zāi)進(jìn)行監(jiān)測(cè)并報(bào)警，在火災(zāi)初期就采取控制措施。

1火災(zāi)探測(cè)報(bào)警系統(tǒng)設(shè)計(jì)

船舶火災(zāi)探測(cè)報(bào)警系統(tǒng)是由火警主機(jī)及顯示器、火災(zāi)探測(cè)器、短路隔離模塊等設(shè)備組成。在船上易發(fā)生火災(zāi)的部位設(shè)置火災(zāi)探測(cè)器，并在船舶火災(zāi)探測(cè)報(bào)警監(jiān)控臺(tái)上顯示探測(cè)器的狀態(tài)，一旦發(fā)現(xiàn)火情，則會(huì)進(jìn)行報(bào)警，并采取相應(yīng)的滅火設(shè)施。感煙探測(cè)器、復(fù)合探測(cè)器及手動(dòng)報(bào)警按鈕等火災(zāi)探測(cè)器大多采用串聯(lián)結(jié)構(gòu)，這些探測(cè)器分部在主、輔機(jī)艙和鍋爐艙、電氣設(shè)備控制室、居住艙及起居處所內(nèi)的脫險(xiǎn)通道等部位，根據(jù)船舶的噸位和用途的不同，火災(zāi)探測(cè)器的數(shù)量會(huì)有較大不同，對(duì)于大型游輪或者大型戰(zhàn)斗艦艇，火災(zāi)探測(cè)器數(shù)量有可能多達(dá)數(shù)百個(gè)，而根據(jù)船舶構(gòu)造的不同火災(zāi)環(huán)路也由一個(gè)到數(shù)個(gè)不等。因此在設(shè)計(jì)工作中優(yōu)化電纜路徑，縮短線路總長(zhǎng)度既可節(jié)約成本，又可以減少施工工程量，縮短施工周期[2]。

船舶火災(zāi)探測(cè)報(bào)警系統(tǒng)首先根據(jù)船舶的艙室性質(zhì)、面積等情況，再結(jié)合火災(zāi)探測(cè)器的屬性，如保護(hù)面積、安裝間距、保護(hù)半徑等約束條件，確定火災(zāi)探測(cè)器的具體位置。然后依照火災(zāi)探測(cè)器之間電纜環(huán)路最短的原則確定探測(cè)器的連接順序組成環(huán)路，環(huán)路從火警主機(jī)t0開(kāi)始，到第一個(gè)火災(zāi)探測(cè)器t1，接著到第二個(gè)火災(zāi)探測(cè)器t2，最終連接到tn-1，最后回到火警主機(jī)t0。

船舶火災(zāi)探測(cè)報(bào)警系統(tǒng)環(huán)路如圖1所示，短路隔離模塊用于保護(hù)線路，附屬于火災(zāi)探測(cè)器，所以具體位置單獨(dú)予以考慮。

圖1　火災(zāi)報(bào)警系統(tǒng)結(jié)構(gòu)示意

2電纜路徑優(yōu)化基本原理

船舶火災(zāi)探測(cè)報(bào)警系統(tǒng)電纜線路可以抽象成經(jīng)典的數(shù)學(xué)模型TSP(traveling salesman problem)問(wèn)題。TSP可以大致描述為某商人要到n個(gè)城市推銷貨物，他從其中一個(gè)城市t0開(kāi)始出發(fā)，需要經(jīng)過(guò)所有城市并且每個(gè)城市只拜訪一次最終到達(dá)城市tn-1，然后返回到出發(fā)城市t0，他必須選擇合適的路徑使他所走的路程最小[3]。船舶火災(zāi)探測(cè)報(bào)警系統(tǒng)中火警主機(jī)可以看成是出發(fā)城市t0，所有火災(zāi)探測(cè)器可以看成是立體空間中的城市，則船舶火災(zāi)探測(cè)報(bào)警系統(tǒng)電纜線路的數(shù)學(xué)描述為有序序列路徑R

(1)

式中:ti——第i個(gè)傳感器，i=(0,1,…,n-1)。

{t0,t1,…,ti,…tn-1}∈T，T為火警主機(jī)t0和所有火災(zāi)探測(cè)器的集合，n為數(shù)量。

如果線路R滿足條件1)，且使線路總長(zhǎng)度f(wàn)(R)的值最小，則f(R)即為所求。

(2)

式中：d(ti,tj)——探測(cè)器ti到tj之間電纜長(zhǎng)度。

傳感器的位置信息可以用三維坐標(biāo)表示，所以需要建立一個(gè)空間坐標(biāo)系，如零點(diǎn)(0,0)為基線和中縱剖面的交點(diǎn)，船艏艉方向?yàn)閤軸，向艏為正，向艉為負(fù)；船左右舷方向?yàn)閥軸，右舷為正，左舷為負(fù)；垂直水平方向?yàn)閦軸，基線以上為正，以下為負(fù)，單位：m。然后確定火警主機(jī)和火災(zāi)探測(cè)器的位置坐標(biāo)。對(duì)于三維設(shè)計(jì)的船舶來(lái)說(shuō)，這個(gè)坐標(biāo)系已經(jīng)存在，對(duì)火災(zāi)探測(cè)器進(jìn)行三維布置之后，直接導(dǎo)出坐標(biāo)數(shù)據(jù)后就可以進(jìn)行路徑規(guī)劃。

傳感器ti的坐標(biāo)為(xi,yi,zi)，由于電纜走向都是平行于坐標(biāo)系的，所以忽略電纜為規(guī)避結(jié)構(gòu)或者設(shè)備進(jìn)行的彎折，火災(zāi)探測(cè)器ti與火災(zāi)探測(cè)器ti+1之間的距離為

(3)

TSP問(wèn)題是一個(gè)典型的NP(Non-deterministic Polynomial)難題，隨著環(huán)路中節(jié)點(diǎn)的增多，解的數(shù)量將呈指數(shù)級(jí)增長(zhǎng)。傳統(tǒng)的方法如窮舉搜索法、分治法、貪心法、分支界定法及動(dòng)態(tài)規(guī)劃法由于時(shí)間復(fù)雜度呈階乘增加在較短時(shí)間內(nèi)得到最優(yōu)解已不大可能[4]。而啟發(fā)式算法如蟻群算法(ACA)、模擬退火(SA)、禁忌搜索(TS)、神經(jīng)網(wǎng)絡(luò)(NN)、粒子群優(yōu)化算法(PSO)、免疫算法(IA)等在一定程度上克服了傳統(tǒng)經(jīng)典方法的不足[5]，提高了算法收斂的效率，其中遺傳算法(GA)對(duì)于此類問(wèn)題有較好的效果。

3遺傳算法的具體實(shí)現(xiàn)

遺傳算法主要包括遺傳編碼、適應(yīng)度函數(shù)和遺傳操作三個(gè)部分[6-7]。

遺傳編碼采用路徑表示編碼，染色體用有序序列R=(t0,t1，…，ti,…,tn-1)表示。

由于要求的最優(yōu)解是電纜路徑最短，所以f(Ri)越大，適應(yīng)度越低，被保留下來(lái)的概率越小，所以適應(yīng)度取函數(shù)f(R)的倒數(shù)，即用f(i)=1/f(Ri)表示。

遺傳操作是遺傳算法的核心，用以模擬自然進(jìn)化過(guò)程的隨機(jī)、迭代、進(jìn)化等過(guò)程。遺傳操作是由3個(gè)基本算子組成：選擇算子、交叉算子及變異算子。

1)選擇算子用來(lái)選擇用于保留適應(yīng)值較高的個(gè)體，即越接近最優(yōu)解的個(gè)體通過(guò)選擇算子保留下來(lái)。選擇算子有多種策略，這里采用輪盤(pán)賭策略，將輪盤(pán)旋轉(zhuǎn)N次(N為群體規(guī)模)，每次產(chǎn)生一個(gè)個(gè)體，共產(chǎn)生N個(gè)個(gè)體構(gòu)成下一代。

2)交叉算子是用來(lái)模擬自然界中繁殖現(xiàn)象的操作，是從老個(gè)體中產(chǎn)生新個(gè)體的主要方法，新生個(gè)體具備雙親個(gè)體的部分特征，體現(xiàn)了遺傳算法的局部搜索能力。

隨機(jī)選取2個(gè)個(gè)體X、Y作為新生個(gè)體Z的雙親。隨機(jī)在X中選取一個(gè)染色體項(xiàng)xr，把X中染色體項(xiàng)xr之前的項(xiàng)加入到新生個(gè)體Z中，然后在Y中找到與xr相同的項(xiàng)ys，依次對(duì)比ys+1,ys+2,…,yn-1,y0,y1,…,ys-1，把不存在于新生個(gè)體Z中的項(xiàng)依次加入到個(gè)體Z的xr之后，使Z中包含所有的探測(cè)器節(jié)點(diǎn)，即產(chǎn)生新個(gè)體Z。這種策略可以遺傳算法后期的加快解的收斂速度，迅速找到局部最優(yōu)解。

3)變異算子是產(chǎn)生新個(gè)體的輔助方法。本文采用2種變異策略，各有50%的概率被選擇。第一種是隨機(jī)選取2個(gè)位置，對(duì)父?jìng)€(gè)體中兩個(gè)位置之間項(xiàng)的順序進(jìn)行反轉(zhuǎn)。第二種是把父?jìng)€(gè)體中城市序列順序隨機(jī)分成S段，重新排列這S段，本文取S=[n/5]，n個(gè)體所含染色體項(xiàng)的數(shù)量即為所有火災(zāi)探測(cè)器和火警主機(jī)數(shù)量之和。

4災(zāi)變遺傳算法

遺傳算法具有較快的收斂性能，但是容易陷入局部最優(yōu)解。雖然輪盤(pán)賭選擇算子和變異算子可以保留和產(chǎn)生遠(yuǎn)離局部最優(yōu)解的個(gè)體，但是依然會(huì)使一些個(gè)體的有效基因因?yàn)榈貌坏接行У膹?fù)制而在遺傳迭代中丟失。所以每當(dāng)在遺傳進(jìn)化進(jìn)入停滯的時(shí)候，需要?dú)⑺喇?dāng)前所有的優(yōu)秀個(gè)體，從而使遠(yuǎn)離局部最優(yōu)解的個(gè)體能夠有充分的自我進(jìn)化的空間，這就是災(zāi)變的概念。所以需要在遺傳算法中加入災(zāi)變算子來(lái)保證遠(yuǎn)離局部最優(yōu)的個(gè)體擁有足夠的空間來(lái)進(jìn)行繁殖進(jìn)化。

災(zāi)變算子決定種群進(jìn)入災(zāi)變時(shí)間和災(zāi)變次數(shù)，包含災(zāi)變條件和終止條件。災(zāi)變條件通過(guò)災(zāi)變初始值INI實(shí)現(xiàn)，每產(chǎn)生新的一個(gè)種群INI就遞減一次，直到為0，就進(jìn)行災(zāi)變操作。若在災(zāi)變前出現(xiàn)了新的最優(yōu)解，則延緩災(zāi)變使INI=k×INI，k1為常數(shù)，k1越大則災(zāi)變時(shí)間越長(zhǎng)。為了使災(zāi)變前還保留一定程度的遠(yuǎn)離局部最優(yōu)解的個(gè)體，設(shè)定k1為1.5。種群不能無(wú)休止地進(jìn)化災(zāi)變，所以需要設(shè)定一個(gè)最大災(zāi)變數(shù)MAX_CAT_CNT=[N/k2]k3，本文中k2取50，k3取2。

選取種群大小64個(gè)，交叉概率為0.5，變異概率0.005，設(shè)定自定義系數(shù)INI=200，F(xiàn)1=1.5，F(xiàn)2=50，F(xiàn)3=1。限于缺少船體和火災(zāi)探測(cè)器三維模型，為驗(yàn)證災(zāi)變遺傳算法的性能，為了實(shí)驗(yàn)結(jié)果更為直觀，隨機(jī)生成200個(gè)坐標(biāo)均在(0.000 0,0.000 0,0.000 0)和(1.000 0,1.000 0,1.000 0)之間的點(diǎn)模擬火災(zāi)探測(cè)器位置信息，初始信息見(jiàn)圖2。

圖2　初始狀態(tài)

經(jīng)過(guò)16次災(zāi)變547 558代，最優(yōu)解產(chǎn)生于第374 942代，即第12次災(zāi)變之后，計(jì)算出的電纜線路總長(zhǎng)度為14.738 993，耗時(shí)15 min 10 s，最優(yōu)解信息見(jiàn)圖3。

圖3　最優(yōu)線路

5結(jié)束語(yǔ)

改進(jìn)的災(zāi)變遺傳算法可以彌補(bǔ)遺傳算法容易陷入局部最優(yōu)解的不足，使解更接近與全局最優(yōu)。引入災(zāi)變遺傳算法可以使火災(zāi)探測(cè)報(bào)警系統(tǒng)電纜走向的設(shè)計(jì)更加快捷和有效，在較短的時(shí)間內(nèi)可以得到較為理想的結(jié)果，節(jié)約了電纜線路設(shè)計(jì)時(shí)間，以及施工的周期和成本。災(zāi)變遺傳算法在在火災(zāi)探測(cè)報(bào)警系統(tǒng)，乃至其他系統(tǒng)的電纜線路設(shè)計(jì)中有著很好的前景。

參考文獻(xiàn)

[1] 朱秋紅.智能化艦船損管系統(tǒng)研究[D].哈爾濱:哈爾濱工程大學(xué),2011.

[2] 汪雪蓮,黃君.遺傳算法在船舶電纜布局優(yōu)化設(shè)計(jì)中的應(yīng)用研究[J].中國(guó)艦船研究,2009(4):72-75,80.

[3] 陸煊,賀軍,朱明富,等.基于災(zāi)變遺傳算法的數(shù)控沖床加工路徑的優(yōu)化[J].計(jì)算機(jī)與數(shù)字工程,2012，40:9-10,13.

[4] 劉朝華，張英杰，吳建輝.一種求解TSP問(wèn)題的改進(jìn)克隆選擇算法[J].系統(tǒng)仿真學(xué)報(bào),2010(7):1627-1631.

[5] 龔本燦,李臘元,蔣廷耀,等.基于局部?jī)?yōu)化策略求解TSP的蟻群算法[J].計(jì)算機(jī)應(yīng)用研究,2008(25):1974-1976.

[6] 李茂軍.單親遺傳算法理論及應(yīng)用[D].長(zhǎng)沙:湖南大學(xué),2002.

[7] 陳霄.DNA遺傳算法及應(yīng)用研究[D].杭州：浙江大學(xué),2010.

Design of Cable Line for Ship Fire Detection and Alarm System Based on Catastrophic Genetic Algorithm

LU Xuan, CUI Mei, SONG Shao, CAO Hong-bo

(China Ship Development and Design Center, Wuhan 430064, China )

Abstract:Aiming at the optimization of cable line of fire detection and alarm system, the structure of fire detection alarm system is analyzed, and the optimization of cable line is abstracted as TSP problem. Based on the genetic algorithm, the concept of disaster is introduced to solve the problem. Realization of the catastrophic genetic algorithm is discussed in detail, which is proved to be helpful in the cable line design of the fire detection and alarm system.

Key words:fire detection and alarm system; route optimization; genetic algorithm; catastrophe

中圖分類號(hào)：U698.4

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1671-7953(2016)02-0058-04

第一作者簡(jiǎn)介：陸煊(1985-)，男，碩士，工程師E-mail:5081484@qq.com

基金項(xiàng)目：國(guó)家部委基金資助項(xiàng)目

收稿日期：2016-01-06

DOI:10.3963/j.issn.1671-7953.2016.02.016

修回日期：2016-01-21

研究方向:船舶輔助系統(tǒng)