基于复数编码的多策略人工蜂群算法

单 娴,杜学东

(1.中国石油大学(华东)理学院,山东青岛266580;2.山东科技大学信息科学与工程学院,山东青岛266510)

1 引 言

随着社会经济和科学技术的不断发展,在工程技术、国防科技、经济管理和制造业等多个领域中涌现出大量的复杂优化问题.由于这些实际问题往往具有数据规模大、信息不确定等特点,在有限的时间内运用传统的精确优化方法已经难以解决.因此,设计高效、实用的优化算法成为科研工作人员研究的热点.通过模拟自然界中生物行为特征而衍生出的启发式优化算法应运而生.

目前常用的启发式优化智能算法包括以遗传算法[1]、差分进化算法[2]和分布估计算法[3]为代表的进化算法,和模拟动物行为特征的粒子群算法[4]、蚁群算法[5]、鱼群算法[6]、猴群算法[7]和人工蜂群算法[8]等群体智能算法.近年来,涌现出一批新的模拟人类行为特征的群体智能算法,如SBA算法[9]、TLBA算法[10]和JOA算法[11]等.由于这些智能算法不需要梯度信息,而且不要求优化函数必须满足凸条件,因而在复杂优化问题的求解中显示出强大的优势.如何通过对各种智能算法进行改进改善其解决优化问题的能力,成为研究者们广泛关注的问题.

人工蜂群算法(artificial bee colony algorithm,ABC)是2005年由Karaboga[8,12]基于蜜蜂采蜜过程中的分工机制和群体智能行为提出的一种启发式群体智能算法.该算法是一种并行直接搜索方法,计算过程中不需要任何梯度信息,算法结构简单,易于在计算机上实现,控制参数较少,具有较好的收敛性和稳定性.因此,自提出以来便被广泛应用至参数优化[13]、聚类分析[14]与生产调度[15]等多个领域,解决了国内外现代工程领域的多种复杂优化问题[16].

国内外学者针对人工蜂群算法展开多个角度的研究,研究的内容主要分为两个方面.

1)通过改进搜索策略提高算法搜索效率.

人工蜂群算法主要由雇佣蜂搜索、观察蜂搜索和侦察蜂搜索三个阶段完成.算法性能的优劣依赖于各个阶段的搜索方程.Zhu等[17]将全局最优解的信息融入搜索方程,提出受gbest引导的ABC算法(GABC).Banharnsakun等[18]考虑将目前最优解(best-so-far)设置为引导项,提出改进的ABC算法.Gao等[19]受DE/best/1和DE/best/2两种变异策略的启发,运用最优解的信息,提出ABC/best/1和ABC/best/2两种改进的搜索策略,有效地提高了算法的开发能力,但与ABC/rand/1相比,则显得探索能力不足.为此,Gao等[20]考虑将ABC/rand/1和ABC/best/1结合,并引入参数M,将两种搜索策略优势互补,更好地平衡了探索能力和开发能力.Li等[21]受PSO算法的启示,在搜索方程中加入由适应度值确定的惯性权重和加速系数.Gao等[22]对搜索公式进行改进,将正交学习策略引入搜索过程,提出CABC算法.Gao等[23]将种群划分为多个子种群,运用各个子种群内部及子种群之间的信息交换进行搜索,提出基于信息学习的改进ABC算法.

从标准ABC算法和上述改进算法中可以看出,不同的引导向量和搜索方程能够对搜索方向产生不同的影响,进而影响算法的收敛速度和计算精度.各种搜索策略在不同类型优化问题中的表现各异,即使对应同一类型优化问题,对于不同规模和不同求解阶段求解效率也略有不同.

2)将人工蜂群算法与其他优化算法相结合改善算法性能.

Kang等[24-26]将Nelder-Mead单形搜索机制、Rosenbrock方法和Hooke-Jeeves方法引入ABC算法,提出混合的单形ABC算法、Rosenbrock-ABC算法和HABC算法.Gao等[27]运用传统的Powell方法作为局部搜索算子对ABC算法进行改进,提高了ABC算法的整体性能.Chen等[28]将模拟退火算法嵌入搜索过程,改善了算法的搜索能力.Mustafa等[29]提出基于PSO和ABC的混合算法.上述算法的改进过程中,运用其他优化算法的特点,将局部搜索与全局搜索有机结合,实现开发能力与勘探能力的均衡.

