第11卷第2期 智能系统学报 Vol.11 No.2 2016年4月 CAAI Transactions on Intelligent Systems Apr.2016 D0I:10.11992/is.201506024 网络出版地址：http://www.cnki.net/kcms/detail/23.1538.TP.20160315.1051.002.html 基于信息反馈和改进适应度评价的人工蜂群算法 陈杰，沈艳霞，陆欣 (江南大学物联网技术应用教育部工程研究中心，江苏无锡214122) 摘要：针对原始人工蜂群算法存在收敛速度慢和易陷入局部最优的不足，提出了一种基于信息反馈和改进适应度 评价的人工蜂群算法。首先，引入种群个体分量记忆机制对个体信息进行反馈以增强种群开发能力，加快算法收敛 速度：其次，为避免因种群后期无法识别优秀个体导致的“早熟”现象，通过改进适应度函数增大不同个体间解的差 异性：最后，采用最优蜜源引导机制改进淘汰更新函数以避免不良个体的产生。对标准函数的测试结果表明，改进 后算法有较快的收敛速度和较高的收敛精度。 关键词：人工蜂群算法：群体智能：进化算法：函数优化：信息反馈 中图分类号：TP18文献标志码：A文章编号：1673-4785(2016)02-0172-08 中文引用格式：陈杰，沈艳霞，陆欣.基于信息反馈和改进适应度评价的人工蜂群算法[J].智能系统学报，2016,11(2)：172179. 英文引用格式：CHEN Jie,SHEN Yanxia,LUXi.Artificial bee colony algorithm based on information feedback and an improved fitness value evaluation[J].CAAI transactions on intelligent systems,2016,11(2):172-179. Artificial bee colony algorithm based on information feedback and an improved fitness value evaluation CHEN Jie,SHEN Yanxia,LU Xin (Research Center of Engineering Applications for IOT,Jiangnan University,Wuxi 214122,China) Abstract:The artificial bee colony (ABC)algorithm converges slowly and easily gets stuck on local solutions; hence,an ABC algorithm based on information feedback and an improved fitness value evaluation is proposed.The algorithm first introduces a memory mechanism for individual components to feedback information to enhance its ca- pacity for population exploitation and to accelerate the convergence speed.Then,it adopts a new fitness function to increase the difference between individuals and to avoid premature convergence from failing to identify the best indi- vidual.Finally,the algorithm integrates an optimal nectar-source guidance mechanism into the knockout function to prevent the production of unexpected individuals.Experiments were conducted on standard functions and were com- pared with those with several typical improved ABCs.The results show that the improved algorithm accelerates the convergence rate and improves the solution accuracy. Keywords:artificial bee colony algorithm;swarm intelligence;evolutionary algorithm;function optimization;in- formation feedback 随着优化问题在工程应用和理论研究上日益突 算法因结构简单、参数较少和易于实现的良好特性 出，基于群体智能理论的优化算法受到人们广泛关 在群体智能算法中脱颖而出。文献[1]中指出 注。近年来，人工蜂群(artificial bee colony,ABC) ABC算法与遗传算法(genetic algorithm,GA)、差分 进化算法(differential evolution,DE)和粒子群优化 收稿日期：2015-06-15.网络出版日期：2016-03-15. 算法(particle swarm optimization,PSO)相比较，其求 基金项目：国家自然科学基金项目(61573167)：高等学校博士学科点专 项科研基金项目(20130093110011)：江苏省自然科学基金项 解质量较好。目前，ABC算法已经在人工神经网络 目(BK20141114). 训练34、组合优化s6)、电力系统优化)等多个领 通信作者：沈艳霞.E-mail:shenyx@jiangnan.edu.cm
第 １１ 卷第 ２ 期 智 能 系 统 学 报 Ｖｏｌ．１１ №．２ ２０１６ 年 ４ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ａｐｒ． ２０１６ ＤＯＩ：１０．１１９９２ ／ ｔｉｓ．２０１５０６０２４ 网络出版地址：ｈｔｔｐ： ／ ／ ｗｗｗ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ＴＰ．２０１６０３１５．１０５１．００２．ｈｔｍｌ 基于信息反馈和改进适应度评价的人工蜂群算法 陈杰，沈艳霞，陆欣 （江南大学 物联网技术应用教育部工程研究中心，江苏 无锡 ２１４１２２） 摘 要：针对原始人工蜂群算法存在收敛速度慢和易陷入局部最优的不足，提出了一种基于信息反馈和改进适应度 评价的人工蜂群算法。 首先，引入种群个体分量记忆机制对个体信息进行反馈以增强种群开发能力，加快算法收敛 速度；其次，为避免因种群后期无法识别优秀个体导致的“早熟”现象，通过改进适应度函数增大不同个体间解的差 异性；最后，采用最优蜜源引导机制改进淘汰更新函数以避免不良个体的产生。 对标准函数的测试结果表明，改进 后算法有较快的收敛速度和较高的收敛精度。 关键词：人工蜂群算法；群体智能；进化算法；函数优化；信息反馈 中图分类号： ＴＰ１８ 文献标志码：Ａ 文章编号：１６７３⁃４７８５（２０１６）０２⁃０１７２⁃０８ 中文引用格式：陈杰，沈艳霞，陆欣． 基于信息反馈和改进适应度评价的人工蜂群算法［Ｊ］． 智能系统学报， ２０１６， １１（２）： １７２⁃１７９． 英文引用格式：ＣＨＥＮ Ｊｉｅ， ＳＨＥＮ Ｙａｎｘｉａ， ＬＵ Ｘｉ． Ａｒｔｉｆｉｃｉａｌ ｂｅｅ ｃｏｌｏｎｙ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｉｎｆｏｒｍａｔｉｏｎ ｆｅｅｄｂａｃｋ ａｎｄ ａｎ ｉｍｐｒｏｖｅｄ ｆｉｔｎｅｓｓ ｖａｌｕｅ ｅｖａｌｕａｔｉｏｎ［Ｊ］． ＣＡＡＩ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｉｎｔｅｌｌｉｇｅｎｔ ｓｙｓｔｅｍｓ， ２０１６， １１（２）： １７２⁃１７９． Ａｒｔｉｆｉｃｉａｌ ｂｅｅ ｃｏｌｏｎｙ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｉｎｆｏｒｍａｔｉｏｎ ｆｅｅｄｂａｃｋ ａｎｄ ａｎ ｉｍｐｒｏｖｅｄ ｆｉｔｎｅｓｓ ｖａｌｕｅ ｅｖａｌｕａｔｉｏｎ ＣＨＥＮ Ｊｉｅ， ＳＨＥＮ Ｙａｎｘｉａ， ＬＵ Ｘｉｎ （Ｒｅｓｅａｒｃｈ Ｃｅｎｔｅｒ ｏｆ Ｅｎｇｉｎｅｅｒｉｎｇ Ａｐｐｌｉｃａｔｉｏｎｓ ｆｏｒ ＩＯＴ， Ｊｉａｎｇｎａｎ Ｕｎｉｖｅｒｓｉｔｙ， Ｗｕｘｉ ２１４１２２， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｈｅ ａｒｔｉｆｉｃｉａｌ ｂｅｅ ｃｏｌｏｎｙ （ＡＢＣ） ａｌｇｏｒｉｔｈｍ ｃｏｎｖｅｒｇｅｓ ｓｌｏｗｌｙ ａｎｄ ｅａｓｉｌｙ ｇｅｔｓ ｓｔｕｃｋ ｏｎ ｌｏｃａｌ ｓｏｌｕｔｉｏｎｓ； ｈｅｎｃｅ， ａｎ ＡＢＣ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｉｎｆｏｒｍａｔｉｏｎ ｆｅｅｄｂａｃｋ ａｎｄ ａｎ ｉｍｐｒｏｖｅｄ ｆｉｔｎｅｓｓ ｖａｌｕｅ ｅｖａｌｕａｔｉｏｎ ｉｓ ｐｒｏｐｏｓｅｄ． Ｔｈｅ ａｌｇｏｒｉｔｈｍ ｆｉｒｓｔ ｉｎｔｒｏｄｕｃｅｓ ａ ｍｅｍｏｒｙ ｍｅｃｈａｎｉｓｍ ｆｏｒ ｉｎｄｉｖｉｄｕａｌ ｃｏｍｐｏｎｅｎｔｓ ｔｏ ｆｅｅｄｂａｃｋ ｉｎｆｏｒｍａｔｉｏｎ ｔｏ ｅｎｈａｎｃｅ ｉｔｓ ｃａ⁃ ｐａｃｉｔｙ ｆｏｒ ｐｏｐｕｌａｔｉｏｎ ｅｘｐｌｏｉｔａｔｉｏｎ ａｎｄ ｔｏ ａｃｃｅｌｅｒａｔｅ ｔｈｅ ｃｏｎｖｅｒｇｅｎｃｅ ｓｐｅｅｄ． Ｔｈｅｎ， ｉｔ ａｄｏｐｔｓ ａ ｎｅｗ ｆｉｔｎｅｓｓ ｆｕｎｃｔｉｏｎ ｔｏ ｉｎｃｒｅａｓｅ ｔｈｅ ｄｉｆｆｅｒｅｎｃｅ ｂｅｔｗｅｅｎ ｉｎｄｉｖｉｄｕａｌｓ ａｎｄ ｔｏ ａｖｏｉｄ ｐｒｅｍａｔｕｒｅ ｃｏｎｖｅｒｇｅｎｃｅ ｆｒｏｍ ｆａｉｌｉｎｇ ｔｏ ｉｄｅｎｔｉｆｙ ｔｈｅ ｂｅｓｔ ｉｎｄｉ⁃ ｖｉｄｕａｌ． Ｆｉｎａｌｌｙ， ｔｈｅ ａｌｇｏｒｉｔｈｍ ｉｎｔｅｇｒａｔｅｓ ａｎ ｏｐｔｉｍａｌ ｎｅｃｔａｒ⁃ｓｏｕｒｃｅ ｇｕｉｄａｎｃｅ ｍｅｃｈａｎｉｓｍ ｉｎｔｏ ｔｈｅ ｋｎｏｃｋｏｕｔ ｆｕｎｃｔｉｏｎ ｔｏ ｐｒｅｖｅｎｔ ｔｈｅ ｐｒｏｄｕｃｔｉｏｎ ｏｆ ｕｎｅｘｐｅｃｔｅｄ ｉｎｄｉｖｉｄｕａｌｓ． Ｅｘｐｅｒｉｍｅｎｔｓ ｗｅｒｅ ｃｏｎｄｕｃｔｅｄ ｏｎ ｓｔａｎｄａｒｄ ｆｕｎｃｔｉｏｎｓ ａｎｄ ｗｅｒｅ ｃｏｍ⁃ ｐａｒｅｄ ｗｉｔｈ ｔｈｏｓｅ ｗｉｔｈ ｓｅｖｅｒａｌ ｔｙｐｉｃａｌ ｉｍｐｒｏｖｅｄ ＡＢＣｓ． Ｔｈｅ ｒｅｓｕｌｔｓ ｓｈｏｗ ｔｈａｔ ｔｈｅ ｉｍｐｒｏｖｅｄ ａｌｇｏｒｉｔｈｍ ａｃｃｅｌｅｒａｔｅｓ ｔｈｅ ｃｏｎｖｅｒｇｅｎｃｅ ｒａｔｅ ａｎｄ ｉｍｐｒｏｖｅｓ ｔｈｅ ｓｏｌｕｔｉｏｎ ａｃｃｕｒａｃｙ． Ｋｅｙｗｏｒｄｓ： ａｒｔｉｆｉｃｉａｌ ｂｅｅ ｃｏｌｏｎｙ ａｌｇｏｒｉｔｈｍ； ｓｗａｒｍ ｉｎｔｅｌｌｉｇｅｎｃｅ； ｅｖｏｌｕｔｉｏｎａｒｙ ａｌｇｏｒｉｔｈｍ； ｆｕｎｃｔｉｏｎ ｏｐｔｉｍｉｚａｔｉｏｎ； ｉｎ⁃ ｆｏｒｍａｔｉｏｎ ｆｅｅｄｂａｃｋ 收稿日期：２０１５⁃０６⁃１５． 网络出版日期：２０１６⁃０３⁃１５． 基金项目：国家自然科学基金项目（６１５７３１６７）；高等学校博士学科点专 项科研基金项目（２０１３００９３１１００１１）；江苏省自然科学基金项 目（ＢＫ２０１４１１１４）． 通信作者：沈艳霞． Ｅ⁃ｍａｉｌ： ｓｈｅｎｙｘ＠ ｊｉａｎｇｎａｎ．ｅｄｕ．ｃｎ． 随着优化问题在工程应用和理论研究上日益突 出，基于群体智能理论的优化算法受到人们广泛关 注。 近年来，人工蜂群（ ａｒｔｉｆｉｃｉａｌ ｂｅｅ ｃｏｌｏｎｙ， ＡＢＣ） 算法因结构简单、参数较少和易于实现的良好特性 在群体智能算法中脱颖而出［１⁃２］ 。 文献［１］ 中指出 ＡＢＣ 算法与遗传算法（ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ，ＧＡ）、差分 进化算法（ ｄｉｆｆｅｒｅｎｔｉａｌ ｅｖｏｌｕｔｉｏｎ，ＤＥ） 和粒子群优化 算法（ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ，ＰＳＯ）相比较，其求 解质量较好。 目前，ＡＢＣ 算法已经在人工神经网络 训练［３⁃４］ 、组合优化［５⁃６］ 、电力系统优化［７］ 等多个领
第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)
域成功应用。 但是，ＡＢＣ 算法作为一种随机优化算 法，也存在收敛速度慢、易陷入局部最优的不足，与 其他群体智能相比，ＡＢＣ 算法的探索能力很强，但 开发能力不足，因此，许多学者致力于 ＡＢＣ 算法的 改进工作，主要集中在对种群初始化［８⁃９］ 、混合算 法［１０⁃１１］和学习策略［１１⁃１３］的探索，这些研究在一定程 度上都提高了 ＡＢＣ 算法的性能，但难以同时拥有较 快的收敛速度和较高的收敛精度。 为了进一步增强 ＡＢＣ 算法的性能，本文在基本 ＡＢＣ 算法的基础上，对种群更新策略，适应度函数 以及淘汰更新函数进行改进。 通过对标准函数的测 试表明，改进后的算法在保持良好探索能力的同时， 有效提高了其开发能力，能够以较快的速度和较高 的收敛精度收敛至最优解。 １ 人工蜂群算法 ＡＢＣ 算法是通过种群协作工作来完成寻优过 程的优化算法，在 ＡＢＣ 算法中，蜂群被分为引领蜂、 跟随蜂和侦查蜂 ３ 类以协同工作。 假设对于一个优 化问题，其最优解在 Ｄ 维空间，采用 ＡＢＣ 算法对其 寻优，主要过程如下： １）初始化种群。 设置种群数量为 Ｎ ，其中引领 蜂和跟随蜂各占一半，即 Ｎ／ ２；设置最大迭代次数和 最大不更新淘汰次数；随机产生 Ｎ／ ２ 个 Ｄ 维的初始 解 ｘ１ ，ｘ２ ，…，ｘＮ／ ２ { } ，其中 ｘｉ ＝ ｘｉ１ ，ｘｉ２ ，…，ｘｉＤ { } ， ｉ ＝ １，２，…，Ｎ／ ２，并对初始解（蜜源）进行适应度评价。 随机产生初始解的公式为 ｘｉｊ ＝ Ｌ ＋ ｒａｎｄ（０，１） × （Ｕ － Ｌ） （１） 式中： ｘｉｊ 是第 ｉ 个更新蜜源的第 ｊ 个分量， ｉ ∈ １，２，…， Ｎ／ ２， ｊ ∈ １，２，…，Ｄ ； Ｌ 为解的下界， Ｕ 为解的上界。 ２）种群更新。 引领蜂随机选择相邻蜜源并与 其产生一个新的蜜源，比较二者蜜源质量，择优保 留；跟随蜂根据由引领蜂蜜源质量信息转化的概率 来选择是否对该蜜源进行邻域搜索并更新。 引领蜂 和跟随蜂的蜜源更新公式为 ｖｎｊ ＝ ｘｉｊ ＋ Ｒ × （ｘｉｊ － ｘｋｊ） （２） 式中： ｋ 为随机产生的正整数， ｋ ∈ １，２，…，Ｎ／ ２，且 ｉ ≠ｋ ； Ｒ 是一个随机数， Ｒ ∈ [ － １，１] ，它控制着邻 域搜索的范围。 ３）概率选择。 跟随蜂根据一定概率决定是否选择 对引领蜂蜜源进行邻域搜索，概率信息计算公式为 Ｐｉ ＝ Ｆｉ ∑ Ｎ／ ２ ｉ ＝ １ Ｆｉ （３） 式中： Ｐｉ 为第 ｉ 个蜜源转化后的概率， Ｆｉ 为第 ｉ 个蜜 源的适应度值。 蜜源的适应度值取决于蜜源质量， 以求取最小值为例，其适应度函数公式为 Ｆｉ ＝ １ １ ＋ ｆｉｔ ｉ ， ｆｉｔ ｉ ≥ ０ １ ＋ ｆｉｔ ｉ ， ｆｉｔ ｉ ＜ ０ ì î í ï ï ïï （４） 式中： ｆｉｔ ｉ 为第 ｉ 个解的函数值。 由式（４）可知，当解 的函数值为正数时，其值越小，蜜源的适应度越大， 跟随蜂选择该蜜源进行邻域搜索的概率越大，得到 较优蜜源的可能性也越大。 ４）种群淘汰。 如果某个解经过一定次数的更 新后，其解的质量仍未得到改善，一般认为该解陷入 局部最优，此时，引领蜂将转化为侦查蜂，由式（１） 重新产生一个新的解。 ２ 改进的人工蜂群算法 ２．１ 基于信息反馈的种群更新 在基本 ＡＢＣ 算法中，种群更新是通过随机选择 一个个体中的某个随机分量进行更新，主要包括选 择过程和更新过程。 选择过程包括种群个体的选择和个体分量的选 择，在基本算法中，二者皆采用随机选择策略，前者 的随机选择有利于保持种群个体的公平竞争，但后 者的随机选择却不利于个体的进化，原因在于即便 一个个体分量的更新对该个体产生了积极的影响， 在下一次迭代更新过程中，也不一定能够继续对该 分量进行深度搜索以获得更优个体，相反，对产生消 极影响的个体分量却在下次迭代中仍存在继续更新 的可能，这样不仅降低了算法收敛速度，而且不利于 提高解的精度。 针对这一问题，本文引入个体分量 记忆机制对个体信息进行反馈，使对个体进化产生 积极影响的个体分量得以充分搜索，改进后算法的 个体分量由随机选择变成根据前一次个体更新情况 的反馈信息选择。 具体做法是在前一次个体分量更 新后，采用个体分量记录器 ＣＨ 记录其蜜源质量是 否得到提高并进行反馈，如提高则 ＣＨ ＝ １，在下次迭 代时仍对该个体分量进行邻域搜索；否则 ＣＨ ＝ ０，随 机选择一个分量进行搜索。 更新过程主要取决于更新公式，基本 ＡＢＣ 算法 中的更新公式虽有效提高了算法的探索能力，但却降 低了算法的开发能力。 本文基于信息反馈的思想，参 考文献［１４］，采用最优个体引导机制对基本更新公式 进行改进，即将前一次迭代产生的最优个体信息反馈 到下一次迭代时个体分量的更新公式中，从而提高算 法的开发能力。 改进后的更新公式为 ｘｐｑ ＝ ｘｋｑ ＋ φ × （ｘ ｂｅｓｔ ｑ － ｘｋｑ） （５） 第 ２ 期 陈杰，等：基于信息反馈和改进适应度评价的人工蜂群算法 ·１７３·
·174. 智能系统学报 第11卷 式中：9∈[-1,1]，xm为新产生个体的第q个分 2.3基于最优引导的淘汰更新函数 量，x。为最优个体的第q个分量，x为需更新的 在种群淘汰过程中，当满足种群淘汰条件时，基 个体分量。 本算法通过式(1)重新产生新的个体，在种群进化 2.2基于对数的适应度函数 后期不仅容易引入不良个体，误导种群进化，而且对 在基本ABC算法中，概率选择过程是跟随蜂通 淘汰个体的完全否定，会导致种群多样性降低。为 过概率信息选择较优蜜源进行深度搜索来推动整个 解决这一问题，本文在满足种群淘汰条件时，采用淘 种群进化，概率信息反映了蜜源质量（适应度值）的 汰蜜源与最优蜜源交叉引导产生新个体，这样不仅 好坏程度，因此，这一信息的获取在该过程中尤为重 可以避免不良个体的引人，防止对种群进化产生误 要。基本算法中的概率信息通过式(3)和(4)计算 导，而且有利于保持种群多样性，其交叉公式为 而来，但对于式(4)而言，当同时存在适应度值无限 m=x ( (9) 接近于零但并不相同时，所有适应度值都将趋于1， 式中：p∈[-1,1]，xm为新产生个体的第q个分 此时，选择概率也将相同，如式(6)所示。 量，x。为最优个体的第g个分量，xm为需淘汰的 ,=1×100么F,≈16P,=0.33 个体分量。 ,=1×100无F,≈16P,=0.33 改进后算法的流程图如图1所示。 (开始 6,=1×10-m6F,=16P,=0.33 种群初始化，CH0,imit=0 (6) 引领蜂随机选择更新个体 式中：3和f分别为式(3)和(4)，由式(6)可知，尽 管ft1、fit2和ft所表示种群个体解的精度差异较 CH=0 大，但种群个体被选择的概率却相同，此时，将无法 区分不同蜜源的蜜源质量好坏，跟随蜂更新的概率 随机选择个体分量选择上次更新分量 选择作用消失，极易导致种群陷入局部最优，出现停 滞不前现象。 引领蜂更新并计算适应度值 针对这一问题，本文采用基于对数的适应度函 数进行改进，通过对数效应增大不同个体适应度值 差异，进而区分不同个体被选择的概率，使得优秀个 Y 达到适应度精度> 体更易被选择更新，而不良个体被选择的概率降低。 具体做法是在最优个体适应度值达到一定精度后， 式(4适应评价 式(7)适应度评价 采用改进的适应度函数对所有个体的解重新评价， 改进后的适应度函数公式为 按式③)转化为概率信息 0.1 F:= 0≤fit.≤10a(7) 1 雇佣蜂根据概率信息选择 0.1+ 更新并计算适应度值 limit=0 Ig fit, 1 式中：α的值取决于计算机对解的识别精度，本文取 按式(9产生蜜源 N 4~8。用式(7)将t、fit2和fit转化为概率信息， <蜜源质量提高 如式(8)所示： CH=1,limit=0 CH=0,limit =limit +1 ,=1×100hF,≈0.676P,≈0.27 ,=1×1005F,≈0.836P,=0.35 <imit<LIM 6t,=1×101mhF,≈0.916P,≈0.38 Y L 达到最大迭代次数> (8) Y 式中：和f,分别为式(3)和式(7)，改进后的适应 (结束 度函数使解的差异性增大，进而影响概率信息，促进 图1改进后算法流程图 概率选择作用。 Fig.1 The flow diagram of improved algorithm
式中： φ ∈ ［ － １，１］ ， ｘｐｑ 为新产生个体的第 ｑ 个分 量， ｘ ｂｅｓｔ ｑ 为最优个体的第 ｑ 个分量， ｘｋｑ 为需更新的 个体分量。 ２．２ 基于对数的适应度函数 在基本 ＡＢＣ 算法中，概率选择过程是跟随蜂通 过概率信息选择较优蜜源进行深度搜索来推动整个 种群进化，概率信息反映了蜜源质量（适应度值）的 好坏程度，因此，这一信息的获取在该过程中尤为重 要。 基本算法中的概率信息通过式（３）和（４）计算 而来，但对于式（４）而言，当同时存在适应度值无限 接近于零但并不相同时，所有适应度值都将趋于 １， 此时，选择概率也将相同，如式（６）所示。 ｆｉｔ １ ＝ １ × １０ －２０ ｆ４→ Ｆ１ ≈ １ ｆ３→ Ｐ１ ＝ ０．３３ ｆｉｔ ２ ＝ １ × １０ －５０ ｆ４→ Ｆ２ ≈ １ ｆ３→ Ｐ２ ＝ ０．３３ ｆｉｔ ３ ＝ １ × １０ －１００ ｆ４→ Ｆ３ ≈ １ ｆ３→ Ｐ３ ＝ ０．３３ ì î í ï ï ï ï ï ï （６） 式中： ｆ ３ 和 ｆ ４ 分别为式（３）和（４），由式（６）可知，尽 管 ｆｉｔ １ 、 ｆｉｔ ２ 和 ｆｉｔ ３ 所表示种群个体解的精度差异较 大，但种群个体被选择的概率却相同，此时，将无法 区分不同蜜源的蜜源质量好坏，跟随蜂更新的概率 选择作用消失，极易导致种群陷入局部最优，出现停 滞不前现象。 针对这一问题，本文采用基于对数的适应度函 数进行改进，通过对数效应增大不同个体适应度值 差异，进而区分不同个体被选择的概率，使得优秀个 体更易被选择更新，而不良个体被选择的概率降低。 具体做法是在最优个体适应度值达到一定精度后， 采用改进的适应度函数对所有个体的解重新评价， 改进后的适应度函数公式为 Ｆｉ ＝ ０．１ ０．１ ＋ １ ｌｇ ｆｉｔ ｉ ， ０ ≤ ｆｉｔ ｉ ≤ １０ －α （７） 式中： α 的值取决于计算机对解的识别精度，本文取 ４ ～ ８。 用式（７）将 ｆｉｔ １ 、 ｆｉｔ ２ 和 ｆｉｔ ３ 转化为概率信息， 如式（８）所示： ｆｉｔ １ ＝ １ × １０ －２０ ｆ７→ Ｆ１ ≈ ０．６７ ｆ３→ Ｐ１ ≈ ０．２７ ｆｉｔ ２ ＝ １ × １０ －５０ ｆ７→ Ｆ２ ≈ ０．８３ ｆ３→ Ｐ２ ≈ ０．３５ ｆｉｔ ３ ＝ １ × １０ －１００ ｆ７→ Ｆ３ ≈ ０．９１ ｆ３→ Ｐ３ ≈ ０．３８ ì î í ï ï ï ï ï ï （８） 式中： ｆ ３ 和 ｆ ７ 分别为式（３）和式（７），改进后的适应 度函数使解的差异性增大，进而影响概率信息，促进 概率选择作用。 ２．３ 基于最优引导的淘汰更新函数 在种群淘汰过程中，当满足种群淘汰条件时，基 本算法通过式（１）重新产生新的个体，在种群进化 后期不仅容易引入不良个体，误导种群进化，而且对 淘汰个体的完全否定，会导致种群多样性降低。 为 解决这一问题，本文在满足种群淘汰条件时，采用淘 汰蜜源与最优蜜源交叉引导产生新个体，这样不仅 可以避免不良个体的引入，防止对种群进化产生误 导，而且有利于保持种群多样性，其交叉公式为 ｘｎｍ ＝ ｘ ｂｅｓｔ ｍ ＋ φ × （ｘ ｂｅｓｔ ｍ － ｘｌｍ ） （９） 式中： φ ∈ ［ － １，１］ ， ｘｎｍ 为新产生个体的第 ｑ 个分 量， ｘ ｂｅｓｔ ｑ 为最优个体的第 ｑ 个分量， ｘｌｍ 为需淘汰的 个体分量。 改进后算法的流程图如图 １ 所示。 图 １ 改进后算法流程图 Ｆｉｇ．１ Ｔｈｅ ｆｌｏｗ ｄｉａｇｒａｍ ｏｆ ｉｍｐｒｏｖｅｄ ａｌｇｏｒｉｔｈｍ ·１７４· 智 能 系 统 学 报 第 １１ 卷
第2期 陈杰，等：基于信息反馈和改进适应度评价的人工蜂群算法 ·175. 3 仿真结果与分析 参数N=50,LIM=D×N/2,测试函数维数为50和 为验证本文所改进的ABC算法(memorial and 100,50维的最大迭代次数为5×10，a=8,100维 modified ABC,MMABC)的性能，对l0种基本函数 的最大迭代次数为1×10，a=4。将测试函数分别 进行测试。表1列出了10种基本测试函数的名称、 采用这2种算法在MATLAB上独立运行30次，表2 公式、搜索范围和理论最优值。 为测试结果，其中Best表示最好值，Mean表示平均 将MMABC与基本ABC进行比较，其中，设置 值，Worst表示最差值，Std表示标准差。 表1标准测试函数 Table 1 Standard test functions Function 函数 公式 搜索范围最优值 万 Sphere na)=x [-100,100] 0 i-1 5 Schwefel2.22 x)=1x+1 [-10,10] 0 -1 万 Schwefel2.21 f（x)=max.lxl [-100,100] 0 f Rosenbrock =管m--月 [-30,30] 0 天 Step x)=立(L+05)2 [-100,100] 0 f后 Quartic )）=,+anbm(0,) [-1.28,1.28]0 方 Schwefel2.26 fx)=- 网 [-500,500]-418.98n Rastrigin fx)= ∑【x2-10eos(2m,)+10] [-5.12,5.12]0 Ackley f(x) =-20exp(-0.2J ~ep(∑cos(2mx)/m)+20 0 fio Griewank [-600,600]0 10 g 10 10 10 遮10 匹10 210 10 10 --MMABC MMABC ------ABC 10 ABC 10 10 0 2 4 代次数 100 6 810 迭代次数 (a)Schwefel2.21 (b)Step 10 MMABC 10° --ABC 10 把10 MMABC 10 ·ABC 10 ×10 10 ×10 0 1015 02530 迭代次数 迭代次数 (c)Quartic (d)Griewank 图2 MMABC和ABC对部分测试函数收敛曲线 Fig.2 Some convergence curves of testing functions between MMABC and ABC
３ 仿真结果与分析 为验证本文所改进的 ＡＢＣ 算法（ｍｅｍｏｒｉａｌ ａｎｄ ｍｏｄｉｆｉｅｄ ＡＢＣ， ＭＭＡＢＣ） 的性能，对 １０ 种基本函数 进行测试。 表 １ 列出了 １０ 种基本测试函数的名称、 公式、搜索范围和理论最优值。 将 ＭＭＡＢＣ 与基本 ＡＢＣ 进行比较，其中，设置 参数 Ｎ ＝ ５０，ＬＩＭ＝ Ｄ × Ｎ／ ２， 测试函数维数为 ５０ 和 １００，５０ 维的最大迭代次数为 ５ × １０ ４ ， α ＝ ８，１００ 维 的最大迭代次数为 １ × １０ ５ ， α ＝ ４。 将测试函数分别 采用这 ２ 种算法在 ＭＡＴＬＡＢ 上独立运行 ３０ 次，表 ２ 为测试结果，其中 Ｂｅｓｔ 表示最好值，Ｍｅａｎ 表示平均 值，Ｗｏｒｓｔ 表示最差值，Ｓｔｄ 表示标准差。 表 １ 标准测试函数 Ｔａｂｌｅ １ Ｓｔａｎｄａｒｄ ｔｅｓｔ ｆｕｎｃｔｉｏｎｓ Ｆｕｎｃｔｉｏｎ 函数 公式 搜索范围 最优值 ｆ １ Ｓｐｈｅｒｅ ｆ（ｘ） ＝ ∑ ｎ ｉ ＝ １ ｘｉ ２ ［－１００，１００］ ０ ｆ ２ Ｓｃｈｗｅｆｅｌ２．２２ ｆ（ｘ） ＝ ∑ ｎ ｉ ＝ １ ｘｉ ＋ ∏ ｎ ｉ ＝ １ ｘｉ ［－１０，１０］ ０ ｆ ３ Ｓｃｈｗｅｆｅｌ２．２１ ｆ（ｘ） ＝ ｍａｘ ｎ ｉ ＝ １ ｘｉ ［－１００，１００］ ０ ｆ ４ Ｒｏｓｅｎｂｒｏｃｋ ｆ（ｘ） ＝ ∑ ｎ－１ ｉ ＝ １ １００ （ｘｉ＋１ － ｘｉ ２ ） ２ ＋ （１ － ｘｉ） ２ [ ] ［－３０，３０］ ０ ｆ ５ Ｓｔｅｐ ｆ（ｘ） ＝ ∑ ｎ ｉ ＝ １ （⌊ｘｉ ＋ ０．５」） ２ ［－１００，１００］ ０ ｆ ６ Ｑｕａｒｔｉｃ ｆ（ｘ） ＝ ∑ ｎ ｉ ＝ １ ｉｘｉ ４ ＋ ｒａｎｄｏｍ［０，１） ［－１．２８，１．２８］ ０ ｆ ７ Ｓｃｈｗｅｆｅｌ２．２６ ｆ（ｘ） ＝ － ∑ ｎ ｉ ＝ １ （ｘｉ ｓｉｎ ｘｉ ） ［－５００，５００］－４１８．９８ ｎ ｆ ８ Ｒａｓｔｒｉｇｉｎ ｆ（ｘ） ＝ ∑ ｎ ｉ ＝ １ ｘｉ ２ － １０ｃｏｓ（２πｘ [ ｉ） ＋ １０] ［－５．１２，５．１２］ ０ ｆ ９ Ａｃｋｌｅｙ ｆ（ｘ） ＝ － ２０ｅｘｐ（ － ０．２ ∑ ｎ ｉ ＝ １ ｘｉ ２ ／ ｎ ） － ｅｘｐ（∑ ｎ ｉ ＝ １ ｃｏｓ（２πｘｉ） ／ ｎ） ＋ ２０ ＋ ｅ ［－３２，３２］ ０ ｆ １０ Ｇｒｉｅｗａｎｋ ｆ（ｘ） ＝ １ ４ ０００∑ ｎ ｉ ＝ １ ｘｉ ２ － ∏ ｎ ｉ ＝ １ ｃｏｓ（ ｘｉ ｉ ） ＋ １ ［－６００，６００］ ０ 图 ２ ＭＭＡＢＣ 和 ＡＢＣ 对部分测试函数收敛曲线 Ｆｉｇ．２ Ｓｏｍｅ ｃｏｎｖｅｒｇｅｎｃｅ ｃｕｒｖｅｓ ｏｆ ｔｅｓｔｉｎｇ ｆｕｎｃｔｉｏｎｓ ｂｅｔｗｅｅｎ ＭＭＡＢＣ ａｎｄ ＡＢＣ 第 ２ 期 陈杰，等：基于信息反馈和改进适应度评价的人工蜂群算法 ·１７５·
·176 智能系统学报 第11卷 表2 MMABC和基本ABC算法的测试结果比较 Table 2 The test results compared between MMABC and ABC Function Dimensions Algorithm Best Worst Mean Std ABC 8.91×10~16 1.13×105 9.62×1016 8.52×107 50 MMABC 0 0 0 ABC 2.09×10-5 2.55×105 2.33×105 1.68×106 100 MMABC 0 0 0 0 ABC 2.28×105 2.52×1015 2.42×105 1.01×10n 50 MMABC 7.95×10255 9.85×10-2 2.12×102 7.95×1025 ABC 4.99×1015 5.42×105 5.19×105 1.37×10~16 100 MMABC 8.59×10254 6.57×10-252 1.64×1022 2.51×1028 ABC 2.85×102 1.39×10- 6.58×10-2 4.12×10-2 50 MMABC 1.35×106 2.22×10~5 8.89×106 7.32×106 ABC 1.14×10 1.33×101 1.21×10 6.64×101 100 MMABC 1.46×107 5.42×10- 2.46×10 1.49×107 ABC 1.71×103 9.23×102 6.31×10-3 3.48×102 50 MMABC 3.01×10 1.88×102 2.57×103 7.84×103 ABC 7.82×10 2.77×10 100 9.94×102 1.02×10 MMABC 9.28×10- 1.16×10 1.13×102 3.23×103 ABC 0 0 0 0 50 MMABC 0 0 0 0 ABC 0 0 0 0 100 MMABC 0 0 0 0 ABC 7.61×102 9.22×102 9.89×102 8.5×103 50 MMABC 2.91×102 3.93×102 3.56×102 3.72×103 ABC 2.61×10- 3.67×101 3.26×10- 3.61×10-2 100 MMABC 1.12×10 1.43×10 1.31×101 1.05×102 ABC -2.09475×101 -2.07116×10 -2.08197×10 7.57×101 50 MMABC -2.09491×104 -2.09491×101 -2.09491×10 3.98×102 ABC -4.18979×10 -4.16614×104 -4.17995×104 8.46×10 100 MMABC -4.18983×104 -4.18983×104 -4.18983×104 2.64×103 ABC 0 5.68×10-14 4.55×10-4 2.27×104 50 MMABC 0 0 0 0 ABC 1.14×1013 2.27×10-5 1.18×10B 5.57×104 100 MMABC 0 0 0 0 ABC 1.04×103 1.47×103 1.35×1013 1.59×104 50 MMABC 1.63×10~16 4.44×1016 3.25×1016 2.35×107 ABC 1.46×101B 1.61×10B 1.55×10s 5.32×105s 100 MMABC 2.33×1016 8.87×10~16 5.78×10~6 1.42×10~7 ABC 1.11×10~6 5.54×10-16 1.99×10-16 1.78×1016 50 MMABC 0 0 0 0 ABC 1.44×1015 100 1.56×10~15 3.27×10~14 6.14×10~14 MMABC 0 0 0 由表2可以看出，无论测试函数是50维，还是 1O0维，MMABC算法在解的收敛精度上与基本ABC
表 ２ ＭＭＡＢＣ 和基本 ＡＢＣ 算法的测试结果比较 Ｔａｂｌｅ ２ Ｔｈｅ ｔｅｓｔ ｒｅｓｕｌｔｓ ｃｏｍｐａｒｅｄ ｂｅｔｗｅｅｎ ＭＭＡＢＣ ａｎｄ ＡＢＣ Ｆｕｎｃｔｉｏｎ Ｄｉｍｅｎｓｉｏｎｓ Ａｌｇｏｒｉｔｈｍ Ｂｅｓｔ Ｗｏｒｓｔ Ｍｅａｎ Ｓｔｄ ｆ １ ５０ １００ ＡＢＣ ＭＭＡＢＣ ＡＢＣ ＭＭＡＢＣ ８．９１×１０ －１６ ０ ２．０９×１０ －１５ ０ １．１３×１０ －１５ ０ ２．５５×１０ －１５ ０ ９．６２×１０ －１６ ０ ２．３３×１０ －１５ ０ ８．５２×１０ －１７ ０ １．６８×１０ －１６ ０ ｆ ２ ５０ １００ ＡＢＣ ＭＭＡＢＣ ＡＢＣ ＭＭＡＢＣ ２．２８×１０ －１５ ７．９５×１０ －２５５ ４．９９×１０ －１５ ８．５９×１０ －２５４ ２．５２×１０ －１５ ９．８５×１０ －２５３ ５．４２×１０ －１５ ６．５７×１０ －２５２ ２．４２×１０ －１５ ２．１２×１０ －２５３ ５．１９×１０ －１５ １．６４×１０ －２５２ １．０１×１０ －１７ ７．９５×１０ －２５５ １．３７×１０ －１６ ２．５１×１０ －２５３ ｆ ３ ５０ １００ ＡＢＣ ＭＭＡＢＣ ＡＢＣ ＭＭＡＢＣ ２．８５×１０ －２ １．３５×１０ －１６ １．１４×１０ １ １．４６×１０ －７ １．３９×１０ －１ ２．２２×１０ －１５ １．３３×１０ １ ５．４２×１０ －７ ６．５８×１０ －２ ８．８９×１０ －１６ １．２１×１０ １ ２．４６×１０ －７ ４．１２×１０ －２ ７．３２×１０ －１６ ６．６４×１０ －１ １．４９×１０ －７ ｆ ４ ５０ １００ ＡＢＣ ＭＭＡＢＣ ＡＢＣ ＭＭＡＢＣ １．７１×１０ －３ ３．０１×１０ －４ ７．８２×１０ －２ ９．２８×１０ －３ ９．２３×１０ －２ １．８８×１０ －２ ２．７７×１０ －１ １．１６×１０ －２ ６．３１×１０ －３ ２．５７×１０ －３ ９．９４×１０ －２ １．１３×１０ －２ ３．４８×１０ －２ ７．８４×１０ －３ １．０２×１０ －１ ３．２３×１０ －３ ｆ ５ ５０ １００ ＡＢＣ ＭＭＡＢＣ ＡＢＣ ＭＭＡＢＣ ０ ０ ０ ０ ０ ０ ０ ０ ０ ０ ０ ０ ０ ０ ０ ０ ｆ ６ ５０ １００ ＡＢＣ ＭＭＡＢＣ ＡＢＣ ＭＭＡＢＣ ７．６１×１０ －２ ２．９１×１０ －２ ２．６１×１０ －１ １．１２×１０ －１ ９．２２×１０ －２ ３．９３×１０ －２ ３．６７×１０ －１ １．４３×１０ －１ ９．８９×１０ －２ ３．５６×１０ －２ ３．２６×１０ －１ １．３１×１０ －１ ８．５×１０ －３ ３．７２×１０ －３ ３．６１×１０ －２ １．０５×１０ －２ ｆ ７ ５０ １００ ＡＢＣ ＭＭＡＢＣ ＡＢＣ ＭＭＡＢＣ －２．０９４ ７５×１０ ４ －２．０９４ ９１×１０ ４ －４．１８９ ７９×１０ ４ －４．１８９ ８３×１０ ４ －２．０７１ １６×１０ ４ －２．０９４ ９１×１０ ４ －４．１６６ １４×１０ ４ －４．１８９ ８３×１０ ４ －２．０８１ ９７×１０ ４ －２．０９４ ９１×１０ ４ －４．１７９ ９５×１０ ４ －４．１８９ ８３×１０ ４ ７．５７×１０ １ ３．９８×１０ －１２ ８．４６×１０ １ ２．６４×１０ －３ ｆ ８ ５０ １００ ＡＢＣ ＭＭＡＢＣ ＡＢＣ ＭＭＡＢＣ ０ ０ １．１４×１０ －１３ ０ ５．６８×１０ －１４ ０ ２．２７×１０ －１３ ０ ４．５５×１０ －１４ ０ １．１８×１０ －１３ ０ ２．２７×１０ －１４ ０ ５．５７×１０ －１４ ０ ｆ ９ ５０ １００ ＡＢＣ ＭＭＡＢＣ ＡＢＣ ＭＭＡＢＣ １．０４×１０ －１３ １．６３×１０ －１６ １．４６×１０ －１３ ２．３３×１０ －１６ １．４７×１０ －１３ ４．４４×１０ －１６ １．６１×１０ －１３ ８．８７×１０ －１６ １．３５×１０ －１３ ３．２５×１０ －１６ １．５５×１０ －１３ ５．７８×１０ －１６ １．５９×１０ －１４ ２．３５×１０ －１７ ５．３２×１０ －１５ １．４２×１０ －１７ ｆ １０ ５０ １００ ＡＢＣ ＭＭＡＢＣ ＡＢＣ ＭＭＡＢＣ １．１１×１０ －１６ ０ １．４４×１０ －１５ ０ ５．５４×１０ －１６ ０ １．５６×１０ －１３ ０ １．９９×１０ －１６ ０ ３．２７×１０ －１４ ０ １．７８×１０ －１６ ０ ６．１４×１０ －１４ ０ 由表 ２ 可以看出，无论测试函数是 ５０ 维，还是 １００ 维，ＭＭＡＢＣ 算法在解的收敛精度上与基本 ＡＢＣ ·１７６· 智 能 系 统 学 报 第 １１ 卷