基于演化蚁群算法的TSP问题研究及应用

论文摘要

蚁群算法是最近几年才提出来的一种新的仿生优化算法,它是由意大利学者M.Dorigo, V.Mahiezzo, A.Colorni等人受自然界中真实蚂蚁群体寻找食物过程的启发而率先提出来的。他们利用蚂蚁搜索食物的过程与旅行商问题之间的相似性,通过人工模拟蚂蚁搜索食物的过程中蚂蚁个体之间的相互协作与信息交流,最终找到从巢穴到食物源最短路径的原理来解决旅行商问题(TSP),并取得了较好的效果。该算法具有高度的本质并行性、较强的鲁棒性、优良的分布式计算机制,易于与其他方法相结合等优点。自蚁群算法提出以来,引起了国内外学者的极大关注,在十多年的时间里,已在组合优化、数据挖掘、网络路由,机器人路径优化,连续函数优化问题上得到了广泛的应用,显示出其在求解复杂优化问题方面的优越性。因此,蚁群算法的研究无论是从理论上还是应用上都具有较高的价值。作为一种近年提出的新型优化算法,还没有像遗传算法,模拟退火算法等那样形成系统的分析方法和坚实的数学基础,许多理论问题有待研究,比如算法搜索时间较长,运行过程中容易出现收敛过早或停滞现象,不能扩大解的搜索范围等。针对这些缺陷,近年来国内外学者对蚁群算法提出了大量的改进方法。TSP是一个具有广泛应用背景和重要理论价值的组合优化问题,已经成为并将继续成为测试组合优化算法的标准问题。本论文围绕蚁群算法的原理,理论及应用,针对目前蚁群算法在解决TSP时存在的一些缺陷,在阅读大量相关文献的基础上提出了几点改进方法。本论文的主要研究成果包括:第一、在信息素更新方式上,引入反馈因子,利用先前的反馈信息,尽力避免不必要的搜索,在信息素更新时,对所有的解不使用统一的信息素更新方式,而是根据反馈因子采取不同解不同对待的策略,对每次循环中的最优解、最差解及一般解分别执行不同的信息素更新方式,增强一般解的信息素,对最优解进行更大限度的增强,对较差解进行削弱,使得属于最优路径的边与属于较差路径的边之间的信息素量差异进一步增大,以便更好的利用蚂蚁先前的反馈信息,使蚂蚁的搜索行为更集中于最优解附近,从而引导问题的解向着全局最优的方向不断进化。第二、提出一种新的启发式演化交叉算子,这种演化交叉不只是单纯的进行随机交叉,而是综合父代基因,再根据各个城市之间的连接关系的一种启发式交叉方式。将这种交叉算子应用到蚁群算法中,随机选择一条路径与最优路径执行这种启发式交叉,通过这种交叉得到的子代将会有效的继承父代较好的基因,从而有利于发现最优解,加快算法的收敛速度。第三、为了进一步防止算法过早陷入局部最优,本论文采用确定性与随机性相结合策略来选择路径,将随机性和探索性结合起来,以获得多样性的解。第四、将这种算法应用到TSP中,通过实验表明,与传统的蚁群算法相比,使用这种基于启发式交叉算子的演化算法来求解复杂TSP问题不但具有更强的全局搜索能力,而且还能提高算法的收敛速度,最终使得算法性能得到明显改善。最后,对本论文的研究工作进行了总结,展望了蚁群算法进一步要研究的内容。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 课题研究背景及意义
• 1.2 蚁群算法的国内外研究现状
• 1.3 本论文的主要工作
• 第二章 TSP 问题
• 2.1 TSP 问题概述
• 2.2 求解TSP 的复杂性及意义
• 2.3 求解TSP 的仿生进化算法概述
• 2.4 本章小结
• 第三章 基本蚁群算法模型
• 3.1 基本蚁群算法的原理
• 3.2 蚁群算法的系统学特征
• 3.3 基本蚁群算法的数学模型
• 3.4 基本蚁群算法的具体实现
• 3.4.1 基本蚁群算法的实现步骤
• 3.4.2 基本蚁群算法的程序结构流程图
• 3.5 基本蚁群算法的选参原则
• 3.6 蚁群算法优缺点
• 3.7 本章小结
• 第四章 现有基本蚁群算法的改进方法
• 4.1 蚁群系统（ACS）
• 4.2 最大最小蚁群模型（MMAS）
• 4.3 最优－最差蚂蚁系统（BWAS）
• 4.4 具有变异特征的蚁群算法（MAS）
• 4.5 带杂交因子的蚁群算法
• 4.6 遗传算法与蚂蚁算法的融合算法（GAAA）
• 4.6.1 GAAA 算法中遗传算法的设计
• 4.6.2 GAAA 算法中蚁群算法的设计
• 4.7 本章小结
• 第五章 改进的演化蚁群算法
• 5.1 基本蚁群算法的不足之处
• 5.2 基本蚁群算法的改进策略
• 5.2.1 路径选择策略的改进
• 5.2.2 信息素更新方式的改进
• 5.2.3 启发式演化交叉操作
• 5.3 改进算法描述及实现
• 5.3.1 改进算法实现步骤
• 5.3.2 改进算法程序结构流程
• 5.4 数据仿真实验
• 实例一：Oliver30 实验仿真
• 实例二：Att48 实验仿真
• 实例三：Eil51 实验仿真
• 实例四：Eil75 实验仿真
• 5.5 本章小结
• 第六章 总结与展望
• 6.1 论文的主要工作和贡献
• 6.2 下一步的工作和展望
• 参考文献
• 附录 TSP 问题
• 致谢
• 个人简历、在学期间发表的学术论文与研究成果