蚁群算法改进及其应用研究

《蚁群算法改进及其应用研究》由会员分享，可在线阅读，更多相关《蚁群算法改进及其应用研究（51页珍藏版）》请在金锄头文库上搜索。

1、 学 号 ：学 号 ： 20070211132007021113 姓 名 ： 杨 玉 会姓 名 ： 杨 玉 会 联 系 电 话 ：联 系 电 话 ： 1328000049213280000492 EmailEmail： yangyuhui6666 yangyuhui6666 所 在 学 院 ： 管 理 与 经 济 学 院所 在 学 院 ： 管 理 与 经 济 学 院 硕硕 士士 学学 位位 论论 文文 论文题目论文题目 蚁群算法改进及其应用研究蚁群算法改进及其应用研究 学科专业名称学科专业名称 管理科学与工程 申 请 人 姓 名申 请 人 姓 名 杨玉会 指 导 教 师指 导 教 师 王洪国

2、教授 论文提交时间论文提交时间 20102010 年年 5 5 月月 2626 日日 单位代码： 10445 学 号： 2007021113 分 类 号： TP301.6 独独 创创 声声 明明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得_ (注：如没 有其他需要特别声明的， 本栏可空)或其他教育机构的学位或证书使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并 表示谢意。 学位论文作者签名： 导师签字： 学位论文版权使

3、用授权书学位论文版权使用授权书 本学位论文作者完全了解 学校学校 有关保留、使用学位论文的规定，有权保留 并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本 人授权 学校学校 可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以 采用影印、缩印或扫描等复制手段保存、汇编学位论文。(保密的学位论文在解 密后适用本授权书) 学位论文作者签名： 导师签字： 签字日期：2010 年 月 日 签字日期：2010 年 月 日 山东师范大学研究生学位论文 目录目录 中文摘要中文摘要 I ABSTRACT . II 第一章第一章 引言引言 1 11 蚁群算法的思想起源 1 12 蚁

4、群算法的研究现状 3 13 本文研究内容 5 14 本文组织结构 5 第二章第二章 基本蚁群算法模型及实现基本蚁群算法模型及实现 6 2.1 基本蚁群算法原理 . 6 2.2 基本蚁群算法模型 . 8 2.3 基本蚁群算法实现步骤 . 13 第三章第三章 蚁群搜索算法中参数设置及收敛性研究蚁群搜索算法中参数设置及收敛性研究 17 31 参数的设置 . 17 3.1.1 关键参数介绍 17 3.1.2 不同参数设置的试验 19 32 收敛性研究 . 21 3.2.1 收敛性定理23 . 21 3.2.2 改善收敛性的途径 23 第四章第四章 基于信息熵的动态自适应蚁群算法基于信息熵的动态自适应蚁

5、群算法 25 4.1 信息熵简介 . 25 4.2 信息熵的计算 . 26 4.3 自适应调节函数 . 27 4.4 改进后的算法基本框架及其实现过程 . 27 4.5 算法仿真与结果分析 . 29 第五章第五章 一种求解一种求解 AGENT 联盟生成问题的贪心蚁群算法联盟生成问题的贪心蚁群算法 30 5.1 Agent联盟生成问题简介 . 30 5.2 基本蚁群算法求解单任务联盟生成问题 . 31 5.3 改进的贪心蚁群算法解决Agent单联盟生成问题 32 第六章第六章 总结与展望总结与展望 38 参考文献参考文献 39 攻读硕士期间发表的论文和参与的项目攻读硕士期间发表的论文和参与的项目

6、 42 致谢致谢 43 山东师范大学硕士学位论文 I 蚁群算法改进及其应用研究蚁群算法改进及其应用研究 中文摘要中文摘要 当人们使用传统寻优方法求解复杂组合优化问题遇到极大困难时，一些研究 者另辟蹊径， 开创性地通过模仿生物体或者生态系统的生态机制构造出了新的算 法，这些算法包括进化算法（遗传算法、遗传规划、进化策略） ，人工神经网络， 人工免疫系统，微粒群算法等，我们统称为智能优化算法。经过近半个世纪的实 践已经证明，智能优化算法在解决复杂组合优化、复杂控制等问题时，具有一些 传统方法不能比拟的优点：鲁棒性好，无需问题本身的详细信息，较好的搜索全 局性等特点。 蚁群算法是由意大利学者 M.D

