粒子群蚁群混合优化算法在船舶机舱布局优化上的应用∗

罗 云 唐丽晴

（武警海警学院计算机教研室 宁波 315801）

1 引言

机舱舱室设计是船舶总体设计的一个重要部分，其布局优化需要兼顾船舶行驶安全、遇险疏散、增加空间利用率等多个目标。但由于机舱布局优化问题的约束条件复杂且优化目标之间相互制约，因而传统的优化算法难以精确地对其求解［1］。基于多种设备之间、设备与舱室之间的复杂的协调关系，尽可能地兼顾多种布局优化的目的，需要给出一种高效的优化算法以精确求得机舱设备的摆放位置。

目前，相关科研工作者已经取得了大量的相关科研成果。韩洋［2］研究了船舶机舱的智能布局优化设计方法。周发模［3］研究了粒子群算法及其在机舱布置优化的应用研究。张国忠等［4］应用遗传算法对机舱关键设备的布置进行优化设计。吴先哲等［5］基于虚拟现实技术，通过运用Tribon、3DS Max 对船舶机舱及设备进行建模并运用Unity 3D进行虚拟装配。该方法能使船舶机舱空间布局及主要设备进行优化。管伟［6］从机装生产设计的角度，结合53000DWT 散货船机舱二层平台综合布置的优化，进行实船三维建模对比分析，找出一套切实可行且具有可比性的优化方案，为优化类似船舶的机舱综合布置提供一些思路，缩短设计周期。何海洋［7］以AutoCAD 为平台，建立机舱模型，利用Multigen Creator和Vega实现其视觉仿真，依照船舶规范，结合人体工程学，应用虚拟技术，实现对舱室优化布置。以上方法能够有效地解决船舶舱室布局优化问题，然而，很少文献考虑利用能够同时兼顾蚁群算法和粒子群算法的混合改进算法来解决船舶舱室布局优化问题。

为将智能优化算法研究的成果更好地应用于船舶舱室优化布局，本文提出了一种结合粒子群算法和蚁群算法的优化策略的混合优化算法并应用于机舱布局优化的具体实际问题中。在Matlab 平台下采用几种不同的优化算法进行对比试验，通过试验结果说明了本文给出的粒子群蚁群混合优化算法具有更佳的算法性能。

2 机舱布局优化问题的约束目标模型

机舱布局优化问题是一个二维布局优化问题，旨在寻到一组机舱设备的摆放位置P ，使得机舱布局最为合理。其中n 为设备数量，( xi,yi)为第i 个设备的中心点坐标。

其约束条件有:

1）设备不靠近机舱舱壁的墙壁

式（1）表示设备与机舱之间必须留有一定的安全距离，L 为机舱长度，H 为机舱宽度，为第i 个设备的长度和宽度，a 为设备与机舱左、右墙壁之间的最小距离，b 为设备与机舱上、下墙壁之间的最小距离。

2）设备与设备之间不干涉

式（2）表示机舱内任意两个不同的设备之间不存在干涉的情况，也即第i 个设备区域内的任一点不在其他设备的区域内。

3）设备与设备之间不干涉

式（3）表示机舱内任意两个不同的设备之间不存在干涉的情况，也即第i 个设备区域内的任一点不在其他设备的区域内。

4）设备与预留通道之间不干涉

式（4）表示机舱设备区域内的任一点( x′,y′)不在机舱内的预留通道区域Ω 中，Ωi为第i 个预留通道，k 为预留通道的数目。

5）主机中心处于机舱的中轴线上

本文仅考虑机舱内含一个主机的情况，此时主机的中心点位于机舱的中轴线上。

其目标函数有:

式（6）中，mi为第i 个设备的质量。

2）人员流通距离f2( P )最小

人员流通距离即是各个设备区域到达楼梯口的距离，它直接描述了当火灾等紧急情况发生时，人员可安全逃生的可能性。人员流通距离越小越好。

式（7）中，F 为楼梯数目。

