人工蜂群算法

甘肃农业大学

硕（博）士研究生论文开题报告

所在院系 信 息 科 学 技 术 学 院 学科专业 农 业 信 息 化 学位级别 专 业 硕 士 学生姓名 莫 敏 敏 入学时间 2014 年 9 月 导师姓名 刘 成 忠 课题名称 人工蜂群算法改进及其应用研究

甘肃农业大学研究生处制

二〇一五年六月

一、立论依据

1.1课题的现状及研究意义 古往今来,优化问题充斥在人类的生活和工作当中,优化算法的利用可以有效的解决这些问题,从而提高工作效率,减小资源浪费。随着人类社会不断向前发展,优化问题变得越来越复杂化、多样化,随之而来的是各种优化算法的产生和发展。 近几百年来,人类社会发生了翻天覆地的变化,科学技术得到了史无前例的巨大发展。20 世纪 30 到 40 年代期间,爆发出了很多古典优化方法不能解决的问题,随之而来地提出了一系列新的解决方法。诸如动态规划和非线性规划,能够有效地解决当时科学、技术和生活中的难题。 二次世界大战过后,到现如今,人类社会取得了巨大的进步。又依次经历了电器时代、信息社会,再到现如今的大数据、智能传感时代,所遇到的问题更加的复杂、多样、大型,所要处理的数据量、要求的精度、以及时间成本等,都不可同日而语。而传统优化算法,求解条件十分苛刻,对大型问题早已为力,在求解速度、精度等方面,也远远不能满足现实要求。大自然是人类的导师。人们惊奇的发现,自然界中,某些群居生物,如蚂蚁、蜜蜂者,个体虽然简单渺小,但当它们有机地组合在一起,分工合作时,可以完成十分复杂的任务。这不禁引起人类感叹和深思科学家们受到这些群居生物集体性行为的启发,提出了一系列的智能优化算法,给现代复杂多样的大型问题的解答,带来了福音。 20 世纪 60 年代,J.Holland 教授提出了遗传算法,并将该算法成功地应用到复杂函数优化等领域。随后又有学者提出了一系列类似于遗传算法的进化算法,例如进化策略等。 20 世纪 80 年代,Metropolis 等受物质退火过程的启示,提出了模拟退火算法, 1983 年,Krikpatrick 等将该算法推广到了组合优化的应用。 20 世纪 90 年代,Dorigo 等受蚂蚁觅食行为的启发,提出了蚁群算法,并将该算法应用到了旅行商问题(TSP)等组合优化问题中,且取得了优良的效果。1995 年,Kennedy 等模拟鸟群的飞行觅食行为提出了粒子群算法,在求解复杂函数优化问题时有很好的效果。2005 年,Karaboga 博士根据蜜蜂的采蜜行为,提出了人工蜂群(Artificial Bee ColonyAlgorithm,ABC)算法。之后,他又和 Basturk 一起,将 ABC 算法应用于函数优化领域,并和已有的随机智能搜索算法进行了比较。实验证明,ABC 算法在优化高维函数时,较传统优化算法有较大的优势。尔后,Karaboga 博士又将 ABC 算法应用到了解约束问题上,再次取得了十分理想的效果。随着越来越多的仿生算法的提出,逐渐形成了计算智能领域的一个新的分支——群智能算法。这些算法克服了传统优化算法的弊端,只涉及最基本的数算,没有苛刻的数学要求,极易实1

现。且这些算法有很好的并行性和正反馈特性,能够分布式、自组织地工作,鲁棒性高,不需要集中控制,不需提供全局信息;能有效解答复杂分布式问题,十分吻合实际需求。因此这些群智能优化算法被大量的运用在各工业、信息领域,如国防、通信、交通、图像处理、形状匹配、智能控制、数据挖掘、移动互联、信息安全、路由算法等邻域。 人工蜂群算法是一种新型的元启发式搜索算法，其实现机理是通过模拟蜂群采蜜过程中体现出的智能行为来实现对问题的求解。由于人工蜂群算法具有简单、灵活、鲁棒性等特点，因此它在数值函数优化、整数规划、组合优化、多目标优化、人工神经网络训练和图像处理等领域有着广泛应用并取得了较好的研究成果。然而，人工蜂群算法作为一种新型算法，其算法模型尚不成熟，在求解NP-Hard的离散域优化问题上的研究尚处于初步阶段。因此，完善人工蜂群算法的理论研究，并探索其在NP-Hard的离散域优化问题上的应用，具有重要的研究价值和现实意义。 人工蜂群算法的特点： (1) 多角色分工机制。蜜蜂按照自己角色采用不同的方法搜索，并根据所得解的质量自发的调整角色，以适应下一次搜索过程。 (2) 协同工作机制。蜜蜂在选择路径时，依据角色决定是否选用以前蜜蜂留下的信息和利用信息的方式，能以较大概率找到优化问题的最优解。 (3)鲁棒性。使用概率规则而不是确定性规则指导搜索，不必知道其他先验的信息有极好的鲁棒性和广泛的适用性。 (4)易于与其他启发式算法结合。 (5)人工蜂群算法具有群智能算法普遍存在的缺点，易陷入局部最优，收敛速度慢；当求解较高维函数优化问题时，求解精度不高等。 针对以上这些不足之处可已经看出猫群算法还有很大的改良空间，通过对算法框架、迭代进化方式的改进，将其他优化算法的思想引入到人工蜂群算法，可以提高算法的优化性能；在较小种群规模和较少迭代次数条件下，在并行猫群算法的追踪过程中引入田口方法，可以提高算法的优化精度高、加快计算速度。因此，对ABC算法的改进是提高算法有良性的关键。 1.2人工蜂群基本流程 (1) 初始时刻,蜜蜂总数的一半被指派为引领蜂,在解空间内,随机搜寻花蜜源;另一半则被指派为观察蜂,在蜂巢等待; (2) 引领蜂找到花蜜源后,返回蜂巢,将信息分享给观察蜂; (3) 观察蜂以一定概率选择引领蜂,并去该引领蜂对应的花蜜源邻近寻蜜; 2

