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

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

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

?

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

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

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

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

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

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

1火災(zāi)探測報警系統(tǒng)設(shè)計

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

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

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

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

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

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

(1)

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

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

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

(2)

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

傳感器的位置信息可以用三維坐標(biāo)表示，所以需要建立一個空間坐標(biāo)系，如零點(0,0)為基線和中縱剖面的交點，船艏艉方向為x軸，向艏為正，向艉為負(fù)；船左右舷方向為y軸，右舷為正，左舷為負(fù)；垂直水平方向為z軸，基線以上為正，以下為負(fù)，單位：m。然后確定火警主機和火災(zāi)探測器的位置坐標(biāo)。對于三維設(shè)計的船舶來說，這個坐標(biāo)系已經(jīng)存在，對火災(zāi)探測器進(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)探測器ti與火災(zāi)探測器ti+1之間的距離為

(3)

TSP問題是一個典型的NP(Non-deterministic Polynomial)難題，隨著環(huán)路中節(jié)點的增多，解的數(shù)量將呈指數(shù)級增長。傳統(tǒng)的方法如窮舉搜索法、分治法、貪心法、分支界定法及動態(tài)規(guī)劃法由于時間復(fù)雜度呈階乘增加在較短時間內(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)對于此類問題有較好的效果。

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

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

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

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

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

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

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

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

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

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

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

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

選取種群大小64個，交叉概率為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)探測器三維模型，為驗證災(zāi)變遺傳算法的性能，為了實驗結(jié)果更為直觀，隨機生成200個坐標(biāo)均在(0.000 0,0.000 0,0.000 0)和(1.000 0,1.000 0,1.000 0)之間的點模擬火災(zāi)探測器位置信息，初始信息見圖2。

圖2　初始狀態(tài)

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

圖3　最優(yōu)線路

5結(jié)束語

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

參考文獻(xiàn)

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

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

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

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

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

[6] 李茂軍.單親遺傳算法理論及應(yīng)用[D].長沙:湖南大學(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

中圖分類號：U698.4

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

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

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

基金項目：國家部委基金資助項目

收稿日期：2016-01-06

DOI:10.3963/j.issn.1671-7953.2016.02.016

修回日期：2016-01-21

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