相关性反映了各个单元之间关系的密切程度，关系越密切的设备应当越靠近。

式（8）中，δi,j为第i 个设备和第j 个设备是相关性系数。

设备应当均匀布置在机舱中轴线的两侧。若集中于一侧，设备正常工作时，设备内会存在自由液面，会造成惯性矩不平衡，影响船舶平稳运行。

式（9）中，nl 和nr 分别为中轴线左侧的设备数目和右侧的设备数目。

3 粒子群蚁群混合优化改进算法

3.1 粒子群算法

粒子群优化算法是1995 年由美国心理学家Kennedy 和电气工程师Eberhart 受鸟群觅食行为的启发下共同提出来的［8～10］。以下给出粒子群算法的更新迭代计算公式。设群体规模为N ，目标搜索空间的维度为D ，第i 个粒子的坐标位置向量为，速度向量为，个体极值为，粒子群全局极值记为。具体的基本粒子群群算法的更新迭代计算公式如下述式（10）所述。

式中i=1,2,…,N 为粒子序号，t 为粒子维度，d为迭代次数，w 为权重因子，c1,c2为加速随机数，一般在0～2之间取值，rand 为0～1之间的随机实数。采用粒子群算法在迭代计算的后期容易陷入局部最优。

3.2 蚁群算法

蚁群算法由意大利学者M.Dorigo 于1992 年提出［11～12］。在蚁群算法中，每只蚂蚁均在进行路径搜索后独立的产生一个可行解，并产生信息素。假设当前共有m 个节点等待蚂蚁访问及选择，在t 时刻，第k 只蚂蚁正处于节点i 处，即将选择下一节点j 进行移动，其移动规则如下:

其中q0已在算法中给出，J 为随机变量，并服从式（12）的概率分布:

每只蚂蚁在构建可行解的同时分泌信息素，局部信息素更新方式如式（13）所示。

当一次循环中的所有蚂蚁均构建了可行解后，对该次循环产生的最优解与已知的最优解进行比较，判断是否产生了新的当前的最优解，若产生，则对该解上的弧信息素进行更新，如式（14）所示。

式（11）～式（15）中，蚁群算法主要变量如下:τij为弧(i,j)上的蚂蚁信息素密度，初始值为τ0；dij为弧(i,j)上的欧式长度；ηij为弧(i,j)上的启发函数值，通常；α 为蚂蚁信息素密度的相对重要性，α ≥0；β 为启发函数的相对重要性，β ≥0；ρ 为蚂蚁信息素的衰减参数，0 ＜ρ ＜1；Lbest为当前最优解的路径长度；Vbest为当前最优解。

3.3 混合优化算法改进策略

由于，粒子群算法使得全部粒子总是向全局极值和个体极值进行学习，因而，粒子群算法是一种寻优模式相对单一的优化算法。蚁群算法也有类似的特点，其最优解对种群的进化方向的影响是很大的。为了克服采用单一的有相对固定寻优指引方向的寻优模式导致的算法容易陷入局部最优的缺点，本文提出了一种同时混入蚁群优化策略的粒子群优化策略的混合优化算法，记为IHOA。目的在于在保持原有粒子群算法和蚁群算法搜索性能的同时，防止算法因为寻优模式单一而导致的陷入局部收敛的缺点。具体的改进的混合优化算法流程图如下所述。

具体的计算步骤如下所述:

Step 1 初始化混合优化算法的各项参数:种群规模m+N 、粒子群规模（粒子数量）N 、迭代次数d 、惯性权重w 、学习因子c1,c2、蚁群规模（蚂蚁数量）m、启发函数的相对重要性β 、蚂蚁信息素的衰减参数ρ 等，其中的粒子群规模与蚁群规模相同m=N ；

图1 改进的混合优化算法流程图

Step2 随机生成m+N 种不同的机舱设备布局方案，也即生成初始种群，初始种群包含初始粒子群和初始蚁群；

