·872· 工程科学学报，第40卷，第7期 thereby allowing the proposed algorithm to achieve fast convergence rate and high optimization accuracy. KEY WORDS artificial bee colony;degree toward optimum;particle bee;Markov chain;population dispersion 人工蜂群算法(artificial bee colony,ABC)由 f0) Karaboga提出)，该算法在海内外优化领域引起很 P:= 团 (1) fa) 大的关注.目前人工蜂群算法在蛋白质的检测和预 测问题、动态路径选择问题、可靠性冗余分配等领域 其中，P,表示选择概率，0：表示第i个蜜蜂，f(0)表 应用中取得良好效果).经典人工蜂群算法原理简 示第i个蜜蜂的适应度值，m表示种群规模.引领蜂 单、参数少且容易实现，但同时也存在进化后期寻优 与跟随蜂对蜜源进行搜索是按公式(2)进行，公式 速度慢、易出现“早熟”现象等不足[).为提高人工 (2)是蜜源搜索公式，同时也被称为引领蜂与跟随 蜂群算法性能，产生了大量改进方案.Bao与 蜂位置更新公式 Zeng[4)系统地分析研究了人工蜂群算法的参数调用 ya=xd+Ra（xa-xd）,ie（1,2,…,m)(2) 机制，提出了三种新的调用方式，改变了原有的参数 其中，ya是新蜜源位置，xa是当前蜜源位置，Ra是区 调用范围：Alatas)应用混沌映射调整了参数，使其 间[-1,1]之间的随机数，xa是当前蜜源邻域中的 一个随机蜜源位置，d是优化问题的参数维度 自适应变化，提高了人工蜂群算法的全局搜索能力； 当某个引领蜂开采蜜源连续limit代不变，则该 Chen等)把模拟退火算子添加到引领蜂的寻优过 引领蜂自动转换成侦察蜂，按新的搜索公式(3)产 程，提高了人工蜂群算法的初步探索能力 生新蜜源，计算其适应度值，同样保留适应度值高的 近年来，由于粒子群算法(particle swarm optimi- 蜜源 zation,PS0)和人工蜂群算法在算法原理和解决实 际问题中有许多相通之处，国内外许多学者对其进 =mi+rand(0,1)(%jm-%min), i∈(1,2，…，m),je(1,2,…,d) (3) 行研究.KRan与GuNduZ☑将粒子群算法和人工 其中，rand(0,1)是[0,1]间的随机数，ma和xmn是 蜂群算法进行混合，该算法将粒子群算法的全局最 参数变量的最大值与最小值. 优作为跟随蜂的位置，又把人工蜂群算法找到的最 优解当作粒子群算法的局部最优：El-Ad8]设计了 2粒子蜂群算法 一种运用人工蜂群算法改善粒子群算法中的参数从 2.1粒子群算法和人工蜂群算法融合的必要性以 而实现两者融合：Si等)提出两种信息交换机制， 及粒子群蜂群算法思想 分别设置了“基站”，实现了粒子群算法和人工蜂群 通过分析人工蜂群算法原理可知，人工蜂群算 算法的信息交互，提高了二者性能 法的全局搜索能力很强，是因为其将种群一半的蜜 本文借鉴了粒子群算法利用全局最优位置的优 蜂作为引领蜂产生初始解并通过保留适应度高的蜜 点，改变了引领蜂的变异方式，在算法后期扩大了解 蜂来进行迭代，这样既保证了解空间的多样性，又增 的搜索范围，更加有效地解决了后期易陷入局部最 强了其全局搜索能力.但现有的侦查蜂机制导致了 优的问题，在很大程度上提高了算法的收敛速度. 当引领蜂找到一个不错的解并且连续几代蜜源适应 多个函数不同维数下的仿真研究说明了本文所提算 度不变时，只能在当前蜜源位置的邻域内搜索一个 法的有效性 新蜜源，这样会大幅度降低搜索效率，从而导致算法 1人工蜂群算法 的收敛速度慢以及过早收敛，出现“早熟”现象 粒子群算法可以较好地利用全局最优解来适时 人工蜂群算法是一种较为新型的群智能优化算 地更新粒子位置，避免提前陷入局部最优.并且粒 法，其原理是通过模仿生物界蜜蜂采蜜来实现寻优. 子群算法和人工蜂群算法都是通过迭代来更新个体 蜂群算法的四个基本组成要素是：蜜源、引领蜂、跟 位置，融合方便.虽然粒子群算法自身在处理复杂 随蜂和侦察蜂：两种最基本的行为模型：招募蜜源和 的多峰问题时效果不是很好，但是人工蜂群算法的 放弃蜜源 引领蜂策略很好地弥补了粒子群算法搜索空间多样 人工蜂群算法是通过蜜蜂不断地局部寻优最终 性差的问题，因此二者融合很有必要 突显出全局最优值.跟随蜂根据引领蜂分享的信 所以，受粒子群算法的启发，在引领蜂变异为侦 息，按下式所描述的概率公式选择蜜源： 查蜂阶段，可以改变其位置更新策略，不单单在现有工程科学学报,第 40 卷,第 7 期 thereby allowing the proposed algorithm to achieve fast convergence rate and high optimization accuracy. KEY WORDS artificial bee colony; degree toward optimum; particle bee; Markov chain; population dispersion 人工蜂群算法( artificial bee colony,ABC) 由 Karaboga 提出[1] ,该算法在海内外优化领域引起很 大的关注. 目前人工蜂群算法在蛋白质的检测和预 测问题、动态路径选择问题、可靠性冗余分配等领域 应用中取得良好效果[2] . 经典人工蜂群算法原理简 单、参数少且容易实现,但同时也存在进化后期寻优 速度慢、易出现“早熟冶现象等不足[3] . 为提高人工 蜂群 算 法 性 能, 产 生 了 大 量 改 进 方 案. Bao 与 Zeng [4]系统地分析研究了人工蜂群算法的参数调用 机制,提出了三种新的调用方式,改变了原有的参数 调用范围;Alatas [5] 应用混沌映射调整了参数,使其 自适应变化,提高了人工蜂群算法的全局搜索能力; Chen 等[6]把模拟退火算子添加到引领蜂的寻优过 程,提高了人工蜂群算法的初步探索能力. 近年来,由于粒子群算法(particle swarm optimi鄄 zation,PSO)和人工蜂群算法在算法原理和解决实 际问题中有许多相通之处,国内外许多学者对其进 行研究. K覦Ran 与 G俟Nd俟Z [7]将粒子群算法和人工 蜂群算法进行混合,该算法将粒子群算法的全局最 优作为跟随蜂的位置,又把人工蜂群算法找到的最 优解当作粒子群算法的局部最优;El鄄Abd [8] 设计了 一种运用人工蜂群算法改善粒子群算法中的参数从 而实现两者融合;Shi 等[9] 提出两种信息交换机制, 分别设置了“基站冶,实现了粒子群算法和人工蜂群 算法的信息交互,提高了二者性能. 本文借鉴了粒子群算法利用全局最优位置的优 点,改变了引领蜂的变异方式,在算法后期扩大了解 的搜索范围,更加有效地解决了后期易陷入局部最 优的问题,在很大程度上提高了算法的收敛速度. 多个函数不同维数下的仿真研究说明了本文所提算 法的有效性. 1 人工蜂群算法 人工蜂群算法是一种较为新型的群智能优化算 法,其原理是通过模仿生物界蜜蜂采蜜来实现寻优. 蜂群算法的四个基本组成要素是:蜜源、引领蜂、跟 随蜂和侦察蜂;两种最基本的行为模型:招募蜜源和 放弃蜜源. 人工蜂群算法是通过蜜蜂不断地局部寻优最终 突显出全局最优值. 跟随蜂根据引领蜂分享的信 息,按下式所描述的概率公式选择蜜源: pi = f(兹i) 移 m n = 1 f(兹n ) (1) 其中,pi 表示选择概率,兹i 表示第 i 个蜜蜂,f( 兹i)表 示第 i 个蜜蜂的适应度值,m 表示种群规模. 引领蜂 与跟随蜂对蜜源进行搜索是按公式(2) 进行,公式 (2)是蜜源搜索公式,同时也被称为引领蜂与跟随 蜂位置更新公式. yid = xid + Rid (xid - xqid ), i沂(1,2,…,m) (2) 其中,yid是新蜜源位置,xid是当前蜜源位置,Rid是区 间[ - 1,1]之间的随机数,xqid是当前蜜源邻域中的 一个随机蜜源位置,d 是优化问题的参数维度. 当某个引领蜂开采蜜源连续 limit 代不变,则该 引领蜂自动转换成侦察蜂,按新的搜索公式(3) 产 生新蜜源,计算其适应度值,同样保留适应度值高的 蜜源. xij = xjmin + rand(0,1)(xjmax - xjmin ), i沂(1,2,…,m),j沂(1,2,…,d) (3) 其中,rand(0,1)是[0,1]间的随机数,xjmax和 xjmin是 参数变量的最大值与最小值. 2 粒子蜂群算法 2郾 1 粒子群算法和人工蜂群算法融合的必要性以 及粒子群蜂群算法思想 通过分析人工蜂群算法原理可知,人工蜂群算 法的全局搜索能力很强,是因为其将种群一半的蜜 蜂作为引领蜂产生初始解并通过保留适应度高的蜜 蜂来进行迭代,这样既保证了解空间的多样性,又增 强了其全局搜索能力. 但现有的侦查蜂机制导致了 当引领蜂找到一个不错的解并且连续几代蜜源适应 度不变时,只能在当前蜜源位置的邻域内搜索一个 新蜜源,这样会大幅度降低搜索效率,从而导致算法 的收敛速度慢以及过早收敛,出现“早熟冶现象. 粒子群算法可以较好地利用全局最优解来适时 地更新粒子位置,避免提前陷入局部最优. 并且粒 子群算法和人工蜂群算法都是通过迭代来更新个体 位置,融合方便. 虽然粒子群算法自身在处理复杂 的多峰问题时效果不是很好,但是人工蜂群算法的 引领蜂策略很好地弥补了粒子群算法搜索空间多样 性差的问题,因此二者融合很有必要. 所以,受粒子群算法的启发,在引领蜂变异为侦 查蜂阶段,可以改变其位置更新策略,不单单在现有 ·872·