.128 智能系统学报 第9卷 索精度较高和鲁棒性较强的特点[34。文献[4]中 1,2,…,NP)的质量对应于解的适应度值ft,NP 指出与遗传算法(genetic algorithm,GA)、差分进化 为蜜源的数量。ABC算法将蜂群分为引领蜂、跟随 算法(differential evolution,DE)和粒子群优化算法 蜂和侦察蜂3种类型，其中引领蜂和跟随蜂各占蜂 (particle swarm optimization,PSO)相比较，ABC算 群的一半，数量等于蜜源的数量，且每个蜜源同一时 法的求解质量相对较好。目前，ABC算法已经成功 间内只有一只引领蜂采蜜2)。 应用于人工神经网络训练、组合优化、电力系统优 设求解问题的维数为D,在t次迭代时蜜源i的 化、系统和工程设计等多个领域。近年来，ABC算 位置表示为X=[xx2…xn],其中，t表示 法得到了学术界的广泛关注，但由于提出时间较晚， 当前的迭代次数；xa∈(L4,Ua),La和U4分别表示 目前的研究成果比较分散且缺乏系统性。 搜索空间的下限和上限，d=1,2,…,D。蜜源i的 1人工蜂群算法 初始位置依照式(1)在搜索空间随机产生： i=La rand(0,1)(U-L) (1)》 1.1人工蜂群算法的生物背景 在搜索开始阶段，引领蜂在蜜源讠的周围根据 蜜蜂是一种社会性群居性动物，虽然单个蜜蜂 式(2)搜索产生一个新的蜜源： 的行为简单，但群体却表现出极其复杂的智慧行为。 "a=xd+p(xa-xa） (2) 自然界中的蜜蜂总能够高效地采集到花蜜，同时还 式中：d是在[1，D]中的一个随机整数，表示引领 能适应环境的改变。生物学家研究发现蜜蜂以跳舞 蜂随机地选择一维进行搜索；j∈{1,2，…，NP}, 的方式来交换蜜源信息[5)。采集到花蜜的蜜蜂，返 j≠i,表示在NP个蜜源中随机选择一个不等于i 回到蜂巢后，通过“8字舞”的形式与同伴交流蜜源 的蜜源；p是[-1,1]均匀分布的随机数，决定扰动 信息。引领蜂跳“8字舞”的持续时间与蜜源的质量 幅度(magnitude of the perturbation)。当新蜜源V,= 成正相关，跟随蜂根据观察到的舞蹈选择蜜源进行 [12…vd]的适应度优于X时，采用贪婪选 采蜜。引领蜂发现的蜜源质量与跟随蜂选择该蜜源 择的方法用V:代替X,否则保留X。所有的引领 的概率成正比。在一定条件下，引领蜂的角色转变 蜂完成式(2)的运算后，飞回信息交流区共享蜜源 为侦察蜂，在蜂巢附近随机搜索新的蜜源。蜜蜂之 信息。跟随蜂根据引领蜂分享的蜜源信息，按式 间的这种信息交流方式使整个蜂群能以协同的方式 (3)计算的概率进行跟随： 高效完成采集蜂蜜的工作。 NP (3) 蜂群实现群体智慧的最小搜索模型包括蜜源、引 n=/ 领蜂、跟随蜂和侦察蜂共4个组成要素，以及招募蜜 然后，跟随蜂采用轮盘赌的方法选择引领蜂，即在 蜂和放弃蜜源2种基本的行为[2.)。蜜蜂对蜜源的搜 [0,1]产生一个均匀分布的随机数r,如果P:大于 索一般有以下3个步骤：1)引领蜂发现蜜源并通过“8 「，该跟随蜂按式(2)在蜜源i的周围产生一个新蜜 字舞”的方式共享蜜源信息：2)跟随蜂根据引领蜂所 源，且采用同引领蜂相同的贪婪选择的方法确定保 提供的蜜源信息，选择蜜源进行采蜜：3)引领蜂多次 留的蜜源。 搜索找到的蜜源质量未有改善时，放弃现有的蜜源， 搜索过程中，如果蜜源X,经过trial次迭代搜索 转变成侦察蜂在蜂巢附近继续寻找新的蜜源。当搜 到达阈值limit而没有找到更好的蜜源，该蜜源X,将 寻到高质量的蜜源时，其角色又将转变为引领蜂。 会被放弃，与之对应的引领蜂角色转变为侦察蜂。 ABC算法是模拟蜜蜂的采蜜过程而提出来的群体智 侦察蜂将在搜索空间随机产生一个新的蜜源代替 能算法。同遗传算法与其他的群体智能算法不同，角 X,上述过程如式(4)： 色转换是ABC算法特有的机制2，]。蜂群通过引领 X1= (L+rand(0,1)(U-L)trial,>limit 蜂、跟随蜂和侦察蜂3类不同角色的转换，从而共同 X,trial,<limit 协作寻找高质量的蜜源6)。在ABC算法搜索寻优的 (4) 过程中，3类蜜蜂的作用有所差别：引领蜂用于维持 为不失一般性，以最小化的优化问题为例，在 优良解：跟随蜂用于提高收敛速度：侦察蜂用于增强 ABC算法中，解的适应度评价依据式(5)计算。 摆脱局部最优的能力[6刀。 1/(1+f),f≥0 fit, (5) 1.2人工蜂群算法的基本原理 1 abs(f),otherwise ABC算法在求解优化问题时，蜜源的位置被抽 式中：f表示解的函数值。 象成解空间中的点，代表问题的潜在解，蜜源(= 综上所述，ABC算法的核心包括3个部分：1)索精度较高和鲁棒性较强的特点［３⁃４］ 。 文献［４］ 中 指出与遗传算法（ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ， ＧＡ）、差分进化 算法（ｄｉｆｆｅｒｅｎｔｉａｌ ｅｖｏｌｕｔｉｏｎ， ＤＥ）和粒子群优化算法 （ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ， ＰＳＯ） 相比较，ＡＢＣ 算 法的求解质量相对较好。 目前，ＡＢＣ 算法已经成功 应用于人工神经网络训练、组合优化、电力系统优 化、系统和工程设计等多个领域。 近年来，ＡＢＣ 算 法得到了学术界的广泛关注，但由于提出时间较晚， 目前的研究成果比较分散且缺乏系统性。 １ 人工蜂群算法 １．１ 人工蜂群算法的生物背景 蜜蜂是一种社会性群居性动物，虽然单个蜜蜂 的行为简单，但群体却表现出极其复杂的智慧行为。 自然界中的蜜蜂总能够高效地采集到花蜜，同时还 能适应环境的改变。 生物学家研究发现蜜蜂以跳舞 的方式来交换蜜源信息［５］ 。 采集到花蜜的蜜蜂，返 回到蜂巢后，通过“８ 字舞”的形式与同伴交流蜜源 信息。 引领蜂跳“８ 字舞”的持续时间与蜜源的质量 成正相关，跟随蜂根据观察到的舞蹈选择蜜源进行 采蜜。 引领蜂发现的蜜源质量与跟随蜂选择该蜜源 的概率成正比。 在一定条件下，引领蜂的角色转变 为侦察蜂，在蜂巢附近随机搜索新的蜜源。 蜜蜂之 间的这种信息交流方式使整个蜂群能以协同的方式 高效完成采集蜂蜜的工作。 蜂群实现群体智慧的最小搜索模型包括蜜源、引 领蜂、跟随蜂和侦察蜂共 ４ 个组成要素，以及招募蜜 蜂和放弃蜜源 ２ 种基本的行为［２，４］ 。 蜜蜂对蜜源的搜 索一般有以下 ３ 个步骤：１）引领蜂发现蜜源并通过“８ 字舞”的方式共享蜜源信息；２）跟随蜂根据引领蜂所 提供的蜜源信息，选择蜜源进行采蜜；３）引领蜂多次 搜索找到的蜜源质量未有改善时，放弃现有的蜜源， 转变成侦察蜂在蜂巢附近继续寻找新的蜜源。 当搜 寻到高质量的蜜源时，其角色又将转变为引领蜂。 ＡＢＣ 算法是模拟蜜蜂的采蜜过程而提出来的群体智 能算法。 同遗传算法与其他的群体智能算法不同，角 色转换是 ＡＢＣ 算法特有的机制［２，４］ 。 蜂群通过引领 蜂、跟随蜂和侦察蜂 ３ 类不同角色的转换，从而共同 协作寻找高质量的蜜源［６］ 。 在 ＡＢＣ 算法搜索寻优的 过程中，３ 类蜜蜂的作用有所差别：引领蜂用于维持 优良解；跟随蜂用于提高收敛速度；侦察蜂用于增强 摆脱局部最优的能力［６⁃７］ 。 １．２ 人工蜂群算法的基本原理 ＡＢＣ 算法在求解优化问题时，蜜源的位置被抽 象成解空间中的点，代表问题的潜在解，蜜源 ｉ （ｉ ＝ １，２，…，ＮＰ） 的质量对应于解的适应度值 ｆｉｔ ｉ， ＮＰ 为蜜源的数量。 ＡＢＣ 算法将蜂群分为引领蜂、跟随 蜂和侦察蜂 ３ 种类型，其中引领蜂和跟随蜂各占蜂 群的一半，数量等于蜜源的数量，且每个蜜源同一时 间内只有一只引领蜂采蜜［２，４］ 。 设求解问题的维数为 Ｄ，在 ｔ 次迭代时蜜源 ｉ 的 位置表示为 Ｘ ｔ ｉ ＝ ｘ ｔ ｉ１ ｘ ｔ ｉ２ … ｘ ｔ ｉＤ [ ] ， 其中， ｔ 表示 当前的迭代次数； ｘｉｄ ∈ （Ｌｄ ，Ｕｄ ），Ｌｄ 和 Ｕｄ 分别表示 搜索空间的下限和上限， ｄ ＝ １，２，…，Ｄ 。 蜜源 ｉ 的 初始位置依照式（１）在搜索空间随机产生： ｘｉｄ ＝ Ｌｄ ＋ ｒａｎｄ（０，１）（Ｕｄ － Ｌｄ ） （１） 在搜索开始阶段，引领蜂在蜜源 ｉ 的周围根据 式（２）搜索产生一个新的蜜源： ｖｉｄ ＝ ｘｉｄ ＋ φ（ｘｉｄ － ｘｊｄ ） （２） 式中： ｄ 是在 ［１，Ｄ］ 中的一个随机整数，表示引领 蜂随机地选择一维进行搜索； ｊ ∈ ｛１，２，…，ＮＰ｝， ｊ ≠ ｉ ，表示在 ＮＰ 个蜜源中随机选择一个不等于 ｉ 的蜜源； φ 是 ［ － １，１］ 均匀分布的随机数，决定扰动 幅度（ｍａｇｎｉｔｕｄｅ ｏｆ ｔｈｅ ｐｅｒｔｕｒｂａｔｉｏｎ）。 当新蜜源 Ｖｉ ＝ ［ｖｉ１ ｖｉ２ … ｖｉｄ ］ 的适应度优于 Ｘｉ 时，采用贪婪选 择的方法用 Ｖｉ 代替 Ｘｉ， 否则保留 Ｘｉ。 所有的引领 蜂完成式（２）的运算后，飞回信息交流区共享蜜源 信息。 跟随蜂根据引领蜂分享的蜜源信息，按式 （３）计算的概率进行跟随： ｐｉ ＝ ｆｉｔ ｉ ／∑ ＮＰ ｉ ＝ １ ｆｉｔ ｉ （３） 然后，跟随蜂采用轮盘赌的方法选择引领蜂，即在 ［０，１］ 产生一个均匀分布的随机数 ｒ， 如果 ｐｉ 大于 ｒ， 该跟随蜂按式（２）在蜜源 ｉ 的周围产生一个新蜜 源，且采用同引领蜂相同的贪婪选择的方法确定保 留的蜜源。 搜索过程中，如果蜜源 Ｘｉ 经过 ｔｒｉａｌ 次迭代搜索 到达阈值 ｌｉｍｉｔ 而没有找到更好的蜜源，该蜜源 Ｘｉ 将 会被放弃，与之对应的引领蜂角色转变为侦察蜂。 侦察蜂将在搜索空间随机产生一个新的蜜源代替 Ｘｉ， 上述过程如式（４）： Ｘ ｔ＋１ ｉ ＝ Ｌｄ ＋ ｒａｎｄ（０，１）（Ｕｄ － Ｌｄ ），ｔｒｉａｌ ｉ ≥ ｌｉｍｉｔ Ｘ ｔ ｉ，ｔｒｉａｌ { ｉ ＜ ｌｉｍｉｔ （４） 为不失一般性，以最小化的优化问题为例，在 ＡＢＣ 算法中，解的适应度评价依据式（５）计算。 ｆｉｔ ｉ ＝ １ ／ （１ ＋ ｆ ｉ）， ｆ ｉ ≥ ０ １ ＋ ａｂｓ（ｆ { ｉ）， ｏｔｈｅｒｗｉｓｅ （５） 式中： ｆ ｉ 表示解的函数值。 综上所述，ＡＢＣ 算法的核心包括 ３ 个部分：１） ·１２８· 智 能 系 统 学 报 第 ９ 卷