Step3 计算N 种机舱设备布局方案的适应度函数值，并基于此对当前粒子群进行排序，以得到个体极值和全局极值；

Step4 采用粒子群算法的更新规则对粒子群中的所有粒子进行更新；

Step5 将这m 只“蚂蚁”置于起始结点0 上，采用蚁群算法的信息素更新规则对所有蚂蚁进行更新；

Step6 粒子群和蚁群交换一定数目k 的个体，其交换数目要小于粒子群规模和蚁群规模k ＜min(m,N)；

Step4 查看是否达到最大迭代次数，如果是则转步骤Step5，否则转步骤Step2；

Step5 输出计算得到的最优解的最大完工时间。

4 仿真实验

4.1 基于测试函数的仿真对比

为验证本文提出的粒子群蚁群混合优化算法相较于其他传统优化算法较优。本文采用De jong测试函数对本文提出的粒子群蚁群混合优化算法、遗传粒子群算法和普通的粒子群算法进行测试。De jong 测试函数的最优解为0.0，其函数公式如下所述。

具体的De jong 函数的仿真测试结果如图2 所述。

图2 采用De jong函数的仿真测试结果图

图2 中，本文提出的粒子群蚁群混合优化算法最优，求得的近似最优解为(x1,x2)=(0.96441,0.99766)；最优解函数值F(x1,x2)=0.4252。

通过算法对比可以发现，粒子群蚁群混合优化算法的寻优性能要优于粒子群算法和蚁群算法。对于测试函数De jong 测试函数来说，粒子群蚁群混合优化算法可以寻到精度更高的近似最优解。

4.2 基于实际算例的仿真对比

基于实际的机舱设备布局优化问题，为验证本文提出的粒子群蚁群混合优化算法相较于其他优化算法更优。本文采用机舱设备布局的实际算例对本文提出的粒子群蚁群混合优化算法、粒子群算法和蚁群算法进行仿真测试。粒子群蚁群混合优化算法、粒子群算法和蚁群算法分别记作IHOA、PSO 和ACO。机舱设备布局优化实际算例选用规格为长8750mm、宽2500mm 的某个民用船的实际机舱，其机舱内的设备尺寸如表1所述。

以下是具体的仿真运行结果。各个优化算法机舱设备布局优化结果得到的如图3～5 所示，各个优化算法机舱设备布局优化结果评分表如表2 所示，各个优化算法的迭代收敛性能如图6所示。

表1 实际算例的机舱内设备尺寸表

图3 粒子群蚁群混合优化算法的机舱设备布局优化结果

图4 粒子群算法的机舱设备布局优化结果

表2 各个优化算法得到的机舱设备布局优化结果的评分表

由图3～5 可知，本文提出的粒子群蚁群混合优化算法的寻优性能更佳，寻到的机舱设备布局优化结果更合理，因此更适合于解决实际的机舱设备布局优化问题。由表2 的评分表更能进一步地验证上述结论。由图6 可知，本文提出的粒子群蚁群混合优化算法的收敛速度更快且寻优精度更高。

图5 蚁群算法的机舱设备布局优化结果

图6 各个优化算法的迭代收敛性能图

5 结语

粒子群算法和蚁群算法都是效率很高的优化算法。然而，粒子群算法和蚁群算法都易于陷入局部收敛，因而不利于求解约束条件复杂和多目标之间存在冲突的机舱设备布局优化问题。为此，本文提出了一种同时兼顾粒子群算法和蚁群算法寻优模式的粒子群蚁群混合优化的改进算法，其改进算法能够有效克服单一寻优模式的优化算法容易陷入局部最优。为验证算法有效性，本文采用了De jong 测试函数和一个具体的机舱设备布局优化问题的实际算例，其优化算法的仿真结果表明粒子群蚁群混合优化的改进算法优于其他两种优化算法，可以用于机舱设备布局优化问题的求解。因此，本文提出粒子群蚁群混合优化的改进算法可以很好地用于机舱设备布局优化问题的求解。