求解约束优化问题的海豚算法

陈建华　陈建荣

摘要：针对广泛存在于实际工程等领域，但使用传统方法难于求解的约束优化问题，提出了一种求解约束优化问题的海豚算法。海豚算法主要通过模仿海豚利用超声波在大海中追逐和捕食猎物的行为进行寻优。对三个经典工程实例的优化结果表明，该算法具有收敛速度快、求解精度高、稳定性好且不易陷入局部极值等优点，非常适合解决约束优化问题。

关键词：约束优化；海豚算法；群智能；优化；算法

中图分类号：TP18 文献标识码：A 文章编号：1009-3044（2018）11-0235-05

Dolphin Swarm Optimization Algorithm for Constrained Optimization Problems

CHEN Jian-hua1，CHEN Jian-rong2，3

（1.You Jiang District Social Insurance Bureau， Baise 533000， China；2. Sun Yat-sen University， School of Data and Computer Science， Guangzhou 510275， China； 3. You Jiang Medical University for Nationalities， Baise 533000， China）

Abstract： The constrained optimization problems are widely present in the practical engineering and other fields， and very difficult to solve by using traditional methods. Dolphin swarm optimization algorithm for constrained optimization problems was proposed. Dolphin swarm optimization algorithm is based on mimicking the behavior of dolphins using ultrasound to chase and prey in the ocean. The experimental results of the three typical engineering design problems shows that the algorithm has the advantages of fast convergence， high accuracy， good stability and is not easy to fall into local extremum， so it is very suitable for solving constrained optimization problems.

Key words： constrained optimization； dolphin swarm optimization algorithm （DSOA）； swarm intelligence； optimization； algorithm

約束优化问题（constrained optimization problems， COPs）是在科学、工程和商业等诸多领域中经常出现但又较难求解的一类数学规划问题，对其进行研究具有非常重要的理论和实际意义[1]。海豚算法[2]（dolphin swarm optimization algorithm， DSOA）是2016年由王勇等通过观察并模拟海豚在海洋中寻找和捕食沙丁鱼群的行为特点而提出的一种新型的群智能算法。对于多维函数的优化问题，与粒子群算法（PSO）、人工蜂群算法（ABC）和蝙蝠算法（BA）相比，海豚算法在全局搜索能力、收敛率、求解精度、有效性和鲁棒性等方面有明显优势。

基于海豚算法的优秀性能，将该算法用于求解约束优化问题。并使用工程实例对算法性能进行验证。

1 海豚算法[2]介绍

1.1海豚的自然特征

海豚是一种非常聪明的海洋生物，它们通常被认为是地球上最智能的物种之一。海豚流线型的体态使得它们非常适合在水中快速游动，因此大多数海豚拥有高超的游泳技巧和非同寻常的潜水能力。当海豚捕食沙丁鱼、攻击鲨鱼、逃避天敌、躲避障碍物、避免陷入死胡同时，海豚能够动态地改变游泳模式和前进方向，并使用例如翻转划水和旋转划水等各种各样的游泳技巧。

海豚是声学生物，超声波是它们的语言。每只海豚头部有“额隆”，它能够产生超声波并接收回声。“额隆”是一种高灵敏度的生物声呐系统。依靠“额隆”，海豚能够快速和精确地探测物体的距离、方向、位置和形状。

海豚平时喜欢群居。特别是当它们追逐或捕食一大群沙丁鱼或攻击鲨鱼时，多达数十只的海豚会生活在一起。

1.2算法的基本假设

为了模拟海豚攻击和捕食的行为，海豚算法给出如下基本假设：1）海豚仅在自己的搜索空间里搜寻、攻击和捕食；2）在海洋里攻击或捕食一大群沙丁鱼的时候，海豚只使用翻转划水模式或旋转划水模式；3）每只海豚仅使用自己的声呐来产生超声波、接收回声、探测物体的状态、与伙伴交流；4）整个搜索过程划分为三个情景：探测目标位置（一群沙丁鱼）；追逐和接近目标；最终捕食或攻击目标；5）海豚根据需要能够动态地改变自身的游泳模式和使用不同的搜索策略。

1.3算法基本规则及搜索方法

给定闭区间[a，b]，使用线性变换[φx=x-b+a2]将其映射到区间[-b-a2，b-a2]。为不失一般性，假设海豚搜索空间为[S=-a1，a1×-a2，a2×…×-an，an?Rn]，其中[ak>0]，[k=1，…，n]。