尽管上述改进方法在一定程度上改善了ABC算法的性能,但这些算法在提高精度,改进效率和避免过早收敛等方面仍具有较大的改进空间.目前对蜂群算法的研究中,普遍考虑采用一种搜索策略展开寻优,而不同的搜索策略在不同问题的各个求解阶段寻优效果存在明显差异,现有研究尚不能为不同优化问题如何选择最佳策略提供有价值的参考.

为此,本文考虑种群个体编码方式和搜索策略对算法效率的影响,提出基于复数编码的多策略人工蜂群算法.利用复数编码方法维持解集的多样性,增强种群个体信息容量.并建立搜索策略知识库,在搜索过程中由种群个体依据自身获取信息自适应选择搜索策略,进而提高算法的搜索能力.最后,采用测试函数对算法性能进行比较和分析.

2 基本人工蜂群算法

人工蜂群由雇佣蜂、观察蜂和侦察蜂三部分构成.其中,雇佣蜂负责搜索食物源,并将获取的食物源信息以摇摆舞的形式传递给观察蜂;观察蜂以一定的概率选择食物源,或者在食物源附近继续搜索新的食物源;若某个雇佣蜂获得的食物源经过若干次搜索后仍然没有得到改善,则该雇佣蜂会放弃该食物源,并转化为侦察蜂重新进行搜索.

食物源的数目与雇佣蜂的数目相同,即等于种群规模SN.一个食物源的位置代表优化问题的一个候选解,称为种群个体,用Xi=(xi1,xi2,...,xiD)表示,其中D为优化问题的维数,i=1,2,...,SN.食物源的花蜜量对应解的适应度值.

根据蜂群的构成,将整个搜索过程分为四个阶段:

1)种群个体初始化阶段

初始食物源在各分量边界范围内由式(1)随机产生

其中j=1,2,...,D,xij为第i个食物源的第j个分量,表示第j个分量的下界和上界,ϕ为[0,1]之间的随机数.

2)雇佣蜂搜索阶段

雇佣蜂在食物源位置附近随机产生新的食物源Vi=(vi1,vi2,...,viD),搜索方程为

其中j和k是随机选择的下标,满足j∈{1,2,...,D},k∈{1,2,...,SN},且k≠i.φij为[-1,1]之间的随机数.

3)观察蜂选择阶段

观察蜂从雇佣蜂处获取食物源信息,运用适应度函数f对第i个食物源进行评估,并根据轮盘赌和贪婪策略选择食物源.当选择概率pi＞s时,观察蜂选择该食物源;否则,根据式(2)重新搜索新的食物源,并对新食物源进行评估.其中s为[0,1]之间的随机数,选择概率

其中fitnessi为第i个食物源的适应度值.

4)侦察蜂搜索阶段

若某个食物源经过limit次循环后仍然未被更新,则该食物源将被放弃,发现该食物源的雇佣蜂转化为侦察蜂,并且由式(1)随机产生一个新的食物源.

3 改进的人工蜂群算法

3.1 基于复数编码的人工蜂群算法

传统智能优化算法中,种群个体的编码采用二进制编码或者实数编码,这使得每个种群个体包含的信息在一定程度上受到限制.受神经网络权值表达的复数编码方法启示[30],考虑用双倍体表示每个食物源个体,从而将个体信息量翻倍,增加了种群的多样性,更加充分地利用到搜索空间的信息.

对于D维的优化问题,食物源个体Y的第j个分量对应一个复数,

其中i是虚数单位,j=1,2,...,D,Rj表示第j个分量的实部,Ij表示第j个分量的虚部.

3.1.1 种群个体的初始化

设优化问题第j个分量的取值范围为[Aj,Bj],随机产生D个模和D个幅角

第i个个体的第j个分量对应的双倍体为(Rj,Ij).由于

可得

由此产生SN×D个双倍体,即SN个食物源个体,每个个体包含D个双倍体.

3.1.2 种群个体的更新

与传统编码方式不同的是,复数编码个体的更新需要对实部和虚部并行进行,从而在增加种群多样性的同时,还可以提高算法的运行效率.

1)复数编码的实部更新

其中j和k是随机选择的下标,满足j∈{1,2,...,D},k∈{1,2,...,SN},且k≠i.Rij为第i个个体第j个分量的实部,φij为[-1,1]之间的随机数.

