一种新型的混沌步长果蝇优化算法*

张 铸，饶盛华,2，张仕杰

(1.湖南科技大学信息与电气工程学院，湖南 湘潭 411201；2.湖南科技大学海洋矿产资源探采装备与安全技术国家地方联合工程实验室，湖南 湘潭 411201)

1 引言

Pan[1]于2011年提出了一种由果蝇觅食行为而演化出来的群体智能全局优化算法——果蝇优化算法FOA(fruit Fly Optimization Algorithm)。相比于其他动物，果蝇具有较好的感官特性，如敏锐的视觉与嗅觉。FOA算法具有易实现、易理解、原理简单、调节参数少等特点，被广泛应用到了生物技术、金融、医学、模式识别、神经网络等领域。因此，对FOA研究具有较好的学术价值[2]。

作为群体智能算法，FOA易陷入早熟收敛且缺少跳出局部最优解的机制，在解高维度复杂的优化问题时尤为突出。为了解决上述问题，Pan[3]提出了一种改进型果蝇优化算法MFOA(Modifided FOA)，通过加入跳出局部最优解参数增强全局收敛能力；韩俊英等[4]提出了一种动态双子群协同进化果蝇优化算法，通过混沌优化在局部最优解附近进行搜索，提高其跳出局部最优解的能力；Yuan[5]等提出了一种多种群果蝇优化算法MSFOA(Multi-Swarm FOA)，通过多种群与缩小搜索半径的方法提高全局收敛能力；Pan等[6]提出了一种通过新的控制参数以及候选解机制提高性能的IFFO(Improved Fruit Fly Optimization)算法；文献[5,7]中提出通过采用自适应步长提高算法全局和局部搜索能力；Wang等[8]提出带有扰动机制的果蝇优化算法，使部分果蝇随机飞行，以增加果蝇群体的多样性；文献[9]中引入Levy飞行策略，提高FOA跳出局部最优解的能力，并将果蝇群体分为优质群体和劣质群体进行不同的搜索，提高种群多样性；张斌等[10]提出一种与模拟退火算法相结合的果蝇优化算法，通过概率吸收最差解作为下一次迭代位置来达到跳出局部最优解的目的；文献[11]提出一种双种群的果蝇优化算法，将果蝇群体分为搜索果蝇和跟随果蝇，并定义群度概念以平衡算法的全局和局部搜索能力。

本文提出一种基于Hénon混沌步长的果蝇优化算法HSFOA(fruit Fly Optimization Algorithm with Hénon chaotic of Step)，通过混沌映射的遍历性和多样性特征来改进FOA的固定步长，扩大其搜索范围；并对混沌步长增加放大系数，以适应不同的搜索环境，提高其搜索效率以及跳出局部最优解的能力。本文详细介绍了Hénon混沌映射的特点，以及HSFOA的原理和伪代码，并用10个测试函数进行了测试，与多种算法进行了对比分析，研究结果表明：HSFOA算法具有较高的全局搜索和跳出局部最优解的能力。

2 标准果蝇优化算法

果蝇优化算法是一种模拟果蝇觅食行为而推演出来的全局优化算法。果蝇通过嗅觉去寻找食物，而在接近食物后再通过灵敏的视觉发现食物[7]。果蝇优化算法原理简单、调节参数少、适应性强、收敛速度快，但也存在寻优结果不稳定等不足[5]。果蝇优化算法的优化步骤如图1所示。

Figure 1 Optimizing steps of FOA图1 果蝇优化算法优化步骤

3 Hénon映射

Hénon映射是一种二维的非线性动力系统，具有不可预测性以及不确定性等特征[12]。Hénon映射对初值敏感，初值不同会导致结果具有极大的差异性，因此其经常应用于信息安全领域[13,14]。Hénon映射是二维空间产生的混沌现象，如式(1)所示：

(1)

Hénon映射是否发生混沌状态由参数a、b的取值决定。研究表明，当a∈(0,1.4)，且b∈(0.2,0.314)时，Hénon映射会产生混沌现象，生成的混沌序列具有随机性。图2所示为b=0.3时，x随参数a(a∈(0,1.4))变化的分叉图。图3所示为b=0.25时，x随参数a(a∈(0.4,1.4))变化的分叉图。

