改进的蚁群算法及其在TSP上的应用研究

论文摘要

自从群体智能的概念提出来以后,很多相应的智能方法和智能算法被陆续提出,并把它们应用在了很多经典算法不能解决的问题当中。通过实际的应用和实验的结果来看,很多群智能算法能够很好地解决一些特定问题,而且最终的结果也很令人满意。蚁群算法作为群智能算法的代表,成为研究的热点。本文从蚁群觅食行为的策略出发,对蚁群觅食过程进行了形式化建模,通过模型的求解从理论上给出了各个参数和系统行为之间的量化关系。接着,通过实验分析了食物源的不同分布对群体行为的影响。而通过对群体数量、信息素的挥发速度的分析,可以了解到群体规模同系统的性能具有幂指数关系。增加群体规模对系统性能有明显的提高,并论证了这种量化关系可以直接为蚁群优化算法的改进提供理论和实验支持。本文以TSP问题为例进行对前面提出结论的研究。首先,介绍了蚁群算法求解TSP问题的规则和形式化描述。接着根据本文所给出的蚁群觅食模型的分析结果,对基本的蚁群算法进行了改进。根据挥发效应和群体规模参数的实验结果,设计了通过引入记忆机制和信息传递蚂蚁来改进蚁群算法性能的算法。最后,本文对形式化的模型和改进的蚁群算法都进行了验证,证明了理论分析和相应改进的正确性。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 研究背景及目的
• 1.2 国内外研究现状
• 1.3 论文研究内容及组织
• 1.3.1 论文研究内容
• 1.3.2 论文的组织结构
• 第2章 相关知识及理论
• 2.1 引言
• 2.2 TSP问题
• 2.2.1 TSP问题简介
• 2.2.2 TSP问题描述
• 2.2.3 TSP问题分类
• 2.2.4 TSP问题计算方法
• 2.3 几种智能计算方法
• 2.3.1 群智能算法介绍
• 2.3.2 进化计算
• 2.3.3 神经网络
• 2.4 几种启发式与智能算法
• 2.4.1 遗传算法
• 2.4.2 免疫进化算法
• 2.4.3 粒子群算法
• 2.4.4 模拟退火算法
• 2.5 仿真平台Starlogo
• 2.5.1 StarLogo介绍
• 2.5.2 StarLogo程序描述
• 2.6 本章小结
• 第3章 蚁群觅食行为及特性分析
• 3.1 引言
• 3.2 蚁群觅食行为
• 3.2.1 觅食中的猎食策略
• 3.2.2 觅食中的招募策略
• 3.2.3 防御阶段
• 3.3 大规模招募策略下的蚁群觅食模型
• 3.3.1 觅食模型介绍
• 3.3.2 系统模型求解
• 3.4 系统模型下觅食特性分析
• 3.5 本章小结
• 第4章 改进蚁群优化算法及其在TSP中的应用
• 4.1 引言
• 4.2 蚁群优化算法与TSP问题
• 4.2.1 蚁群算法的基本思想
• 4.2.2 蚁群算法过程
• 4.3 改进的蚁群算法
• 4.3.1 蚁群算法改进
• 4.3.2 改进蚁群算法描述
• 4.4 仿真实验与分析
• 4.5 本章小结
• 结论
• 参考文献
• 攻读硕士学位期间发表的论文和取得的科研成果
• 致谢
• 个人简历