《人工蚁群算法的实现与性能分析》由会员分享，可在线阅读，更多相关《人工蚁群算法的实现与性能分析（28页珍藏版）》请在金锄头文库上搜索。
1、目录错误！未定义书签。扌摘 要iiAbstract第一章引言11.1非对称TSP问题（ATSP）及其求解方法概述11.2人工蚁群算法的主要思想和特点11.3主要工作2第二章ATSP问题分析32.1 ATSP问题的数学模型32.2 ATSP问题与TSP问题的比较3第三章 求解ATSP问题的人工蚁群算法43.1 ATSP问题的蚁群算法表示43.2人工蚁群算法的实现43.2.1人工蚁群算法的流程图5322蚁群的规模、算法终止条件63.2.3路径选择方法和信息素的更新方法7第四章实验和分析104.1 测试环境104.2测试用例104.3实验结果及参数分析104.3.1 br17.atsp 的测试结果1
2、04.3.2 ft53.atsp 的测试结果124.3.3 ftv33.atsp 的测试结果134.3.4 ftv35.atsp 的测试结果154.3.5 br17.atsp相关参数修改后的测试结果16第五章总结19致谢20参考文献21旅行商问题（TSP问题）是组合优化的著名难题。它具有广泛的应用背景，如计算机、 网络、电气布线、加工排序、通信调度等。已经证明TSP问题是NP难题，鉴于其重 要的工程与理论价值,TSP常作为算法性能研究的典型算例。TSP的最简单形象描述是: 给定n个城市，有一个旅行商从某一城市出发,访问各城市一次且仅有一次后再回到原出 发城市，要求找出一条最短的巡回路径。TSP
3、分为对称TSP和非对称TSP两大类，若两城 市往返距离相同，则为对称TSP，否则为非对称TSP。本文研究的是对称的ATSP。实质上，ATSP问题是在TSP问题上发展而来的，它们的区别就在于两座城市之间的 往返距离是否相同。例如，有A，B两个城市，在TSP问题中，从A到B的距离是等于从 B到A得距离的，是一个单向选择的连通问题。而在ATSP问题中，从A到B的距离就不 一定等于从B到A的距离，所以这是双向选择的联通问题。本文主要阐述了用人工蚁群算法的原理和一些与其相关联的知识结构点。通过对算 法原理的理解，及在函数优化问题上的应用，与优化组合问题的研究来了解ATSP问题 以及人工蚁群算法解决实际问
4、题上的应用与研究。关键词：ATSP ；组合优化；人工蚁群算法；TSPAbstractTraveling salesman problem (TSP) is the Famous combination of the optimization problem. It has broad applications, such as computer, network, electrical wiring, processing, sort and communication scheduling,and etc.Has already proved TSP is a difficult NP pr
5、oblem, givening its important engineering and theoretical valued, TSP is often used as the typical example of algorithm performance study.The most simple image description of TSP is: given n city, a traveling salesman start from one city, Visit other cities once and only once again return to the sta
6、rt city , asked to identify a shortest path of the tour.TSP can be classificated symmetric TSP and asymmetric TSP two big kinds.If two cities from the same distance,that is symmetric TSP, or for the asymmetric TSP.This paper studies the ATSP problem.In essence, ATSP problem is based on the TSP probl
7、em.The difference lies in two cities round trip distance between the same or different.For example,there are two cities,A and B , in TSP problem,from A to B is equal to the distance from B to have A distance,it s a one-way choice the connected problems.But in ATSP problem,from A to B doesnt necessar
8、ily equal to the distance from the distance B to A, so this is the two-way choice connectivity problem.This paper mainly expounds the employing workers group of the principle and some associated knowledge structure of the points.Through the understanding of the principle of the algorithm, and in the
9、 application of the function optimization problems,And the optimized combination problems research to understand ATSP problems and one worker ants group algorithm of solving practical problems with the application of research.Keywords : ATSP ;Combinatorial optimization ; People ants group of algorit
10、hm ; TSP第一章引言1.1非对称TSP问题(ATSP )及其求解方法概述非对称旅行商问题是一个NP完全问题，目前求解ATSP问题的主要方法有模拟退 火算法、遗传算法、蚁群算法等。ATSP是指给定n个城市和各城市间的距离，要求确定一条经过各个城市当且仅当一 次的最短路线，并且这N个城市之间两两城市的往返距离不一定相等。它是一种典型的 组合优化问题。基于人工蚁群算法求解ATSP问题，是近年来刚刚兴起的热门课题。然而 在科学管理与经济决策的许多应用领域中，现实世界存在着大量的多目标优化问题。对于 非对称旅行商问题，实际中经常要同时考虑多个目标，如路程最短、时间最短、费用最省、 风险最小等多方面
11、的因素。目标之间往往存在冲突性。如何在多个目标中寻找一个公平、 合理的解是比较复杂的问题。1.2人工蚁群算法的主要思想和特点蚁群算法是受到真实蚁群集体行为的启发而得到的新型优化算法，人工蚂蚁和真实 蚂蚁存在异同。人工蚂蚁和真蚂蚁的蚂蚁一样，是一群相互合作的个体并且他们有着共 同的任务，他们都是通过使用信息素进行间接通讯，而且人工蚂蚁利用了真实蚂蚁觅食 行为中的自催化机制。但人工蚁群也存在真蚂蚁所不具有的一些特性，蚁群这种记忆并 非存储于蚂蚁个体，而是分布在路径上。人工蚂蚁实质上是由一个离散状态到另一个离 散状态的跃迁。信息素的释放时间是根据不同情况而改变的。为了提高系统总体上的性 能。蚁群被赋
12、予了其他的功能，如局部优化、原路返回等。蚁群算法是对自然界蚂蚁的寻径方式进行模似而得出的一种仿生算法。蚂蚁在运动 过程中，能够在它所经过的路径上留下一种称之为外激素(pheromone)的物质进行信息 传递，而且蚂蚁在运动过程中能够感知这种物质，并以此指导自己的运动方向，因此由 大量蚂蚁组成的蚁群集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越 多，则后来者选择该路径的概率就越大。人工蚁群有一定的记忆能力，能够记忆已经访 问过的节点。同时，人工蚁群在选择下一条路径的时候是按一定算法规律有意识地寻找 最短路径，而不是盲目的。例如 在TSP问题中，可以预先知道当前城市到下一个目的 地的距
13、离；每只蚂蚁也可以记录自己走过的节点和路径。1.3主要工作蚁群算法最初是应用在对称的旅行商问题，下面对求解旅行商问题进行简单的说 明。旅行商问题就是指给定n个城市，并给出两两城市间的距离。要求确定一条经过各 城市最短的路径。蚂蚁根据城市的距离和连接边上信息素浓度为变量的概率函数选择下 一城市。为了满足问题的约束条件，在完成一次循环前，不允许蚂蚁选择已经访问过的 城市，需要由禁忌表控制。完成循环后，路径上都会留下浓度不同的信息素。我们可以 通过对信息素浓度的强度，从而选择出最短路径。第二章ATSP问题分析2.1 ATSP问题的数学模型ATSP问题(dijHdji, v i , j = 1, 2,
14、 3,n),非对称旅行商问题较难求解，我们一般是 探讨对称旅行商问题的求解。若对于城市V = v1 , v2 , v3，,vn 的一个访问顺序为 T= t 1 , t 2 , t 3，,ti,tn ，其中 tiV ( i = 1, 2, 3,n)，且记 t n+1 = t 1 ,则旅 行商问题的数学模型为：min L =E ni =1dti, ti+1。ATSP问题表示为一个罗个城市的有向 图G= (N,仝，其中”=1,2涉,基=,俺)叮亘”)城市之间距离为ij n x n,目标函i数为f(W)= 口 I，其中2 n为城市1, 2,，n的一个排列，n+12.2 ATSP问题与TSP问题的比较实
15、质上，ATSP问题是在TSP问题上发展而来的，它们的区别就在于两座城市之间 的往返距离是否相同。例如，有A,B两个城市，在TSP问题中，从A到B的距离是等于 从B到A得距离的，是一个单向选择的连通问题。而在ATSP问题中，从A到B的距离 就不一定等于从B到A的距离，所以这是双向选择的联通问题OTSP较ATSP问题简单点， 在算法实现上也容易点，但实际上可以看作是ATSP问题是TSP问题的发展，在此基础 上多了路径往返的问题。旅行商问题(Traveling Salesman Problem,简称TSP)即给定n个城市和两两城市 之间的距离，要求确定一条经过各城市当且仅当一次的最短路线。其图论描述
16、为:给定图 G =(V, A )，其中V为顶点集，A为各顶点相互连接组成的边集，设D = ( dij )是由 顶点i和顶点j之间的距离所组成的距离矩阵，要求确定一条长度最短的Hamil ton回路， 即遍历所有顶点当且仅当一次的最短距离。旅行商问题可分为如下两类：1) 对称旅行商问题(dij = dji , P i, j = 1, 2, 3,，n);2) 非对称旅行商问题(dij H dji , v i, j = 1, 2, 3,，n)。非对称旅行商问题较难求解，我们一般是探讨对称旅行商问题的求解。若对于城市V二 v1,v2,v3,，vn 的一个访问顺序为T二t1,t2,t3,，ti ,，tn ,其中ti e V
