群蚁算法文献综述

《群蚁算法文献综述》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、西安理工大学本科生毕业设计（论文）文献综述题目：基于蚁群算法的旅行商问题求解姓名：学号：学院：理学院专业：信息与计算科学年级：2012级指导教师：2016年4月28日16基于蚁群算法的旅行商问题求解毕业设计文献综述摘要本文综述了有关蚁群算法和旅行商问题的相关理论。首先阐述了该算法的基本原理和算法模型，然后给出了在旅行商问题中的理论和应用的具体过程，最后对问题进行总结。关键词：蚁群算法；旅行商问题；算法模型；综述；Abstract:ThispaperreviewsthetheoriesabouttheantcolonyalgorithmandtheTravelingSalesm

2、anProblem.Firstlydescribesthebasicprincipleandalgorithmmodelofthealgorithm,andthengivesaspecificprocessinthetravelingsalesmanproblemintheoryandapplication,andfinallytosummarizetheproblem.Keywords:antcolonyalgorithm;algorithmmodel;travelingsalesmanproblem一、课题的背景及意义1.旅行商问题旅行商问题(TravelingSales

3、manProblem,简称TSP)是一个经典的NP难题，也是组合优化中研究最多的问题之一，它解决如何找到一条从一个城市出发经过若干个城市后又返回原城市的最短路径。城市管道铺设优化、物流业的车辆调度、制造业中的切割路径优化等，现实生活中的优化问题都可以归结为TSP问题进行求解。寻找一种有效的解决该问题的算法，具有重要的现实意义。TSP的历史很久，最早的描述是1759年欧拉研究的骑士周游问题，即对于国际象棋棋盘中的64个方格，走访64个方格一次且仅一次，并且最终返回到起始点。TSP由美国RAND公司于1948年引入，该公司的声誉以及线性规划这一新方法的出现使得TSP成为一个知名且

4、流行的问题。2.蚁群算法蚁群算法(AntColonyAlgorithm,简称ACA)是由意大利学者Dorigo.M等人首先提出来的一种新型的模拟进化算法。其主要特点就是：16通过正反馈、分布式协作来寻找最优路径。这是一种基于种群寻优的启发式搜索算法。它充分利用了生物蚁群能通过个体间简单的信息传递，搜索从蚁穴至食物间最短路径的集体寻优特征，以及该过程与旅行商问题求解之间的相似性，得到了具有NP难度的旅行商问题的最优解答。同时，该算法还被用于求解Job-Shop调度问题、二次指派问题以及背包问题等，显示了其适用于组合优化类问题求解的优越特征。该算法采用了分布式并行计算机制，易于与

5、其他方法结合，而且具有强的鲁棒性，是求解TSP问题的一种理想方法。算法的主要思想为：模拟蚂蚁觅食行为。蚂蚁在运行过程中会释放一种特殊的分泌物--信息素来寻找路径。信息素会随着时间消减，后面的蚂蚁选择信息素多的路径，这样便形成了一个正反馈机制。在整个寻径过程中,虽然单只蚂蚁的选择能力有限，但它们的行为具有非常高的自组织性，相互之间交换路径，最终寻找到最优路径。二、国内外研究的发展历程及现状1.旅行商问题1.1TSP问题数学模型TSP在图论意义下常常被称为最小Hamilton回路。Hamilton回路最早由天文学家哈密顿(WilliamRowanHamilton)提出，指的是在一

6、个有多个城市的地图网络中，寻找一条从给定的起点到给定的终点沿途恰好经过所有其他城市一次的路径。Euler等人最早研究了该问题的。这个问题从字面意义上很好理解，但却是延续至今的一个世界难题。这里用数学语言描述TSP。此处首先引入赋权图，赋权图是指每条边都有一个非负实数对应的图。这个实数称为这条边的权。赋权图在实际问题中非常有用。根据不同的实际情况，权数的含义可以各不相同。例如，可用权数代表两地之间的实际距离或行车时间，也可用权数代表某工序所需的加工时间等。记为赋权图，为顶点集，为边集，各顶点间的距离已知。设16则经典的TSP问题可写为如下的数学规划模型上式中，为集合S中所含图的

7、顶点集。约束（a）和约束（b）意味着对每个点来说，仅有一条边进和一条边出；约束（c）则说明了没有任何子回路。于是，满足上面三个约束条件的解就构成了一条Hamilton回路。1.2TSP问题分类经过多年的研究与发展，TSP问题已经从单一的简单TSP问题扩展到现在的多种形式。如接上一节的描述，当时，这时的TSP称为对称型TSP。从对问题的限制条件上看，TSP主要有下面几种类型：第一种，就是没有任何限制条件的，就是给出距离矩阵，求出最短路径。第二种，要求满足三角形不等式的，即满足对所有的，有不等式成立，称为三