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

(中国舰船研究设计中心，武汉 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

研究方向:船舶辅助系统