郜怀通，王荣杰,2，曾广淼，刘文霞

(1．集美大学轮机工程学院，福建 厦门 361021；2．福建省船舶与海洋重点实验室，福建 厦门 361021)

0 引言

为了应对越来越复杂的优化问题，人们基于生命系统，研究出了诸多优化算法，比如基于“优胜劣汰，适者生存”的进化类算法，典型代表有：通过遗传和变异进行求解的遗传优化算法(genetic algorithm,GA)[1]、模仿生物群体的合作和竞争进行求解的差分进化方法(differential evolution,DE)[2]、模仿生物体内免疫系统的进化进行求解的免疫算法(immune algorithm,IA)[3]等。模仿生物种群觅食和迁徙行为群智能算法典型代表有：模仿鸟群迁徙行为求解的粒子群优化算法(particle swarm optimization,PSO)[4]、模仿蜂群觅食行为求解的人工蜂群优化算法(artificial bee colony,ABC)[5]、模仿蚁群觅食行为求解的蚁群优化算法(ant colony optimization,ACO)[6]等。

国内外主要将群智能优化算法应用于解决多约束问题，Kamil等[7]提出了一种使用群智能算法来增强水下图像颜色的方法;Guan等[8]将改进的群算法用于船舶内壳的参数设计与优化，在保证船舶安全性的同时，极大地提高了船舶的载运能力；Zhang等[9]将群智能算法用于图像分割，可以更加精确地从图像中提取有意义的特征，提高了图像识别的精度。

ABC算法和PSO算法，在无约束目标优化中展现出了较好的收敛性和搜索性。本文使用这两种算法对多个约束优化问题进行处理。文中对约束处理有如下的创新：

1)对算法第k次迭代得到的优化解,将其满足约束条件的个数q(k)设定为权值，进行优化解替换时,优先考虑权值的大小，使更新解始终满足q(k)≥q(k-1)，k≥2。

2)改进的群智能算法将步长由确定值改为每次迭代都会变化的随机值，增强了算法的搜索能力。

1 约束问题

约束优化问题的形式如式(1)所示：

适应度函数：f(x1,…,xn)。

约束条件：

(1)

式(1)中，存在n个自变量x1,…,xn，定义域为[zi,oi]，求得的向量x=[x1,…,xn]在使得f(x1,…,xn)的解最优的同时，需要满足所有约束函数gj(x1,…,xi)的值域。

求解过程中，一次需要求出多组优化解，分别储存在向量x1,…,xK中，设定k=1,…,K，如果向量xk满足约束条件的个数大于向量xk+1满足约束条件的个数，则xk优于xk+1;如果xk满足约束条件的个数等于xk+1满足约束条件的个数，则比较xk与xk+1的适应度函数，确定最优值。即以xk满足约束条件的个数(即等式/不等式gj(x)成立的个数)作为最高评价准则，其次比较xk的适应度函数值f(xk)。

这就要求在通过算法求解的过程中需要建立评价函数，将每组自变量满足条件的个数，储存在向量aevaluate中，用于选择优质的自变量。

本文选择解决方案由式(2)所示。

(2)

其中：F(x)用来存放适应度函数；f(x)max是满足所有约束的解中可行性最差的解。如果求得的解均不能满足所有的约束条件，则f(x)max取值为0。

2 群智能算法

2.1 ABC算法

ABC算法主要分为初始化、工蜂(EB)、观察蜂(OB)、侦查蜂(SB)四个阶段[10-11]。初始化阶段设定蜂群的规模为sn，维度为n，使用式(3)随机生成初始解ai,j,

ai,j=a_minj+rand[0 1]·(a_maxj-a_minj)。

(3)

其中：rand[0 1]表示在0～1产生一个随机数；a_maxj和a_minj分别为蜜源a第j维的解能取到的最大值和最小值，j=1,2,…,n,i=1,2,…,sn。将a存入矩阵v。

EB、OB和SB阶段蜜源的位置由式(4)进行更新，

a(i,j)=v(i,j)+2{rand[0 1]-0.5}[v(i,j)-v(r,j)]。

(4)

其中：r是[1sn]之间随机的一个整数，且不等于i。

ABC算法的运算流程如图1所示。

ABC算法在实际应用中被发现了一些固有的缺点。例如，在处理单峰问题时，收敛速度比差分优化算法慢。除此之外，在解决复杂的多模态问题时，极容易陷入局部最优[13]。为了平衡ABC算法的探索和开发能力，众多研究人员开始对ABC算法进行改进。比如使用自适应方法改进ABC算法[13-14]，引入其他群智能算法的搜索方程改进ABC算法[15-16]。

