一种离散混合蛙跳算法及其应用①

张 强,郭玉洁

(东北石油大学 计算机与信息技术学院,大庆 163318)

混合蛙跳算法(Shuffled Frog Leaping Algorithm,SFLA)[1]是Eusuff 和Lansey 通过模拟青蛙种群的觅食过程而设计出的一种群智能优化算法,具有概念简单、参数少且全局寻优能力强等优点.目前,许多研究学者将其成功应用到不同的工程领域,雷德明等[2]提出一种新型蛙跳算法(SFLA),用于求解低碳混合流水车间调度问题,得到高效率的调度方案.徐俊等[3]将改进后的混合蛙跳算法(ISFLA)用于求解云工作流调度,实验证明相同的迭代次数下ISFLA 优化的效果更好.张萍等[4]将人工鱼群与蛙跳算法结合起来改进矢量匹配法,实现电压传输函数的有理拟合.陈科尹等[5]提出一种改进的混合蛙跳算法,有效解决了传统采摘机器人相机标定方法的不足.蔡宁等[6]提出一种融入Pareto思想的改进混合蛙跳算法(SFLA)用于求解实际资源约束下拆卸线平衡问题,实验证明改进SFLA 具有良好的综合求解优势.杨哲等[7]将改进实数编码混合蛙跳算法(IR-SFLA)和二进制编码的(IB-SFLA)分别应用到水电站经济负荷分配和机组组合问题,实验证明IR-SFLA 算法能有效提升水资源利用效率,IB-SFLA在求解大规模机组电力调度问题时可获得高质量的解.张异[8]设计一种求解包装配送问题的混沌蛙跳布谷鸟算法,实验证明CFLCSA 可以得到高效率的配送策略.艾子义等[9]提出一种新型蛙跳算法(SFLA)用于求解低碳柔性作业车间调度问题,实验表明新型SFLA 具有较强的搜索能力和竞争力.李荣波等[10]针对标准混合蛙跳算法的不足,提出一种改进混合蛙跳算法(ISFLA),来求解梯级水库优化调度问题,得到了较好的优化结果.

目前,针对SFLA 算法已有了许多先进的研究成果,但对于离散混合蛙跳算法的理论研究相对较少,且缺乏相对的实际应用研究.因此,本文提出了一种离散混合蛙跳算法(Discrete Shuffled Frog Leaping Algorithm,DSFLA),在DSFLA 算法中引入扰动系数来调控最劣解的跳跃方向,从而协调迭代过程中算法的全局探索和局部开发能力；并将扰动系数作为阈值,引用螺旋更新位置来改进族群内个体的更新策略,精细算法的局部搜索能力；同时为了提高算法的全局探索能力,随机选择种群内的参照个体进行位置更新；此外采用全局最优解变异提高种群的多样性,有助于算法跳出局部最优；最后利用改进的Sigmoid 函数对SFLA 进行离散化处理保证了个体的多样性.对改进效果进行仿真验证,并将DSFLA 与其它9 种优化算法在求解油田措施规划模型上进行对比,DSFLA 取得了很好的寻优效果.

1 离散混合蛙跳算法原理

1.1 基本混合蛙跳算法

基本混合蛙跳算法(SFLA)[1]数学模型思想是：一个湿地里有若干块石头,青蛙可以在石头上跳跃寻找食物最多的点,每只青蛙带有不同的信息,将青蛙种群分为不同的组,通过不同的青蛙个体进行信息交流,实现局部搜索,当局部搜索进行到一定程度时,混合种群中的各组青蛙,实现种群内部的信息交换.根据这一仿生机制,基本蛙跳算法的寻优过程主要由4 部分组成.

(1)种群初始化

在湿地中随机生成N个青蛙组成的初始种群,其中d维解空间的第i个青蛙表示为Xi={xi1,xi2,···,xid},i=1,2,···,N.

(2)划分族群

通过计算种群内青蛙的适应度值,根据该值对青蛙进行降序排列；并将种群划分为m个族群,每个族群包含n个青蛙,其中N=m×n.

(3)局部搜索

① 基于局部最优解的族群内个体更新策略

将第i个族群中最优解和最劣解分别标记为Xib,Xiw,D为跳跃步长,[Dmin,Dmax]为跳跃步长的范围,在迭代过程中循环对每个族群中的Xiw进行局部搜索,族群最优解的更新方式如式(1)、式(2)所示.若得到的新解Xi′w的适应度值优于Xiw,则取代原来族群中的解；否则将进行操作②.

② 基于全局最优解的族群内个体更新策略

将种群中适应度最好的解标记为Xg,采用全局最优解Xg代替Xib更新Xiw,全局最优解的更新方式如公式(3)和(4)所示,若产生的新解Xi′w仍未优于Xiw；则进行操作③,随机产生一个新解取代Xiw.

