求解旅行商问题和非线性方程组的蚁群算法

论文摘要

旅行商问题（TSP）和非线性方程组都是具有广泛的应用背景的重要问题。TSP是一类典型的组合优化问题,它在交通运输、电路板线路以及物流配送等领域都有广泛的应用。特别地,它是测试蚁群算法有效性的一个典型问题。非线性方程组是科学和工程领域中的一个重要问题,它在数值天气预报、石油地质勘探、计算生物化学、控制邻域和轨道设计等方面均有较强的应用背景。特别地,约束优化问题的Kuhn-Tucker条件是非对称非线性方程组。因此,研究求解它们的方法具有重要的理论价值与现实意义。尽管有许多求解TSP问题的方法,然而传统的算法因其计算时间随着问题规模的增大而增大,在有限的时间内很难求出最优解。随着进化算法（如遗传算法、蚁群算法、粒子群算法等）的深入研究,人们开始应用这类算法来求解TSP问题,并取得了较好的实验结果。特别地,模拟自然界蚂蚁群体觅食行为的蚁群算法,因其内在的正反馈机制,并行分布式计算以及易于与其他算法相结合等优点,使其在解决TSP问题上表现出了很强的寻优能力。因此,本文第二章从旅行商问题入手,对基本蚁群算法的发展背景、基本原理、实现步骤、复杂度,收敛性及算法的特点作了详细介绍。第三章,针对对称TSP问题,在总结已有算法的基础上,重点分析了蚁群系统（ACS）和蚁群遗传算法（ACSGA）的优缺点,为避免蚁群算法陷入局部最优,首先引入遗传算法的杂交算子;其次,为了加快收敛速度和解的精度,分别引入候选列表和2—交换策略,进而提出了求解TSP的改进蚁群算法。仿真结果表明该算法有效地避免了局部最优,并且在执行效率和求解质量上均有所提高。尽管传统的牛顿型迭代法仍然是求解非线性方程组的最常用的方法之一,但是由于其对初始值的依赖性特别强而限制了它们在工程中的应用。近几年流行起来的进化算法如遗传算法等,因其较强的全局搜索能力和较快的收敛速度,在解决大型、复杂及状态多变的非线性方程组方面表现出较好的求解能力。因此针对非对称非线性方程组,本文第四章总结了已有算法,并分析了一类求解无约束优化问题的蚁群算法,实验表明该算法具有较强的收敛性和较高的求解精度。为此我们将其推广应用于求解非线性方程组,首先将非线性方程组转化为等价的无约束优化问题,其次通过引入拟牛顿法以及对参数采用动态的自适应选择机制来加速局部搜索速度和增强其稳定性,进而提出求解非线性方程组的拟牛顿蚁群算法。仿真实验表明该算法是稳定和有效的。与拟牛顿法和蚁群算法相比,新算法不仅提高了解的精确性,而且增强了收敛的可靠性。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 旅行商问题及其研究进展
• 1.2 非线性方程组及其研究进展
• 1.3 蚁群算法的基本特征及研究进展
• 1.4 本文的主要工作
• 第二章 基本蚁群算法
• 2.1 蚁群算法的基本原理
• 2.2 基本蚁群算法模型及其实现
• 2.3 算法的复杂度分析
• 2.4 收敛性分析
• 2.5 蚁群算法的特点
• 2.6 本章小结
• 第三章 求解旅行商问题的改进蚁群算法
• 3.1 引言
• 3.2 蚁群系统（ACS）及蚁群遗传算法（ACSGA）概述
• 3.3 改进策略及其实现
• 3.4 数值模拟
• 3.5 结论
• 第四章 求解非线性方程组的改进蚁群算法
• 4.1 引言
• 4.2 求解函数优化问题的蚁群算法
• 4.3 改进策略及模型实现
• 4.4 试验结果
• 4.5 结论
• 总结
• 参考文献
• 致谢
• 攻读学位期间的研究成果