7、origo 等人提出的一种智能优化算法， 它具有智 能优化算法的优点， 但它本身也存在着一些固有的不足， 比如说易陷入局部收敛， 收敛速度慢等。本文针对蚁群算法的这些不足，对以下几个方面进行了研究。 (1) 针对蚁群算法实现中有关参数取值对算法整体性能影响很大这一问题， 我们对参数的合理取值区间进行了实验研究，通过保持其他参数值不变，只改变 一个参数值的方法，我们统计得出了利于算法性能提高的参数取值； (2) 对蚁群算法的收敛性进行了分析和证明，得出了几个可以改善算法整体 性能的途径，如调整信息素的更新方式和调整蚂蚁选择路径的方式。 (3) 蚁群算法实现中，信息素挥发度系数太大与太小都不利于算

8、法搜索整体 性能的提高，为了改善搜索性能，我们引入了信息熵概念，在每次迭代完成后计 算解种群的信息熵值，用此值来动态调整信息素挥发度系数的大小，调节算法搜 索全局性与收敛速度的问题；基于此原理我们提出了一种动态自适应蚁群算法， 通过对 TSP 问题的求解验证了其有效性。 (4) 提出了一种贪心蚁群算法来解决联盟生成问题，通过与解决此问题的几 种其他算法进行实验比较， 证明用贪心蚁群算法来解决 Agent 联盟生成问题是可 行的和有效的，为联盟生成问题的求解提供了新的途径。 关键字关键字：智能优化算法，蚁群算法，信息熵，TSP 问题，Agent 联盟生成问题 山东师范大学硕士学位论文 II IM

9、PROVEMENT AND APPLICATION STUDY OF ANT COLONY OPTIMIZATIONM ALGORITHM ABSTRACT When people had serious trouble in solving complex Combination Optimization Problem apliying some traditional methods,some researchers had a fresher way and constructed some new algorithms by imitating ecological mechanis

10、ms of organism or ecosystem.These new algorithms include Evolutionary Algorithm(Genetic Algorithm,Genetic Programming,Evolution Strategy)、Artifical Neural Network、 Artificial Immune Systems、 Particle Swarm Optimization, and so on.We generally call they Intelligent Optimization Algorithms.After nearl

11、y half a centruy of practice,It is proven that Intelligent Optimization Algorithms have lots of advantages that other traditional algorithms have not when they are used to solve some complex Combination Optimization Prolem and Control Problem.These advantages include good robustness、good global prop

12、erty of search、no details of issues themselves,and so on. Ant Colony Algorithm(ACO) were presented by Italys scholar M.Dorigo et al in 1991.It has some advantages that Intelligent Optimization Algorithms have,and it also have some immanent disadvantage, which converges too slowly and falls into loca

13、l extrema easily and so on.Based on the above disadvantages,the following parts will be researched on this paper. (1) Directed towards the issue that parameter values have a great effect on the overall performance of ACO when to implement it,we make an experimental study on reasonable parameter valu

14、e range.By means of making other parameter value remain unchanged,changing only a parameter value,we obtain best parameter value that can make ACOs performance superior. (2) In this paper,we analyzed and proved the convergence of ACO simply and obtain several methods by which the overall performance

15、 of ACO could be improved.For example,adjusting the update mode of Pheromone,adjusting the mode that ant select paht. (3) In algorithm performance,the value of coefficient has a great effect 山东师范大学硕士学位论文 III on ACOs searching ability.To improve the searching ability,we introduce the conception of in

16、formation entropy.Based on information entropy,we present a new improved ACOInformation Entropy-based Adaptive Ant Colony Algorithm.By applying it to resolve TSP problem,we prove the new algorithm is more effective than the original algorithm. (4) We present a greedy ant colony algorithm(GAOA) and use it to resolve the Agent Coalition Generation Problem.By contradistinctive experiment,we prove it is feasib