人工蜂群算法(Artificial Bee Colony Algorithm, ABC),是模拟工蜂的觅食行为提出的,由三个基本部分组成,包括蜜源、雇佣蜂和未雇佣蜂;定义两种行为,包括招募蜜蜂到蜜源和放弃蜜源。
蜜源:由含蜜量的多少、距离蜂巢的远近以及采集花蜜的难易程度决定。在人工蜂群算法中对应适应度值,蜜源的质量直接决定了目标函数的优劣。
雇佣蜂:(Employed Bees),也称为引领蜂,主要任务是勘探蜜源,数量与发现的蜜源数量相同,任务是将每一个蜜源信息传递到蜂巢的其他蜜蜂。
非雇佣蜂:分为跟随蜂(Onlooker Bees)和侦察蜂(Scout Bees)。初始时刻,跟随蜂的数量和雇佣蜂相同,在蜂巢中等待雇佣蜂传递回信息后按照一定的策略选择蜜源,并进行开采;侦查蜂在蜂巢附近探索新的蜜源,如果探索到的蜜源优于已选择蜜源则对其进行替换。
1.4.1 算法模型
对各引领蜂的位置进行初始化,随机产生$2N$个位置,并取较为优异的$N$个位置作为蜜源位置,引领蜂根据采蜜经验,在领域范围内利用下式产生一个新位置,评估新位置的蜜源质量,即当前位置的适应度值。若蜜源质量高于原蜜源质量,则新位置替换原位置。
其中$v_{ij}$是新位置,$x_{ij}$是原位置,$x_{kj}$是随机选取的邻居蜜源位置;$\phi$是在$[-1,1]$上服从均匀分布的随机数;$k=1,2,…,BN$(BN为种群规模);$j={1,2,…,n}$($n$为维数)。
引领蜂通过跳摇摆舞将蜜源信息分享给跟随蜂,跟随蜂利用下式通过轮盘赌机制来选择一个蜜源,在利用式(1)在此蜜源附近随机产生新蜜源新位置,比较新位置和原位置的蜜源质量,若新位置的蜜源质量更好,则保存新位置。
其中,$fit_i$指当前蜜源位置的适应度值。
如果一个蜜源经过limit代后,其适应度都没有任何改变,则当前蜜源放弃。此外,当前蜜源处的引领蜂变成侦查蜂,侦查蜂利用式(3)进行随机搜索新蜜源:
反复进行上述搜索过程,直到算法迭代次数$t$达到预定的最大迭代次数,或者最好解达到预定误差精度时算法结束。流程如下图所示:
1.4.2 应用案例
电子商务自动谈判研究-多Agent自动谈判模型
其他基于生物学原理的优化算法
- 蝙蝠算法:多目标多选择背包问题
- 萤火虫群优化算法:平面选址问题
- 布谷鸟优化算法:函数优化和多维背包问题,测试函数整体比PSO好很多
- 人工鱼群算法:电力系统无功优化、波浪发电系统最优负载、出租车智能调度、大规模多背包问题、机器人路径规划
- 细菌觅食优化算法:城市轨道交通调度优化、永磁同步电机、贝叶斯网络结构学习、柔性作业车间调度问题、投资组合、输电网规划
- 生物地理学优化算法:
- 模拟植物生长算法:多目标旅行商问题