基于邻域分割的多种群协同进化人工蜂群算法

郭书杰,王步云,吕玉鹏

(91550部队 指控中心，辽宁 大连 116023)*

基于邻域分割的多种群协同进化人工蜂群算法

郭书杰,王步云,吕玉鹏

(91550部队 指控中心，辽宁 大连 116023)*

在人工蜂群算法中，随着优化过程的进行，蜂群的多样性会急剧降低，进而导致算法陷入局部最优.针对这一问题，提出了基于邻域分割的多种群协同进化人工蜂群算法，该算法将待解问题的解空间分割成相互独立的多个领域，在每个领域上和整个解空间上分别使用不同的蜂群来优化，并且定期进行蜜源信息的交换，来提高蜂群的多样性.使用标准函数对改进算法的优化性能进行了测试，测试结果表明改进后的算法具有更好的全局寻优能力.

人工蜂群算法；函数优化；群智能

0 引言

为了解决函数优化的问题，由Karaboga于2005年提出的了人工蜂群算法[1- 2](artificial bee colony algorithm，以下简称ABC 算法)，该算法是一种新兴的模拟生物群体智能的优化方法，具有实现简单、参数数量较少、应用范围广等多种优点.Karaboga和Akay的研究结果表明，ABC算法的性能比差分进化算法、微粒群算法以及遗传算法等常见的群体智能优化算法更具优势[3].鉴于ABC算法的上述优点，ABC算法已经被成功地应用于解决多种不同类型的实际优化问题，如参数优化[4]、符号回归[5]、神经网络[6- 7]以及路径优化问题[8]等.尽管ABC算法具有诸多优点，但也存在着过早收敛、局部搜索能力较弱等缺点.为了解决这些问题，在对算法优化过程进行详细研究的基础上，对算法做了改进，提出了一种基于邻域分割的多种群协同进化人工蜂群算法.

1 人工蜂群算法

人工蜂群算法通过模拟自然界中蜂群的采蜜行为，将蜂群分为引领蜂、跟随蜂和侦察蜂三类，并将整个优化过程分解为引领蜂开采、跟随蜂开采、侦查蜂开采三个阶段.在引领蜂开采阶段，引领蜂在自己找到的蜜源周围进行局部探索；在跟随蜂开采阶段，跟随蜂根据引领蜂发现的蜜源的适应度择优选择一个蜜源，并在该蜜源周围进行局部探索；如果在某一蜜源附近的多次探索均未能找到更优的蜜源，则进入侦察蜂开采阶段：与该蜜源对应的引领蜂变成侦察蜂，随机生产一个新蜜源进行探索.

假令蜜源的数量为NP，蜜源Xi对应的适应度为fiti，蜜源维持代数阈值为limit，待解问题的维数为D，第i维Xid的取值范围为[Ldi,Udi]，则人工蜂群算法的搜索步骤如下[1,9- 10].

(1) 初始化各蜜源：设置优化代数iterMax、维持代数limit、问题维度及各维度的取值范围等参数；使用公式(1)随机生成NP个蜜源.

(1)

(2)为蜜源Xi分配一只引领蜂，并按式(2)在该蜜源周围进行索，得到新蜜源Vi.

(2)

其中,d是[1-D]中的随机整数；j∈{1,2，…，NP}并且j≠i.

(3)对新蜜源Vi进行评价，若Vi优于Xi则用Vi取代Xi，否则保留Xi.

(4)由式(3)计算引领蜂找到的蜜源被跟随的概率，跟随蜂采用轮盘赌的方法选择蜜源Xj.

(3)

(5)跟随蜂采用与引领蜂相同的方式进行搜索.

(6)判断蜜源是否满足被放弃的条件，即判断Xi的持续未更新代数traili是否大于等于limit，若是，则使用式(1)随机生成一个蜜源来取代Xi.

(4)

(7)判断算法是否满足终止条件，若满足则终止，并输出最优解，否则转到步骤(2)继续执行.

2 改进的人工蜂群算法

2.1 算法模型

为了便于描述，给出以下定义.

定义1 领域：令A为函数F(Xi)的解空间，将A分割为k个子集合{S1，S2，…,Sk}，使得S1，S2，…Sk满足以下条件：①Si(i=1,…,k)≠φ;②S1∩S2∩…∩Sk=φ;③S1∪S2∪…∪Sk=A，则称{S1，S2，…,Sk}定义了A的一个k分割；称Si为A的一个领域.

定义2 主群(Master)：令A为函数F(Xi)的解空间，使用人工蜂群算法对函数F(Xi)进行优化时，在整个A上进行优化搜索的蜂群为主群.

定义3 从群(Slave)：令A为函数F(Xi)的解空间，使用人工蜂群算法对函数F(Xi)进行优化时，对A进行一次k(k>1)分割，则在整个A的领域Si上进行优化搜索的蜂群为从群.

在基于邻域分割的多种群协同进化人工蜂群算法中，对待解函数F(Xi)的解空间进行一次k分割，形成k个领域{S1，S2，…,Sk}，在每一个领域Si上生成1个从群，使用人工蜂群算法在该领域内进行优化搜索；在F(Xi)的解空间A上生成1个主群，使用人工蜂群算法在该空间中进行优化搜索.主群和各个从群间定期进行信息交流：每隔一定的进化代数，从各个子群中选出最优秀的蜜源，取代主群的最差蜜源.改进算法的模型如图1所示.

图1 改进的人工蜂群算法的模型图

2.2 算法步骤

基于邻域分割的多种群协同进化人工蜂群算法的处理步骤如下.

(1)设置算法参数：种群大小NP、优化代数iterMax、维持代数limit、问题维度D和各维度的取值范围Ldi及Udi、迁移代数NT、领域个数NS;