对于每一個属于[S]的区间[-ak，ak]，首先在复平面内构造方域[F=hR+ihI|hR，hI∈-ak，ak]，其中[i]为虚部。那么，点[hR+ihI∈Fk]可以表示为[hR=ρkcosθk]，[hI=ρksinθk]，[ρk=h2R+h2I]，其中[0≤ρk≤ak]，[θk∈0，2π]。

第[j]只海豚的初始速度表示为[VjR1+iVjI1]，其中[VjR1=vjR，1，…，vjR，n]，[VjI1=vjI，1，…，vjI，n]。

1.3.1探测目标位置

假设在开始时，第[j]只海豚探测到有一群沙丁鱼位于[ρjk（cosθjk+isinθjk）]。则第[j]只海豚获得坐标如下：

[xjR，k（1）=ρjkcosθjk]，[xjI，k（1）=ρjksinθjk]， and[XjR（1）+iXjI（1）]. （1）

其中，[ρjk]是[[0，ak]]内的随机数，[θjk]是区间[[0，2π]]内的随机角度，[i]为虚部，[XjR（1）=（xjR，1（1），…，xjR，n（1））]，[XjI（1）=（xjI，1（1），…，xjI，n（1））]， [k=1，…，n]，[j=1，…，M]， [M]为海豚个体的数量。

1.3.2追逐和接近目标

假设在[t]时刻，第[j]只海豚的位置和移动速度分别为[XjR（t）+iXjI（t）]和[VjR（t）+iVjI（t）]，它找到的最优目标（一群沙丁鱼）位于[PjR（t）+iPjI（t）]，当前海豚群体探测到的最优目标（一群沙丁鱼）表示为[GR（t）+iGI（t）]（[GR（t）+iGI（t）]为最优目标的质心），其中[i]为虚部。

则在[t+1]时刻，第[j]只海豚的位置和速度通过如下公式给出：

[VjR（t+1）=w1?VjR（t）+cjR1（t）?（PjR（t）-XjR（t））+cjR2（t）?（GR（t）-XjR（t））+cjR3（t）?（GI（t）-GR（t））] （2）

[VjI（t+1）=w2?VjI（t）+cjI1（t）?（PjI（t）-XjI（t））+cjI2（t）?（GI（t）-XjI（t））+cjI3（t）?（GR（t）-GI（t））] （3）

[XjR（t+1）=XjR（t）+VjR（t+1）] （4）

[XjI（t+1）=XjI（t）+VjI（t+1）] （5）

其中，[XjR（t），XjI（t）]，[GR（t），GI（t）∈Rn]，[βq]是[[0，1]]内的[n]维随机向量，[w1]和[w2]是惯性权重，[cjR1（t）]，[cjR2（t）]，[cjR3（t）]，[cjI1（t）]，[cjI2（t）]和[cjI3（t）]是加速控制函数。[cjR3（t）（GI（t）-GR（t））]和[cjI3（t）（GR（t）-GI（t））]称为错误纠正项。

1.3.3捕食或攻击目标

