大型TSP问题的蚁群优化规则研究.doc

硕士学位论文 大型大型 tsptsp 问题的蚁群优化规则研究问题的蚁群优化规则研究 research on ant colony optimization rules of large tsp problem 作者姓名：作者姓名： 专专 业：管理科学与工程业：管理科学与工程 研究方向：管理科学研究方向：管理科学 指导教师：指导教师： 培养单位：商学院培养单位：商学院 i 摘要 大型 tsp 问题的蚁群优化规则研究 旅行商(traveling salesman problem，tsp)问题，是一个古老并且典型 的 np-hard 组合优化问题。当 tsp 问题的规模较小时，通过很多方法都能够快 速高效的求出问题的解，但是随着问题规模的不断扩大,所求解的数量也以指 数的形式快速增加,因此想要获得理想的解集必然要付出巨大的时间代价或是 在短时间内根本无法得到一个理想的结果。tsp 问题特别是大型 tsp 问题的有 效求解，不但有着极其重要的理论价值、学术价值，更能帮助解决社会生活中 的许多实际的问题，其实用性非常之高。因此，这一难题一直是中外众多研究 学者们在不断研究的热点问题。为了在 tsp 问题的研究上有新的突破，人们开 始尝试从一些新的角度来思考并提出新的思路来解决该问题。 随着“群智能”思想的提出，一系列以研究 tsp 问题为基础的智能优化算 法相继出现，比如神经网络、遗传算法、模拟退火算法、线性规划算法、蚁群 算法等，在对 tsp 问题的解决上，这些算法都表现出一定的优势，也存在各自 的缺点。其中，由于蚁群算法的理论原理和 tsp 问题的求解过程具有一定的相 似性，所以对 tsp 问题的处理与其他算法相比具有更好的效果。但人们的目标 远不止如此，一切可以使该算法更加优化的研究一直在继续着。尽管蚁群算法 已经表现出很好的求解性能，但是随着问题规模的放大，算法的弊端就显露无 遗。当面对数据量较多的大型 tsp 问题时，基本蚁群算法或是各种改进算法还 是在存着求解效率低、求解的精度小、易于陷入局部最优等问题。针对这一现 象，本文通过优化蚁群算法的计算规则提出一了种改进的分段多功能蚁群算法， 并以大型 tsp 问题为对象进行以下研究： （1）介绍并描述了 tsp 问题及大规模 tsp 问题的计算复杂性，对其现有的 各种算法进行了对比介绍，并分析了他们各自存在的问题。 （2）对蚁群算法的产生背景、原理、模型和特征进行了详细的介绍，并针 对其优缺点研究展望了它的发展前景与方向。 ii （3）对传统蚁群算法的规则进行优化更新，通过对传统的蚁群算法中的概 率选择模型和蚁群的分类规则进行了改进，提出了一种新的算法-分段多功能 蚁群算法，并对算法中各个参数的设置做了研究讨论。然后分别选取了小规模 tsp 问题和大规模 tsp 问题进行仿真实验。实验结果表明，改进后的算法能够 在合理的运行时间内获得较好的全局最优解。 （4）对本文的研究工作进行了总结，指出了本文研究的缺点和不足，并展 望了蚁群算法今后的研究内容与方向以及改进的蚁群算法在其他领域的应用。 关键词：关键词： tsp 问题，蚁群算法，规则优化 iii abstract research on ant colony optimization rules of large tsp problem the traveling salesman problem (the traveling salesman problem, tsp), is an old and typical np-hard combinatorial optimization problems. if tsps scale is smaller, many ways are able to quickly and efficiently find the solution of the problem, but as the expanding of the problems scale , the number of solution also increase rapidly in the form of index, so getting a ideal solution set is bound to spend huge time or in a short period of time there could hardly be a desirable outcome. tsp problem especially for large tsp, its effective problem solving, not only has an extremely important theoretical value and academic value ,but also of more help to solve many practical problems in social life, its usefulness is very high. therefore, this problem has been a hot issue for the numerous chinese and foreign scholars to research. in order to realize new breakthroughs in the tsp, people began to think from some new angles and propose new ideas to solve the problem. with the arrival of “swarm intelligence“, a series of intelligent optimization algorithms which based on the study tsp problem have appeared, such as neural networks, genetic algorithms, simulated annealing, linear programming algorithm, ant colony algorithm and so on. in solving the tsp problem, these algorithms are certain advantages, but also defective. because the theoretical principles of ant colony algorithm and tsp problem solving process has a certain similarity, compared to other algorithms , ant colony algorithm could deal with the tsp problem with better results. the goal of the people is far more than it, any study that can make the algorithm more optimization has been continued. although the ant colony algorithm has demonstrated good performance in solving tsp problem, but with the enlarged scale of the problem, the drawbacks iv of the algorithm were revealed. when we are dealing with large amount of data from large-scale tsp problem, the basic ant colony algorithm, or a variety of improved algorithm still have some shortcomings,like the solution inefficiency, solving accuracy is small, easy to fall into local optimum, and so on. in allusion to this phenomenon, by optimizing the calculation rules of the ant colony algorithm, this paper proposes an improved segmentation and multi-function ant colony algorithm, and around the large tsp problem the following questions are discussed in this paper： （1）introduction and describes the computational complexity of tsp problem and large scale tsp problem, the existing tsp problem solutions were compared to analyzing their problems. （2）carried out a detailed introduction to the ant colony algorithm for the background, principles, models and features, and studying for the development of direction and outlook for its advantages and disadvantages. （3）optimize and update the rules of traditional ant colony algorithm, with the improving of the probability select model and the classification rules of the ant colony in traditional ant colony algorithm，put forward a new sectional multifunctional ant colony algorithm. research and discuss the settings of various parameter in ant colony algorithm. then selected small-scale tsp problems and large-scale tsp problem doing simulation experiment. the experimental results show that the improved algorithm can obtain better global optimal solution within a reasonable run time. （4）summarize the main research work, pointing out the shortcomings and deficiencies of this study ，and prospect the content and area that ant colony algorithm will be further studied and the application of improved ant colony algorithm in other fields. keywords： v tsp problem, ant colony algorithm, optimization rules i 目目 录录 第 1 章 绪论.1 1.1 研究背景 1 1.2 研究内容 2 1.3 论文的组织结构 3 第 2 章 tsp 问题5 2.1 tsp 问题概述.5 2.2 tsp 问题的定义和数学模型.6 2.3 tsp 问题的已知算法及存在的问题.7 2.3.1 精确求解方法 .7 2.3.2 近似求解方法.9 2.4 tsp 问题的应用12 2.5 本章小结 .13 第 3 章 蚁群算法15 3.1 蚁群算法产生背景 .15 3.2 蚁群算法的原理 .15 3.3 蚁群算法的模型 .19 3.4 蚁群算法的特征 .23 3.5 蚁群算法的前景展望 .24 ii 3.6 本章小结 .25 第 4 章 蚁群算法规则优化-分段多功能蚁群算法.27 4.1 对基本蚁群算法的认知 .27 4.2 分段多功能蚁群算法 .29 4.2.1 多功能搜索策略29 4.2.2 信息素的设置29 4.2.3 转移概率与分段搜索策略30 4.2.4 信息素的更新规则32 4.2.5 改进算法的流程32 4.3 蚁群算法参数分析 .35 4.3.1 信息素残留因子 1-的选择 .35 4.3.2 信息素启发因子的选择37 4.3.3 信息素自启发因子的选择 39 4.3.4 对与的组合选择 41 4.3.5 蚂蚁数目的选择42 4.4 仿真实验 .46 4.4.1 对小规模 tsp 问题的仿真实验46 4.4.2 对一类大规模 tsp 问题的仿真实验50 4.5 本章小结 .51 第 5 章 总结与展望52 iii 5.1 研究工作总结 .52 5.2 研究展望 .52 参考文献.54 致谢.60 iv 第 1 章 绪论 1 第第 1 1 章章 绪论绪论 1.1 研究背景研究背景 由于计算机的发明与普及，使得优化理论有了坚实的发展后盾，优化理论 与方法开始成为一门十分活跃的学科并被并开始受到广泛的关注与研究。他在 经济计划、航天航空、生产管理、工程设计等各行各业都得到了十分广泛的应 用。近几十年来，优化学术领域发生了重大的变化与改革，人工智能和人工生 命技术的发展为该领域注入了新的力量。基于仿生学原理、通过模拟自然现象 或过程的各种优化方法如雨后春笋般相继被提出，如遗传算法(genetic algorithm,ga)、神经网络算法（artificial neural network, ann） 、模拟退 火(simulated annealing,sa)、蚁群算法（ant colony optimization, aco） 等，他们对于经典的优化算法不能或者难以解决的复杂问题有较好的适用性， 显示了无法比拟的优势，并且取得了令人瞩目的成就。 旅行商（tsp）问题既是计算机科学中的一个典型问题，也是组合数学中 的经典问题。tsp 问题从 1932 年产生发展以来就一直受到各个领域众多学者们 的研究与追捧。历经 80 年的研究，虽然获得了大量的研究成果，但是对这个 问题的有效求解至今仍是悬而未决，相信在将来相当长一段时间内也并不能被 彻底解决。现在，旅行商问题被认为是组合优化领域里一个非常经典的 np 难 题，也已经证明出它具有 npc 计算复杂性1。研究 tsp 问题的求解方法的意义 在于：他对于解决一些数据量庞大且复杂的实际应用问题具有重要的参考价值， 基于这一原因，只要是能够简化该问题的求解或者提高求解性能的理论与方法， 都会受到各方面关注和并获得较高的赞扬。现实生活中有许许多多的问题比如 旅游线路的规划与安排、邮递员问题、物流配送路线问题、产品的生产安排等 问题都是 tsp 问题的一种。因此，tsp 问题的求解具有重要的理论意义和实际 意义2，所以对其最优路径的算法研究自然而然的成为当前炙手可热的话题。 虽然我们对于 tsp 问题已经做了大量的研究，但较好的研究成果仅限于小型 tsp 问题中，一旦遇到庞大的数据量，其运算结果往往不如人意。由此可见， 吉林大学硕士学位论文 2 大型 tsp 问题的研究仍是一项亟需处理而又艰巨无比的任务。 蚁群算法（ant colony optimization, aco） ，又称蚂蚁算法, 是由意大 利科学家 marco dorigo 等人在 20 世纪 90 年代初提出来的3，它一种受到自然 界蚂蚁觅食行为过程中通过信息素的沟通来找到蚁穴到食物的最短路径的启发 而提出的一种生物优化算法。蚂蚁通过自身释放的信息素来进行信息交流和相 互的沟通，并能够以此来找到一条通往食物地的最短路径，蚁群算法理论思想 正是借鉴了蚁群的这种群体性能。由于蚁群算法模拟设计了正反馈机制与蚂蚁 间的交互协作机制，利用了蚁群单个个体之间的简单信息传递来完成寻找最短 路径搜索食物的特点来实现算法,使得该过程与 tsp 问题求解具有较大的的相 似性，从而能够对具有 np 难度的 tsp 问题给出较优的解答。蚁群算法在问题 的快速求解基础上，又使全局优化特征以及较短时间内计算结果的合理性得到 了保证（这只是同其他算法的比较而言） ，因此，蚁群算法成为了求解 tsp 问 题最常见的算法之一。同时,该算法还被用于求解背包问题、车辆路径问题 (vehicle routing problem, vrp)等,显示了他在组合优化类问题求解中的优 越性。蚁群算法的持续优化与更新对进一步研究并解决大型 tsp 将有着十分重 要的作用与意义。 1.2 研究内容研究内容 本文将优化的蚁群算法用于大型 tsp 问题的求解，主要研究工作包括： 1.首先收集了国内外关于 tsp 问题和蚁群算法相关资料，并阅读了相关 的文献，对 tsp 问题和蚁群算法的基本思想及理论有了初步的了解；其次从蚁 群算法和 tsp 问题理论、模型、特点、算法实现、实际应用等方面着手做进一 步的深入研究，并对他们的未来发展的方向与趋势做了预测与展望。 2.分析了大型 tsp 问题的处理难度以及基本蚁群算法在其应用中的缺陷， 本文对基本蚁群算法的规则进行了优化并提出了一种改进的蚁群算法分段 多功能蚁群算法。改进的基本思想主要是通过选择概率模型和蚁群分类规则的 优化来实现的，优化目标是使改进算法能够在快速合理的收敛到全局最优解的 第 1 章 绪论 3 基础上保证解的质量，这样算法的搜索能力和性能都得到了显著提高（但是较 之搜索速度，全局最优解仍是我们主要关注的问题） 。改进内容主要包括： （1）改进传统蚁群算法单一蚂蚁种群的求解方法，实现蚁群的多功能分 工。 （2）在求解大型 tsp 问题时，通过分段搜索，适当放大蚁群初期选择概 率，加快解的进化，提升搜索速度；待到一定阶段再恢复正常的选择概率，保 证算法的全局搜索性。 （3）进行模拟仿真实验。利用 tsplib 中的数据分小规模和大规模两类对 改进后的分段多功能蚁群优化算法进行算法测验。通过实验测试结果及与基本 蚁群算法的对比我们得知，此优化算法在合理的运算时间内保证了较高求解质 量，适宜求解大型 tsp 问题。 1.3 论文的组织结构论文的组织结构 本文由四部分组成：研究背景，基础理论介绍，规则优化的分段多功能蚁 群算法求解 tsp 问题的理论与实现，总结与展望。 各章内容组织如下： 第一章介绍了研究背景与研究内容，对论文进行综合性概述，简要介绍了 tsp 问题和蚁群算法，给出了论文的组织结构。 第二章首先对 tsp 问题进行概述，然后详细的介绍 tsp 问题的定义和数学 模型。其次，列举了 tsp 问题现有的各种解决方案，并分析了每种方案存在的 问题，为后文面向大型 tsp 问题时蚁群算法的改进提供依据。最后，介绍了 tsp 问题在现实生活中的一些应用。 第三章从蚁群算法的产生背景出发，详细的分析介绍了基本蚁群算法的理 论原理并从 tsp 问题的角度详述了其它的数学模型、算法步骤和结构流程框架。 本章内容是蚁群算法的基础理论分析，以便后文能在此基础上做深入的研究分 析，针对关键点做作规则优化，是文章能够进入下一步研究的基础与保证。 第四章针对基本蚁群算法在处理大型 tsp 问题时的缺陷，提出了一种基于 吉林大学硕士学位论文 4 规则优化的改进的蚁群算法分段多功能蚁群算法。其改进的思想主要是根 据概率选择模型和蚁群分类规则的优化而实现的。然后利用 tsplib 数据分两 类对改进的蚁群算法进行仿真测试，然后根据测试结果对算法的性能进行了分 析。 第五章主要是对全文进行总结，并对后续的研究提出展望。本文所提出的 改进蚁群算法只是针对tsp问题的应用进行了测验，实验证明该算法对于tsp问 题的求解效用有了提高，但对于其他的领域该算法是否适用还有待进一步探讨。 第 2 章 tsp 问题 5 第第 2 2 章章 tsptsp 问题问题 2.1 tsp 问题概述问题概述 tsp 问题即旅行商问题，又被称为货郎担问题，是一个古老的组合优化问 题4。tsp 问题的最早研究始于欧拉，他经过研究在 1759 年提出了 tsp 问题的 初始雏形，描述为以国际象棋棋盘中 64 个方格为路线，在走遍所有方块的前 提下，如何建立一个从起点出发并最终返回的不重复回路。1948 年，美国兰德 公司开始积极并广泛的推进 tsp 问题的研究，他们在研究中发现该问题的求解 复杂度十分之高，并且会随着原始数据的增加问题难度以指数的形式无限增长， 由此 tsp 问题便成为了在组合优化领域中一个典型的难题，这也吸引了各领域 众多学者们的兴趣并开始积极投入研究。随着理论和科技的发展，对 tsp 问题 的研究不断的深入并取得了较大的成果，它但是还是存在许多尚待解决的问题， 目前已经被归入 np 完全类问题的范畴5。 tsp 问题有很多种类型，如对称型 tsp、非对称型 tsp、平面 tsp、时间窗 tsp 问题等6。在现实社会领域中，tsp 问题也开始被广泛的利用，由于其自身的特殊特点，它也经常被用来比较其他 算法性能的优越性。tsp 问题的历史可以分成以下几个阶段7： 1800-1900 年，首次描述 tsp 问题； 1920-1930 年，给出了 tsp 问题的普遍定义； 1940-1950 年，研究者把 tsp 问题纳入 np-hard 范畴； 1954 年， 第一次解出关于 42 个城市的 tsp 问题的最优解； 1980 年，crowder 和 padberg 求解了 318 个城市的问题； 1987 年，padberg 和 rinaldi 求解了 2392 个城市的问题； 1992 年，以 3038 个城市坐标为基础的 tsp 问题得到解决； 1994 年， tsp 问题的求解能力不断扩展，已经达到了求解 7397 个城市的水平； 2003 年 2 月，hisao tamaki 发现了 tsplib 中 pla33810 的一个次优解； 2004 年 2 月，找到了 pla85900 问题中的一个次优解。 tsp 问题作为一个具有重要的理论意义和广泛应用价值的组合优化问题， 吉林大学硕士学位论文 6 在农业、工业、商业、国防，特别是交通路线等方面的存在大量的运用，因此 受到了诸多领域研究者们的关注。由于遍历所有的路径排列组合数随着城市数 n 的增加呈指数形式增长，所以想要在短时间内精确的获得问题的最优解的是 十分困难的，因此寻求一个有效的近似求解方法是十分必要且更合乎实际的。 经过多年的研究总结，我们发现 tsp 问题的求解的需要克服两大难题：如何避 免算法陷入局部最优；如何提高算法的运行效率。20 世纪 90 年代，学者们提 出了蚁群算法这一理论概念并将其应用于 tsp 问题，且取得了较之其他算法相 对理想的研究成果，目前以至于未来该算法仍旧是众多研究人员的重点研究对 象之一。在随后时间内，遗传算法、启发式搜索方法、模拟退火算法、人工神 经网络等一系列智能优化算法的方法也相继提出并应用到 tsp 问题中，同样得 到了人们广泛的关注。 2.2 tsp 问题的定义和数学模型问题的定义和数学模型 tsp 问题可以定义为：在规模为 n 个城市集合中,要在给出每个城市之间的 距离的条件下找出一条线路最短的路径使得该路径能够不重复的通过所有的城 市并且最终回到出发地。如果某 tsp 问题中有个城市，便可以从中找出m 条回路，当很大时，回路的数目将成为天文数字，此时想要精准的求 2 )!1(m m 出其全局最优解以目前的技术条件来说是十分困难的。 用图论的方法可以将 tsp 问题描述为：在一个正权图 g =(w ,s)中，顶点 的集合为 w =1,2, n，各定点之间的连线集为 s，已知各顶点连线之间的 距离，要找到一个权值最小的哈密尔顿回路，这称之为最佳哈密尔顿回路8。 其数学模型为：设有 n 个城市 v=v1,v2,vn，访问顺序为 t=t1,t2,tn,其中 tn+1=t1(t v,i 1n),则问题就化为求 n i ji t d 1 1, min 其中表示遍历所有的的城市且每个城市不能重复访问，最后再回到起点 的所有的回路的集合。可详细描述如下： 第 2 章 tsp 问题 7 1 1 1 1 ,minccdccdt l l i iid 其中，c,c= , , ,，i=1，2，3,l， 1 c 1 c 2 c 3 c l c 1,2,3,l,ij, i,j=1,2,3,l i c ji cc 上述公式中 c 为城市集合, 为城市的编号，i=1,2,3,l；为编号为 i c ji ccd, 和的两城市之间的距离，且有= 。 i c j c ji ccd, ij ccd, tsp 问题的实质是对于 n 个城市（每个城市对应一个坐标） ，在城市之间相 互连通的情况下，找到一条最短的路径 =v1,v2,vn（其中 vi 表示第 i 个 城市） ，使得 1 1 1 1 ,minccdccdt l l i iid 能取最小值。 2.3 tsp 问题的已知算法及存在的问题问题的已知算法及存在的问题 目前，求解 tsp 问题的主要方法有两大类9:一类是精确求解算法，另一类 是近似求解算法或者称作启发式求解算法，部分近似求解算法也称作智能优化 算法。 2.3.1 精确求解方法精确求解方法 精确求解算法10是 tsp 问题研究初期使用比较多的一种算法，就是在毫无 遗漏的在全局中进行搜索，对有可能的解全部进行一次计算，并在所有的计算 结果中找到果最好的解即最优解。一般来说，传统的求解算法都属于精确求解 算法的范畴。由于精确求解算法本身的特性使其对所求解的要求非常严格，因 此会产生很大的计算强度，一旦遇到一些大规模的数据，算法的运行几乎是不 可能的。尽管精确求解算法存在很大的弊端，但是它还是有一定存在的价值， 并可供其它算法借鉴其思路。常见的精确求解算法主要有： 吉林大学硕士学位论文 8 （1）穷举搜索法 这是求解 tsp 问题最初使用的的一种方法。该方法思路清晰简单，但是却 要花费大量的计算时间。因为它首先要将所有可能的路径组合都列举出来并分 别计算出它们的长度，然后从中选择长度最短的一条路径，以此作为所求的最 优解。如果要用它来解决城市数量为 n 的 tsp 问题，计算量将达到(n-l)!/2。 因此，在数据量较大的实际问题中，运用该方法几乎没有任何实际意义。 （2）动态规划法5 记 a 为集合2,3,n的子集，为以 1 为起点 为终点的将kacak,k a 中所有的点集都走遍的最佳规划线路。当|a|=1 时， ，当|a|1 时， tsp 问题的动态规划方程可以便可以nkdkkc k ,.3 , 2, 3 写为： kajdjkackac jk |,min, 然后再按照上述方程进行迭代求解。 因为动态规划算法的计算时间较长，n 规模的 tsp 问题需要的时间度为 ，计算的空间范围也比较大，达到了，所以该算法一般都不用 n no2 2 nno 2 于处理大规模数据的问题。 （3）分支定界算法 分支定界法11是使用最为广泛的搜索算法之一。它通过建立一个约束条件 对整个解的搜索过程加以控制，该约束条件使搜索解不断的在可控的范围内进 行修改且逐渐向最优解靠近，并最终发现最优解。设定不同的约束条件，定界 的方法和结果也不尽相同。如何设定约束条件是分支定界法最重要内容。现在 最常用的约束限制条件包括以下几种： 1以下属的分派问题为约束条件 2以最小权为 1 的生成树问题为限制界限 3通过匹配问题约束限制 在实际的应用当中，分支定界算法可以且易于与其它算法结合使用，结合 第 2 章 tsp 问题 9 之后的新算法在求解性能上可以进一步的提升。在处理小规模的 tsp 问题时， 可以单独使用分支定界算法进行计算并保证解的有效性，但如果问题的规模过 大，该方法一般只能求出一个模糊的近似解，这时便可以再通过其他算法对这 个近似解加以优化从而获得更好的解集。 （4）线性规划法 线性规划法12作为一种早期的算法，在旅行商问题的研究起步阶段可以算 是效用较高的，但是现阶段对该算法的单独使用已经微乎其微了，主要也是作 为其他算法的一种辅助形式。它的首先根据求解目标确定一个规划问题，再为 该规划问题设立一定得约束条件，在约束条件的限制下产生新的规划范围并不 断缩小规划目标，直至得到目标的最优解。 同分支定界发与其他算法的结合相反，线性规划法是在其它求解算法求出 问题近似解的基础下，将此此近似解作为线性规划的下限，再通过约束条件的 控制计算求出精确解。 2.3.2 近似求解方法近似求解方法 由于精确求解算法的有效性只能在中小规模的问题中体现出来，所以在实 际应用中求解大规模问题就显得力不从心。这时我们采用近似求解算法10或者 智能优化算法来处理大规模的优化问题能获得更好的求解效果。 我们通过公式来衡量比较算法的有效性，其中 c 表示通过近似求 * /cc 解算法得到的最优解，表示问题已知的最优解， 代表可接受的最差情况的 * c 限制条件，若 越小，则说明算法求解的有效性越高。我们所熟知的神经网络 法、插入算法、模拟退火算法、粒子群算法、遗传算法等都是较为典型的近似 求解算法，但更确切的说，他们属于智能优化算法。 （1）插入算法 插入求解算法13的基本思想是先在众多城市中选出两个元城市，把他们 之间的路径连接起来产生一个初始回路，然后将剩余的城市按一定的约束条 件逐个插入到初始回路当中。约束条件必须要保证插入新的城市以后形成的 新回路的路径是所有可能的路径中最短的。根据上述思想，插入求解算法的 吉林大学硕士学位论文 10 主要运算过程分为以下两步： 1、首先确定一个初始回路(i,j)以及准备插入初始回路的目标元素 s。然 后根据设定好的约束条件将目标元素 s 插入到初始回路(i,j)之间，这样变形 成一个新具有三个元素的回路,i,s,j,； 2、根据上述方法再次插入新的目标元素，直到所有待插入的元素都已经 存在这个回路当中，这时包含所有目标元素的最优回路的解便产生了。 插入求解算法的回路解的主要受到两方面的影响，一是如何选取初始的目 标元素，二是怎样确定下一步的插入过程需要插入的合适的目标元素即插入规 则的设定。根据插入规则的不同可将插入算法分成不同的类别，最常用的插入 算法包括:最小值插入法、顶点插入法、邻近域插入法、最远距离插入法等。 每种方法都不是十全十美的，都存在一定的缺陷，在实际应用中需要具体问题 具体分析，才能选出最适合的算法类型。 （2）神经网络算法 人工神经网络 (artificial neural network, ann) 12，是一种模拟人脑 的组织和活动原理，以数据为驱动而构造的非线性映射模型。它类似人脑一样 能处理分析出许多复杂的因果关系，通过对大量的因果关系的聚类和分析，从 中发现目标行为的运动规律并加以利用。对于那些数学模型难以描述的系统它 可以很轻松的进行处理，并具有强大的自组织、自适应、联想记忆、并行处理、 任意逼近非线性和容错鲁棒等特性，在复杂问题的处理中特别适用。人工神经 网络在函数逼近、专家系统、自适应控制、组合优化等众多领域都具有广泛的 应用。 在 tsp 问题得处理上神经网络技术已经日趋成熟，但是由于对该算法的参 数设置没有一个统一的标准，想要获得一个相对理想的参数，必须要在事前对 数据行进多次反复的测试，所以在计算过程中还是存在着很大的缺陷，这是神 经网络的发展过程中面临的最大阻碍。 （3） 模拟退火算法 模拟退火算法是一种将组合优化问题与统计力学的热平衡相结合的求解方 第 2 章 tsp 问题 11 法14，在该算法中我们通常会定义一个能量函数，以此来代替组合优化问题中 的目标函数，在能量物体不断的退火及变化的过程中，其能量逐渐的趋于平衡， 最优解便产生于这个平衡点。 模拟退火算法在运行时对参数的设置要求也非常严格，参数设置的偏差对 最优的计算结果会有很大的影响，用户要通过大量的数据测试和一些经验知识 根据具体问题设置不同的参数，这样就造成了整个算法的庞大的工作量，影响 了算法的实现。 （4）遗传算法 遗传算法15（genetic algorithms，ga）是 j.holland 于 1975 年受到生 物进化理论的启发而提出的16。再生物进化过程中染色体是通过适者生存的 形式来进化的，遗传算法正是模拟了染色体的这种生存过程来对 tsp 问题进行 求解。在对环境最不断的适应和淘汰过程中，最终存活的下来染色体便是最优 染色体，根据这一模式，我们可以通过模拟该过程对 tsp 问题中的全局最优解 进行求解。 遗传算法也是目前应用最为广泛的组合优化算法之一，他可以准确的模拟 自然界中染色体的优胜劣汰模式过程。由于整个遗传算法运行过程几乎没有外 界条件的限制干扰，所以整个遗传算法的操作实现过程是比较简单的6。这也 是遗传算法最为显著的特点和优势。 但是在求解 tsp 的过程中遗传算法也同样的表现出自身的缺点:容易产生 局部最优解以及算法的运行速度较慢。为了克服自身的缺点，遗传算法也经常 与其他算法相结合使用，已达到更好的求解效果。 （5）粒子群优化算法 粒子群优化算法17 (particle swarm optimization，pso)最初是由 kennedy 和 eberhart 提出的，一种基于群智能的新兴迭代优化算法。该算法对 自然界中鸟群的飞行觅食行为进行了模拟,粒子群通过合作与信息交流不断改 变自己的寻优路线直至找到最优解。因为该算法的收敛速度快，对解决复杂优 化问题有较好的效果，所以已被广泛的应用到信号处理、多目标优化和决策支 吉林大学硕士学位论文 12 持模式识别等领域中。将粒子群算法应用于求解 tsp 问题可以是是目前以及未 来的一个新的研究方向。 （6）蚁群算法 蚁群算法是人们在自然界真实蚁群觅食行为的启发下提出的一种群智能生 物模拟算法，算法具有随机搜索性14。由于蚁群的觅食过程与 tsp 问题的行为 模式的类似，因此，用蚁群算法来模拟蚂蚁搜索食物的过程并应用到 tsp 问题 中是十分可取的。由于基本的蚁群算法是在局部搜索的基础上进行全局搜索， 易于陷入局部最优解，影响算法结果的全局最优性，所以许多改进的蚁群算法 相继被提出，本文所的分段多功能蚁群算法即是将蚁群算法的概率选择模型以 及蚂蚁的分类规则进行了改进。详细内容将在下面的章节进行介绍。 2.4 tsp 问题的应用问题的应用 最初，tsp 问题并不是直接应用于实际问题当中的，因为 tsp 最开始仅是 为其他的算法提供思维方向，这些算法通过对 tsp 问题的研究再大量地应用到 各种现实优化问题中。随着研究的发展与成熟，tsp 开始广泛的直接应用于实 际问题，给研究领域带来了新的活力。 对于校车路线的优化问题是 tsp 问题最早的应用。现在，tsp 问题最常见 的应用就是对旅游路线的规划设计6。首先计划好所有要经过的旅游城市，根 据具体情况计算出各个城市之间的旅行距离和旅行费用以后，找出以最节省的 时间和费用访问完所有的旅游城市的最优路径。随着网络的发展以及数字时代 的到来，我们能够更方便快速的解决该问题。只需要找到所有旅行要经过的城 市的网络地图，并利用网络地图的信息把所有要经过的城市的地理位置数据化， 建立一个 tsp 坐标数据，然后再用 tsp 问题的算法进行求解，就可以快速便捷 的得到一条旅行最佳路径。 除了旅游线路设计的应用， tsp 问题在其他很多领域都有着广泛的实际应 用11。如：在物流配送系统中的应用18。随着物流业的蓬勃发展，企业之间的 竞争日益激烈，合理规划配送路线降低企业成本，提高效益，tsp 问题的应用 第 3 章 蚁群算法 13 成为了各个企业提高竞争力的重要措施。其中包括多路径的配送问题、配送车 辆的调度问题等。tsp 问题的其他应用还包括：电路主板上钻孔顺序的安排， 通过 tsp 运算找到最优解便可以找到最节省时间的钻头移动顺序；在基因工程 中的应用等。 目前 tsp 问题已经在很多领域中解决了许多的实际问题，但在时代快速发 展的环境下，各个领域都会出现了信息量的快速增加，因此需要面对信息量庞 大且复杂的决策问题。同时，人们对决策结果的要求也更加严格，这就为我们 的决策带来了双重的困难度。因此，在未来发展的过程中，随着决策数据量的 不断增加，如何快速有效的解决大型 tsp 问题将会是今后的重点研究课题。 2.5 本章小结本章小结 本章主要对 tsp 问题进行了概述，介绍了 tsp 问题的定义和数学模型，并 例举了几种 tsp 问题的已知算法及各自的优缺点。对 tsp 问题的应用做了简要 的介绍，在未来的实际决策中 tsp 问题将会被广泛应用。但是面对数据量较大 的大型 tsp 问题，如何高效的完成决策运算还有待进一步研究。 吉林大学硕士学位论文 14 第 3 章 蚁群算法 15 第第 3 3 章章 蚁群算法蚁群算法 3.1 蚁群算法产生背景蚁群算法产生背景 社会学研究认为大多数动物都是以群体为组织进行活动的，如鱼群、鸟群、 蚁群等，他们的活动往往是带有较强的群体性，群体中的个体行为则是随机而 简单的。但是这些随机简单的个体行为在群体性下却能演变出独立进行筑巢、 觅食、迁徙、防御等复杂程度较高的行为活动，科学家们将动物这种单个个体 以集体的形式表现出来的智能行为称之为“群体智能” 。受到这种动物的社会 性行为（单个个体在群体之间相互合作的行为）的启发，学者们模拟这些社会 性动物群体的系统构成，提出了许多新颖的算法用来求解复杂的优化问题，这 些算法统称为群智能算法19。经过生物学家的长期观察发现，蚂蚁在寻找食物 的时候不管地理环境如何复杂它们总能够发现一条从蚁穴到食物之间的最短路 径，通过进一步研究发现蚂蚁在发现食物后会在返回蚁穴搬救兵的路径上留下 了一种挥发性的化学物质，这种化学物质就是信息素(pheromone)20。研究发 现蚂蚁在发现食物后释放出的信息素强度与食物的品质和质量之间都是成正相 关关系的，其它同类在发现信息素后就会按照信息素的轨迹行进，而蚂蚁在选 择觅食途径时都更倾向于信息素浓度最高的途径。信息素具有引导其它的蚂蚁 迅速觅得食物的功能，它的存在使蚂蚁快速找到蚁穴和食物之间的最短路径成 为可能。可以想象，蚂蚁在选择觅食途径时都更倾向于信息素浓度最高的途径， 蚁群的这种群体觅食行为便可以描述为一种正反馈现象:某一条路径上留下的 信息素越多，即该路径走过的蚂蚁越多，则其他蚂蚁选择这条路径的概率也就 越高，蚁群之间就是通过这种协同工作的方式找到食物的21。蚁群算法就是根 据自然界蚁群“智能”觅食行为而提出的一种以随机搜索为先导、协同工作为 本质的全局优化算法。 3.2 蚁群算法的原理蚁群算法的原理 在昆虫世界中，蚁群是由大量的蚂蚁组成的一个大家庭，是一个表现出高 吉林大学硕士学位论文 16 度社会性、组织性的物种群体。观察发现蚂蚁间彼此的沟通几乎很少借助视觉 和触觉，更多的，在大规模的集体行动上它们主要借助信息素来获取沟通信息。 虽然单只蚂蚁个体的行为极为简单，但是这些单独的个体以群体的形式却能够 通过协同劳动表现出令人惊讶的智能行为。其中工蚁的觅食行为是最容易观察 到的，每个工蚁都具有以下的智能行为:一般时候工蚁都在穴巢附近作无规则 地行走，一旦发现食物，工蚁如果能自己搬回家就独自单独行动，否则就会找 更多工蚁来协助搬运食物。它们会在沿途留下信息素作为指引标记，按照食物 的数量和质量释放相应信息量，其它的蚂蚁经过后就能根据该信息素找到食物， 信息素浓度越高，蚂蚁找到该食物的速度就越快。工蚁的集体觅食行为就是一 种对信息的正反馈，这种对信息的正反馈现象也称之为增强型学习系统，可以 帮助蚂蚁快速正确的找到食物的最短路径22-27。 蚂蚁在最初碰到一个陌生的分叉路口时，会任意选择一条路径前行，在行 进的同时还会释放一种路径长度有关信息素。通常情况下如果该条路径的长度 越大，蚂蚁就越不倾向于选择该路径，所以所释放的信息量就会越小。后来的 蚂蚁也具有同样的习性，再次通过这个路口时会同样会选择信息量大的路径前 行且根据路径的长短再次释放相应的信息素，这便是前文所提到的正反馈原理。 随着不断的选择和淘汰，最优路径上的信息量越来越大，便会将整个蚁群都吸 引到最优路径上来。纵观整个蚂蚁的整个觅食的过程，在信息素的指引作用下， 单个蚂蚁的简单选择行为却在蚂蚁之间相互的沟通作用下发生了质的飞跃，通 过这种自发的组织行为找到了最优的目标路径。 蚁群上述的这种寻优过程包括两个阶段：一是自适应阶段，二是协作阶段。 在自适应阶段，每个蚂蚁对于路径的信息完全不了解，只是随机选择路径 进行搜索，为后来的信息沟通做基础准备。经过一段时间的搜索以后，蚂蚁对 每条路径上都有了一定得了解，寻优过程开始进入协作阶段，这时的搜索便带 有一定的规律性。为了能够产生性能更好的解，蚂蚁通过相互的协作和信息素 的指引，蚂蚁便逐渐的向最优路径靠近知道发现最优路径为止。 第 3 章 蚁群算法 17 在自适应阶段蚂蚁对以后的沟通要做的了解主要包括三个部分: （1）蚂蚁的记忆 在一次循环中，蚂蚁完成一个路径的选择以后，就不会再对该路径进行搜 索，所以需要建立一个禁忌表来防止蚂蚁最路径的重复搜索。 （2）蚂蚁间通过信息素进行交流 信息素是蚂蚁之间进行相互通讯的工具。先经过某路径的蚂蚁会以信息素 浓度的强弱来提示后来的蚂蚁，这样，在别的蚂蚁行进到该路径时就有了一定 的选择依据，不再是盲目随机的选择。 （3）蚁群的集群