基于災變遺傳算法的船舶火災探測報警系統電纜線路設計

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

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

?

基于災變遺傳算法的船舶火災探測報警系統電纜線路設計

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

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

摘要：針對火災探測報警系統電纜線路的優化問題，首先分析火災探測報警系統結構，把電纜線路優化抽象為TSP問題，在遺傳算法的基礎上引入災變的概念，對該問題進行求解，介紹災變遺傳算法的實現，證明遺傳算法在火災探測報警系統電纜線路設計中的優勢。

關鍵詞：火災探測報警系統；線路優化；遺傳算法；災變

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

1火災探測報警系統設計

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

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

船舶火災探測報警系統環路如圖1所示，短路隔離模塊用于保護線路，附屬于火災探測器，所以具體位置單獨予以考慮。

圖1　火災報警系統結構示意

2電纜路徑優化基本原理

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

(1)

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

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

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

(2)

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

傳感器的位置信息可以用三維坐標表示，所以需要建立一個空間坐標系，如零點(0,0)為基線和中縱剖面的交點，船艏艉方向為x軸，向艏為正，向艉為負；船左右舷方向為y軸，右舷為正，左舷為負；垂直水平方向為z軸，基線以上為正，以下為負，單位：m。然后確定火警主機和火災探測器的位置坐標。對于三維設計的船舶來說，這個坐標系已經存在，對火災探測器進行三維布置之后，直接導出坐標數據后就可以進行路徑規劃。

傳感器ti的坐標為(xi,yi,zi)，由于電纜走向都是平行于坐標系的，所以忽略電纜為規避結構或者設備進行的彎折，火災探測器ti與火災探測器ti+1之間的距離為

(3)

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

3遺傳算法的具體實現

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

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

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

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

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

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

隨機選取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中包含所有的探測器節點，即產生新個體Z。這種策略可以遺傳算法后期的加快解的收斂速度，迅速找到局部最優解。

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

4災變遺傳算法

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

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

選取種群大小64個，交叉概率為0.5，變異概率0.005，設定自定義系數INI=200，F1=1.5，F2=50，F3=1。限于缺少船體和火災探測器三維模型，為驗證災變遺傳算法的性能，為了實驗結果更為直觀，隨機生成200個坐標均在(0.000 0,0.000 0,0.000 0)和(1.000 0,1.000 0,1.000 0)之間的點模擬火災探測器位置信息，初始信息見圖2。

圖2　初始狀態

經過16次災變547 558代，最優解產生于第374 942代，即第12次災變之后，計算出的電纜線路總長度為14.738 993，耗時15 min 10 s，最優解信息見圖3。

圖3　最優線路

5結束語

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

參考文獻

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

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

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

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

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

[6] 李茂軍.單親遺傳算法理論及應用[D].長沙:湖南大學,2002.

[7] 陳霄.DNA遺傳算法及應用研究[D].杭州：浙江大學,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

文獻標志碼：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

研究方向:船舶輔助系統