本文中使用了文献[17]提出的MABC算法。MABC算法参考了具有较强全局收敛能力和稳健性的DE算法[18]，引入了DE算法的搜索方程。MABC算法的搜索方程如下所示。

EB阶段:ebi,j=amin,j+rand[0 1](amax,j-amin,j);

OB阶段:obi,j=ebi,j+rand[0 1](ebr,j-ebi,j);

SB阶段:sbi,j=obi,j+2{rand[0 1]-0.5}(obi,j-obk,j)。

其中：ebi,j、obi,jsbi,j分别代表EB、OB、SB阶段的更新解；amin,j和amax,j分别代表蜜源ai,j第j维的最小值和最大值；r,l,k皆为[1np]之间一个随机的整数，且r≠l≠i,k≠i。

2.2 PSO算法

PSO算法的初始化方程如式(5)所示：

(5)

其中：ai,j是粒子群的初始位置；vi,j是粒子群的初始速度；amin,j和amax,j分别是位于矩阵a第j维的最小值和最大值；vmin,j和vmax,j分别是速度v第j维的最小值和最大值。

进行一次搜索之后，粒子群的位置和速度根据式(6)进行更新：

Vi,j=w-vi,j+c1rand[0 1](pj-ai,j)+

c2rand[0 1](gj-ai,j)，Xi,j=ai,j+Vi,j。

(6)

其中：p是粒子群的个体最优位置；g是粒子群的全局最优位置；w是粒子的惯性权重，代表粒子有维持自己先前速度的趋势，用来平衡算法的全局收敛能力和局部收敛能力，一般取值为[0.8，1.2]；c1、c2是粒子群的学习因子，用来调节粒子向p和g方向的搜索长度，一般都取值为1.5。

PSO算法优化流程如图2所示。

3 算法的多约束问题优化

3.1 ABC算法的实现

使用ABC算法进行优化时，步骤如下。

步骤1：设定蜂群的数量为sn，i=1,2,…,sn，蜂群维度为n，j=1,2,…,n。最大迭代次数设为K；迭代次数计数器为k，k=0,1,2,…。允许连续得不到更优解的次数设为Klimit，连续得不到更优解的计数器为t，t=0,1,2,…；创建存储矩阵G。

步骤2：蜂群初始化。

1)设定第j维的优化解能取到的最大值为a_maxj，最小值为a_minj；k=0。

2)初始化蜂群，通过式(3)创建初始解a。将初始解a存入矩阵v，矩阵a、v第i行数据分别表示为ai和vi。

3)设定适应度函数f(x)，约束函数gd(x)，d=1,…,D，D为约束函数的个数。设定第i组解满足约束函数个数的计数器为ddi，ddi=1,…,D。满足的约束条件越多，适应度函数的值越靠近目标值，寻到的解越好。

4)计算矩阵v第i组解的f(xi)和ddi，i=1,2,…,sn。

步骤3：EB阶段。

1)若t≤Klimit,使用式(4)创建更新解a；若t≥Klimit，使用式(3)创建更新解a且令t=0。

2)如若出现ai,j>a_maxj或ai,j

3)计算更新解a第i组解的适应度函数值f_eb(xi)和满足约束的个数dd_ebi，i=1,2,…,sn。

4)对比ddi和dd_ebi，如果ddidd_ebi保留vi；若ddi=dd_ebi，对比f(xi)和f_eb(xi)，若f_eb(xi)比f(xi)更靠近目标值，将vi替换为ai，否则保留vi。i=1,2,…,sn。

5)若适应度函数最优值没有得到更新，t=t+1。

6)若t>Klimit，则跳至步骤3 1)。

步骤4：OB阶段。

1)使用式(4)创建更新解a。

2)如若出现ai,j>a_maxj或ai,j

3)计算更新解a第i组解的适应度函数值f_ob(xi)和满足约束的个数dd_obi，i=1,2,…,sn。

4)对比ddi和dd_obi，如果ddidd_obi，保留vi；若ddi=dd_obi，对比f(xi)和f_ob(xi)，若f_ob(xi)比f(xi)更靠近目标值，将vi替换为ai，否则保留vi。i=1,2,…,sn。

5)若适应度函数最优值没有得到更新，t=t+1。

6)若t>Klimit，则跳至步骤3 1)。

步骤5：SB阶段。

1)使用式(4)创建更新解a。

2)如若出现ai,j>a_maxj或ai,j

3)计算更新解a第i组解的适应度函数值f_sb(xi)和满足约束的个数dd_sbi，i=1,2,…,sn。