(4) 评价所有蜜蜂找到的花蜜源的收益率,在花蜜源之间进行选择,保存较好的花蜜 源,重新指派引领蜂和观察蜂; (5) 判断是否有花蜜源需要放弃,如果有,则该处引领蜂转变成侦查蜂,在蜂巢附近 随机搜索花蜜源,找到花蜜源后,又回到蜂巢招募蜜蜂;否则跳到第 6 步; (6) 记录当前最好的花蜜源; (7) 重复 2-6 步,直至满足某一特定条件; (8) 结束,输出最好的花蜜源的位置。 1.3人工蜂群应用领域 国防、通信、交通、图像处理、形状匹配、智能控制、数据挖掘、移动互联、信息安全、路由算法等邻域。 主要的参考文献 [1] Alam M.S,Kabir M.W,Islam M.M.Self-adaptation of Mutation Step Size in ArtificialBee Colony Algorithm for Continuous Function Optimzation[C].2010 13th internationalConference on computer and Information Technology,2010:69-74 [2] Zhong Y.W,Lin J, Ning J.Hybrid Artificial Bee Colony Algorithm with ChemotaxisBehavior of Bacterial Foraging Optimization Algorithm[C] . Seventh InternationalConference on Natural Computation,2011,2:1171-1171 [3] Karaboga D., Basturk B..Artificial Bee Colony (ABC) Optimization Algorithm forSolving Constrained Optimization Problems [J].LNCS:Advances in Soft Computing: Foundations of Fuzzy Logic and Soft Computing,2007,45(29):7-798 [4] Karaboga D., Akay B..A Comparative Study of Artificial Bee Colony Algorithm [J].Applied Mathematics and Computation,2009,214(1):108-132 [5] 王兴伟,邹荣珠,黄敏.一种基于蜂群算法的 ABC 支持型 QOS 组播路由机制[J].计算机科学,2009,36(6):47-52 [6] R. Srinivasa Rao, S.V.L. Narasimham, M. Ramalingaraju. Optimization of Distribution Network Configuration for Loss Reduction Using Artificial Bee Colony Algorithm [J]. International Journal of Electrical Power and Energy Systems Engineering (IJEPESE) 2008, 1(2), www.waset.org/journals/waset/v45/v45-119.pd [7] 杨进,马良.蜂群算法在带时间窗的车辆路径问题中的应用 [J].计算机应用研究2009:26(11):4048-4050 [8] Karaboga D,Akay B.Artificial Bee Colony Algorithm on Training Artificial NeuralNetworks [A]. Signal Processing and Communications Applications [C]. 3

2007:1-4Report-TR06[R]. Erciyes University, Engineering Faculty, Computer EngineeringDepartment,2005 [9] 肖永豪.蜂群算法及在图像处理中的应用研究[D].广州:华南理工大学,2011 [10] 吴斌,史忠植。一种基于蚁群算法的 TSP 问题分段求解算法哪.计算机学报,2001, 24(12):78-81 [11] 银建霞.人工蜂群算法的研究及其应用[D].西安:西安电子科技大学,2012 [12] 王志刚.基于粒子群和人工蜂群算法的混合优化算法[J].科学技术与工程,2012, 12(20):1671-1815 [13] 马牧.基于蜂群算法的遗传算法研究及其在地形匹配中的应用[D].西安:西安电子科技大学,2010 [14] 罗钧,李妍.具有混沌搜索策略的蜂群优化算法[J].控制与决策,2010,25(12):

二、研究方案