③ 随机生成新个体更新策略

其中,rand为[0,1]随机数组成的向量,Dmax表示跳跃步长的最大边界值.

(4)全局混合

将完成局部搜索后的族群个体重新混合并排序,再次分组和进行族群内部更新,直到算法满足结束条件.

1.2 离散混合蛙跳算法原理

1.2.1 族群内个体更新原理改进

基本混合蛙跳算法的族群内个体更新策略主要体现在族群内最劣解不断向最优解的位置方向移动.当迭代到达一定程度后,族群内最优解和全局最优解难以被更新,最劣解朝某一固定方向不断跳跃,易导致算法陷入局部最优.为了提高算法跳出局部最优的能力,本文引入扰动系数A来调节个体的跳跃步长,并将扰动系数A作为概率阈值,采用标准SFLA族群个体更新位置和螺旋更新位置两种策略来模拟青蛙的觅食行为.基本混合蛙跳算法的跳跃步长规则如图1所示,可以看出族群中的最劣解Xw跳跃位置的范围,被限定在当前位置与族群最优位置之间,这种跳跃规则限制了算法的搜索空间.因此,本文引入扰动系数A来调控青蛙的跳跃步长.由式(7)可知,A的取值范围是[−α,α]中一个随机值,当|A|＞1时,青蛙将扩大跳跃范围,有更大的可能去寻找潜在优秀解(改进后的跳跃步长规则如图2所示)；当|A|≤1时,蛙群将缩小跳跃范围在局部区域进行精细搜索.在迭代初期,扰动系数的值较大,保证算法的全局搜索能力,随着迭代的增加,扰动系数逐渐减小,保证算法的局部搜索能力,从而平衡SFLA算法在优化过程中的全局探索和局部开发能力.

其中,t表示当前迭代次数,Tmax表示最大迭代次数,rand为[0,1]随机数组成的向量.

图1 基本跳跃步长规则

图2 改进的跳跃步长规则

由进化理论可知优秀个体的周围很大程度上存在更多的潜在优秀个体；基本SFLA 算法的迭代后期,族群内最优解保持不变,易导致算法陷入局部最优.为了提高算法的局部搜索能力,引用螺旋更新位置策略来改进族群内个体的更新方式,螺旋更新位置策略使最劣解沿着螺旋运动轨迹向最优解的位置方向移动,螺旋运动方式能对最优解附近区域进行更加全面精细的搜素,寻找到更多潜在的优秀解.本文将引入的扰动系数作为阈值,当|A|≤1时,采用螺旋更新位置策略；当|A|＞1时,则采用标准SFLA 族群内个体更新策略.其更新公式表达如下：

其中,l为[-1,1]随机概率,b为限定对数螺旋形状的常数(通常值取1),Xib表示族群内最优位置.

1.2.2 随机搜索策略

在基本混合蛙跳算法迭代过程中,随机生成新个体的更新策略具有一定的混乱性和无序性,不利于算法的收敛.因此本文通过随机选择种群中的一个青蛙个体作为参照青蛙,以此来寻找其它更优的解.这样既实现了种群内部信息的充分交流,同时增强了算法的搜索能力,使该算法能在全局范围内进行搜索.其更新公式表达如下：

其中,Xrand表示一个随机位置向量,rand为[0,1]随机数组成的向量.

1.2.3 全局最优解变异

全局最优解作为重要的信息源会影响整个群体的走势,但在种群迭代后期,全局最优解难以被更新,易导致算法停滞.因此,本文借鉴2-opt 方法对全局最优解进行变异,通过让种群内邻域解参与到信息交互中,从而增加种群的多样性,有助于算法在迭代后期跳出局部最优.其更新公式表达如下：

其中,Xg表示全局最优位置,d表示优化空间的维度.

根据文献[11]提出的通过计算种群的多样性度量值来评测种群多样性的方法,在DSFLA 算法中引入全局最优解变异策略,利用式(13)计算的其种群的多样性度量值,并将结果与标准SFLA 算法做对比,对比结果如图3所示.

图3 种群多样性度量

其中,Tmax表示最大迭代次数,N表示种群规模,D表示数据维数,xtij表示迭代t次第i个种群的第j个分量,表示所有种群的第j个分量的平均值.上述间距公式,Q(t)表示种群多样性度量值,其值越大表示种群平均间距越大,种群多样性越大.

由图3可知,随着迭代次数的不断增加,DSFLA算法种群多样性度量值逐渐趋向于比SFLA 算法较大的一个值,因此DSFLA 算法的种群性多样性更大.

1.2.4 离散化原理