4)对比ddi和dd_sbi，如果ddidd_sbi，保留vi；若ddi=dd_sbi，对比f(xi)和f_sb(xi)，若f_sb(xi)比f(xi)更靠近目标值，将vi替换为ai，否则保留vi。i=1,2,…,sn。

5)若适应度函数最优值没有得到更新，t=t+1。

6)若t>Klimit，则跳至步骤3 1)。

7)令k=k+1。

8)Gk,1～n储存第k次迭代中的最优解，Gk,n+1储存对应的适应度函数值。

9)若k≥K，进行步骤f；不然跳至步骤3 1)。

10)输出最优解储存矩阵G。

3.2 PSO算法的实现

使用PSO算法进行优化时，步骤如下。

步骤1：设定粒子群的数量为sn，i=1,2,…,sn，粒子群的维度为n，j=1,2,…,n。最大迭代次数设为K；迭代次数计数器为k，k=0,1,2,…；惯性权重设为ω；学习因子设为c1和c2；创建存储矩阵G，储存个体最优位置的向量P，储存全局最优位置的向量g。

步骤2：粒子群初始化。

1)设定第j维的优化解的能取到的最大值为amax,j，最小值为amin,j，最大速度为vmax,j，最小速度为vmin,j；k=0。

2)初始化粒子群，通过式(5)创建粒子群初始位置a，粒子群初始速度v，矩阵a和v的第i行数据分别表示为ai和vi。

3)设定适应度函数f(x)，约束函数gd(x)，d=1,…,D，D为约束函数的个数。设定第i组解满足约束函数的个数的计数器为ddi，ddi=1,…,D。满足的约束条件越多，适应度函数的值越靠近目标值，寻到的解越好。

4)计算初始解a第i组解的f(xi)和ddi，i=1,2,…,sn。

步骤3：更新粒子群。

1)使用式(6)更新粒子群的速度V和位置A，矩阵A、V的第i行数据分别表示为Ai和Vi。

2)如若出现Vi,j>v_maxj，Vi,ja_maxj或Ai,j

3)计算更新解A第i组解的适应度函数值f_A(xi)和满足约束的个数dd_Ai，i=1,2,…,sn。

4)对比ddi和dd_Ai，如果ddidd_Ai保留ai和vi；若ddi=dd_Ai，对比f(xi)和f_A(xi)，若f_A(xi)比f(xi)更靠近目标值，将ai替换为Ai，vi替换为Vi，否则保留保留ai和vi,i=1,2,…,sn，更新向量p和g。

5)令k=k+1。

6)Gk,1～n储存第k次迭代中的最优解，Gk,n+1储存对应的适应度函数值。

7)若k≥K，进行步骤d；不然跳至步骤3 1)。

步骤4：输出最优解储存矩阵G。

4 仿真实验分析

本节中，使用6个测试函数，分别用三个算法进行计算，所有的问题中，都从不同的初始自变量开始运行30次，ABC算法和MABC算法中的蜂群个数sn都设置为20，PSO中的粒子群个数sn设置为100。

本文使用的6个测试函数如下所示。

测试函数1。

约束函数：g1(x)=4.84-(x1-0.05)2-(x2-2.5)2≥0；

测试函数2。

约束函数：g1(x)=10-(2x1+2x2+x10+x11)≥0；

g2(x)=10-(2x1+2x3+x10+x12)≥0；

g3(x)=10-(2x1+2x3+x10+x12)≥0；

g4(x)=-(-8x1+x10)≥0；

g5(x)=-(-8x2+x11)≥0；

g6(x)=-(-8x3+x12)≥0；

g7(x)=-(-2x4-x5+x10)≥0；

g8(x)=-(-2x6-x7+x11)≥0；

g9(x)=-(-2x8-x9+x12)≥0；

0≤xi≤1,i=1,…,9，0≤xi≤100,i=10,11,12，0≤xi≤1,i=13。

测试函数3。

适应度函数：

-10≤xi≤10,i=1,2,…,7。

测试函数4。

约束函数：g1(x)=85.334 407+0.005 685 8x2x5+0.000 626 2x1x4-0.002 205 3x3x5≥0；

g2(x)=92-(85.334 407+0.005 685 8x2x5+0.000 626 2x1x4-0.002 205 3x3x5)≥0；

g3(x)=80.512 49+0.071 317x2x5+0.002 995 5x1x2+0.002 181 3x3-90≥0;

g4(x)=110-(80.512 49+0.0713 17x2x5+0.002 995 5x1x2+0.002 181 3x3)≥0;

g5(x)=9.300 961+0.004 702 6x3x5+0.001 254 7x1x3+0.001 908 5x3x4-20≥0；