2)复数编码的虚部更新

其中j和k是随机选择的下标,满足j∈{1,2,...,D},k∈{1,2,...,SN},且k≠i.Iij为第i个个体的第j个分量的虚部,φij为[-1,1]之间的随机数.

3.1.3 适应度函数的计算方法

由于每个个体的各个分量都是由实部和虚部构成,需要先将各个分量的编码由二维空间确定的复数转化到一维空间确定的实数,然后再计算相应的适应度.具体的操作过程可以描述为

1)由复数的模确定实数值

2)由幅角确定实数变量

其中xij表示转换后的实数自变量.然后得到新个体的适应度值,并对其进行评价,若优于当前个体的适应度值,则进行替换,否则进行下一次迭代.

3.2 多策略人工蜂群算法

已有的人工蜂群算法中,对雇佣蜂和观察蜂均采用某一种搜索策略获取食物源.仅采用一种搜索策略,

每次只产生一个新的个体,无法兼顾搜索的多样性.而且,某一种搜索策略可能适用于一类或几类优化问题,而对其他的优化问题则无法得到理想的求解结果.不同的搜索策略对于同一优化问题,获得的结果也可能存在较大的差异.为解决单一搜索策略可能造成的不足,考虑采用多种搜索策略自适应选择的方式对食物源进行搜索.

论文设计一种自适应搜索策略调整方法.首先建立产生食物源个体的搜索策略知识库,然后对应每一次搜索,从知识库中选取三种搜索策略产生三个新的个体,并从三个候选个体中选取适应度最优者进入下一代种群.

策略1个体Xi从自身邻域范围内选取个体Xk,根据自身信息和个体Xk的信息进行更新,搜索方程为

其中j和k是随机选择的下标,j∈{1,2,...,D},k∈{1,2,...,SN},且k≠i.

策略2个体Xi从自身邻域范围内选取两个个体Xk1和Xk2,根据自身信息和个体Xk1、Xk2的信息进行更新,搜索方程为

其中j,k1和k2是随机选择的下标,j∈{1,2,...,D},k1∈{1,2,...,SN},k2∈{1,2,...,SN},且k1̸=i,k2̸=i,k1̸=k2.

策略3个体Xi从自身邻域范围内选取两个个体Xk1和Xk2,根据当前种群中最优个体Xbest的信息和个体Xk1,Xk2的信息进行更新,搜索方程为

其中j,k1和k2是随机选择的下标,j∈{1,2,...,D},k1∈{1,2,...,SN},k2∈{1,2,...,SN},k1̸=i,k2̸=i,k1̸=k2.

其中策略1适用于搜索范围较小,食物源分布较为密集的情形;策略2在策略1的基础上,局部搜索能力有所改善;策略3适用于搜索范围较大,食物源分布较为分散的情形.

3.3 改进人工蜂群算法流程

基于复数编码方式和多种搜索策略,提出改进的人工蜂群算法(简称CCABC算法).算法流程如下:

步骤1参数设定.设置种群个体的数量SN、个体更新限制次数limit和最大迭代次数MaxCycle;

步骤2初始化种群.采用复数编码方法产生初始种群,并计算种群个体的适应度值,记录当前最优个体Xbest的相关信息;

步骤3雇佣蜂运用式(10)、式(11)和式(14)～式(16)对个体Xi进行更新,产生新个体的实部和虚部,并根据式(12)和式(13)转换为相应实数,得到备选个体V1,V2和V3.计算三个个体的适应度值,选择最优个体Vi.若f(Vi)＜f(Xi),则Xi←Vi,triali←0;否则,triali←triali+1;

步骤4按照式(3)计算个体的选择概率.观察蜂依据轮盘赌方法选择个体Xi,并利用式(10)～式(16)进行更新,得到备选个体V1、V2和V3.计算三个个体的适应度值,选择最优个体Vi.将Vi与Xi进行比较,保留较优个体;

步骤5若triali＞limit,雇佣蜂转化为侦察蜂,并依据复数编码方法产生新个体Sol取代原个体Xi.

步骤6计算当前种群的适应度值,并记录最优个体Xbest的相关信息.迭代次数iter←iter+1;

步骤7判断是否达到终止条件或最大迭代次数,若满足,则返回最优个体和最优解,停止迭代;否则,继续执行步骤3.

4 实验仿真与分析

4.1 算法测试环境