Figure 2 Chaotic graph of Hénon mapping (b=0.3)图2 Hénon映射混沌图(b=0.3)

Figure 3 Chaotic graph of Hénon mapping(b=0.25)图3 Hénon映射混沌图(b=0.25)

由图2可知,随着参数a的递增，x的范围逐渐变大且取值均匀，因此可将其混沌值作为果蝇算法的步长。经研究表明，图3中，a∈(0,0.562)时x值均大于0，且随着a递增x发生分叉，并同时往2个方向变化。这种映射关系可提高果蝇算法的全局搜索能力；a∈(0.562,1.4)时，随着a递增x的范围逐渐扩大，使x取值范围具有良好的遍历性和多样性，其可扩大果蝇算法搜索范围，提高其跳出局部最优解能力。但是，由图2和图3可知x虽存在遍历性和多样性，但对于大范围大数值搜索情况，其取值太小无法跳出局部最优解。因此，引入放大系数，如式(2)所示，以加强其跳出局部最优解的能力。

X=N*x

(2)

其中，N为混沌步长放大系数。

4 HSFOA算法

在FOA中，步长的选择直接影响到算法的收敛速度和精度，因此本文将Hénon映射的混沌值作为步长，Hénon映射所发生的混沌现象具有较好的遍历性、多样性，可以解决果蝇优化算法的易早熟和收敛不足的问题，从而提高算法的效率和跳出局部最优解的能力。HSFOA的步骤和伪代码如下所示。

算法1 HSFOA

步骤1 初始化参数：sizepop(种群规模)，maxgen(最大迭代次数)，a(Hénon混沌参数)，b(Hénon混沌参数)，N(混沌步长放大系数)。

步骤2 果蝇群体位置(X_axis，Y_axis)通过式(3)进行初始化；

X_axis=rand×(UB-LB)+LB

Y_axis=rand×(UB-LB)+LB

(3)

其中,rand为[0,1]的随机数，UB和LB分别为搜索范围的上下界。

步骤3 嗅觉搜索阶段。根据式(4)更新所有果蝇个体位置：

Xi=X_axis+randValue

Yi=Y_axis+randValue

(4)

其中，randValue是一个返回值为[-1,1]的随机函数。

步骤4 计算果蝇个体位置与原点距离Di,再求出味道浓度判断值Si:

(5)

Si=1/Di

(6)

步骤5 根据式(1)对此时的最优解进行混沌化，产生混沌步长L。

步骤6 根据式(2)对混沌步长进行迭代放大，得到此时果蝇个体的位置(Xt，Yt)：

(7)

步骤7 计算果蝇个体位置与原点的距离Dt，并求出味道浓度判断值:

(8)

St=1/Dt

(9)

步骤8 求出此时味道浓度值:

Smellt=fitness(St)

(10)

步骤9 若此时味道浓度优于最优味道浓度值，则取代最优味道浓度值，并记录此时的果蝇位置:

(11)

步骤10 进入迭代寻优，重复执行步骤2～步骤9。

HSFOA伪代码:

1:initializationsizepop,maxgen,randValue,a,b;

2:Xi=X_axis+randValue;

3:Yi=Y_axis+randValue;

5:Si=1/Di;

6:Smelli=fitness(Si);

7: [bestSmell,bestIndex]=min(Smelli);

8:Smellbest=bestSmell;

9:X_axis=X(bestIndex),x=X_axis;

10:Y_axis=Y(bestIndex),y=Y_axis;

11: whilet

12:Xi=X_axis+randValue;

13:Yi=Y_axis+randValue;

15.Si=1/Di;

16.smelli=fitness(Si);

17: fori=1:N

19: end for

20: forj=1:sizepop

21:L=j×x;

本次施工在闸室上下游齿及两侧岸墙底板下采用高压灌浆摆喷墙，组成封闭基础以提高闸基的防渗能力。同时通过采用围井注水试验进行检查，在场地交通允许下，可进行开挖检查，每处高喷灌浆工程可作一个围井试验和一处开挖检查，可有效提高该工程的防渗能力。

22:Xt=X_axis+L;

23:Yt=Y_axis+L;

25:St=1/Dt;

26:Smelli=fitness(Si);

27: [bestSmell,bestIndex]=min(Smelli);

28: ifbestSmell

29:Smellbest=bestSmell;

