一种多样性增强的混合萤火虫算法

刘振，鲁华杰，任建存

（海军航空大学 岸防兵学院，山东 烟台 264001）

0 引言

智能进化算法近年来广泛兴起，并已逐步成为研究的热点[1-2]。人工萤火虫算法是一种新型智能进化算法，目前受到广泛关注，该算法受到萤火虫觅食和求偶行为启发，模拟自然界中萤火虫智能搜索行为的群智能算法。最早由英国米德尔塞克斯大学的Yang[3]率先系统地阐述并提出，因其新颖的进化方式，灵活的搜寻模式，优良的进化性能，基本型萤火虫算法和相应的改进版本，被广泛应用于组合优化及多目标追踪[4]等问题中，并已经取得了良好的效果。

从萤火虫算法的进化机制和运行流程可以看出，由于控制参数少，算法运行简单，因而利用较少的进化操作就能获得满意的效果，但同时也注意到由于萤火虫算法本身属于智能控制程度不高的进化算法，人工参与和可控程度偏低，导致算法往往依据生物本质性能进行进化，因而算法收敛效果不佳，进化容易停滞，并易收敛到局部极值。

当前对萤火虫算法的研究已经较为广泛，也出现了很多改进方式，其主要改进方法可以概述为：

（1）对萤火虫算法的整体运行架构和编码机制的调整，例如文献[6]将萤火虫的编码问题进行了拓展推广，提出基于回报和代价的二进制编码的萤火虫算法用于求解特征选择问题。文献[7]提出一种紧致型萤火虫算法，借鉴紧致遗传进化的优势，提高萤火虫算法的运算效率，取得了良好的进化效果。文献[8]提出利用对立搜索方式初始化萤火虫种群，用以提高种群搜索过程中的方向性。

（2）从生物进化角度出发，考虑萤火虫生物本质特点进行改进，例如文献[9]提出一种改进的离散萤火虫算法，为提高算法的进化性能和寻优区域，将萤火虫个体的视野域依据进化代数进行动态调整，早期设置较小的视野域以便于全局搜索，在进化后期自适应增大视野域。

（3）在充分保证全局寻优性能的基础上，引入局部的寻优方式，例如引入交叉变异以及混沌搜索等局部调整方法，在保留萤火虫算法本质寻优特性的基础上，提高算法跳出局部极值的能力。文献[10]提出一种自适应改进萤火虫算法用于渐进脉宽调制问题，自适应的更改吸引度和移动因子系数，提高算法跳出局部极值的能力，同时对最优解进行变异，依据概率适时选择变异后个体的对应位数。文献[11-13]将混沌搜索方式引入到萤火虫算法中，提高算法的全局寻优能力，其中文献[13]系统分析了不同混沌映射方式对算法的影响，并指出了基于混沌的萤火虫算法的发展方向。

（4）通过与其他算法的融合，以提高萤火虫算法的整体性能，例如文献[14]和[15]分别将量子进化算法和遗传算法引入到萤火虫算法中，前者在传统二进制萤火虫算法的基础上，引入动态量子旋转门操作，以期提高算法求解最优电力质量检测布局的整体性能。后者将进化规划的多种操作方式引入到萤火虫算法中，将个体适应度进行排序并利用精英个体更新萤火虫位置，对萤火虫个体采用交叉和变异操作。

本文在充分研究萤火虫算法的特性和运行方式的基础上，针对基本萤火虫算法局部进化能力存在的不足，为提高进化过程中的种群多样性，提出一种多样性增强的混合萤火虫算法DeHFA，对种群进化结构进行了调整，将种群分为主种群、子种群和精英种群，采用分布式协同框架方式，同时利用视野阈和历史最优值对萤火虫的位置进行更新，采用混沌搜索方式进行局部调整，并采用了自适应的进化参数。

1 基本萤火虫算法及其改进策略

萤火虫算法受到萤火虫发光的启示，以萤火虫发光作为吸引信号，更新萤火虫位置信息，该算法具有三个基本原则：

（1）所有萤火虫都是无性别的，因此可以被其余所有萤火虫吸引；

（2）吸引度与亮度是成正比关系的，对于任意两个萤火虫，亮度较差的个体将会被亮度高的个体吸引，亮度会受到距离影响，随着距离而衰减；

（3）萤火虫的亮度与待分析问题的目标函数密切相关。

以Xi和Xj分别表示两个萤火虫所处的位置，则两者的距离可以表示为：

两者之间的吸引度可以表示为：

其中，β0为初始吸引系数，即距离为0时的吸引度，一般可选为1，λ表示吸收率，用于度量光亮强度的衰减程度。