假设在[t]时刻，一群海豚已经连续追逐目标[ω]步（[ω

[xjR，k（t+1）=rR，l] （6）

[xjI，k（t+1）=rI，l] （7）

其中，[rR，l]是区间[[gR，l（t）-ε（t），gR，l（t）+ε（t）]]内均匀分布的随机数，[rI，l]是区间[[gI，l（t）-ε（t），gI，l（t）+ε（t）]]内均匀分布的随机数，[l]是属于集合[1，…，n]的随机数，[ε（t）]是满足[|ε（t）|?1]的递减正函数，[t]为时间步长，正整数[ω]满足[t≥ω]，[ω

1.3.4搜索模式转换条件

给定海豚个体数量[M]，优化问题（以求最小值为例）的目标函数[fX]，[X=（x1，…，xn）∈S]，[t]时刻第[j]只海豚的位置为[XjR（t）+iXjI（t）]。记

[Yj=12（f（XjR（t））+f（XjI（t）））]，[j=1，…，M] （8）

对[Yj]按升序排序，将[Yj]的顺序记为[Oj（t）]。取

[μj（t）=（Oj（t）-1）/M] （9）

称[μj]为转换因子。容易看出[0≤μj（t）<1]。若[Yj=min{Yl|l=1，…，M}]，则有[Oj（t）=1]。若[Yj=max{Yl|l=1，…，M}]，则[Ol（t）≤Oj（t）=M′≤M]，[l=1，…，M]。

搜索模式的转换根据下面两条规则进行：

规则一：若[t≤ω]或[η<μj]，则第[j]只海豚根据公式（2）， （3）， （4）和（5）更新自己的位置和速度。

规则二：若[t>ω]且[μj≤η]，则第[j]只海豚根据公式（6）和（7）更新自己的位置和速度。

其中，[η]是[[0，1]]内的随机数。

1.4算法流程

算法输入参数：[w1]，[w2]，[cR1]，[cI1]，[β1]，[β2]，[ω]，最大迭代次数[Gen]，海豚个体数[M]。

Step1：对[M]只海豚进行初始化。[t=0]。

Step2：计算所有海豚个体的适应度值。

Step3：若未找到最优解或[t

Step4：[t=t+1]。

Step5：若[t≤ω]，则用式（2），（3），（4），（5）对[M]只海豚的位置进行更新，转Step2。否则转Step6。

Step6：根据式（8）计算[Yj]，并对[Yj]排序。根据式（9）计算[μj]。产生[[0，1]]内的随机数[η]。

Step7：依次对[M]只海豚进行位置更新。若[μj≤η]，则用式（6），（7）对第[j]只海豚进行位置更新，否则用式（2），（3），（4），（5）对第[j]只海豚进行位置更新。[j=1，2，…，M]。转Step2。

Step8：算法终止，输出最优解。

2 约束优化问题描述

一般的约束优化问题可描述为：

[minfX]

[s.t.] [giX≤0]，[i=1，2，…，m]

[hjX=0]，[j=1，2，…，p]

[lk≤xk≤uk]，[k=1，2，…，n]

其中，[X=x1，x2，…，xn∈Ω?S]为决策向量，[Ω]为可行域，[S]为决策空间。[fX]为目标函数，[giX]为[m]个不等式约束，[hjX]为[j]个等式约束。[lk]和[uk]分别为[xk]的上下界。

3 实验分析

3.1实验环境及仿真实例

实验采用Intel? Core（TM） i7-4790K CPU @4.00 GHz、16GB内存、SanDisk SDSSDHII120G硬盘的台式机，操作系统为Windows 10 64位专业版，仿真软件为Matlab 2015b。

选取的三个仿真实例分别为伸缩绳、焊接条和压力管的设计问题[3-5]。

（1）伸缩绳设计问题。

伸缩绳结构如图1所示。该问题属于连续型约束优化问题，优化目标是寻求满足对最小偏差、切应力、湍振频率等一系列约束条件的3 个决策变量，即平均卷直径[Dx1]、线直径[dx2]和活动卷的数量[Px3]，使得伸缩绳的重量最小。其目标函数及约束条件如下：

[minfx=x3+2x2x21]

[s.t.] [g1x=1-x32x371785x41≤0]

[g2x=4x22-x1x212566x2x31-x41+15108x21-1≤0]

[g3x=1-140.45x1x22x3≤0]

[g4x=x1+x21.5-1≤0]

其中，[x1∈0.05，2]，[x2∈0.25，1.3]，[x3∈2，15]。

（2）焊接条设计问题。

焊接条结构如图2所示。该问题属于连续型约束优化问题，优化目标是寻求满足切应力[τ]、弯曲应力[σ]、杆条弯曲载荷[Pc]、末端偏差[δ]和边界条件等约束条件的4个设计变量[hx1]、[lx2]、[tx3]和[bx4]，使得制造焊接条所需的总费用最小。其目标函数及约束条件如下：

[minfx=1.10471x21x2+0.04811x3x414.0+x2]

[s.t.] [g1x=τx-13600≤0]

[g2x=σx-30000≤0]

[g3x=x1-x4≤0]

[g4x=0.10471x21+0.04811x3x414.0+x2-5.0≤0]

[g5x=0.125-x1≤0]

[g6x=δx-0.25≤0]

[g7x=6000-Pcx≤0]

其中，

[τx=τ'2+τ'τ''x2R+τ''2]

[τ'=60002x1x2]

[τ''=MRJ]

[M=600014+x22]

[R=x22+x1+x324]

[J=22x1x2x2212+x1+x324]

[σx=504000x4x23]

[δx=2.1952x33x4]

[Pc=4.013E1-0.0282346x3x3x346L2]

式中，[L=14]，[E=30×106]。决策变量取值范围：[x1，x4∈0.1，2]，[x2，x3∈0.1，10]。

（3）压力管设计问题。

压力管结构如图3 所示。该问题属于混合约束优化问题，优化目标是寻求满足一系列约束条件的4个设计变量[Ts]（[x1]，圆柱形管子的厚度）、[Th]（[x2]，半球形盖子的厚度）、[R]（[x3]，圆柱形管子的内径）和[L]（[x4]，圆柱形管子的长度，不包括两端的盖子），使得材料、焊接、铸造等费用在内的总费用最少。其中，[Ts]和[Th]均为0.0625英寸的整数倍，[R]和[L]是连续变量。其目标函数及约束条件如下：

[minfx=0.6224x1x3x4+1.7781x2x23+3.1661x21x4+19.84x21x3]

[s.t.] [g1x=-x1+0.0193x3≤0]

[g2x=-x2+0.00954x3≤0]

[g3x=-πx23x4-4πx333+1296000≤0]

[g4x=x4-240≤0]

其中，[x1，x2∈1，99]，[x3，x4∈10，200]。

3.2參数设置及计算结果

算法参数统一设置如下：海豚规模[M=50]，算法最大迭代次数[Gen=500]，[w1=w2=0.6]，[cR1=cI1=2]，[β1=β2=2]，[ω=20]，[cR2=cR3=β1Gen-t/Gen]，[cI2=cI3=β2Gen-t/Gen]，[εt=1/1000t100]。

算法连续独立运行30次，求解结果见表1-表6。注：“-”表示文献未给出计算结果。

3.3实验结论

从表1和表2伸缩绳设计问题的实验结果可知，DSOA算法找到的最优解比文献[6-9]优，与文献[10，11]一致。但在平均解、最差解和标准差三个指标上，DSOA算法均优于其他方法。

从表3和表4焊接条设计问题的实验结果可知，在最优解、平均解、最差解和标准差四个指标上看，除文献[10]算法求解结果与DSOA算法基本相当外，其余均差于DSOA算法。

从表5和表6压力管设计问题的实验结果可知，仅DSOA算法能找到全局最优，其他算法均陷入局部最优，说明DSOA算法具有很强的避免陷入局部极值的能力。DSOA算法在标准差指标上比文献[6，9，13]略差，其余指标均比其他方法要好。

DSOA算法求解伸缩绳、焊接条和压力管设计问题的收敛曲线，如图4-图6所示。由图可知，算法收敛速度是很快的。

4 结束语

将DSOA算法应用于求解约束优化问题，并使用三个工程实例对算法性能及有效性进行验证。实验结果表明，與对比方法相比，DSOA算法具有收敛速度快、求解精度高、稳定性好等优点，并且拥有很好的全局搜索能力。因此，DSOA算法对于求解约束优化问题是非常适用且有效的。

参考文献：

[1]王勇， 蔡自兴， 周育人，等.约束优化进化算法[J].软件学报，2009，20（1）：11-29

[2]Wang Yong， Wang Tao， Zhang Cheng-zhi， et al. A New Stochastic Optimization Approach： Dolphin Swarm Optimization Algorithm[J]. International Journal of Computational Intelligence and Applications，2016，15（2）

[3] Rao S S.Engineering Optimization[M].3rd ed.New York：Wiley，1996.

[4] Arora J S.Introduction to optimum design[M].New York：Mc-Graw-Hill，1989.

[5] Kannan B K，Kramer S N.An augmented Lagrange multiplierbased method for mixed integer discrete continuous optimization and its applications to mechanical design[J]. Trans of the ASME，Journal of Mechanical Design，1994，116：318-320.

[6] Coello C A C.Use of a self-adaptive penalty approach for engineering optimization problems[J].Computers in Industry，2000，41：113-127.

[7] Coello C A C，Montes E M.Constraint-handling in genetic algorithms through the use of dominance-based tournament selection[J].Advanced Engineering Informatics，2002，16：193-203.

[8] Coello C A C，Becerra R L.Efficient evolutionary optimization through the use of a cultural algorithm[J].Engineering Optimization，2004，36：219-236.

[9] He Q，Wang L.An effective co-evolutionary particle swarm optimization for constrained engineering design problems[J].Engineering Applications of Artificial Intelligence，2007，20：89-99.

[10]庞兴，王勇.PSO与捕鱼策略相结合的优化方法[J].计算机工程与应用，2011，47（8）：36-40，50.

[11]A.H.Gandomi，X.S.Yang，et al. Bat algorithm for constrained optimization tasks[J]. Neural Comput & Applic，2013，22：1239-1255.

[12] LIU H，CAI Z，WANG Y.Hybridizing particle swarm optimization with differential evolution for constrained numerical and engineering optimization[J].Applied soft computing， 2010，10（2）：629-640.

[13] HUANG F，WANG L，HE Q.An effective co-evolutionary differential evolution for constrained optimization[J]. Applied mathematics and computation，2007，186（1）：340-356.