31:Y_axis=Y(bestIndex),x=X_axis;

32: end if

33: end for

34:t=t+1;

35: end while

5 仿真实验与结果分析

为了验证HSFOA有效性和可行性，本文设计了2组仿真对比实验。(1)与同种类型的改进型果蝇算法MFOA、IFFO和标准FOA进行仿真对比分析；(2)与经典的智能优化算法PSO(Partical Swarm Optimization)、遗传算法GA(Genetic Algorithm)、蝙蝠算法BA(Bat Algorithm)进行仿真对比分析。

为了更方便直观地对比分析，实验采用10个经典的测试函数，并以误差值与标准差作为参考标准。表1给出了10个测试函数的维度、搜索区间和最优值，其中，F1～F3的维数为2维，F4～F10的维数为30维。

本文实验种群规模为30，最大迭代次数为200；MFOA的随机值randValue=1；IFFO的最大半径λ_max=(UB-LB)/2，最小半径λ_min=1×10-5;HSFOA的Hénon混沌参数a∈(0,1.4)，b=0.25，运行F1、F2，F4～F7时混沌步长放大系数N=10，运行F3、F8时混沌步长放大系数N=3；PSO的加速常数c1=c2=1.5，惯性因子w=0.75，最大速度Vmax=1，最小速度Vmin=-1；GA的交叉率pc=0.6，变异率pm=0.001；BA的响度A=0.25，响度衰减系数alf=0.85，脉冲发射频率增加系数BAma=0.02，脉冲发射率r=0.5。

将表1所示的10个测试函数F1～F10分别采用HSFOA、IFFO、MFOA、FOA算法单独进行20次独立寻优，寻优结果如表2所示。

由表2可见，与IFFO、MFOA、FOA相比较，本文提出的HSFOA寻优到的最优值更接近理论值，其寻优得到的误差与标准差均优于IFFO、MFOA、FOA的；对比IFFO、MFOA、FOA的稳定性，F4、F5、F7、F8的标准差均达到10-11以上，高出其他算法最少2个数量级，而对于F1、F2、F3、F6、F9，标准差虽只高出1个数量级，但其仍然优于其他算法，因此HSFOA具有更高的稳定性；同时HSFOA的误差均优于其他算法，说明其具有更好的寻优能力，尤其在F7、F8时，HSFOA的误差达到了10-10以下。综上可得，相比于同种类型的果蝇优化算法，HSFOA具有较好的稳定性和全局搜索能力。

下面将HSFOA与智能优化算法PSO、GA、BA进行仿真实验与对比分析，以验证HSFOA的有效性。将F1～F10在HSFOA、PSO、GA、BA中独立运行20次，结果如表3所示。

Table 1 Test functions表1 测试函数

Table 2 Experimental results comparison of HSFOA and other FOAs表2 HSFOA与其他FOA实验结果比较

由表3可见，HSFOA的结果更接近函数的最优值，其误差和标准差均优于PSO、GA、BA最少2个数量级，可见HSFOA有较好的稳定性和局部搜索能力。对于F2、F3，HSFOA优于PSO、GA、BA最少2个数量级，而对于F1、F6，HSFOA优于PSO、GA、BA最少4个数量级，其中运行F4、F5、F7、F8时优于其他算法9个数量级，而运行F9、F10时虽只略优于其他算法，但其仍取得了较好的结果。综上可得，相比于智能优化算法，HSFOA具有较好的全局搜索和跳出局部最优的能力。

6 结束语

针对果蝇优化算法存在算法易早熟、收敛不足的问题，将Hénon混沌映射引用为步长因子，提出了一种混沌步长果蝇优化算法。Hénon混沌映射a∈(0,0.562)时，可提高算法全局搜索能力，a∈(0.562,1.4)时，可提高算法跳出局部最优解的能力。采用10个经典测试函数进行测试，将HSFOA与同类型的果蝇优化算法MFOA、IFFO和标准FOA进行了对比分析，并与智能优化算法PSO、GA、BA进行了对比分析，结果表明：相比于MFOA、IFFO、FOA、PSO、GA、BA，HSFOA具有较高的全局搜索和跳出局部最优解的能力。

Table 3 Experimental results comparison of HSFOA and other intelligent algorithms表3 HSFOA与其他智能优化算法实验结果比较