萤火虫位置的更新方式为：

其中，α(rand-0.5)为扰动因素，α为随机移动因子，α∈[0，1]，α越大使得萤火虫能够在更广阔的空间搜索，相反α越小的时候，则只能进行局部搜索。

从基本萤火虫算法的进化特性和进化方式可以看出，其具有收敛速度快，进化机制简单等优势，但同时也注意到萤火虫算法作为一种受生物机制启发的进化算法，控制参数较少，仅利用群智能个体之间松散的本质特性寻优，无法有效地进行勘探和开采的协调，必然存在过早收敛，且容易陷入局部极值等问题。因此针对当前萤火虫算法存在的问题，本文从整体框架结构、参数调整方式、局部搜索方式等方面提出了系统的改进方式，以增强种群进化过程中的多样性，提高算法的收敛能力。

2 多样性增强的混合萤火虫算法

为提高萤火虫算法的进化性能，需要扩展算法的寻优空间，提高种群多样性，增加进化过程的灵活性。因此本文从这一思想出发，充分考虑到多种群协同进化的特点和优势，利用分布式的种群进化框架，将优良精英个体引入到个体更新过程中，提高种群进化的指引性，并引入了混沌优化和参数自适应变化等局部调整方法。

2.1 分布式多种群协同进化

在传统萤火虫进化算法中，往往利用单一种群进行进化，不能实现多个小生境的信息交流和协同进化，无法保证进化性能的持续改进，进化效率有待提高。借鉴生物多样性进化机制的特点，本文提出构造多种群协同进化模型[16]，将整个种群结构在进化层次上进行划分，依据种群的适应度和进化的职责功能划分为：主种群（M）、子种群（Subi，i=1，2，3，4）和精英种群（Ei，i=1，2，3，4），并构成分布式结构体系，其进化结构拓扑如图1所示。子种群之间可以进行优良个体的交流，精英种群为子种群优良个体构成的群集，主种群是从所有精英种群中再次选择优良个体而构成的种群。各种群独立进化，主张群能够进行全局范围内的广泛搜索，子种群进行局部范围内的精细搜索，而精英种群内能够在主种群全局搜索和局部勘探的基础上，精确寻找全局最优解，各个种群之间能够进行最优个体交流，利用最优个体进行萤火虫位置的更新。

图1 分布式协同框架结构Fig.1 Framework of distributed cooperative evolution

从图1可以看出，主种群为M，为整个种群规模，将主种群平均划分为4个子种群独立进行进化，Subi为第i个子种群，Ei为第i个精英种群，gbi为第i个子种群的最优个体，子种群Subi中最优的λ1个个体构成精英种群Ei，精英种群Ei完成一次进化后，将其中的最优的λ2(λ2＜λ1)个个体构成主种群M。各子种群之间进行个体交流，交流方式按照式（4）进行：

2.2 利用最优值更新个体位置

从生物进化的本质特点出发，每个萤火虫都具有特定的视野阈值，采用固定的视野阈值将极大地限制算法的能力，根据种群进化情况，提出一种自适应的视野阈值，其进化视野阈值范围如图2所示。

图2 萤火虫视野阈示意图Fig.2 View threshold of firefly

定义萤火虫视野范围为：

其中，1≤t≤Tmax，Tmax为最大迭代次数，则可以得到为常数，第i个个体的视野阈范围定义为：

在萤火虫算法的进化吸引过程中，优良个体的引导作用将会极大地提升算法进化性能[17]，并有效地指导算法进化方向。利用历史最优解和当前代内的最优解，引导当前种群趋向于优良个体，并能加快个体寻优速度，提高进化效率和进化性能。因此利用视野阈值范围内获得的最优个体位置xgb(t)和当前代个体历史最优位置xpb(t)，按照式（7）更新个体位置：

2.3 分阶段混沌进化方式

混沌进化本质上是利用混沌运动所具有随机性和遍历性等特点，进行搜索和寻优的一种进化方法。由于混沌进化具有对初始条件敏感等特点，因此比传统进化方法具备一定的优越性。在以往的混沌进化中，较多的采用Logistic映射，在有效地扩大搜索范围的同时，也注意到，其寻优速度容易受到Logistic遍历不均匀的影响。文献[18]指出Tent映射方式具有较快收敛速度和较强的全局遍历性，在保留初始种群个体均匀性的基础上，又使得种群个体具有良好的多样性。因此为保证所提出的算法具有全局勘探性能，将两种不同混沌搜索方式有机地融合，利用Logistic映射产生全局分布范围更广的初始种群，充分利用自适应Tent混沌搜索方式的优良特性进行局部搜索，提高种群深度开采的能力，两阶段混沌进化过程为：

