西安理工大学
本科生毕业设计（论文）文献综述
题 目： 基于蚁群算法的旅行商问题求解 姓 名： 学 号：
学 院： 理学院 专 业： 信息与计算科学 年 级： 2012级 指导教师：
2016 年 4 月 28 日
1
基于蚁群算法的旅行商问题求解
毕业设计文献综述
摘要
本文综述了有关蚁群算法和旅行商问题的相关理论。首先阐述了该算法的基本原理和算法模型，然后给出了在旅行商问题中的理论和应用的具体过程，最后对问题进行总结。
关键词：蚁群算法；旅行商问题；算法模型；综述；
Abstract: This paper reviews the theories about the ant colony algorithm and the Traveling Salesman Problem. Firstly describes the basic principle and algorithm model of the algorithm, and then gives a specific process in the traveling salesman problem in theory and application, and finally to summarize the problem.
Key words: ant colony algorithm; algorithm model; traveling salesman problem
一、课题的背景及意义
1. 旅行商问题
旅行商问题( Traveling Salesman Problem, 简称TSP)是一个经典的NP难题，也是组合优化中研究最多的问题之一，它解决如何找到一条从一个城市出发经过若干个城市后又返回原城市的最短路径?1?。城市管道铺设优化、物流业的车辆调度、制造业中的切割路径优化等，现实生活中的优化问题都可以归结为TSP问题进行求解。寻找一种有效的解决该问题的算法，具有重要的现实意义。
TSP的历史很久，最早的描述是1759年欧拉研究的骑士周游问题，即对于国际象棋棋盘中的64个方格，走访64个方格一次且仅一次，并且最终返回到起始点。
TSP由美国RAND公司于1948年引入，该公司的声誉以及线性规划这一新方法的出现使得TSP成为一个知名且流行的问题。 2. 蚁群算法
蚁群算法(Ant Colony Algorithm,简称 ACA)是由意大利学者Dorigo. M等人首先提出来的一种新型的模拟进化算法?2~4?。其主要特点就是：通过正反馈、
2
分布式协作来寻找最优路径。这是一种基于种群寻优的启发式搜索算法。它充分利用了生物蚁群能通过个体间简单的信息传递，搜索从蚁穴至食物间最短路径的集体寻优特征，以及该过程与旅行商问题求解之间的相似性，得到了具有 NP难度的旅行商问题的最优解答。同时，该算法还被用于求解 Job-Shop调度问题、二次指派问题以及背包问题等?2~4?，显示了其适用于组合优化类问题求解的优越特征。
该算法采用了分布式并行计算机制，易于与其他方法结合，而且具有强的鲁棒性，是求解TSP问题的一种理想方法。算法的主要思想为：模拟蚂蚁觅食行为。蚂蚁在运行过程中会释放一种特殊的分泌物--信息素来寻找路径。信息素会随着时间消减，后面的蚂蚁选择信息素多的路径，这样便形成了一个正反馈机制。在整个寻径过程中,虽然单只蚂蚁的选择能力有限，但它们的行为具有非常高的自组织性，相互之间交换路径，最终寻找到最优路径。
二、国内外研究的发展历程及现状
1.旅行商问题
1.1 TSP 问题数学模型
TSP 在图论意义下常常被称为最小 Hamilton 回路。Hamilton 回路最早由天文学家哈密顿(William Rowan Hamilton)提出，指的是在一个有多个城市的地图网络中，寻找一条从给定的起点到给定的终点沿途恰好经过所有其他城市一次的路径。Euler等人最早研究了该问题的。这个问题从字面意义上很好理解，但却是延续至今的一个世界难题。
这里用数学语言描述 TSP。此处首先引入赋权图，赋权图是指每条边都有一个非负实数对应的图。这个实数称为这条边的权。赋权图在实际问题中非常有用。根据不同的实际情况，权数的含义可以各不相同。例如，可用权数代表两地之间的实际距离或行车时间，也可用权数代表某工序所需的加工时间等。
（V，E）（1,2,?,n）记G?为赋权图，V?为顶点集，E为边集，各顶点间的距离
。设 （dij?0，dij??，i，j?V）dij已知
?1，若（i，j）在最优回路上xij???0，其他3
（2-1）
则经典的 TSP 问题可写为如下的数学规划模型
minZ???dijxiji?1j?1nn （2-2）
n?xij?1，i?V（a）??j?1?n?xij?1，j?V（b）??s.t.?i?1?i?1???xij?S?1，?S?V（c）?i?Sj?S??xij?{0,1}（2-3）
上式中， S为集合S中所含图的顶点集。约束（a）和约束（b）意味着对每个点来说，仅有一条边进和一条边出；约束（c）则说明了没有任何子回路。于是，满足上面三个约束条件的解就构成了一条 Hamilton 回路。 1.2 TSP 问题分类
经过多年的研究与发展，TSP 问题已经从单一的简单 TSP 问题扩展到现在的多种形式。如接上一节的描述，当 dij?d（时，这时的 TSP 称为对jii，j?V）称型 TSP。从对问题的限制条件上看，TSP主要有下面几种类型：
第一种，就是没有任何限制条件的，就是给出距离矩阵，求出最短路径。 第二种，要求满足三角形不等式的，即满足对所有的1?i，j，k?n，有不等式dij?djk?di成立，称为三角形 TSP。一般情况下，现实问题大部分都是满足三角不等式的，可以说三角形不等式 TSP 是 TSP 问题的主要形式。
第三种，就是在欧式平面上的 TSP。它是以欧式平面上的坐标和欧式距离来定义的城市之间的距离。
TSP 问题还能扩展为很多别的问题，如多旅行商问题，即由多人完成巡回的 TSP。还有就是多目标旅行商问题，该问题在每条边上都有权值，权值有 n 个，要使得这 n 个目标值都尽可能小的解就是多目标旅行商问题。这在现实情况中很常见，如要求考虑路程最短、时间最少，风险最低等因素。 1.3 求解 TSP 问题方法
前面章节已经提到，求解 TSP 问题方法很多，主要分为经典方法和仿生优
4
相关推荐：
loading