g6(x)=25-(9.300 961+0.004 702 6x3x5+0.001 254 7x1x3+0.001 908 5x3x4)≥0，

78≤x1≤102， 33≤x2≤45， 27≤xi≤45,i=3,4,5。

测试函数5。

适应度函数：f5(x)=-0.5(x1x4-x2x3+x3x9-x5x9+x5x8-x6x7)。

g5(x)=-((x1-x5)2+(x2-x6)2-1)≥0；

g6(x)=-((x1-x7)2+(x2-x8)2-1)≥0；

g7(x)=-((x3-x5)2+(x4-x6)2-1)≥0；

g8(x)=-((x3-x7)2+(x4-x8)2-1)≥0；

g10(x)=-(x2x3-x1x4)≥0；

g11(x)=x3x9≥0；

g12(x)=-x5x9≥0；

g13(x)=-(x6x7-x5x8)≥0；

-10≤xi≤10,i=1,…,8，0≤x9≤20。

测试函数6。

2(x6-1)2+5x7+7(x8-11)2+2(x9-10)2+(x10-7)2+45。

约束函数：g1(x)=105-4x1-5x2+3x7-9x8≥0;

g2(x)=-10x1+8x2+17x7-2x8≥0；

g3(x)=8x1-2x2-5x9+2x10+12≥0；

g8(x)=3x1-6x2-12(x9-8)2+7x10≥0,

10≤xi≤10,i=1,…,10。

使用MABC、ABC、PSO算法分别对测试函数进行优化计算，每个函数计算30次，对这30次计算的最优值、最差值、中值、平均值进行统计，结果如表1所示。

表1 优化结果

由表1可得，MABC算法和ABC算法对约束问题的处理能力强于PSO算法。同样的迭代次数，MABC算法得到的解优于ABC算法得到的解。由约束函数5可知，PSO算法会陷入局部最优，导致结果会出现较大的波动。

将约束函数每次迭代得到的最优值进行统计，绘制出每个约束函数的适应度进化曲线，用来评价函数的收敛能力，如图3所示。

如图3a和图3e所示，f1和f5中，ABC算法和MABC算法均寻到了满足全部约束的解，MABC算法的收敛能力优于ABC算法的收敛能力。PSO算法陷入了局部最优，寻不到满足所有约束的解。

如图3b所示，约束函数2中，三种算法都寻到了满足全部约束条件的解，PSO算法得到的解相较于其他两种算法差。MABC算法对最优值的搜索能力优于ABC算法。

如图3c所示，约束函数3中，三个算法寻找到的最优解皆能满足全部约束条件。搜索过程中因为以满足约束条件作为第一标准，PSO算法出现了大程度的波动。三个算法中最优值仍然由MABC算法寻到。

如图3d和图3f所示，约束函数4和约束函数6中，MABC算法和ABC算法都搜索到了满足所有约束函数的解，但MABC算法搜索到的解明显优于ABC算法搜索到的解。PSO算法陷入局部最优，没能搜索到满足全部约束的解。

在群智能算法中种群数量的大小对算法的收敛能力和搜索能力有着较大的影响，上文使用的MABC算法的蜂群数量都为20，为了进一步分析种群数量对MABC算法性能的影响，将蜂群数量分别更改为5、10、15、25、30、50，并统计了这7种情况取的最优解所需的迭代次数，如表2所示。

由表2可得：在相同的迭代次数的情况下，蜂群数量为5和10时，收敛和搜索能力，相较于上文选择的20都有明显的下降，容易出现不能满足全部约束的情况，容易出现局部最优的情况；蜂群数量为15，在进行足够迭代次数的情况下，可以取得最优解；蜂群数量为25和30时，对仿真结果的收敛速度有一定的影响，但均能得到让人满意的最优解；蜂群数量为50时，算法会在较少迭代次数的情况下得到最优解，收敛曲线会在开始就出现断崖式下跌，不利于比较算法的优化能力。最后的仿真结果发现群智能算法中的种群数量对算法收敛和搜索的能力有着极大的影响，优化过程中应通过多次尝试，尽可能地选择合适的种群数量。

表2 种群数量对算法优化能力的影响

5 结论

本文提出利用群智能算法处理多约束优化问题。首先构造同时计算约束条件和优化适应度的目标函数，然后建立约束问题的数学模型，进行ABC算法和PSO算法的仿真实验。仿真结果可知，MABC算法的收敛和搜索能力强于ABC算法和PSO算法；PSO算法在约束问题的处理上，容易陷入局部最优，普适性弱于ABC和MABC算法。本文基于群智能算法的多约束问题优化方法可以广泛应用于油船内壳结构优化，规划无人机的航行轨迹等工程领域。