人工蜂群算法及应用新探

赵 越 茹婷婷 袁 越

(1:吉林建筑大学计算机科学与工程学院,长春 130118;2:吉林建筑大学基础科学部，长春 130118)

0 引言

近年来,生物学家在对蜜蜂进行研究的过程中发现,蜂群采蜜的效率非常高.一个蜂群往往能很快地发现距离蜂巢一定范围内较优质的蜜源并由蜂群将其采回.在一个蜂群系统中,由侦察蜂来侦察附近的蜜源.发现目标之后,侦察蜂会飞回蜂巢附近跳出优美的舞姿,其动作幅度与其发现蜜源的质量正相关.该舞姿会吸引一定数量的蜜蜂采蜜.依据蜜源的不同质量,采蜜蜜蜂分散开来并飞往不同的目标采蜜.相对于侦察过程中所耗费的资源,整个蜂群以较小的代价获取了最多的食物,这充分体现了群体智慧[1-2].据此,2005年Karaboga首次提出了人工蜂群算法.该算法的实质就是通过仿生的手段来模拟蜂群采蜜的过程,具有较高的灵活性和适应性[3-4].目前该算法已成为群体智能算法领域中一个非常活跃的研究方向,已解决许多工程与技术问题.

1 人工蜂群算法的建模思想

使用人工蜂群算法完成问题建模的过程中,每一个问题的可行解可作为一个蜜源.蜜源能够提供花蜜的多少即为该可行解优劣程度的一个表征.我们假设每一个引领蜂仅对应一个蜜源,当该蜜源的花蜜消耗完毕后,该引领蜂即变为侦察蜂.由侦察蜂完成新蜜源的搜寻,找到蜜源后侦察蜂又成为一个引领蜂.

人工蜂群算法是一类带启发的Monte Carlo算法,能完成由候选解构成的目标集合通过不断进化来得到较优或最优解.算法的进化过程由3个步骤完成,具体如下：① 每只引领蜂附着于一个蜜源,它们之间是一一对应关系.由引领蜂在蜜源邻域搜索可行解,当发现更好的蜜源时则更新并依附于新的目标；② 根据引领蜂提供的蜜源信息,跟随蜂按照一定的选择策略依附于一个蜜源,并在该蜜源附近搜索新解.若发现更好的蜜源则通知引领蜂更改其附着的蜜源.在这样的方式下,较优质的蜜源将吸引更多的跟随蜂到其邻域完成搜索,能够增加获取较优解的可能；③ 若对于预先设定的阈值(如进化代数)解的进化过程出现停滞,则引领蜂重新变为侦察蜂,重新随机寻找新的蜜源,并以此开始新的搜索过程.

使用这3个步骤,通过合理的设定结束条件或迭代次数,算法能逐渐收敛于最优解或较优解.

2 人工蜂群算法的框架结构设计

人工蜂群算法能够以迭代的方式完成解的寻优过程.首先在问题的解空间生成M个可行解(蜜源),并将它们与引领蜂建立一一对应的关系，然后完成一轮迭代过程,由每一只引领蜂在其附着蜜源的邻域内寻找一个新的蜜源.如果新蜜源的花蜜储量(适应度值)高于现有蜜源,那么，引领蜂更新附着状态,依附于新的蜜源,否则仍旧附着在原先蜜源.在所有引领蜂确认所附着蜜源之后,所有引领蜂将全部蜜源信息发布给跟随蜂,由跟随蜂按照某种选择原则选取一个蜜源.若以概率的方式选取,假设蜜源k的花蜜储量为fk,则每一个跟随蜂选取该蜜源前往的概率pk可表示为:

(1)

从式(1)可以看出,好的蜜源能够吸引的跟随蜂一定较多.当每只跟随蜂确定自己的蜜源之后,便开始在该蜜源的邻域进行搜索,以期找到更好的蜜源.当蜜源k的所有跟随蜂对邻域搜索结束后,选取适应度最高的蜜源作为蜜源k的新位置,即找到一个更优解.若蜜源k在迭代步数内仍未取得更优解,则视为迭代已陷入局部最优,此时引领蜂转化为侦察蜂,抛弃此蜜源并在可行解空间内随机生成新的解作为新的蜜源,重新开始迭代过程.

人工蜂群算法的框架结构设计如下.

算法开始

(1) 算法初始化:

① 设置参数M，MAXGen，MAXHny，HnyIteri=0(i=1，…，M)；

/*MAXGen代表最大迭代代数,MAXHny代表每个蜜源迭代代数限制*/

② Form=1 toMdo /*初始种群数量为M*/

随机生成蜜源Hm(0);

(2) 算法迭代:

Foriter=1 toMAXGendo

① 对于引领蜂:

Fori=1 toMdo

{将每一个引领蜂附着于一个蜜源之上(两者一一对应),并计算该蜜源的适应度;

搜索邻域蜜源并计算其适应度;

取前述适应度高的蜜源,并更新;}

② 对于跟随蜂:

Forj=1 toMdo

{依据所有蜜源的适应度值,以概率的方式选择一个蜜源前往;

在该蜜源的邻域搜索得到新蜜源,并计算其适应度;

将前述适应度高的蜜源保存;}

③ 侦察蜂寻找新蜜源的过程:

对于所有蜜源:

Fori=1 toMdo

{IfHi(iter)=Hi(iter-1) thenHnyIteri=HnyIter+1;

IfHnyIteri=MAXHnythen

{舍弃蜜源,原先附着其上的引领蜂变为侦察蜂;

在可行解空间随机生成蜜源,侦察蜂再次变为引领蜂并附着其上;

HnyIteri=0;}

}

④ 记录下目标适应度值最高的蜜源(最优解);

iter=iter+1;

}

(3) 结果输出:返回所得的最优解(适应度最高的蜜源).

3 实验结果分析

现以多维背包问题为例,在OR-Library实验室提供的测试数据集上选取测试实例,使用VC++ 6.0对人工蜂群算法编程实现,每个实例运行10次,结果如表1所示.

表1 人工蜂群算法应用于多维背包问题结果分析

4 结语

实践表明,人工蜂群算法是一种较优秀的群体智能算法.尽管产生时间较晚,算法的很多方面(如引导信息素、信息素扩散机制、最优种群大小等)尚需进一步研究,但其性能仍可与现有许多群体智能算法相媲美,如蚁群算法、粒子群算法等.人工蜂群算法现已成为人工智能领域的一个研究热点问题.随着各项研究的不断深入,人工蜂群算法一定能够更多的解决更多实际问题.

参 考 文 献

[1] 石俊萍,李必云.改进蜂群算法的旅行商问题仿真[J].计算机工程与设计,2013(4):1420-1423.

[2] 刘 勇,马 良.函数优化的蜂群算法[J].控制与决策,2012(6):886-889.

[3] 丁海军,李峰磊.蜂群算法在TSP问题上的应用及参数改进[J].中国科技信息,2008(3):241-242.

[4] 王 辉.改进的蜂群算法[J].计算机工程与设计,2011(11):3869-3872.