2.1研究目标 （1）理解和掌握人工蜂群算法的基本原理，研究算法的优势和缺陷； （2）结合各种算法的优缺点，对人工蜂群算法进行改进； （3）将改进后的蜂群算法应用到组合优化问题中去； （4）将改进后的算法应用到电子商务模型建立与求解中； 2.2研究内容 由于人工蜂群算法的研究刚刚起步，一些思想处于萌芽阶段，严格的理论尚不成熟。针对对人工蜂群算法的改进技术主要集中于常态的增加参数、加入部分操作算子等方面；对于算法框架、迭代进化方式等的改进的研究较少；人工蜂群算法本身的思想、原理、参数设置以及种群多样性研究，仍停留在实验探索阶段，并未有更深入的分析与讨论；算法收敛性分析与证明研究还未出现这些问题，本课题的主要研究内容有： 1.了解蜂的生物学基础，两种重要的工作模式，人工蜂群算法的基本原理与数学描述包括搜寻模式与追踪模式过程的描述； 2.经典理论和人工蜂群算法结合，通过运用基准测试函数，对基本的人工蜂群算法相关4 参数的设置进行分析，并给出建议取值； 3.研究探讨人工蜂群群算法的改进技术，并将其应用到电子商务模型建立和求解中。 2.3拟研究方法 由于本次设计需要对算法的理论和程序两个方面进行研究，因此，需要采用的方法有很多：观察法、实验法（对人工蜂群算法参数设置做详细研究并通过比较试验数据，选取合适参数并进行相应函数的仿真实验）、经验总结法（根据过去失败成功的例子总结出经验）、探索性研究法和文献研究法（通过对相关中外文文献的阅读和总结不断的学习）。 2.4技术路线 确立设计题目以及大致的思想框架 查阅资料了解蜂群的生物学基础 了解分析蜂群算法的基本原理 蜂群算法的收敛性及性能的分析 蜂群算法的应用研究 对蜂群算法改进技术的研究 对蜂群算法相关参数的设置分析 2.5实验方案 本次设计的完成主要需要借助理论和编程两大部分。 理论方面，需要借助大量的算法文献和论文作参考。 在程序方面，以求5个基准测试函数的最小值为例，进行仿真实验，测试软件平台为Visual C++、Windows 7，机器主频为2.8HZ，内存为6GB。通过对程序进行大量的仿真实验，最后得出结果与类似PSO，GA等算法比较得出相应的结论。 首先，阅读大量有关ABC的中英文文献是改进的基础，从文献中深刻体会ABC基本原理，参数设置，算法流程等基础知识。 第二，从ABC算法相关的论文中领会改进的思路，并作出记录。 第三，合理借鉴其他文献的思路和想法，和自己的学习体会相结合，整理出自己的一套改进方法，并请老师或者相关知识的人审核。最后，根据自己总结出的改进方案，利用编程软件写出程序。 第四，分析验证算法的收敛性，算法参数对算法性能的影响。将改进后的算法应用的具体实例中并进行实验证明改进后算法的可行性。 2.6可行性分析 可行性研究是为了弄清楚算法是不是可以实现和值得进行研究的过程，实际上是一次大大简化系统分析和系统设计的过程，所以，进行可执行性的分析是非常必要的，也是很重要5 的。 国内外学者从该算法的改进和应用方面已经做了初步研究，可以为本设计提供一定的理论基础与依据；导师团队从事算法研究多年，可以提供大量指导性的意见，丰厚的理论基础和经验指导；本次试验的器材是计算机一台，CPU:CORE I7，主频2.8HZ，内存6G,成本低完全可以满足试验的要求；本校信息楼提供的各种硬软件设施齐，为前期算法的理论知识的收集，后期实验的仿真测试提供了良好的物质基础。 2.7预期的研究进展 计划进度： 2015年7月至2015年8月 查阅文献资料，学习智能优化算法的基本相关知识，收集蜂群相关算法，扑捉作者的思路。 2015年8月至9月 通过对文献资料的学习，对蜂群算法的收敛性及其性能作出分析。 2015年9月至10月 完成对蜂群算法的参数设置分析。 2015年10月至11月 结合作者的思路和自己创新出的思想，设计一种属于自己的改进的蜂群算法，并编出程序。 2015年11月至12月 撰写毕业论文，完成毕业论文的初稿。 2016年1月至3月 对论文进行修改，最后定稿。

6

三、经费预算

支出科目 1、业务费 2、实验材料费 3、仪器设备费 4、其它 合计 0.1 金额（万元） 0.1 计算根据及理由 注：预算支出科目按下列顺序填写：1、论文课题业务费2、实验材料费、3、仪器设备费

四、论证委员会成员

姓 名 研究方向 职称、职务 工 作 单 位 签 名 王联国 李 广 刘成忠 韩俊英 郭晓燕 农业信息化 农业信息化 农业信息化 智能数据挖掘 计算机应用 教授、院长 教授、院长 副教授、主任 副教授、主任 副教授、主任 甘肃农业大学信息学院 甘肃农业大学林学院 甘肃农业大学信息学院 甘肃农业大学信息学院 甘肃农业大学信息学院 参加开题报告论证会的总人：14 其中教师人数：5 7

五、论证意见

论证主持人签字： 年 月 日 六、学院意见

负责人： （盖章）

年 月 日

8