（1）混沌初始化种群阶段

依据zi+1，j=μzi，j(1-zi，j)，i=1，…，N-1，N为种群规模，μ=4，随机产生一个D维的初始向量：

依次产生迭代向量z1，z2，…，zN，并将混沌变量映射到当前解空间，则：

其中，i=1，2，…N，j=1，2，…，D，UBj和LBj分别表示第j维的上界和下界。

（2）Tent混沌自适应搜索阶段

Tent混沌映射公式为：

1）将当前搜索位置xi依据zi，j(0)=变换到（0，1）范围内，其中i=1，2，…，N，j=1，2，…，D；

2）利用Tent混沌映射公式，产生Tent混沌变量zi，j(t)，t=1，2，…，tmax；

3）依据

将混沌载波变量映射到原有解空间范围内；

4）判断yi，j(t)和xi，j(t)位置优劣情况，并保留最优位置；

5）判断是否达到最大混沌迭代次数，若达到则混沌迭代结束，否则返回2）；

6）判断是否所有个体完成Tent混沌搜索，若没有，则返回2）。

2.4 参数自适应调整

在算法进化过程中，前期设置较大的α便于进行全局范围内搜索，后期当算法进入到最优值附近进行开采操作过程中，采用较小的α，进行局部开采，则参数自适应调整可按照式（11）进行。

其中，δ和α0设置为常数，α0∈(0，1)。

本文提出的多样性增强的混合萤火虫算法（DeHFA），其主要进化流程可以描述为：

步骤1：设置种群规模N，循环迭代次数Tmax，α0、β0、λ等参数信息，循环迭代次数t=1；

步骤2：依据式（8）和式（9），利用 Logistic映射初始化种群X(t)；

步骤3：将种群划分为一个主种群M，4个子种群Subi(i=1，2，3，4)以及4个精英种群Ei(i=1，2，3，4)；

步骤4：分别在主种群、子种群和精英种群中，子种群之间执行式（4）的个体交流，视野阈范围按照式（6）限定，利用式（7）更新萤火虫位置，参数α依据式（11）设定；

步骤5：执行2.3节提出的Tent混沌自适应搜索，对当前种群中的个体执行一次Tent混沌搜索；

步骤6：当达到算法最大迭代次数或者满足收敛精度要求，则结束迭代，否则转步骤3。

3 收敛性分析

对本文提出的多样性增强的混合萤火虫算法（DeHFA）的收敛性进行分析，首先给出相应的假设、定义和引理。

假设1给定目标函数f：Rn→R为可行区域S上的连续函数，并且在该问题的可行区域范围S内是有界闭内。

定义1在概率空间范围内存在随机序列ξn(n=1，2，…)，如果存在随机变量ξ，当满足存在∀ε＞ 0，使得，则称随机序列{ξn}以概率1收敛于随机变量ξ。

引理1（Borel-Cantelli引理）设{Ak：k≥1}是概率空间上的事件集合，令，若，

引理2如果ΔX=X(t+1)-X(t)，则ΔX～N(μ，σ)。

根据相应的假设、定义和引理，可综合推导出DeHFA满足定理1，即DeHFA满足以概率1收敛到全局最优解。

定理1令{X(t)}为本文提出的DeHFA位置序列，并且令{Xg(t)}∈X(t)为其最优解序列，如果满足假设1条件，则DeHFA以概率1收敛于全局最优解，即

证明对于∀ε＞0，令

其中X*为全局最优解，不失一般性，假设对于极小化问题，X*=min(f(x)：x∈Ω)，可得到：

由引理 2 可知，Δf(Xg(t))～N(μ1，σ1)，因此可以得到令由引理1可以得到：，由定义 1，可以得到f(Xg(t))以概率1收敛于X*，即{Xg(t)}以概率1收敛于全局最优解，定理1得证。

4 仿真分析

将本文所提出的DeHFA利用16个基准函数f1-f16进行仿真对比分析，设置种群规模N=100，Tmax=100，α0=0.5，β0=1，λ=0.01，rm=1，δ=0.5。仿真平台软硬件配置为：Intel（R）Core（TM）i3-3220处理器，内存2.00 GB，Windows 2007，仿真软件为Matlab R2009a。

将本文提出的多样性增强的混合萤火虫算法（DeHFA）与基本萤火虫算法（FA），文献[3]提出的模糊C均值聚类萤火虫算法（FAFCM），文献[5]提出的引入Tent混沌映射萤火虫算法（CFA），文献[11]提出的具有混沌性质的自适应萤火虫算法（AFA），进行仿真对比分析。分别采用低维函数和高维函数进行仿真对比，其中函数变量的取值范围已经给出，对于低维函数，其维数取为2，对于高维函数，其维数取值分别为10和20，表1为基准仿真函数的详细描述。

