资源描述：
《人工蜂群算法及其在组合优化中的应用研究.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第31卷第6期太原科技大学学报Vo.l31No.62010年12月JOURNALOFTAIYUANUNIVERSITYOFSCIENCEANDTECHNOLOGYDec.2010文章编号:1673-2057(2010)06-0467-05人工蜂群算法及其在组合优化中的应用研究郑伟,刘静,曾建潮(太原科技大学复杂系统与计算智能实验室,太原030024)摘要:人工蜂群算法是一种启发式算法,通过模拟自然界蜂群觅食过程来解决现实中的优化问题。算法中将每只蜜蜂看做一个智能体,若干智能体间相互合作,高效地完成对目标的搜索、优化。总结人工蜂群算
2、法用于解决组合优化问题的一般方法,以01背包问题为例对算法进行仿真测试,实验结果表明:人工蜂群算法有效且优于存在的蚁群算法。关键词:人工蜂群算法;组合优化;背包问题中图分类号:TP391.9文献标志码:A蜂群算法(BeeColonyAlgorthm)是以自然界中组合优化中应用,具有重要意义。蜂群的自组织模型和群体智能为基础的一种仿生本文总结人工蜂群算法解决组合优化问题的算法。D.Karaboga在2005年成功地将蜂群算法应框架,并解决背包问题。[1]用到函数的数值优化问题上,并提出比较系统的1人工蜂群算法基本原理简介ABC算法
3、(ArtificialBeeColonyAlgorithm),算法简单,鲁棒性强,在无约束性数值优化问题上比其他初始化时,随机生成Ns个可行解并计算函数启发式算法更具优越性。2006年,D.Karaboga和值,将函数值从优到劣排名,前50%作为蜜源位置B.Basturk又将ABC应用到约束性数值优化问题即引领蜂,后50%为跟随蜂。随机产生可行解的公[2]上,并取得良好的效果。式如式(1):组合优化方面,2006年,ChinSoonChong等人jjjjxi=xmin+rand(0,1)(xmax-xmin)(1)[3]利用蜂群算法成功解决车间
4、调度问题;2008年,式中,j{1,2,...,Q}为Q维解向量的某个分量。[4]他们又成功解决了旅行商问题。2008年,Alok蜜蜂记录自己到目前为止的最优值,并在当前Singh利用人工蜂群算法在一个给出的无向带权图蜜源附近展开临域搜索,产生一个新位置替代前一[5]中成功找出具有叶子约束的最小生成树。在国位置的公式为:内,丁海军、李峰磊成功将人工蜂群算法应用到解vij=xij-ij(xij-xkj)(2)[6]决TSP问题上,并且提出了参数的改进,取得很式中,j{1,2,...,Q},k(1,2,...,sn),k为随好的效果。2
5、009年,胡中华、赵敏实现了将ABC算机生成且ki,ij为[-1,1]之间的随机数。[7]法应用于路径规划问题中。2009年,李瑞明利用ABC算法中,跟随蜂选择引领蜂的概率公式为:人工蜂群算法对工件尺寸有差异的单机批调度问fiti题进行成功优化[8]。Pi=sn(3)!fitn现实生活中有许多重要的实际应用和理论研n=1究问题,都具有组合性质,且很多都已被证明是NP式中fiti为第i个解的适应值,对应食物源的丰富程难问题,如:TSP问题、背包问题、图着色问题、车间度。食物源越丰富,被跟随蜂选择的概率越大。为防作业调度问题等。因此研究人工蜂群
6、算法及其在止算法陷入局部最优,算法limit次迭代没有改进,收稿日期:20091202作者简介:郑伟(1982-),男,硕士研究生,主要研究方向为智能仿真。468太原科技大学学报2010年放弃该解,由侦察蜂产生一个新的位置代替。种∀记忆#功能,记住访问过的食物源,即禁忌序列,ABC算法的流程为:每次要对食物源进行访问前,先到禁忌序列中查看步骤1初始化;是否曾访问过,如果已访问过,则转向下一食物源,步骤2侦察蜂随机搜索食物源;否则对其进行访问,这个过程就是禁忌搜索(Tabu步骤3计算转移概率并进行角色转换
7、;Seach,TS)。步骤4跟随蜂依据概率对食物源进行搜索;2.4转移概率步骤5若不满足终止条件,则转步骤2.人工蜂群算法解决组合优化问题中的转移概[4]率一般形式如下:2人工蜂群算法解决组合优化问题的框架∀ij!ij,j,sallow∀组合优化(CombinatorialOptimization)问题的目kpij=!is!is(4)salow标是从由离散变量组成的可行解集中求出最优解。0,otherwise蜂群算法可以用来解决组合优化问题,方法如下。k式中:pij表示第k只蜜蜂由状态i到状态j的概率;ij2.1初始化
8、解空间为从状态i到j的启发信息;为控制启发信息重要组合优化(CombinatorialOptimization)问题的目性的参数;!ij表示状态i转移