由于实际工程应用中所计算的变量都是离散的,因此,本文提出一种离散二进制蛙跳算法编码方式对青蛙位置进行离散化处理.为了保证迭代过程中青蛙的位置只能取0 或1,通常使用Sigmoid 函数[12]将位置压缩到[0,1]区间,其公式如式(14)、式(15)所示,式(14)中的矩阵运算需用到“./”.利用标准Sigmoid 函数对青蛙个体位置映射的结果如图4所示,可以看出,映射结果大都集中在0.35～0.65 之间,若直接用标准Sigmoid 函数对映射结果离散化处理,则个体容易产生“靠拢”现象,会导致算法陷入局部最优,过早停滞.

为了提高算法的搜索能力,本文通过对最优位置和当前位置的差值进行映射,同时建立跳跃步长D与位置转换概率间的关系来改进Sigmoid 函数；映射结果如图5所示,可以看出,映射结果值分布在0～1 之间,更好的保证了离散化后个体的多样性,为算法的优化过程奠定了多样性基础.改进后的Sigmoid 函数公式表达如下：

其中,xg表示当前最优位置,x表示位置向量,D表示跳跃步长,VarS ize表示维数大小.“./”和“.*”表示矩阵运算,在计算中保持矩阵维度一致.

图4 标准Sigmoid 函数

图5 改进Sigmoid 函数

1.3 离散混合蛙跳算法

离散混合蛙跳算法(DSFLA)的具体操作步骤如算法1 所示.

算法1.离散混合蛙跳算法1.初始化参数(种群规模N,族群数m,维数D,局部搜索次数L,最大迭代次数Tmax)；2.随机生成初始青蛙种群；for t=1:Tmax 3.4.应用式(6)、式(7)更新参数,计算每个个体 的适应度值F,按照适应度值降序排列,并进行族群划分；for j=1:L α,A xi 5.

6.7.计算第i 个族群的局部最优解xib,局部最劣解xiw,全局最优解xg；if |A|≤1 for i=1:m 8.x′iw 9.应用式(6)～式(9)得到新的；10.else x′iw 11 应用式(6)～式(9)得到新的；12.end if x′iw x′iw 13.应用式(15)～式(17)对更新后的个体 进行离散化处理,得到新的；if F(x′iw) better than F(xiw)14.xiw=x′iw 15.else 16.x′iw 17.应用式(3)、式(4)得到新的；x′iw x′iw 18.应用式(15)～式(17)对更新后的个体 进行离散化处理,得到新的；if F(x′iw) better than F(xiw)19.xiw=x′iw 20.else 21.x′iw 22.应用式(10)、式(11)得到新的；x′iw x′iw 23.应用式(15)～式(17)对更新后的个体 进行离散化处理,得到新的；xiw=x′iw 24.end if 25.

26.end if 27.end for 28.end for xg x′g 29.应用式(12)对全局最优解 进行变异,得到新的；if F(x′g) better than F(xg)30.xg=x′g;31 F(xg)=F(x′g)32.；33.end for end if 34.

2 实验仿真测试

本文选用了9 个常用的基准测试函数[13]如表1所示.将离散混合蛙跳算法(DSFLA),同基本混合蛙跳算法(SFLA)[1],鲸鱼优化算法(WOA)[14],灰狼算法(GWO)[15],飞蛾扑火算法(MFO)[16],布谷鸟算法(CSA)[17],蝙蝠算法(BAT)[18],多元宇宙算法(MVO)[19],粒子群算法(PSO)[20],乌贼算法(CFA)[21]9 种优化算法进行实验对比.参数设置如表2所示,最大迭代次数为100,种群数为60,重复10 次,采用平均值(mean),标准差值(std)以及迭代中的最优值(best)来评价算法的性能.

表1 基准测试函数

表3为10 种优化算法在9 个测试函数中的实验结果对比.图6～图14为对应的迭代图.以最优值和平均值为评判标准,通过比较10 种算法的优化结果可知,在函数参数条件设定相同的情况下,DSFLA 寻优结果最好.上述实验结果主要原因是DSFLA 引入扰动系数更新策略来随机选取族群最优解的位置作为最劣解的跳跃方向,可以更好的平衡算法在不同迭代时期的全局搜索和局部开发能力,使青蛙可以更快的靠近食物；同时将扰动系数作为阈值,引用螺旋更新位置来改进族群内个体更新策略,对最优解位置附近进行精细搜索,使青蛙能够更准确的找到食物的位置,从而提高了算法局部搜索的精度.

以方差为评判标准,DSFLA 的收敛精度和方差都较优于其它9 种算法.实验结果主要原因是在迭代过程中,其它个体会逐渐集中在最优个体的位置附近,导致算法过早停滞；DSFLA 算法通过全局最优解变异的方式增加种群的多样性,避免青蛙个体全部聚集在某个局部最优位置；同时采用随机搜索策略,提高算法的全局搜索能力.

