浅谈人工蜂群算法的发展运用
2020-02-28邵江琦胡福良
邵江琦,胡福良
(1.浙江大学环境与资源学院资源环境科学1601班,浙江 杭州310058;2.浙江大学动物科学学院,浙江 杭州310058)
1 群体智能
群体智能的概念起源于对自然界中某些昆虫群体的观察,是指群居性生物依靠相互协作在宏观层面上表现出的智能行为。最早有关群体智能的研究是由Reynolds在1987年提出的鸟类群体飞行行为的仿真模型Boids[1]。该模型是通过模拟现实中的鸟类群体运动行为,利用计算机复制并重现其运动轨迹,进行抽象建模,来扩展开发新的运动形式。
随着群体智能研究的发展,其良好的解决问题的优化性能也越来越被人们所关注。自20世纪90年代开始,高效优化技术的需求与计算机应用技术的高效发展,模拟生物群体智能行为以解决复杂问题已经成为优化领域的研究热点,并逐步发展成以群体智能为核心的理论体系。近些年在物联网、移动互联网的快速发展趋势下,群体智能逐渐发展成将人类智能与智能机器相互融合的技术,并在群智感知计算、联邦学习及众包等领域取得突破性进展[2]。
本文所介绍的人工蜂群算法(artificial bee colony,ABC)是群体智能算法中具有代表性的一种,是通过模拟蜜蜂的觅食行为来解决多维与多模的数值优化问题,由Dervis在2005年提出[3]。该算法自提出以来就受到众多学者的极大关注,广泛应用于神经网络、工程应用、数据挖掘和图像识别等领域[4]。
2 人工蜂群算法
2.1 蜜蜂的觅食行为
虽然单个蜜蜂的行为很简单,但是蜜蜂群体却能够表现出极其复杂的行为,可以在自然当中高效地采集花蜜,还能够迅速适应生存环境的改变。
自然界中的蜂群总是能够较快地找到优质蜜源,人类对其觅食行为的研究也由来已久。早在一个世纪前,Maurice Maeterlinck就通过实验观察蜜蜂行为发现采蜜的工蜂具有告诉同群工蜂相关信息的能力。动物学家Karl von Frisch通过长期对蜜蜂行为的观察研究发现蜜蜂依靠舞蹈的形式来与同伴传递蜜源信息,引领蜂跳“摆尾舞”的持续时间和振动频率与蜜源质量正相关,跟随蜂依靠其所观察到的舞蹈来选择特定蜜源进行采蜜,选择蜜源的概率也同蜜源质量成正比。在一定条件下,引领蜂可转变为侦察蜂,在蜂巢附近随机搜索新的蜜源。蜜蜂个体间的信息交互令整个蜂群能协同高效地完成采集任务。
2.2 算法原理
人工蜂群算法将蜂群采蜜行为概括为“为食物源招募蜜蜂和放弃某个食物源”这2种最基本的行为方式以及“食物源、被雇佣蜂和未被雇佣蜂”这3个基本元素[5]。
2.2.1食物源
食物源的价值由多方面因素综合决定,例如食物源距蜂巢的远近、获取花蜜的难易程度以及所含花蜜的丰富程度等。出于方便,在此算法中,统一用“适应度值”来综合表示食物源的价值,适应度值越高,越容易招募更多的蜜蜂,使好的花朵得到开采。
2.2.2 被雇佣蜂
即引领蜂,是已经发现了食物源的蜜蜂,与食物源一一对应,它们的主要任务是探索开发食物源。引领蜂也拥有食物源的相关具体信息,例如食物源距蜂巢的距离、方向以及食物源所含花蜜的丰富程度等,并把这些信息带回巢穴和其他蜜蜂共享。引领蜂从食物源回到蜂巢卸下花蜜后有3种选择:①如果食物源数量较少或将要耗尽,则放弃食物源成为非雇佣蜂;②食物源花蜜充足将在巢穴舞蹈为其发现的食物源吸纳更多的蜜蜂,之后返回食物源采蜜;③不进行舞蹈直接返回食物源继续采蜜。
2.2.3 未被雇佣蜂
即非雇佣蜂,包括2种非雇佣蜂,即侦察蜂和跟随蜂,主要任务是开发食物源。初始时刻,对于非雇佣蜂有2种选择:
(1)成为侦察蜂。随机搜索蜂巢附近的食物源,如果侦察蜂找到了食物源,将成为引领蜂,记录下食物源的相关信息并开始采蜜。在一般情况下,侦察蜂的数目是蜂群的5%~10%。侦察蜂的设置增加了算法逃离局部最优解的能力。
(2)成为跟随蜂。在蜂巢观察完引领蜂的舞蹈之后,通过舞蹈的剧烈程度、持续时间,确定食物源的适应度值,根据适应度值的大小并以轮盘赌的方式挑选决定食物源采蜜。跟随蜂的设置增加了算法的收敛性能。
蜂群通过引领蜂、侦察蜂与跟随蜂三者之间的相互转换,共同协作寻找优质蜜源。从算法搜索的寻优过程上看,引领蜂用来储存维持优良的解;侦察蜂用来加强逃离局部最优解的能力;跟随蜂用来增加算法的收敛性能[6]。
2.3 算法流程
(1)随机产生CSN(蜂群规模)个初始解xi,将其中一半与引领蜂对应,并计算各个解的适应度值,将最优解记录下来。
(2)引领蜂根据特定的随机公式做领域搜索过程产生新解vi,并计算新解的适应度值。
(3)假如vi的适应度值大于xi,就用vi替换xi,把vi作为当前最优解,否则保留xi。
(4)根据特定的概率公式依靠xi的适应度值来得到关于xi的概率值Pi。
(5)跟随蜂根据Pi的大小选择食物源,用随机公式进行领域搜索来获得新解vi,计算其适应度值。
(6)同(3)。
(7)判断是否有需放弃的解,若有,则侦察蜂随机生成一个新解xi代替。
(8)记录迄今为止最好的解。
(9)判断是否满足循环终止条件,若满足,则输出最优解,否则返回(2)。
2.4 人工蜂群算法特征
人工蜂群算法从自然界中蜜蜂采蜜行为抽象获得,在算法特征上表现出与自然蜂群行为相同的特点,具体说明如下:
2.4.1 系统性
自然界当中的蜂群每只蜜蜂都以整体的一员有序工作,个体之间的互相影响合作,使整个蜂群实现了个体无法完成的任务,体现了整体大于部分和的系统原理。而人工蜂群算法把蜂群觅食行为抽象化,使得多只人工蜂的求解能力明显优于单只人工蜂的和,同样也显示出了整体的系统性能。
2.4.2 分布式
分布式是将一个十分复杂的问题分成许多小的部分,并把这些部分分配给众多不同的对象处理,最后将计算结果综合得到最终结果。当蜂群需要完成某项工作时,蜂群的分布式性能得以体现,蜜蜂们为了相同的目标独立进行工作,最终目标的实现不会受到某些个体的意外或缺陷影响。人工蜂群算法的人工蜂也在问题阈值内的同时相互独立地计算问题解,整个问题的求解不会受某只人工蜂无法成功获得解而被影响,提高了算法的可靠性与延展性。
2.4.3 自组织
自组织理论是从20世纪60年代末期开始建立并逐渐发展的一种系统理论,是在没有外部指令条件下,系统内部各子系统之间能自行按照某种规则形成一定的结构或功能的自组织现象。类似蚂蚁、蜜蜂这样的昆虫,个体十分简单,但个体间的协同作用明显,能够完成许多复杂的工作任务,体现出很强的自组织性。而自组织性也是蚁群算法、微粒群算法、人工蜂群算法等群体智能算法的共同特性,人工蜂群算法在算法初期时,人工蜂单独无序地各自寻找解答,但随着一定时间内的算法进程,会逐渐趋向于最优解附近寻解,在没有外部影响的情况下形成了明确的计算目的,体现了从无序转化为有序的自组织进化。
2.4.4 反馈
反馈是指系统的输出成为输入的部分,并反过来作用于系统本身,影响系统输出的流程,是控制理论的基本因素。在蜜蜂的觅食行为当中,蜜蜂能够高效地找到优质蜜源,主要是通过在蜂巢舞蹈来传递交换信息,假如蜜源所含的花蜜越多,吸纳到的蜜蜂也会越多。人工蜂群算法也包含相似的反馈机制,通过反馈流程来引导算法系统趋向于最优解。
2.5 算法效率
在算法效率的验证当中,往往会利用算法来寻找一些复杂函数的最优解,通过收敛速度以及结果精度来评判算法质量。人工蜂群算法的提出者Dervis Karaboga在他的文章当中首先给出了运用此算法求解一些测试函数的结果,包括Sphere函数、Rosenbrock函数、Griewank函数等,结果表明人工蜂群算法无论是在平均值或是标准差方面都表现明显优于几种主流优化算法,体现了人工蜂群算法具有良好的搜索精度与较快的收敛性,能够满足足够的优化控制需求[5]。此后对人工蜂群算法的众多研究也证实了其卓越高效的算法性能,可有效地解决数值函数优化问题,又被用于人工神经网络训练、约束化问题解决以及模糊聚类实现等研究领域[7]。笔者也利用基本的人工蜂群算法尝试了编译运算求解常用的Schaffer’s F6测试函数,该函数的最优解为0,在计算过程中发现人工蜂群算法在60次运算内就能完成收敛过程,计算结果精度达到10的-6次方数量级,在短时间内可获得精度较高的“最优解”。
3 人工蜂群算法应用研究
最初人工蜂群算法的提出是为了解决优化函数求解问题,以其解决此类问题的天然优势在该领域得到广泛应用,取得了巨大成功。此后在国内外众多学者的关注推动下,其应用领域得到不断拓展,目前已经成功地在系统工程设计、神经网络训练和图像信号处理等众多领域得到了开发推广。
3.1 系统工程设计
许多系统工程设计可以被理解为求优化函数解的问题,非常适用于人工蜂群算法(ABC)的应用。刘紫薇等[8]在复合材料分层吸能成分设计中,利用ABC算法对所得的代理模型进行优化,试验表明优化处理后的复合材料管具有良好的抗冲击性能,取得了较好的效果。杨静宗等[9]基于改进的ABC算法预测浆体管道的临界淤积流速,具有良好的局部与全局搜索的性能,比常规预测方法得到的结果更为精确,优于传统的临界淤积流速经验计算公式。
3.2 神经网络训练
人工神经网络作为人工智能研究中的重要分支,在传统训练方法上存在无法确定最优参数的缺陷[10]。而ABC算法的群体智能本质非常有利于同神经网络的结合,能够优化神经网络的结构,提高神经网络的收敛精度与收敛速度。ABC算法的提出者Karaboga最早将ABC算法应用于训练前馈神经网络,表现出了优于其他算法的训练效果[11]。Asteris和Nikoo[12]利用ABC算法优化前馈神经网络模型,来解决确定钢筋混泥土填充框架结构的振动周期问题,与传统模型相比,表现出更高的灵活性和准确性。
3.3 图像信号处理
ABC算法在图像信号处理上也具有广泛应用。Anan[13]提出了一种增强图像边缘检测的ABC算法,利用ABC找到最合适的边缘滤波器,优化边缘检测的阈值,在图像边缘检测研究中具有较高的准确性,优于其他现有算法。Erik等[14]使用人工蜂群算法改进了常见的圆形检测方法霍夫变换,提高了算法的计算量和存储量,得到了一个快速的多圆检测器,在该领域取得创新性。
4 群体智能或许是智能技术的未来
基于蜜蜂觅食行为得到的人工蜂群算法是一种新兴的群智能优化技术,以其控制参数少、计算简单、易实现、鲁棒性强和适用范围广等特点,受到广泛的关注,应用前景十分广阔。在人类长时间对蜜蜂的研究过程中,从最早对行为特征的研究发展到蜂群群体智能的研究并逐渐扩展到人工智能,蜜蜂的智慧在当前信息化时代可为算法理论研究取得显著性突破提供帮助。
人类的大脑由众多神经元建立,在漫长的进化历程中,构建出了能力强大的神经元系统,用于获取关于世界的信息,并依靠其做决定、提出意见、解决问题,伴随着学习与有创造性的行动,创造了智能。在相当长的一段时间里这种创造智能的方式一直被认为是创造智能的唯一途径,即仅仅关注个体的智慧能力水平。而在对自然的关注研究中发现,有许多生物体——尤其是社会有机体,进化出了将个体的大脑连接至群体系统的能力。假如说大脑是一个能够产生智能的神经元网络,那么具备这种连接至群体能力的自然界群体即是众多大脑形成的网络,这些大脑之间的联系十分紧密,创造出了另一种令人惊叹的智能形式——群体智能。这发生在了蜜蜂身上,发生在蚂蚁身上,也发生在鸟类和鱼类身上。
对比蜂群智能与人类智能,蜜蜂的大脑比一粒沙子还小,其中只有不到一百万个神经元,能够独立完成的功能非常少,相比之下人类的神经元足有800亿个还多,对人类而言蜜蜂个体的智能十分有限。但蜜蜂却需要解决诸如选择合适的筑巢地点、高效地采集花蜜等非常复杂的问题,“适者生存”理论使蜜蜂在长期的进化中形成了蜂群思维,抑或群体智能,将众多蜜蜂的大脑聚集在一起,找到一个最优的解决方案,解决单个大脑无法解决的问题,对蜜蜂此类行为的研究将会有助于我们解决众多复杂的社会性问题。
长期以来人类对自然的认识学习不断提高着人类的能力,提升着文明的高度,尤其是工业革命以来众多依靠仿生学技术取得的科技成就使技术得到了跨越式的发展。当下,群体智能研究逐渐开展,并被应用于智能技术领域中,目前取得的相关理论成就也均体现了群体智能的良好特性,或许,智能技术的未来就在群体智能身上。
5 结语
人工蜂群算法等群体智能算法来源于对自然界中生物群体简单行为的观察研究,具有极佳的算法效率性能,在复杂问题的优化解决领域取得了广泛的应用。当前,信息时代的发展进步亟需人工智能领域取得重大突破,而基于生物行为的群体智能具有广阔的应用前景,已逐渐成为智能研究的一个重要方向。在蜜蜂群体行为的智能化发展方向上,还有非常巨大的研究潜力,蜜蜂这类与人类关系密切的“小”昆虫,将继续在人类史上发挥其“大”作用。