表1 基准仿真函数Table 1 Benchmark function for stimulation

4.1 低维函数分析

将本文提出的DeHFA，以f1-f8函数为例进行仿真分析，其中函数的维数均设置为2，对比算法为基本萤火虫算法（FA），文献[3]提出的模糊C均值聚类萤火虫算法（FAFCM），文献[5]提出的Tent混沌萤火虫算法（CFA），文献[11]的自适应萤火虫算法（AFA），其中除f1函数最优值为-1外，其余函数最优值均为0。五种算法分别独立运行30次，统计其中的最优值、均值和标准差，其实验统计结果如表2所示。

表2 低维函数仿真对比分析Table 2 Comparison results for the simulation of low dimension function

从统计结果可以看出，本文提出的DeHFA在大部分函数上的最优值、均值和标准差能够优于其他几种算法，但同时也注意到基本萤火虫算法由于缺乏有效的全局搜索和局部开采手段，因而寻优效果较差。在加入了模糊C均值聚类方式以后，算法性能有所提高，当采用了混沌搜索方式，例如CFA，以及自适应机制以后，如AFA，萤火虫算法性能都有了较大程度的提高。本文提出的DeHFA在充分考虑协同进化框架，并采用了相关的局部开采操作，性能有了较大程度的提高。从所对比函数的标准差可以看出，多样性提高明显，充分表明了协同进化、混沌优化及参数自适应调整方法的综合运用极大地提高了算法的种群多样性，有效地提高了种群的进化性能。为了更加充分地进行对比分析，给出f3函数的仿真对比图，如图3所示。

图3 f3仿真对比结果Fig.3 Comparison results for f3

从图3的仿真对比图可以看出，基本萤火虫算法寻优迭代效果较差，一般需要较长的迭代次数才能找到较优解，FAFCM将两种算法进行了一定的融合，但模糊C均值聚类并不是一种局部搜索能力很强的方法，因此提高的性能有限，同时也发现当函数的维数较低时，DeHFA优势并不明显，其性能只是略优于CFA和AFA。

4.2 高维函数仿真分析

将本文提出的DeHFA，以f9-f16函数为例进行仿真分析，其中函数的维数分别设置为10和20，对比算法与前述一致。五种算法分别独立运行30次，统计其中的均值和标准差，其实验统计结果如表3所示。

表3 高维函数仿真对比分析Table 3 Comparison results for the simulation of high dimension function

从表3的统计结果可以看出，本文提出的DeHFA在高维函数上显示出较好的优越性，在f9-f16函数上，无论是10维和20维时，与其他几种进化算法相比，都能取得最优值，特别是种群的多样性，从标准差对比可以看出有了明显的提高。主要是因为本文提出的DeHFA采用了协同进化框架结构，从整体上增强了算法全局勘探的能力，同时在局部开采上又采用了参数自适应和两阶段混沌搜索，与简单的混沌搜索和参数自适应等更新方式相比，在全局勘探和局部开采能力上都有了一定程度的提高。为了更清楚的对算法进行对比分析，分别给出维数为10时的f13函数和f14函数进行仿真对比分析，分别如图4和图5所示。

图4 f13仿真对比结果Fig 4 Comparison results for f13

图5 f14仿真对比结果Fig 5 Comparison results for f14

从仿真对比图可以看出，当函数维数增高以后，对于优化算法来说，将变得越来越困难，基本萤火虫算法FA以及模糊C均值聚类萤火虫算法FAFCM，都出现了初始寻优方向盲目，需要较多的循环迭代才能达到最优解附近，而对于CFA和AFA来说，由于分别采用了一些局部增强的搜索方法，因而使得算法能够在经历过初期的动荡以后，较快的稳定到最优值附近搜索，而DeHFA随着函数的维数增加，受到的影响相对较小，优势得到进一步的体现，充分表明了协同进化搜索框架和局部增强方法运用后，提高了萤火虫算法的搜索能力。

5 结论

本文针对传统萤火虫算法全局寻优能力不强等问题，从提高种群进化多样性角度出发，提出一种能够增强种群多样性的混合萤火虫算法。DeHFA采用了协同进化框架结构，并采用了两阶段的混沌进化和参数自适应调节方式，仿真结果也验证所提出算法的正确性。本文算法的出发点在于提高算法的收敛精度和进化效率，并没有考虑系统的开销，因此在保证进化精度和进化效率的同时，尽可能地提高进化速度是以后研究的重点。