蚁群算法及其在TSP中的应用

论文摘要

自从上世纪50年代中期创立仿生学以来,人们不断地从生物进化的机理中得到启发,提出了许多用于解决复杂优化问题的新方法,比如神经网络、遗传算法、模拟退火算法、进化规划等,并成功应用于解决实际问题。由意大利学者Marco Dorigo, V.Maniezzo ,A.Colorni于1992年首先提出的一种基于种群的模拟进化算法-蚁群优化（Ant Colony Optimization ACO）,它是一种新颖的仿生进化算法,适用于求解复杂组合优化问题。目前,蚁群系统己成功应用于求解旅行商问题（Traveling salesman problem TSP）、二次分配问题（QAP）和job-shop调度问题,取得了很好的实验效果。受其影响,蚁群系统的研究已经逐渐引起了更多学者和专家的关注。虽然,该研究方法处于研究的初级阶段,但是一些研究成果已经显示出蚁群系统在求解复杂优化问题方面的优越性。本文的工作如下:①对蚁群算法的理论及其在TSP中的应用进行了较为深入、系统的研究。介绍了蚁群算法基本模型的原理、特点、构成和实现方法,对蚁群算法参数的合理选取进行了详细的实验分析,给出了算法参数选取的基本原则。②对于传统的蚂蚁算法容易出现早熟和停滞现象,及传统的蚁群算法中的信息素进行了动态的自适应调整,提出了一种新的自适应蚂蚁算法,选取几个TSP问题进行实验,结果表明改进后的算法具有更好的搜索全局最优解的能力,并具有更好的稳定性和收敛性。最后对全文的研究工作进行了总结,并展望了蚁群算法进一步还要研究的课题。

论文目录

摘要

ABSTRACT

1 引言

1.1 引言

1.2 蚁群算法的起源

1.3 本文的主要工作

1.4 本文结构

2 蚁群算法的基本原理

2.1 引言

2.2 基本蚁群算法的原理

2.2.1 蚁群觅食的行为描述

2.2.2 基本蚁群算法的机制原理

2.3 TSP（旅行商问题）

2.3.1 TSP 的描述

2.3.2 TSP 的重要性

2.4 基本蚁群算法的模型

2.5 算法执行描述

2.5.1 基本蚁群算法的程序结构流程

2.5.2 其具体实现步骤

2.6 本章小结

3 蚁群算法的研究现状

3.1 引言

3.2 蚁群算法的特征

3.3 最大最小蚁群算法（MMAS）

3.4 自适应蚁群算法

3.5 带杂交算子的蚁群算法

3.6 基于蚁群算法的TSP 分段求解算法

3.7 本章小结

4 蚁群算法的参数分析

4.1 引言

4.2 信息素残留因子的选择

4.3 信息素启发式因子α的选择

4.4 信息素自启发因子β的选择

4.5 总信息素的选择

4.6 蚂蚁数目的选择

4.7 本章小结

5 改进的蚁群算法

5.1 引言

5.2 信息素的更新

5.3 参数的设置

5.4 局部搜索策略

5.5 实验结果

5.6 本章小结

6 总结与展望

6.1 本文总结

6.2 展望

致谢

参考文献

附录

蚁群算法及其在TSP中的应用

论文摘要

论文目录

相关论文文献