综上所述,针对标准混合蛙跳算法在求解高维复杂函数时存在收敛精度低和寻优速度慢等问题,本文采用的改进的策略能够明显提高了DSFLA 算法的收敛速度和寻优性能.

表2 算法参数设置

表3 实验结果对比表

图6 F1 迭代图

图7 F2 迭代图

图8 F3 迭代图

图9 F4 迭代图

图10 F5 迭代图

图11 F6 迭代图

图12 F7 迭代图

图13 F8 迭代图

图14 F9 迭代图

3 基于DSFLA 的油田措施方案优化

本文以年度利润和累积利润投入比最大为目标函数,建立油田措施规划模型,通过和其它9 种算法优化结果进行对比,分析DSFLA 在优化油田措施规划中的性能.

3.1 实验油田措施规划数学模型

(1)目标函数

油田措施规划问题是在满足油田开采的约束条件的前提下,分配开采井组,使油田的年度利润和累积利润投入比最大,其目标函数如下：

式中,F1是年度利润,F2是累积利润,N为井数目,K为措施数,a,b,c分别是吨油成本、吨水成本、吨液成本,d为递减率,t为开发时间,x1ij为第i口油井第j个措施的年度增油量,y1ij为第i口水井第j个措施的年度增油量,z1ij为第i口井第j个措施的年度增液量,w1ij为 第i口井第j个措施的年度增注量,x2ij为第i口油井第j个措施的累积增油量,y2ij为第i口水井第j个措施的累积增油量,z2ij为第i口井第j个措施的累积增液量,w2ij为第i口井第j个措施的累积增注量,priceij是第i口井措施数为j的价格.

(2)约束条件

1)措施增油量约束

式中,to是油井增油目标,取值为7.1×104t,te是水井增油目标,取值为7.5×104t,∂ 为误差百分比,取值为0.03.

2)措施增液量和增注量约束

式中,tl是 增液量上限,取值为18×104t,ti是增注量上限,取值为30×104m3.

3)措施数上限约束

式中,Limitij是采油井的措施数上限.

3.2 实验分析

为验证所提算法在求解油田措施规划模型中的性能,本章采用10 种优化算法针对2490 口措施井进行方案分配.算法的参数设置如表1所示,最大迭代次数为1000,种群大小为100,实验结果如图15,图16所示.图15,图16表示的是10 种优化算法迭代情况图.表4,表5表示10 种优化算法得到的最优值、最差值、平均值和标准差.

图15 年度利润对比图

图16 累积利润对比图

由表4和表5的实验结果可知,从最优值、最差值方面来看,DSFLA 得到的优化结果最好.在迭代过程中,DSFLA 算法引入扰动系数更新策略,更好的调控族群内最劣解和最优解之间的距离；并将扰动系数作为阈值,使用基于族群最优解的个体更新位置和螺旋更新位置两种策略,精细算法的局部搜索能力；此外,为了增加种群多样性,采用全局最优解变异的方式；同时,采用随机搜索策略来提高算法的全局搜索能力；为了保证离散化处理后青蛙种群的多样性,采用改进的Sigmoid 函数离散化位置向量,避免种群的多样性不会在离散化处理后突然骤减,提高了算法跳出局部最优的能力.

从标准差和平均值方面可知,DSFLA 算法相较于其它算法有较好的稳定性.此外,从图15和图16中可知,相较于其它算法,CSA 算法最早陷入局部最优,BAT、GWO、MFO、WOA 和PSO 算法在600 代左右停滞,SFLA 算法在700 代以后也不再变化,而DSFLA算法的收敛曲线在700 以后仍有上升的趋势,由于最优解变异和随机搜索策略提高了DSFLA 在迭代后期跳出局部最优能力,并且扰动系数更新策略扩大DSFLA算法的搜索空间,因此同其他9 种算法相比,DSFLA可以得到高质量的解.

综上所述,DSFLA 算法在求解油田措施规划模型时,能够显著提升油田开采的经济效益.

4 结论与展望

本文提出一种离散混合蛙跳算法(DSFLA),该算法引入扰动系数、螺旋位置更新策略、随机搜索策略以及全局最优解变异策略来对标准混合蛙跳算法的更新策略进行改进,此外，为了让改进的算法更适合求解离散优化问题,利用改进的Sigmoid 函数对位置进行离散化处理.通过9 个基准测试函数的实验结果表明了改进策略的高效性,并成功的将其应用到油田措施规划模型优化问题中,结果表明,与其它9 种算法的优化结果相比,DSFLA 算法求解质量更优.今后将进一步研究本算法在其它工程领域的应用.