(2)对每一个领域Si，根据步骤(1)设定的参数，完成参数配置，生成从群Slavei；按照第一节中给出的人工蜂群算法启动优化搜索;

(3)在解空间A上生成主群Master；根据步骤(1)设定的参数，完成参数配置，并按照第一节中给出的人工蜂群算法启动优化搜索;

(4)如果当前进化代数iter是迁移代数NT的整数倍，则从各个Slavei中选出最优解来替换主群Master中的最劣解;

(5)判断算法是否满足终止条件，若满足则终止，并输出最优解.

图2 改进的人工蜂群算法的流程图

算法处理流程如图2所示.

3 实验及结果分析

为了测试改进算法的优化性能，使用VisualStudio2010编写了标准算法和改进算法两套程序，选取两个标准函数，通过对比标准算法和改进算法的优化结果来验证改进算法的先进性.

3.1 测试函数

测试中选取了一个单峰函数和一个非线性多峰值函数来检验改进算法的全局搜索性能.测试函数如表1所示；被测函数的三维映像图如图3、4所示.

表1 标准函数

图3 f1：Sphere函数三维映像图

图4 f2：Rastrigin函数三维映像图

3.2 测试结果

使用相同的参数配置的标准人工蜂群算法和改进后的人工蜂群算法，分别对函数f1和f2的不同维数进行优化搜索，每种算法独立运行20次，所搜索到的最有解的平均值如表2所示.算法的参数配置为如下：种群大小NP=50、优化代数iterMax=100、维持代数limit=5、迁移代数NT=2、领域个数NS=5.

表2 测试结果

由上述测试结果不难看出，不论是求解单峰函数的优化问题还是求解非线性多峰值函数的优化问题，与经典人工蜂群算法相比，改进后的算法能够有效防止过早收敛的发生，具有较好的全局搜索能力；求解单峰函数的优化问题时，改进算法的优势更为明显.

4 结论

通过将问题的解空间进行分割形成相互独立的多个领域，对每一个领域i中分别使用一个人工蜂群算法Slavei来探索该领域内的最优解，同时，在问题的整个解空间上也使用一个人工蜂群算法Master来探索整个解空间上的最优解，通过定期将每个Slavei找到的最优解迁移到Master中来替换其最劣解，可以有效保持蜂群的多样性，提高算法的优化性能.由于基于邻域分割的多种群协同进化人工蜂群算法需要同时维持多个蜂群的优化搜索，因此其时间复杂度要高于经典算法.

[1]KARABOGAD.Anideabasedonhoneybeeswarmfornumericaloptimization[R].TechnicalReport,Kayseri:ErciyesUniversity,2005.

[2]KARABOGAD,BASTURKB.Apowerfulandefficientalgorithmfornumericalfunctionoptimization:Artificialbeecolony(ABC)algorithm[J].JournalofGlobalOptimization,2007,39(3):459- 471.

[3]KARABOGAD,AKAYB.Acomparativestudyofartificialbeecolonyalgorithm[J].AppliedMathematicsandComputation,2009,214(1):108- 132.

[4]贾宗圣,司锡才,王桐.基于人工蜂群技术的海杂波参数优化方法[J].中南大学学报(自然科学版),2012,43(9):3485- 3489.

[5]KARABOGAD,OZTURKC,KARABOGAN,etal.Artificialbeecolonyprogrammingforsymbolicregression[J].InformationSciences,2012,209(11):1- 15.

[6]GARROBA,SOSSAH,VZQUEZRA.Artificialneuralnetworksynthesisbymeansofartificialbeecolony(ABC)algorithm[C].//Proc.oftheIEEECongressonEvolutionaryComputation.NewOrleans:IEEE,2011:331- 338.

[7]YEHW,HSIEHT.Artificialbeecolonyalgorithm-neuralnetworksforS-systemmodelsofbiochemicalnetworksapproximation[J].NeuralComputingandApplications,2012,21(2):365- 375.

[8]SZETOWY,WUY,HOSC.Anartificialbeecolonyalgorithmforthecapacitatedvehicleroutingproblem[J].EuropeanJournalofOperationalResearch,2011,215(1):126- 135.

[9]周新宇,吴志健,王明文.基于正交实验设计的人工蜂群算法[J].软件学报,2015,26(9):2167- 2190.

[10]秦全德，程适，李丽，等．人工蜂群算法研究综述[J]．智能系统学报，2014，9(2):127- 135．

下期待发表文章摘要预报

Multi Group Cooperative Evolutionary Artificial Bee Colony Algorithm based on Neighborhood Segmentation

GUO Shujie,WANG Buyun,LV Yupeng

(Command and Control Center of 91550 Troops PLA,Dalian 116023,China)

In artificial bee colony algorithm,the diversity of the swarm will be reduced dramatically with the optimization process,which leads to the local optimization of the algorithm.To solve this problem,a multi swarm cooperative evolutionary artificial bee colony algorithm based on neighborhood segmentation is proposed.In this algorithm, the solution space of the problem to be solved is divided into a plurality of fields which are independent of each other.Different swarm optimizations are used in each field and the whole solution space,and regularly exchanges the information of nectar are conducted to improve the diversity of the swarm.The optimization performance of the improved algorithm is tested by using the standard function.The test results show that the improved algorithm has better global searching ability.

artificial bee colony algorithm;function optimization;swarm intelligence

1673- 9590(2017)03- 0112- 04

2016- 10- 11

国家“863”高技术研究发展计划资助项目(2012AA041402- 4)；辽宁省教育厅优秀青年学者成长计划资助项目(LJQ2013048)

郭书杰(1978-)，男，工程师，博士，主要从事软件工程方面的研究E-mail:shujieguo@126.com.

A