一种改进的蚁群算法求解旅行商问题

论文摘要

20世纪90年代初,意大利学者等人受蚂蚁在觅食过程中可以找出从巢穴到食物源的最短路径的启发,提出了蚁群算法(ant cp;pmu algorithm),它是继禁忌搜索算法、模拟退火算法、遗传算法、人工神经网络等启发式搜索算法之后出现的一种新的启发式搜索算法。蚁群算法不仅能够智能搜索、全局优化,而且具有稳健性、正反馈、分布式计算、易与其它算法结合等特点,鲁棒性强,在基本蚁群算法模型的基础上进行修改,便可用于其它问题;正反馈过程使得该方法能很快发现较好解;分布式计算使得该方法易于并行实现,个体之间不断进行信息交流和传递,有利于发现较好解,不容易陷入局部最优;与启发式算法相结合,可改善算法的性能。它成功应用于解决许多组合优化问题。一些初步研究和应用已显示出蚁群算法在求解复杂优化问题方面的一些优越性,特别是离散优化问题。因此,蚁群算法已成为当前群智能领域中最令人感兴趣和最富有魅力的研究课题之一。目前的研究主要集中在比利时、意大利、德国等国家,国内的研究主要在上海、北京、东北少数几个学校和研究所开展了此项工作,主要围绕旅行商及相关问题的实验仿真。本课题的主要工作包括以下三个方面:首先对蚁群算法进行基础理论研究,旨在对蚁群算法近年来的研究进展进行总结,归纳算法的成功应用领域和存在的不足,并对不足之处进行深入理论分析,目的在于提高蚁群算法的总体性能。第二是针对算法容易陷入局部最优解,在算法中加入扰动量,扩大搜索范围,从而有效控制算法陷入局部最优解。针对蚁群算法收敛速度慢,本文充分利用蚁群在最差路径上的信息,对蚁群算法信息素更新规则上进行了改进。最后,运用MATLAB平台对改进蚁群算法求解经典的旅行商问题进行仿真实验,实验结果表明,本课题提出的改进蚁群算法有效的避免程序过早的陷入局部最优解,同时提高了蚁群算法的速度。目前国内外在蚁群算法理论上的研究甚少,所以本课题将改进的蚁群算法应用到旅行商问题,是一次有效的尝试。

论文目录

• 摘要
• ABSTRACT
• 第1章 引言
• 1.1 研究背景与意义
• 1.2 国内外研究现状
• 1.3 本文的组织结构
• 第2章 蚁群算法基本理论
• 2.1 蚁群算法基本模型
• 2.2 蚂蚁系统
• 2.3 其他蚁群算法
• 2.3.1 最大最小蚁群算法
• 2.3.2 具有变异和分工特征蚁群算法
• 2.3.3 基于分布均匀度的自适应蚁群算法
• 2.3.4 具有感觉和知觉特征的蚁群算法
• 第3章 旅行商问题
• 3.1 模拟退火算法
• 3.1.1 模拟退火算法基本思想
• 3.1.2 模拟退火算法求解旅行商问题
• 3.2 禁忌搜索算法
• 3.2.1 禁忌搜索算法的基本思想
• 3.2.2 禁忌搜索算法求解旅行商问题
• 3.3 遗传算法方法
• 3.3.1 遗传算法的基本思想
• 4.3.2 遗传算法求解旅行商问题
• 3.4 混合优化策略方法
• 3.4.1 混合优化策略背景和方法
• 3.4.2 混合优化策略求解旅行商问题
• 3.5 各种方法的优缺点及比较
• 第4章 蚁群改进算法研究
• 4.1 蚁群算法求解旅行商问题模型
• 4.2 蚁群算法的缺点
• 4.3 蚁群算法的改进
• 4.3.1 加入扰动的改进
• 4.3.2 信息素更新规则的改进
• 4.3.3 算法实现
• 4.4 实验结果
• 第5章 结束语
• 参考文献
• 致谢
• 攻读学位期间发表的学术论文目录
• 学位论文评阅及答辩情况表