为验证算法的有效性,对15个基准测试函数[19,20]进行仿真实验.其中f1～f6是单峰函数,f7是不连续的阶梯函数,f8～f12是多峰多极值函数,f13～f15是转移的多峰多极值函数.表1给出了15个测试函数的名称、维数、搜索空间范围和最优值.

表1 测试函数说明Table 1 Benchmark functions used in experiments

对所有的测试函数,维数D和种群规模SN分别设置为30和50,最大迭代次数MaxCycle=1 000,阈值limit=1 000.为了说明算法的有效性和优越性,运用MATLAB编程并进行仿真.将算法的计算结果与单一搜索策略ABC/rand/1和ABC/best/1进行比较,每个测试函数在不同算法上均独立运行30次,统计其最优值运算结果的均值Mean和标准方差SD.均值能够反映算法所能达到的精度,标准方差则可以反映算法的稳定性.结果如表2所示.

表2 CCABC算法,ABC/rand/1算法和ABC/best/1算法性能比较Table 2 Result comparisons of CCABC,ABC/rand/1 and ABC/best/1

从表2中可以看出,CCABC算法在15个函数上的性能都要明显优于实数编码单一策略的ABC算法.具体而言,在f6,f7和f12～f15上,CCABC算法和ABC/best/1均取得全局最优值;而在函数f8上,仅有CCABC算法取得了全局最优值.对于函数f1～f5和f9～f11,CCABC算法的计算精度与ABC/rand/1算法、ABC/best/1算法相比均有提高.因此,与实数编码单一策略的ABC/rand/1算法和ABC/best/1算法相比,CCABC在性能上具有明显的改善,能够获取更高的数值精度.

为了进一步直观展示出CCABC算法的寻优效果,将ABC/best/1算法和CCABC算法对两种测试函数的收敛曲线进行比较,如图1和图2所示.

在函数f3的进化过程中,算法均以较快的速度收敛.由函数f9进化过程曲线可以看出,在CCABC算法的运行前期,算法的搜索速度较快,每一代的最优值随迭代次数增加下降较为明显;随着进化的进行,适应度函数曲线变化逐渐平缓,种群个体函数最优值向测试函数的最优解靠近.与ABC/best/1算法相比,CCABC算法在算法的计算精度和收敛速度上均有大幅度的提高.

图1 函数f3收敛性能比较Fig.1 Convergence performance of different ABCs on f3

图2 函数f9收敛性能比较Fig.2 Convergence performance of different ABCs on f9

表3 CCABC算法与MPEDE算法、HCLPSO算法和JOA算法的性能比较Table 3 Result comparisons of CCABC,MPEDE,HCLPSO and JOA

为评估CCABC算法在求解全局优化问题上的性能,选取10个测试函数,将CCABC算法与近期相关文献提出的三种优化算法(MPEDE算法[31],HCLPSO算法[32]和JOA算法[11])的计算结果进行对比.表3给出每种算法在每个测试函数上的最优解的均值和标准方差.从表3中可以看出,CCABC算法在8个测试函数上取得了最佳性能.在函数f9上得到的最优值略差于MPEDE算法,但具有相同的数量级,且优于HCLPSO算法和JOA算法.仅在函数f4上,CCABC算法的表现逊于其他三种算法.通过与其他算法的对比可以看出,CCABC算法在全局优化问题上能够取得相对满意的优化效果.

5 结束语

优化问题广泛存在于社会经济、科学技术与工业制造等多个领域.智能算法为优化问题的求解提供了新的思路和方法.人工蜂群算法是继遗传算法、粒子群算法等方法之后提出的一种群体智能优化算法,在解决优化问题方面表现出良好的性能.基本人工蜂群算法计算精度较低,要提高求解精度,可以从解的编码方式、搜索策略和参数设置等多个方面进行改进.本文提出基于复数编码的多策略人工蜂群算法.该算法运用复数编码方法产生多样性好的解集,并建立策略知识库,在搜索过程中自适应选择搜索策略对解集进行更新.选取15个测试函数进行仿真实验,并将实验结果与其他人工蜂群算法、MPEDE算法、HCLPSO算法和JOA算法进行比较.数值计算结果证明了CCABC算法的有效性.该算法在解决全局优化问题上与其他算法相比具有一定的优越性.对于如何将其应用到其他类型优化问题及实际工程领域中,将是下一步研究的方向.