基于改进NSGA-Ⅱ的船舶管路路径设计
2022-04-28董宗然王法胜楼偶俊卞璇屹
董宗然，王法胜，楼偶俊，卞璇屹
(1.大连外国语大学 软件学院，辽宁 大连 116044；2.大连民族大学 信息与通信工程学院，辽宁 大连 116600；3.大连理工大学 船舶工程学院，辽宁 大连 116024)
0 引言
船舶管路如同人体的血管，负责在船舶设备间传输油、气、水、电等资源，对船舶功能实现和性能表现有着重要影响。船舶管路设计一般可分为：初步设计、功能设计、详细设计、生产设计和系统支持信息5个连续阶段[1]。其中，管路路径的布局优化设计属于详细设计阶段的重要工作。船舶空间常按功能划分为不同区域，如机舱区、生活区、甲板区、特殊功能区等。机舱空间相对狭小，设备和管路繁多，布局约束复杂，因此机舱区的管路布局优化是船舶管路设计的难点[2]。船舶管路路径设计本质上是在设备接口间寻找满足约束条件和优化目标的连通路径，目前主要依靠人工在不断试错中完成，十分低效。因此，研究自动化船舶管路路径设计方法具有重要意义。
相关研究在过去近二十年中发展迅速，一些代表性研究包括：KANG等[3]提出采用基于知识规则的专家系统布置船舶管路，并给出了一个原型系统;PARK等[4]提出一种基于单元生成技术的管路设计方法，但由于单元生成模式有限，不适合复杂的管路布局;ASMARA[5]提出一个针对船舶机舱管路详细设计的算法框架，为管路自动设计系统开发指明方向;KIM等[6]在CAD环境下基于网络优化法开发了一个船舶管路设计系统，但该方法由于精度较低，只适合为管路初步设计提供参考;范小宁[7]提出基于蚁群算法布置船舶管路，JIANG等[8]、WANG等[9]对其工作进行了扩展研究。笔者早期工作提出基于最短快速算法[10]和LEE—禁忌搜索算法[11]求解船舶布管，关注算法效率和复杂约束处理，近期工作则侧重遗传算法在船舶管路布局方面的改进研究[12-13]，关注布管质量提升。相关研究从解决小规模简单问题逐渐发展到解决大规模实际问题，但大多停留在实验室研究阶段。此外，以SolidWorks、Catia、UG等为代表的商业建模软件目前也提供了自动步路模块，但只能按有限连接模式生成两点间的简单路径，同时缺少避障功能，仍然依赖设计师手工调整。出现以上现象的主要原因是船舶管路路径设计是在复杂约束条件下的多目标优化问题，而传统算法将多目标优化通过线性加权方式转换为单目标优化，仅输出唯一优解或类似优解(具有相同评价值的多个优解)[5,7-9,11-14]。这类算法获得的优解不一定是最优解，优解集也不是Pareto优解集，计算结果依赖各目标权重设置，限制了算法推广。近年来，多目标优化问题的研究热度很高，其中使用多目标进化算法(Multi-Objective Evolutionary Algorithms, MOEAs)求解的研究最为丰富[15]。KONAK等[16]综述了基于遗传算法的多目标优化算法发展历程和设计要素，其中最具代表性的研究为NSGA(non-dominated sorting genetic algorithm)[17]及NSGA-Ⅱ[18]。NSGA提出较早，但存在非支配排序计算复杂度高，缺少精英解保护机制，需要指定共享参数等不足；NSGA-Ⅱ基于快速非支配排序策略对NSGA进行改进，在保证求解质量的前提下降低时间复杂度并且不需要指定共享参数，是目前多目标优化研究的主流算法。在此基础上，参考Pareto设计思路，一些学者还设计出了多目标蚁群优化(Multi-Objective Ant Colony Optimization, MOACO)[19-20]和多目标粒子群优化(Multi-Objective Particle Swarm Optimization, MOPSO)[21-22]，但不如NSGA-Ⅱ算法成熟和应用广泛。管路路径设计属于多目标优化问题，更适合采用多目标优化算法求解。AHMED等[23]尝试使用NSGA-Ⅱ在二维空间求解多目标路径设计问题；郭秀[24]以管路长度、弯头数、安装性为优化目标，探索了应用NSGA算法求解直角管路的布局优化问题；柳强等[25-26]采用NSGA-Ⅱ求解发航空发动机的布管问题；文献[27-28]初次尝试应用NSGA-Ⅱ布置三维船舶管路。以上研究已证明多目标优化算法在求解各类管路路径设计问题中前景很好，但由于问题复杂性和领域局限性，目前相关研究仍然较少，同时多目标优化算法在实际应用中容易出现早熟收敛、寻优性能差、解集分布不均等问题。为此，本文针对船舶管路路径设计提出一种基于NSGA-Ⅱ的改进算法，主要研究内容包括：
(1)算法优化目标设计。根据实际管路布局需求，扩展算法所能处理的优化目标和约束条件，使布局结果更符合需要。
(2)算法流程改进。在NSGA-Ⅱ框架基础上引入改进策略，提升算法寻优能力、稳定性和收敛性。
(3)算法应用扩展。为应对工程中的大量复杂管路，基于改进多目标算法和人工决策给出布局成束管路和分支管路的流程。
1 问题建模
1.1 布局空间和路径
布局空间内安装着各类设备，可用包络矩形法近似替代原始设备外形，既满足布管精度又便于算法设计[2,5,7]。网格分解法是管路设计问题中最流行的预处理方法，将空间网格分解后便可借助网格属性描述管路路径、障碍区域和布局约束等[2,5,7-14,25-28]。网格划分过程如下：根据最小管径尺寸(网格边长L)将三维布局空间划分成网格集合，将障碍空间覆盖的网格标记为“禁用”状态，将允许管路经过的空间网格标记为“自由”状态，对于“自由”状态网格，通过网格能量值区分网格所在区域对管路的接受程度，将期望管路通过空间网格设置为低能量，不期望管路通过空间网格设置为极高能量，其余自由空间网格设置为常规能量。
在网格空间中布置管路p时，若其管径(Dp)大于网格边长L，为保证p不与障碍物和已布置管路发生干涉，可采用膨胀法处理，通过式(1)[12,28]计算障碍物向外膨胀距离，在布置管路p前先对障碍物做膨胀处理(膨胀空间网格标记为“临时禁用”状态)，然后运行寻路算法可保证管路p的中心线路径扩展回原始尺寸后不与障碍物干涉，最后将膨胀空间恢复成初始状态(“临时禁用”被重置为“自由”状态)。采用障碍膨胀法，可以在同一网格空间完成不同管径管路的布局。
(1)
式中：Np表示障碍物向外膨胀的网格数;Dp表示管路p的最大管径;L表示网格边长。
将布局空间划分网格后，各网格位置可用行、列、层构成的网格坐标描述，设布局空间左、下、后顶点网格坐标为(0,0,0)，序号为k的网格坐标记为(Rk,Ck,Lk)。令管路起点所在网格序号为0，终点所在网格序号为N，则路径总长度为N个网格边长之和，路径可用网格位置序列表示，如式(2)所示。
p(0→N):(R0,C0,L0)→…→(Rk,Ck,Lk)→
(Rk+1,Ck+1,Lk+1)→…→(RN,CN,LN)。
s.t.
|Rt+1-Rt|+|Ct+1-Ct|+|Lt+1-Lt|=1,
t=0,…,N-1。
(2)
文献[8]的方法用起点、折弯点、终点位置坐标表示管路，但在路径评价中也需转换成上述路径表示，本质上与此相同。
1.2 优化目标和约束
实际船舶布管中考虑的优化目标和约束较多[2]，本文算法处理如下主要优化目标和约束条件：
(1)优化目标
Obj.1连接管路接口的管路路径长度尽可能短；
Obj.2管路路径的折弯数目尽可能少；
Obj.3管路尽可能靠近支撑面(舱壁、地板、设备表面)敷设，方便安装固定；
Obj.4管路路径尽可能避免出现“凹兜”结构(路径在竖直方向形成的U型管段)，减少传输介质在“凹兜”处发生阻滞；
Obj.5管路相邻折弯间距离尽可能不小于限定长度(L)，减少管路折弯的加工成本；
Obj.6对管路接口靠近的多条同类管路尽可能成束敷设，以便共享支架，节省成本并提高美观性。
(2)约束条件
Con.1管路路径能连接管路接口点，而且不与障碍物(舱室结构、设备、已布置管路、预留空间等)发生干涉，可通过路径生成算法保证该约束；
Con.2管路路径与船体结构间保持正交布置，即管路布局走势与地面或设备等刚性结构垂直或平行，该约束可通过网格分解模型和布管算法保证，实际布局中允许某些管路倾斜放置，可由设计师手工调整。
设p是路径空间R中长度为N的一条网格路径，则船舶管路路径设计问题的多目标形式如式(3)所示：
minf(p)={Obj.1,Obj.2,Obj.3,Obj.4,
Obj.5,Obj.6}
={flength(p),fbends(p),fpower(p),fpocket_num(p),
fover_limit_num(p),fneighbor_cells_convert(p,q)}。
s.t.
h(p)=0,g(p)=0。
(3)
其中：Obj.1～Obj.6对应优化目标;h(p)、g(p)对应约束条件Con.1和Con.2，h(p)为0表示路径不与环境空间发生干涉，g(p)为0表示路径与刚性结构正交布置。
fneighbor_cells_convert(p,q)=1.0/(x-(y-z))，表示路径p与路径q(已布置管路)并行敷设程度的度量值。计算方法如下：先统计路径p与路径q间相邻网格数目x、路径p经过的网格数目y、当前最短路径经过的网格数目z。x-(y-z)表示有效并行网格数目的估算值，值越大并行效果越好，取其倒数形式转化成最小值优化问题，fneighbor_cells_convert(p,q)∈(0,1]。原理如图2所示，p路径中x取值较大，是因为p在q附近有迂回路径导致，迂回路径的网格数目被记入到x中，需减掉(估算值为p路径与当前最短路径网格数之差)。
2 基于改进NSGA-Ⅱ的管路路径设计
船舶管路路径设计是典型的多目标优化问题。求解多目标优化问题，早期使用最多的是加权求和法，将多目标优化转换为单目标优化，该方法实现简单，但需要主观指定目标权重。此外，单目标优化算法一次运行仅能给出唯一优解或评价值相同的类似优解，而基于多目标优化的NSGA-Ⅱ算法，一次运行可给出问题的Pareto优解集(每个优解适度满足各目标而又不被其他优解支配[16])，为设计者提供更多参考方案。
2.1 求解管路布局的改进NSGA-Ⅱ框架
根据NSGA-Ⅱ算法框架，提出改进算法求解船舶管路布局设计，流程如下。
算法1Dong-MO算法。
步骤1算法预处理。包括：导入问题模型、网格划分布局空间、设置网格状态(能量值和障碍标记)、选定待布局管路、对环境障碍物做膨胀处理等。
步骤2初始化算法参数。包括：种群规模pop_size、交叉概率cross_rate、变异概率mutate_rate、进化代数max_num、爬山次数climb_num、路径不同个体占比阈值differ_rate。
步骤3初始化最优解集pareto，即pareto=∅。
步骤4基于改进A*和连接点策略生成初始种群parent[12]，计算parent中个体的各目标值。
步骤5迭代变量置0，即iter=0。
步骤6复制种群parent到子代种群child。
步骤7在child种群上执行交叉、变异、爬山算子。
步骤8计算child种群中个体各目标值。
步骤9合并parent和child到新种群combo，即combo=parent∪child。
步骤10对combo种群个体进行快速非支配排序(fast-non-dominated-sort)和拥挤度距离计算，将combo种群个体分类到不同的非支配前沿面集合F1,F2,…,Fk。
步骤11根据前沿面排序和拥挤度距离，从combo个体中选出新一代parent种群[18]。
步骤12将最优前沿面F1中个体与pareto解集个体按2.2.4节算法(non_dominated_merge)进行非支配合并，更新pareto。
步骤13去除pareto中存在的重复个体(布局路径相同个体保留一个)。
步骤14检查parent中路径不同个体占比是否超过阈值differ_rate，若超过，则去除parent中多余重复个体，并生成新个体补充到parent种群以维持种群规模不变。
步骤15判断iter是否小于进化代数max_num，若是，则iter=iter+1，转步骤6，否则转步骤16。
步骤16输出pareto优解集。
影响NSGA-Ⅱ性能的关键因素是快速非支配排序(fast non-dominated sorting)，其时间和存储复杂度分别是O(MN2)和O(N2)，M是目标个数，N是种群规模[18]。
相比经典的NSGA-Ⅱ[16,18]，新算法改进表现为：在步骤7中引入爬山算子；在步骤12中将当前迭代优解与全局优解进行非支配合并；为避免种群出现过多同质个体，在步骤14加入种群多样性保持操作。此外，针对船舶管路布局问题设计了遗传编码和进化算子。
2.2 算法关键步骤设计
2.2.1 路径编码和种群生成
遗传算法的编码被称为染色体，由基因片段组成。本文采用可变长编码，即将连接起点S和终点T的管路路径编码成从起点到终点所经过的网格序列，同时要求路径编码中的任何网格不经过障碍空间。
进化种群由一定数量的编码个体组成，初始种群是遗传进化的起点状态。由于初始种群质量对算法性能影响较大，采用基于A*算法的随机路径生成算法构建高质量初始种群个体[12]。文献[27-28]基于LEE算法构建种群个体，算法性能和个体质量方面与A*算法相比没有优势[12]。A*算法可用于在三维网格空间快速生成两点间距离短、折弯少、尽量贴壁敷设的连通路径。为保证初始种群中的个体多样性，引入连接点策略，即先在布局空间的非障碍网格中随机选择网格作为中间连接点，之后用A*算法分别构建起点到连接点和连接点到终点的路径段，再将二者连接形成完整路径，重复以上过程，直到个体数量满足种群规模。为了进一步提高解质量，可规定连接点仅从邻接支撑表面的网格(S1)中选取。高质量路径都是低能量的，路径势必包含很多靠近支撑表面的网格(S2)。因为S2⊂S1，所以从S1中选择连接点范围足够，且能提高优解生成概率。采用连接点策略构建个体路径可能会生成非法路径，为方便观察，以二维图为例说明(如图3和图4)，图3a两段路径在连接点附近发生重叠，图4a两段路径连接后存在环路。因此，可采用去重叠和去环路算法对生成个体进行后处理，保证个体路径的有效性，去除重叠和环路后的路径如图3b和图4b所示。
2.2.2 遗传算子
2.2.3 局部爬山算子
在种群进化中，交叉和变异操作之后得到的子代路径可通过尝试改变折弯模式提升质量。本文基于两种折弯模式修改策略，即rectangle-mode和cuboid-mode。
rectangle-mode中，在待优化路径中随机找出相邻的3个折弯点(B1-B2-B3)，3个折弯可处在不同平面，以B1和B3折弯为对角顶点位置构建矩形，尝试调整B2位置到对角位置，可将当前连接模式更换成另一种连接模式(XY↔YX、XZ↔ZX、YZ↔ZY)，“↔”表示转换，如XY模式表示从B1开始先沿X探索路径网格，再沿Y探索路径网格到达B3，其他情况与此类似，如图7a所示。
cuboid-mode中，在待优化路径中随机找出相邻的4个折弯点(B1-B2-B3-B4)，以B1和B4折弯点为对角顶点构建长方体，则两顶点间的连接模式共有6种(XYZ↔XZY↔YXZ↔YZX↔ZXY↔ZYX)，调整B2、B3位置，可将当前连接模式变换成其他连接模式之一，如图7b所示。
爬山操作将得到的新个体与原个体进行比较，若新个体好于原个体，则替换原个体。本文多目标优化没有单目标优化中的个体评价值，因此提出基于多目标的比较算子，若原个体(pold)通过折弯模式变化得到的新个体(pnew)满足让折弯数和路径能量两个目标至少一个变好，而其他目标不下降，则接受当前折弯模式修改，条件表达如式(4)所示：
((fbends(pnew) fpower(pold)) or (fbends(pnew)≤fbends(pold) and fpower(pnew) flength(pold) andfpocket_num(pnew)≤fpocket_num(pold) andfover_limit_num(pnew)≤fover_limit_num(pold) and fneighbor_cells_convert(pnew,q)≤fneighbor_cells_convert(pold,q)。 (4) 为了保证爬山效果，每代进化建议对child种群内的所有个体分别执行climb_num次rectangle-mode和cuboid-mode爬山操作。 2.2.4 精英保留 每次迭代经过快速非支配排序后，迭代最优解会被保存在Pareto前沿面F1中，其中的优解个体可能是进化所能找到的最优解，也可能是当前搜索到的最优解。为了不丢失迭代中能发现的全部精英个体，设置一个Pareto精英解集，用于保存进化中发现的当前最优解，要求其中的个体间互不占优。因此需要在每次迭代后将F1中个体与Pareto解集中个体进行非支配合并，合并算法(non-dominated-merge)描述如下。 算法2non-dominated-merge算法。 输入：F1为当前迭代获得的最优前沿面个体集合，pareto为保存当前精英个体的集合; 输出：pareto，为将F1与原pareto合并更新后的新精英解集合。 for X in F1: flag=True for Y in pareto: flag=False break if flag==True: for Z in pareto: pareto=pareto-{Z} pareto=pareto∪{X} 2.2.5 种群更新和多样性保持 文献[27-28]的方法先采用模糊集理论对Pareto解集中个体的目标值进行规范化，使各目标取值范围在[0,1]之间，再基于个体目标值之和与解集个体的目标值之和计算个体适应值，种群更新的选择算子使用个体适应值和二分锦标赛策略实现。 本文没有采用个体适应值进行非支配排序和选择下一代种群，而是基于快速非支配排序得到的个体前沿面级别和拥挤度距离作为排序依据构建下一代种群。主要原因是文献[27-28]的方法中，基于适应值进行个体优劣比较与单目标优化类似，虽然一些布局方案的路径不同，但适应值可能相同，而基于多目标的非支配排序来比较个体优劣，更符合NSGA-Ⅱ算法，得到的Pareto解种类更丰富，计算量相对更小。 由于每次迭代需将父代种群P先复制一份给子代种群Q，再在子代种群Q上进行交叉、变异，该过程可能会在Q中产生父代种群P中原来就有的个体。随着P与Q合并，以及对合并种群进行快速非支配排序和拥挤度计算，选出新一代种群P，将导致P中出现管路布局相同的个体。由于重复的优秀个体彼此不占优，随着进化发展，P中的重复个体比例升高，导致早熟收敛。为此提出如下改进：在每代种群P选出之后，计算路径不同个体所占的比例(重复个体算一个)，当比例低于阈值时，将重复个体保留一个，删除其他的，再用连接点策略和A*算法生成相同数目的新个体补充到P中。改进策略使精英个体得以保留，又提高了种群多样性。 管路布局设计中对接口靠近、性质相同的管路，希望成束布局以共用支架。为实现基于改进NSGA-Ⅱ算法的多管路成束布局，提出以下算法流程。 算法3管路成束布局流程。 步骤1读取预定义的布局配置文件，确定各管路敷设顺序和相邻关系，设管路布置顺序为{p1,p2,…,pN}，相邻关系为后一条管路(pk+1)靠近前一条管路(pk)布置。 步骤2按提出算法(Dong-MO)布置管路p1，算法结束后从p1的Pareto解集中选择一个优解方案p1(l1)。 步骤3对p1(l1)路径经过的网格设置状态(管路ID、障碍标记)，并将p1(l1)路径周围网格能量值设为0。 步骤4按Dong-MO算法布置下一条管路p2，生成p2种群个体时要求连接点在p1(l1)路径周围网格中随机选取，以提高个体靠近p1布置概率，中间连接点个数从步骤1配置文件读取并对连接点做排序[12]。算法结束后，从p2的Pareto解集中选择一个优解方案p2(l2)，参照步骤3对p2(l2)进行设置。 步骤5参照步骤2～步骤4，继续完成后续管路p3,…,pN的布置。 步骤6输出由{p1(l1),p1(l2),…,pN(lN)}构成的多管路成束布局方案。 船舶中存在大量分支管路，分支管路布局需要确定分支管路布置顺序和分支点位置。该决策可由人或算法生成。文献[5,11]先由算法随机生成布管次序，再通过比较确定最终顺序，分支点位置则按接口到已布完分支的最短路径方式生成；文献[28]则基于管路分级和通过比较接口间的欧氏距离之和来确定接口连接次序。多目标优化需要从Pareto解中选择优解，因此可由用户制定分支策略，增加布局灵活性。基于改进NSGA-Ⅱ算法的分支管路设计流程如下。 算法4分支管路布局流程。 步骤1读取预定义的分支管路接口连接顺序(按接口尺寸降序排列)，记为{b1,b2,b3,…,bN}。 步骤2先按Dong-MO算法布置b2到b1的分支路径，再从Pareto解集中选择一个优解方案，记为b2(l1)。 步骤3观察b2(l1)，若不满意，则恢复布管环境，转步骤2重新设计；若满意，则标记b2(l1)分支所经过的网格状态(管路ID)。 步骤4基于OpenGL拾取技术在b2(l1)路径网格中为b3接口选取连接点P(也可按[11]中算法生成)，再用Dong-MO算法设计b3到P的分支路径，从Pareto解集中选择一个优解方案，记为b3(l2)。 步骤5观察b3(l2)，若不满意，则重置布管环境，转步骤4重选连接点P或保持不变，调用Dong-MO算法重新设计b3到P路径；若满意，则标记b3(l2)分支所经过的网格状态。 步骤6参照步骤4～步骤5完成剩余接口{b4,…,bN}到已完成分支的路径设计(P在已布分支网格中选取)。 步骤7输出由{b2(l1),b3(l2),b4(l3),…,bN(lN-1)}构成的分支管路设计方案。 为了分析算法表现，分别采用仿真算例和实际算例进行验证。仿真算例考察算法寻优能力、收敛性、稳定性和时间代价；实际算例考察算法求解复杂问题时的表现。 开发环境：Microsoft Visual Studio 2019 VC++，编译器优化设置为最大优化(优选速度)/O2；OpenGL；SolidWorks；Python。运行环境：Intel(R)Core(TM)i5-8265U CPU，RAM 24.0 GB，Windows 10 x64。 3.1.1 布局空间描述 设管路布局空间为100×100×100的立方体空间，坐标原点位于中心。考虑机舱障碍较多，布管空间有限，在空间内设置了13个长方体障碍物，各障碍物对角顶点坐标如下：{(-45,-50,20)～(-30,20,0);(0,-50,30)～(50,10,10);(0,-50,-10)～(50,50,-30);(-40,-50,50)～(-20,50,30);(-50,-50,-20)～(-20,50,-30);(-20,-10,-40)～(0,0,20);(-50,-50,-20)～(-30,-20,0);(-30,-50,-50)～(10,30,-40);(-20,-50,-40)～(0,-40,20);(-10,0,-10)～(0,50,10);(30,-50,50)～(20,-40,40);(-10,-50,50)～(-20,-10,20);(-14,-10,-16)～(-6,-16,8)}。 3.1.2算法参数设置 种群规模pop_size=40，交叉概率cross_rate=0.85，变异概率mutate_rate=0.05，进化代数max_num=100，连接点个数mid_points_num=1(单管路、成束布局时首条管路)或3(成束布局时后敷设管路)，爬山次数climb_num=20，种群内不同个体占比阈值differ_rate=40%；网格空间靠近内侧面和障碍物表面的网格能量值设为0，连接点从能量值为0的网格中选取，相邻折弯间管段长度设为2倍网格边长。 3.1.3 单管路布局算例 用50×50×50的粒度将布局空间网格化，算例中各管路起点和终点的网格坐标为：P1(49,0,49)～(0,23,0)，P2(49,0,49)～(49,23,0)，P3(0,0,49)～(0,23,0)，P4(0,0,49)～(49,23,0)。 为了对比研究，分别用本文算法Dong-MO、根据文献[27-28]算法思想实现的算法Sui-MO(以LEE算法构建路径，用模糊集理论计算个体评价值，算法步骤和参数与Dong-MO相同)和单目标遗传算法Dong-SO[13]对以上布局问题进行求解。因为算法具有随机性，每种算法均布置管路10次以上。 分析各算法一次运行后所求得的最优解信息(取Sui-MO算法获得解个数最多的一次)，如表1所示，其中“包含优解个体数目”表示在个体路径的6个度量目标相同时，路径布局不同的个体数目。与表1对应的Dong-MO和Sui-MO求得路径布局如图8、图9所示(路径间有重叠，需要时可逐一观察单条路径布局)。Dong-SO方法布局效果可参考文献[13]，其布局结果只是Dong-MO和Sui-MO方法结果之一。 表1 管路布局结果信息 注：成束度量取值范围为(0,1]，当该值为1时，表示路径与成束布置无关;记为“-”时，表示不适用。 通过对比可知，各算法求得优解均能满足路径的能量值最低、不违反折弯长度限制和不带“凹兜”结构，本算例为单管路布局，不涉及成束敷设，因此成束度量值列为1，算法差别主要体现在发现优解数目和布局路径种类方面。单目标优化算法Dong-SO每次运行只能得到唯一优解，Sui-MO每次运行能获得评价值相同的部分Pareto优解，不能发现子目标不全相同且互不支配的优解，Dong-MO算法获得优解数目最多，可完全包含其他两种方法的优解，布局样式更丰富。 统计Dong-MO算法在P1～P4管路上10次运行获得Pareto优解个数，如表2所示。不同管路间获得解的个数差别较大主要与布局空间形状有关，布局空间顶部位置可供P1、P2形成优解通路较少，而可供P3、P4形成优解通路较多；改进算法每次运行能找到P1、P2的几乎全部Pareto优解，也能找到P3、P4的绝大部分Pareto优解；P1、P2管路解个数接近均值，P3、P4管路解个数在均值附近波动，说明算法寻优性能稳定。 表2 Dong-MO算法10次运行获得优解个数 观察Dong-MO算法在P1～P4管路布局上的一次运算，路径不同个体随迭代过程在种群中的比例不断变化，如图10所示，可见种群会随着进化过程出现同质化(相同个体增多)，多样性保持策略能够及时剔除重复个体并补充新个体，使种群多样性维持在合理水平，促进算法发现更多优解。 3.1.4 多管路成束布局算例 对于多管路成束布局，布管顺序不同或对先布局管路的方案选择不同都会影响最终布局效果。例如，Case 1按P5、P6、P7顺序依次布置，先布置P5，得到的Pareto优解集如图11a所示，从布局结果中选择下方一个长度短的布局结果，在此基础上布置后续管路，得到的一个布局效果如图11b，若为P5选择上方一个折弯少的布置方案，得到的一个并行布局效果如图11c；若按P7、P6、P5顺序布置，先布置P7，得到的优解集如图12a，分别以P7下方两个不同方案为基础成束布局，得到的效果如图12b和12c。可见，用多目标优化算法结合顺序和优解选择可以构建多种布局方案，相比单目标方法只给出唯一方案，改进方法能更好地满足用户需求。 本文方法基于多目标比较确定个体间支配关系，但优化目标不是硬性约束，选出的优解不能保证满足每个目标的最优状态。例如，算法获得的一个优解在P6和P7中存在违反折弯间距离限制的情况(如图15)，这会导致折弯加工成本增大。因此，工程师在选择结果时需做核查或借助算法滤掉非法解。 对比Case 1和Case 2获得布局效果1时的一次运算中，100次迭代的耗时统计如表3所示。由网格划分粒度可知，Case 2网格数是Case 1的8倍，去除障碍网格后有效网格数小于8倍，算法计算时间上Case 2接近Case 1的7倍，说明算法耗时与网格数目线性相关，算法计算性能良好。 表3 不同网格划分下算法耗时对比 3.2.1 布局问题描述 该实际算例取自文献[28]，为某溢油应急处置船中机舱管系的燃油管路，布局空间涉及的主要设备包括：燃油日用柜2个、蒸汽锅炉1个、热水锅炉1个、柴油发电机2台、主机2台、燃油输送泵2台。上述设备简化模型主要部件对角顶点网格位置参见文献[28]中的表4。布局空间尺寸为5 700 mm×3 360 mm×9 600 mm。鉴于管路最小管径为22 mm，网格精度取30 mm，布局空间划分为190×112×320个立方体网格单元。 管路布局需求为在上述空间中设计6条连接相应设备的燃油管路P1～P6。该管路系统原理参见文献[28]中图21，各条管路所连接的设备、接口点网格位置、管径尺寸等参见文献[28]中表5，其中管路P1、P2、P6为等管径分支管路，管路P3、P4、P5为非等管径分支管路。 3.2.2 算法参数设置 由于该算例网格数目远多于上节算例，约是50×50×50划分网格数的54倍，100×100×100划分网格数的7倍，为了提升计算速度，将种群规模(pop_size)减小为20，其他参数设置与前节算例相同。 实际管路布局通常对接口方向有要求，因此计算前可将接口网格位置向外延伸一段距离，本实验中默认接口延伸距离为4个网格尺寸。考虑管路P3、P4、P5在燃油日用柜下方的主分支管路接口位置靠近，且需跨越燃油泵连接两侧燃油柜，因此采用与文献[28]类似策略，加大此处接口延伸距离，分别设置为28、30、32网格距离。文献[28]中提到将接口位置向外延伸可使布局更加灵活，但没有给出具体延伸数值。 按管路P1～P6主分支管径尺寸由大到小确定布置顺序为：P1或P2→P4或P5→P3→P6，实验中取P1→P2→P4→P5→P3→P6；分支点位置按选定接口点到已布完分支间的最短路径方式生成，对于非等径分支管路，按各接口尺寸降序排列，管路P1～P6接口连接顺序分别为：{1,2,3,4}，{1,2,3,4}，{1,2,3,4,5,6}，{1,2,3,4,5,6}，{1,2,3,4}，{1,3,4,2}。 3.2.3 布局结果及分析 本文算法(Dong-MO)完成布局后可在软件环境中实时观察设计效果，为方便工程师结合经验交互式修改结果，软件实现了到CAD建模系统的导出接口，在SolidWorks中显示的机舱燃油管路布局效果如图16所示。 用Dong-MO算法获得的两个优化布局如图17所示，与文献[28]算法(记为Sui-MO*)结果进行对比分析(如表4)，可得如下结论： (1)由于多目标优化结果与Pareto解的选取策略有关，因此Dong-MO在该算例上可产生多种布局方案，表4中列出Dong-MO的两个结果，左侧对应图17a，右侧对应图17b，它们在P3之外的管路上获得了不同路径，方案1、2的路径总长度和总折弯数分别为(2 773,44)，(2 828,43)，两者整体优化目标相差不大，长度上的差别主要由P6路径不同引起；虽然方案2的路径长度大于方案1，但其靠近锅炉设备的管路更短，减少了为管路做隔热处理的代价。 (2)Dong-MO与Sui-MO*在P1、P2、P3布局效果上接近，但在P4、P5、P6布局效果上有差异，Sui-MO*的路径总长度和总折弯数为(3 224,42)。对比发现Dong-MO和Sui-MO*总折弯数相近，但Dong-MO的总路径长度小于Sui-MO*，主要是因为Dong-MO可在P5、P6上找到更短路径。此处长度对比不是精确比较，原因如下：文献[28]没有给出接口延伸距离，且设备模型仅包含主要部件，数据不完整会影响结果准确复现；路径长度统计时对分支点网格计数规则可能不同，Dong-MO路径总长度为各分支长度累加，在分支点处有少量重复计数，文献[28]对此未说明；文献[28]中表5的管路P4、P5接口数据与该文献图22中P4、P5的接口位置无法对应(在燃油日用柜下方接口交换了位置)，Dong-MO算法以表5数据为准计算，由此可能导致长度统计上的差别。此外，文献[28]中表4发电机1的第6个坐标应为(146,33,118)，而非(46,33,118)，否则与设备模型相差较大。 (3)Sui-MO*对管路P5的布局不如Dong-MO布局合理。因为P5在燃油柜下方接口是管径为42 mm的一级接口，在蒸汽锅炉和热水锅炉上接口是管径为34 mm的二级接口，为提高燃油供应效率，应让二级接口与一级接口间的主分支管连接。Sui-MO*布局中存在二级接口间共享部分路径与主管相连的情况。这与Sui-MO*算法将分支管路间的重叠长度作为子优化目标有关。 文献[28]提到对Sui-MO*结果仅作少量修改即可满足实际布管需求，实验表明Dong-MO算法同样适于该案例设计，甚至在路径长度、布局合理性等方面表现更好，说明了本文算法的有效性和先进性。 表4 机舱燃油管路路径对比 续表4 本文提出一种基于NGSA-Ⅱ的船舶管路路径设计方法。使用A*算法和连接点策略构建种群个体和遗传算子；基于个体多目标间的比较关系定义支配算子，同时考虑多个布局优化目标，增加了Pareto解集的多样性；通过引入爬山操作、精英保留和种群多样性保持来改进算法框架以提高算法寻优能力；在多目标单管路算法的基础上给出了多管路成束布局和带分支管路布局的求解过程。相比将多目标优化转化为单目标优化后再求解的传统算法，本文所提算法能在一次运算中求得高质量的Pareto优解集，为工程师提供更多参考；与基于文献[27-28]方法的多目标船舶布管算法相比，本文算法求得的Pareto优解数量更多、布局类型更丰富。 未来将基于OpenMP或CUDA技术对算法作并行化改进，提升算法效率；探索基于机器学习技术的船舶管路设计方法。2.3 成束管路布局设计
2.4 分支管路布局设计
3 实验及结果分析
3.1 仿真模型管路设计算例
3.2实船机舱燃油管路设计算例
4 结束语
