第2期 陈杰，等：基于信息反馈和改进适应度评价的人工蜂群算法 ·173. 域成功应用。但是，ABC算法作为一种随机优化算 源的适应度值。蜜源的适应度值取决于蜜源质量， 法，也存在收敛速度慢、易陷入局部最优的不足，与 以求取最小值为例，其适应度函数公式为 其他群体智能相比，ABC算法的探索能力很强，但 1 fit≥0 开发能力不足，因此，许多学者致力于ABC算法的 1 fit; (4) 改进工作，主要集中在对种群初始化8、混合算 1 fit,, fit <0 法[1o和学习策略1]的探索，这些研究在一定程 式中：ft为第i个解的函数值。由式(4)可知，当解 度上都提高了ABC算法的性能，但难以同时拥有较 的函数值为正数时，其值越小，蜜源的适应度越大， 快的收敛速度和较高的收敛精度。 跟随蜂选择该蜜源进行邻域搜索的概率越大，得到 为了进一步增强ABC算法的性能，本文在基本 较优蜜源的可能性也越大。 ABC算法的基础上，对种群更新策略，适应度函数 4)种群淘汰。如果某个解经过一定次数的更 以及淘汰更新函数进行改进。通过对标准函数的测 新后，其解的质量仍未得到改善，一般认为该解陷入 试表明，改进后的算法在保持良好探索能力的同时， 局部最优，此时，引领蜂将转化为侦查蜂，由式(1) 有效提高了其开发能力，能够以较快的速度和较高 重新产生一个新的解。 的收敛精度收敛至最优解。 2改进的人工蜂群算法 1人工蜂群算法 2.1基于信息反馈的种群更新 ABC算法是通过种群协作工作来完成寻优过 在基本ABC算法中，种群更新是通过随机选择 程的优化算法，在ABC算法中，蜂群被分为引领蜂、 一个个体中的某个随机分量进行更新，主要包括选 跟随蜂和侦查蜂3类以协同工作。假设对于一个优 择过程和更新过程。 化问题，其最优解在D维空间，采用ABC算法对其 选择过程包括种群个体的选择和个体分量的选 寻优，主要过程如下： 择，在基本算法中，二者皆采用随机选择策略，前者 1)初始化种群。设置种群数量为N,其中引领 的随机选择有利于保持种群个体的公平竞争，但后 蜂和跟随蜂各占一半，即N/2:设置最大迭代次数和 者的随机选择却不利于个体的进化，原因在于即便 最大不更新淘汰次数：随机产生N/2个D维的初始 一个个体分量的更新对该个体产生了积极的影响， 解{x1,x2,…,xw2},其中x:={xa,x2,…,xD},i= 在下一次迭代更新过程中，也不一定能够继续对该 1,2,…,N/2,并对初始解（蜜源）进行适应度评价。 分量进行深度搜索以获得更优个体，相反，对产生消 随机产生初始解的公式为 极影响的个体分量却在下次迭代中仍存在继续更新 x=L+rand(0,1)x (U-L) (1) 的可能，这样不仅降低了算法收敛速度，而且不利于 式中：x:是第i个更新蜜源的第j个分量，i∈1,2，…， 提高解的精度。针对这一问题，本文引入个体分量 N/2,j∈1,2，…，D:L为解的下界，U为解的上界。 记忆机制对个体信息进行反馈，使对个体进化产生 2)种群更新。引领蜂随机选择相邻蜜源并与 积极影响的个体分量得以充分搜索，改进后算法的 其产生一个新的蜜源，比较二者蜜源质量，择优保 个体分量由随机选择变成根据前一次个体更新情况 留：跟随蜂根据由引领蜂蜜源质量信息转化的概率 的反馈信息选择。具体做法是在前一次个体分量更 来选择是否对该蜜源进行邻域搜索并更新。引领蜂 新后，采用个体分量记录器CH记录其蜜源质量是 和跟随蜂的蜜源更新公式为 否得到提高并进行反馈，如提高则CH=1,在下次迭 Ug=x+RX(xg-x与) (2) 代时仍对该个体分量进行邻域搜索：否则CH=0,随 式中：k为随机产生的正整数，k∈1,2，…，N/2,且 机选择一个分量进行搜索。 i≠k;R是一个随机数，R∈[-1,1]，它控制着邻 更新过程主要取决于更新公式，基本ABC算法 域搜索的范围。 中的更新公式虽有效提高了算法的探索能力，但却降 3)概率选择。跟随蜂根据一定概率决定是否选择 低了算法的开发能力。本文基于信息反馈的思想，参 对引领蜂蜜源进行邻域搜索，概率信息计算公式为 考文献[14]，采用最优个体引导机制对基本更新公式 F 进行改进，即将前一次迭代产生的最优个体信息反馈 P:w2 (3) 到下一次迭代时个体分量的更新公式中，从而提高算 ∑F i=1 法的开发能力。改进后的更新公式为 式中：P:为第i个蜜源转化后的概率，F:为第i个蜜 x网=x+p×(xg-xa) (5)域成功应用。 但是，ＡＢＣ 算法作为一种随机优化算 法，也存在收敛速度慢、易陷入局部最优的不足，与 其他群体智能相比，ＡＢＣ 算法的探索能力很强，但 开发能力不足，因此，许多学者致力于 ＡＢＣ 算法的 改进工作，主要集中在对种群初始化［８⁃９］ 、混合算 法［１０⁃１１］和学习策略［１１⁃１３］的探索，这些研究在一定程 度上都提高了 ＡＢＣ 算法的性能，但难以同时拥有较 快的收敛速度和较高的收敛精度。 为了进一步增强 ＡＢＣ 算法的性能，本文在基本 ＡＢＣ 算法的基础上，对种群更新策略，适应度函数 以及淘汰更新函数进行改进。 通过对标准函数的测 试表明，改进后的算法在保持良好探索能力的同时， 有效提高了其开发能力，能够以较快的速度和较高 的收敛精度收敛至最优解。 １ 人工蜂群算法 ＡＢＣ 算法是通过种群协作工作来完成寻优过 程的优化算法，在 ＡＢＣ 算法中，蜂群被分为引领蜂、 跟随蜂和侦查蜂 ３ 类以协同工作。 假设对于一个优 化问题，其最优解在 Ｄ 维空间，采用 ＡＢＣ 算法对其 寻优，主要过程如下： １）初始化种群。 设置种群数量为 Ｎ ，其中引领 蜂和跟随蜂各占一半，即 Ｎ／ ２；设置最大迭代次数和 最大不更新淘汰次数；随机产生 Ｎ／ ２ 个 Ｄ 维的初始 解 ｘ１ ，ｘ２ ，…，ｘＮ／ ２ { } ，其中 ｘｉ ＝ ｘｉ１ ，ｘｉ２ ，…，ｘｉＤ { } ， ｉ ＝ １，２，…，Ｎ／ ２，并对初始解（蜜源）进行适应度评价。 随机产生初始解的公式为 ｘｉｊ ＝ Ｌ ＋ ｒａｎｄ（０，１） × （Ｕ － Ｌ） （１） 式中： ｘｉｊ 是第 ｉ 个更新蜜源的第 ｊ 个分量， ｉ ∈ １，２，…， Ｎ／ ２， ｊ ∈ １，２，…，Ｄ ； Ｌ 为解的下界， Ｕ 为解的上界。 ２）种群更新。 引领蜂随机选择相邻蜜源并与 其产生一个新的蜜源，比较二者蜜源质量，择优保 留；跟随蜂根据由引领蜂蜜源质量信息转化的概率 来选择是否对该蜜源进行邻域搜索并更新。 引领蜂 和跟随蜂的蜜源更新公式为 ｖｎｊ ＝ ｘｉｊ ＋ Ｒ × （ｘｉｊ － ｘｋｊ） （２） 式中： ｋ 为随机产生的正整数， ｋ ∈ １，２，…，Ｎ／ ２，且 ｉ ≠ｋ ； Ｒ 是一个随机数， Ｒ ∈ [ － １，１] ，它控制着邻 域搜索的范围。 ３）概率选择。 跟随蜂根据一定概率决定是否选择 对引领蜂蜜源进行邻域搜索，概率信息计算公式为 Ｐｉ ＝ Ｆｉ ∑ Ｎ／ ２ ｉ ＝ １ Ｆｉ （３） 式中： Ｐｉ 为第 ｉ 个蜜源转化后的概率， Ｆｉ 为第 ｉ 个蜜 源的适应度值。 蜜源的适应度值取决于蜜源质量， 以求取最小值为例，其适应度函数公式为 Ｆｉ ＝ １ １ ＋ ｆｉｔ ｉ ， ｆｉｔ ｉ ≥ ０ １ ＋ ｆｉｔ ｉ ， ｆｉｔ ｉ ＜ ０ ì î í ï ï ïï （４） 式中： ｆｉｔ ｉ 为第 ｉ 个解的函数值。 由式（４）可知，当解 的函数值为正数时，其值越小，蜜源的适应度越大， 跟随蜂选择该蜜源进行邻域搜索的概率越大，得到 较优蜜源的可能性也越大。 ４）种群淘汰。 如果某个解经过一定次数的更 新后，其解的质量仍未得到改善，一般认为该解陷入 局部最优，此时，引领蜂将转化为侦查蜂，由式（１） 重新产生一个新的解。 ２ 改进的人工蜂群算法 ２．１ 基于信息反馈的种群更新 在基本 ＡＢＣ 算法中，种群更新是通过随机选择 一个个体中的某个随机分量进行更新，主要包括选 择过程和更新过程。 选择过程包括种群个体的选择和个体分量的选 择，在基本算法中，二者皆采用随机选择策略，前者 的随机选择有利于保持种群个体的公平竞争，但后 者的随机选择却不利于个体的进化，原因在于即便 一个个体分量的更新对该个体产生了积极的影响， 在下一次迭代更新过程中，也不一定能够继续对该 分量进行深度搜索以获得更优个体，相反，对产生消 极影响的个体分量却在下次迭代中仍存在继续更新 的可能，这样不仅降低了算法收敛速度，而且不利于 提高解的精度。 针对这一问题，本文引入个体分量 记忆机制对个体信息进行反馈，使对个体进化产生 积极影响的个体分量得以充分搜索，改进后算法的 个体分量由随机选择变成根据前一次个体更新情况 的反馈信息选择。 具体做法是在前一次个体分量更 新后，采用个体分量记录器 ＣＨ 记录其蜜源质量是 否得到提高并进行反馈，如提高则 ＣＨ ＝ １，在下次迭 代时仍对该个体分量进行邻域搜索；否则 ＣＨ ＝ ０，随 机选择一个分量进行搜索。 更新过程主要取决于更新公式，基本 ＡＢＣ 算法 中的更新公式虽有效提高了算法的探索能力，但却降 低了算法的开发能力。 本文基于信息反馈的思想，参 考文献［１４］，采用最优个体引导机制对基本更新公式 进行改进，即将前一次迭代产生的最优个体信息反馈 到下一次迭代时个体分量的更新公式中，从而提高算 法的开发能力。 改进后的更新公式为 ｘｐｑ ＝ ｘｋｑ ＋ φ × （ｘ ｂｅｓｔ ｑ － ｘｋｑ） （５） 第 ２ 期 陈杰，等：基于信息反馈和改进适应度评价的人工蜂群算法 ·１７３·