基于粒子群算法的TSP问题研究

毕业设计(论文) 题目：基于粒子群算法的TSP问题研究院（系） 理学院 专 业 信息与计算科学 班 级 姓 名 xxx 学 号 xxx 导 师 xxx 2014年 6月 毕业设计(论文) 题目：基于粒子群算法的TSP问题研究院（系） 理学院 专 业 信息与计算科学 班 级 101001 姓 名 xxx 学 号 101001106 导 师 xxx 2014年 6月 西安工业大学毕业设计（论文）任务书院（系） 理学院 专业 信息与计算科学 班 101001 姓名 xxx 学号 101001106 1.毕业设计（论文）题目： 基于粒子群算法的TSP问题研究 2.题目背景和意义： 粒子群算法，也称粒子群优化算法（Particle Swarm Optimization），缩写为 PSO， 是近年来发展起来的一种新的进化算法（Evolutionary Algorithm - EA）。1995 年由Eberhart 博士和kennedy 博士提出。PSO 算法属于进化算法的一种，和遗传算法相 似，它也是从随机解出发，通过迭代寻找最优解。但它比遗传算法规则更为简单，它没有 遗传算法的“交叉”(Crossover) 和“变异”(Mutation) 操作，它通过追随当前搜索到的最 优值来寻找全局最优。 旅行商问题，即TSP问题（Traveling Salesman Problem）是数学领域中著名的优化问 题之一，很多现实问题可归结为TSP问题。粒子群优化算法原理简单，从算法提出的伊 始，就被广泛应用于求解各类优化问题。因此用粒子群算法求解典型的优化问题TSP 问题，具有很高的理论与现实意义。 3.设计(论文)的主要内容（理工科含技术指标）： 1）了解粒子群算法的由来，熟练掌握粒子群算法的原理； 2）了解TSP问题的本质，知道现实中都有哪些问题可以转化为TSP问题，知道此问题在 现实生活中的广泛存在性； 3）用粒子群算法求解TSP问题，要求程序实现（可以用数学软件如matlab之类的来实现）， 并作出理论分析。 4.设计的基本要求及进度安排（含起始时间、设计地点）： 第1 周- 第2 周 对相关资料进行整理 并提交开题报告 第2 周- 第8 周 深入了解相关内容和理论 第9周- 第10 周 完成中期报告和外文翻译 第11周-第16周 对相关内容进行整理，完成毕业设计论文初稿 第17周-第18周 修改论文，准备答辩 5.毕业设计（论文）的工作量要求 实验（时数）*或实习（天数）： 图纸（幅面和张数）*： 其他要求： 指导教师签名： 年 月 日 学生签名： 年 月 日 系（教研室）主任审批： 年 月 日 基于粒子群算法的TSP问题研究I摘 要1995年，肯尼迪（Kennedy）与埃伯哈特（Eberhart）两位学者提出了粒子群算法。粒子群算法具有易理解、易实现和全局搜索能力强等特点，因此该算法问世以后迅速得到科学与工程领域的广泛关注，已经成为发展最快的智能优化算法之一。文章介绍了基本粒子群算法的概念和原理，并介绍了旅行商问题的概念及数学定义。基本粒子群优化算法已经成功地应用于求解连续域问题, 但是，对于离散域问题求解研究还很少。很不幸旅行商问题恰恰就属于离散问题，因此接下来文章介绍了几种可以解决旅行商问题的改进粒子群算法，并详细介绍了其中的两种：引入模糊矩阵的改进粒子群算法和引入交换序和交换算子的改进粒子群算法。这两种改进的粒子群算法实现了对旅行商问题的求解。实验结果表明这两种改进粒子群算法的有效性。关键词：粒子群算法； 全局搜索； 旅行商问题； 连续； 离散 Particle swarm optimization (PSO)-based algorithm For the traveling salesman problem (TSP) AbstractThe Particle swarm optimization (PSO) algorithm originally developed by Kennedy and Eberhart in 1995.Thealgorithmhasthecharacteristicsthat easy to understand,easy to implement andglobalsearchingability.It had gotextensiveattentioninthefieldofscienceandengineering as soon as the algorithm was proposed. By now,PSO hasbecameoneof themost popular optimization algorithms. We introduced the concepts and some principles of PSO and the mathematical definition of TSP. We know PSO has succeeded in many continuous problems, but there is less research about discrete problems. Unfortunately, TSP just belong to such a problem.According to this, some improved PSO algorithms to solve TSP was introduced,and two of them was described in detail. One algorithm is improved by introduce the fuzzy matrix and the other is improved by introduce the permutation concept.We applied the two improved PSO algorithms on the problem of TSP successfully.The results shows both of them are available .Keywords: The Particle swarm optimization; Global Search; Traveling salesman problem; Continuous; Discrete 西安工业大学毕业设计（论文）目 录摘 要IAbstractII1 绪 论11.1 背景和意义11.2 国内外研究的进展情况11.3 主要内容21.4 结构安排22 基本的粒子群算法32.1 思想起源32.2 算法的原理42.3 算法的流程和流程图52.4 算法的优缺点分析83 旅行商问题93.1 TSP问题介绍93.2 TSP问题定义94 改进的粒子群算法求解TSP问题114.1 改进的粒子群算法简介114.2 引入模糊矩阵的粒子群算法求解TSP问题124.2.1旅行商问题的解用模糊矩阵表示124.2.2引入模糊矩阵的粒子群算法重新定义134.2.3引入模糊矩阵的粒子群算法求解旅行商问题的具体操作154.3 引入交换算子和交换序的粒子群算法求解TSP问题184.3.1引入交换算子和交换序的粒子群算法定义和流程184.3.2实验结果与参数设置205 结 论27致 谢29毕业设计（论文）知识产权声明30毕业设计（论文）独创性声明31参考文献32附 录 1 程序34附 录 2 外文翻译原文45I 西安工业大学毕业设计(论文)1 绪 论1.1 背景和意义粒子群算法（Particle Swarm Optimization）,缩写为PSO。1995年由肯尼迪（Kennedy）与埃伯哈特（Eberhart）两位学者所提出，他们发明PSO灵感来源于对鸟群捕食行为的研究。粒子群算法的理论基础是把每一只鸟看作为一个粒子，并赋予该粒子（个体）拥有记忆性，并能通过与粒子群体中的其他粒子之间的通信而寻求到最适解。目前，粒子群算法在函数优化，神经网络训练，模糊系统控制，组合优化入侵检测，以及决策调度等多个领域得到广泛的应用。粒子群算法有较强的全局搜索能力，但也容易陷入局部极值导致早熟。 旅行商问题（Travelling Salesman Problem），英文缩写为TSP，是数学领域中著名问题之一，也是一个典型的NP完全问题。问题描述为：假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。目前解决旅行商问题的主要算法有：蚁群算法，免疫算法，遗传算法等等。粒子群算法中每个粒子由一个多维向量表示, 其下一代粒子的飞行方向和速度由个体最优解和群体最优解向量来修正, 基本粒子群算法已成功应用于求解连续域问题,但解决离散问题还是存在很大困难的。为了解决诸多实际工程中的离散问题, 通过引入交换序和交换因子重构了粒子群算法并成功应用于小规模TSP问题求解。也可以通过引入模糊矩阵重构粒子群算法同样成功应用于旅行商问题求解。本文会详细介绍引入模糊矩阵的粒子群算法和引入交换序和交换因子的粒子群算法并总结各自的优缺点。由于旅行商问题的特殊性，因此任何能使该问题的求解得以简化的方法，都将受到高度的评价和关注。因此，用粒子群算法去解决旅行商问题具有很高研究价值。1.2 国内外研究的进展情况1995年由肯尼迪（Kennedy）与埃伯哈特（Eberhart）两位学者在IEEE国际神经网络学术会议发表了题为“Particle Swarm Optimization”的论文，标志着PSO算法诞生。1999年美国的Clerc M.发表的文章自适应粒子群优化算法对PSO算法的收敛性进行了研究，证明采用收敛因子能够确保算法的收敛。1999年Suganthan P N.在发表的文章优化与邻域第一次提到带邻域操作的SO模型，克服了PSO模型在优化搜索后期随迭代次数增加和搜索结果无明显改进的缺点。2001年来自普度大学工程与技术院的Parsopoulos K E.提出将拉伸技术用于PSO最小化问题的求解，力图避免PSO算法易陷于局部最小值的缺点。2004年由来自中国江苏科技大学电子信息学院的高尚,韩斌,吴小俊，杨静宇等学者，他们结合了遗传算法、蚁群算法和模拟退火算法的思想, 对粒子群算法进行了优化并提出了混合粒子群算法，通过这种优化的粒子群算法使得组合优化问题很容易解决。1.3 主要内容 清楚基本的粒子群算法的原理并知道如何应用；了解旅行商问题的本质及生活中哪些问题都可以转化为旅行商问题；了解有哪些改进的方法可以求解旅行商问题，并选择几种改进的粒子群算法详细介绍。使用Matlab实现引入交换序和交换算子的改进粒子群算法并解决旅行商问题。并对粒子群算法的参数进行研究，选出粒子群算法解决旅行商问题效率比较高的参数。最后，总结各种改进粒子群算法解决旅行商问题的优点和缺点。1.4 结构安排 第一章绪论中分别介绍了基本粒子群算法和旅行商问题，以及国内外研究现状和论文所研究的主要内容。第二章详细介绍了基本粒子群算法思想起源和算法具体流程。第三章详细介绍了旅行商问题概念，数学定义和应用领域。第四章中，首先，介绍了几种可以求解旅行商问题的改进粒子群算法，并详细介绍了其中的两种。然后，使用Matlab实现了一种求解旅行商问题的改进粒子群算法。在附录中给出了具体实现代码。29 西安工业大学毕业设计(论文)2 基本的粒子群算法2.1 思想起源1995年IEEE国际神经网络学术会议发表了题为“Particle Swarm Optimization”的论文，标志着粒子群优化(Particle Swarm Optimization, PSO)算法 1诞生。粒子群算法是一种基于迭代的优化工具。系统初始化一组随机解，粒子在解空间通过个体间的协作与竞争，实现复杂空间最优解的搜索。同时，粒子群算法又不像其他进化算法那样对个体进行交叉、变异、选择等进化算子操作，而是把个体看作是在D维搜索空间中没有质量和体积的粒子，每个粒子被随机初始化位置和初速度，粒子通过参考全局最佳位置和局部最佳位置，进行进化也就是改变他的位置和速度。通过这样不断的迭代来求解问题。粒子群算法具有很好的生物社会背景2而且易理解、参数少、易实现。目前在科学研究与工程实践中得到了广泛关注3-10。人工生命的主要研究领域之一是探索自然界生物的群体行为，从而在计算机上构建其群体模型。生物仿真学给人类的生活带来了巨大的改变，因此科学家对研究此课题有很大的兴趣，生物学家Craig Reynolds在1987年提出了一个非常有影响的鸟群聚集模型7，在他的仿真中，每一个个体遵循：(1) 避免与邻域个体相冲撞；(2) 匹配邻域个体的速度；(3) 飞向鸟群中心，且整个群体飞向目标。仿真中仅利用上面三条简单的规则，就可以非常接近的模拟出鸟群飞行的现象。1990年，生物学家Frank Heppner也提出了鸟类模型8，它的不同之处在于：鸟类被吸引飞到栖息地。在仿真中，一开始每一只鸟都没有特定的飞行目标，只是使用简单的规则确定自己的飞行方向和飞行速度（每一只鸟都试图留在鸟群中而又不相互碰撞），当有一只鸟飞到栖息地时，它周围的鸟也会跟着飞向栖息地，这样，整个鸟群都会落在栖息地。1995年，美国社会心理学家James Kennedy和电气工程师Russell Eberhart1共同提出了粒子群算法，其基本思想是受对鸟类群体行为进行建模与仿真的研究结果的启发。他们的模型和仿真算法主要对Frank Heppner的模型进行了修正，以使粒子飞向解空间并在最好解处降落。Kennedy在他的书中描述了粒子群算法思想的起源。自20世纪30年代以来，社会心理学的发展揭示：我们都是鱼群或鸟群聚集行为的遵循者。在人们的不断交互过程中，由于相互的影响和模仿，他们总会变得更相似，结果就形成了规范和文明。人类的自然行为和鱼群及鸟群并不类似，而人类在高维认知空间中的思维轨迹却与之非常类似。思维背后的社会现象远比鱼群和鸟群聚集过程中的优美动作复杂的多：首先，思维发生在信念空间，其维数远远高于3；其次，当两种思想在认知空间汇聚于同一点时，称其一致，而不是发生冲突。但思维背后的社会现象还不能完全理解鸟类的社会行为。显然，我们的模仿协调性远不及鸟类自身行为的协调性。综上，从开始的简单鸟类的社会行为模仿到复杂的鸟类社会行为模仿，最后模仿越来越接近真实的鸟类社会行为，这就是粒子群算思想诞生的过程。2.2 算法的原理 粒子群优化算法首先初始化一群随机粒子，这些初始化的粒子都是空间搜索的潜在解，并且每个粒子都有一个被优化函数决定的适应值（fittness），每个粒子还有一个速度决定它们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索1。粒子通过跟踪两个极值来更新自己；第一个就是粒子本身所找到的最优解，这个解称为个体极值（pbest）；另一个极值是整个种群目前找到的最优解，这个极值是全局极值（gbest）。假设在一个维的目标搜索空间中，有个粒子组成一个群落，其中第个粒子表示为一个维的向量，。第个粒子的“飞行”速度也是一个维的向量，为 ，。第个粒子目前为止搜索到的最优位置称为个体极值，为 ，。整个粒子群目前为止搜索到的最优位置为全局极值，为 在找到这两个最优值时，粒子根据如下的公式(1)和(2)来更新自己的速度和位置12： (2.2.1) (2.2.2)其中为惯性权重，为学习因子，为0到1之间均匀分布的随机数。粒子群算法的性能很大程度上取决于算法参数的选择，选取较好的参数，不仅能缩短算法执行的时间，而且可以提高解决问题的准确性。这其中决定算法性能的参数有：粒子数、惯性权重、学习因子、等，各个参数的选择一般情况下可以参考如下：l 粒子数：粒子数的多少选择一般是根据问题的复杂性决定的。对于一般优化问题取20到40个粒子完全可以得到很好的结果。l 粒子的维度：这是由优化问题决定，就是问题解的维度。l 学习因子：学习因子使粒子具有自我总结和向群体中优秀个体的学习能力，一般取值范围为0到4。l 惯性权重：决定了粒子对当前速度继承多少，合适的选择可以使粒子具有均衡的探索能力和开发能力。惯性权重越大粒子的全局搜索能力越强，反之惯性权重越小粒子的局部搜索能力越强。2.3 算法的流程和流程图算法的流程如下： 步骤1：初始化粒子群，包括群体规模，每个粒子的位置和速度；步骤2：计算每个粒子的适应度值，并将当前微粒的位置和适应值存储在pbest中，将所有粒子的pbest中适应值最好的个体存储在gbest中； 步骤3：根据公式(2.2.1),(2.2.2)更新粒子的速度和位置；步骤4：每个粒子，用它的适应度值和个体极值比较出较优为新； 步骤5：所有粒子的新的pbest选出最优的，为新的gbest；步骤6：如果满足结束条件(通常为预设的计算精度或到达最大循环次数)退出，否则返回步骤3。 算法的流程图如下： 开始求出整个群体的全局最优值求出每个粒子的个体最优计算每个粒子的适应值初始化每个粒子的速度和位置根据方程(2.2.1)对粒子的速度进行进化根据方程(2.2.2)对粒子的位置进行进化是否满足条件 否是 输出结果 总结：对于这种连续性的问题,用粒子群算法求解,只要随着粒子数和迭代步数的增加,求解的结果会不断趋近最优解。2.4 算法的优缺点分析 粒子群算法的优点：粒子群优化算法(PSO)是模拟鸟群觅食过程中的行为提出的一种基于群体智能的演化计算方法。该算法易于描述，在求解过程中只有非常少的参数需要调整并且无集中控制约束，不会因个体的故障影响整个问题的求解，确保了系统具备很强的鲁棒性，相比其它演化算法，只需要较少的函数计算次数就可达到收敛，因此能以较大概率找到问题的全局最优解。最后该算法最大的优势也在于编程简单，易实现。粒子群算法的缺点：在求解全局最优解的过程中对于有多个局部极值点的函数，容易陷入到局部极值点中，得不到正确的结果。此外，由于粒子群算法问世时间不长在搜索纠结过程中缺乏精密搜索方法的配合，导致使用粒子群算法这种方法往往不能得到精确的结果。再则，PSO方法提供了全局搜索的可能，但并不能严格证明它在全局最优点上的收敛性。因此，PSO一般适用于存在多个局部极值点而并不需要得到很高精度的优化问题。对于本文而言，基本粒子群算法有一个致命的的缺点，它速度更新和位置更新都是由特定的连续函数决定的，所以它只能解决连续性优化问题，对于求解离散问题存在困难。 西安工业大学毕业设计(论文)3 旅行商问题3.1 TSP问题介绍旅行商问题(Traveling Salesman Problem,简称TSP)是一个典型的NP问题也是一个典型的组合优化问题。旅行商问题描述如下：给定n个城市及两两城市之间的距离，求一条经过各城市一次且仅一次的最短路线。对于n个城市的TSP问题，存在着（n-1）! /2条可能的路径，随着城市数目n的增长，可能路径的数目以n的指数倍增加。如果使用穷举法搜索，需要考虑所有可能的情况，并两两比较，找出最优解，那么可搜索的路径及距离之和的计算量将正比于n! /2，算法的复杂度呈指数增长，要求出旅行商问题的最优化解是很困难的，这也是该问题被认为是NP问题的原因。同样不幸的是，旅行商问题为离散问题，使得可以解决该问题的方法更少。因此，任何可以求解旅行商问题的方法都应被高度关注。在生产生活中许多问题都可以转化为旅行商这类问题的模型，因此旅行商问题具有很高的实际应用价值，例如：城市管道铺设优化、物流行业中的车辆调度优化、制造业中的切割路径优化以及电力系统配电网络重构等现实生活中的很多优化问题都可以归结为旅行商模型来求解，目前旅行商问题应用的一个非常重要方面就是无人飞机的航路设计问题，即事先针对敌方防御区内的威胁部署和目标的分布情况，对无人作战飞机的飞行航路进行整体规划设计，可以综合减小被敌方发现和反击的可能性降低耗油量，从而显著提高UCAV（无人战斗机）执行对地攻击（或侦察）任务的成功率。3.2 TSP问题定义 设n为城市数目为n*n阶距离矩阵，代表从城市i到城市j的距离，。问题是要找出访问每个城市且每个城市恰好只访问一次的一条Hamilton回路，且其路径的总长度是最短的。这条Hamilton回路可以表示为(1,2,.,n)的所有循环排列的集合，即为(1,2,.,n)的排列， 表示访问第i个城市后访问第j个城市。 目标函数（在粒子群算法中也可以叫做适应值函数）：城市Hamilton回路总长度为： (3.2.1)引入决策变量： (3.2.2)旅行商问题定义虽然非常简单，使用穷举法可以让旅行商得到确定的最优解，但随着需要访问城市数目的增加，会出现所谓的组合爆炸现象。所以，城市数目比较多的时候使用穷举搜索策略几乎是不可能做到的。 西安工业大学毕业设计(论文)4 改进的粒子群算法求解TSP问题4.1 改进的粒子群算法简介 由第二章的基本粒子群算法介绍，我们可以看出基本的粒子群算法对适应度函数是有连续的要求。因此，基本粒子群算法在很多连续优化问题中得到成功应用，但粒子群算法不能直接应用到离散问题中，那么，如果非要用它解决离散问题，就必须对算法进行改进。我们需要对方程(2.2.1)和方程(2.2.2)进行改写并且重新定义方程中加法和乘法的含义。下面我将介绍几种改进的粒子群算法，这些算法可以比较好的解决旅行商这种离散型问题。王翠茹，张江维，王 等1314对粒子群优化算法进行了改进后，粒子不仅根据自身和同伴中最好的个体调整自己的飞行速度，而且按照一定的概率向其他个体学习，这种强化后的学习行为更符合自然界生物的学习规律，更有利于粒子发现问题的全局最优解。同时借鉴单点调整算法思想，提出了调整因子和调整序概念用以重构粒子群算法。傅 刚15认为，用粒子群算法解决旅行商问题时，调整因子的先后顺序决定下一代种子的优劣，以及能否很快地收敛到最优值，如何恰当地解决惯性权重个体间的协作和个体历史最优以及群体最优对个体的影响是快速高效解决这一问题的关键。旁巍，王康平，周春光等16通过引入模糊矩阵提出了一种改进的粒子群优化算法，采用模糊矩阵来表示粒子的位置和速度，并重新定义速度和位置更新公式中的各种运算符号，这种改进的粒子群算法给求解旅行商问题提供了一种新思路。基于这种思路下文将会介绍详细的实现过程。郭文忠等17在介绍目前已经有多种针对惯性权值的研究的基础上，提出引入模糊技术，并提出了佳粒子距的概念，并给出了一种惯性权值的模糊自适应调整模型及其相应的粒子群优化算法，使用不同的惯性权值更新同一代种群，用于TSP问题的求解。实验结果表明改进后的算法不仅在求解组合优化问题中的有效性，而且同时提高了算法的性能，加快了收敛速度。2012年中国学者易云飞，陈国鸿18提出了基于k-means的改进粒子群算法求解旅行商问题。也是一种基本粒子群算法进行了改进，每一步都借鉴贪心算法的思想取局部最优，这样产生的初始种群全局最优值已经比较接近问题的解，可以节省搜索时间,提高算法收敛速度。针对粒子群算法易陷入局部最优的缺陷，采取了适合于求解旅行商问题的基于k-means的改进策略,对粒子群进行聚类分析，实现了粒子之间的信息交换,扩大了粒子的搜索空间。两个种群同时寻优,种群内部独立进行粒子群算法进化，种群个体最优之间以一定概率进行交叉，两个种群同时寻优可以减小算法陷入局部最优的概率，种群间个体最优的交叉能够增强两种群间以及粒子间的信息共享，及时传递最优值信息，提高粒子向更好解进化的速度。实验结果表明这种改进粒子群算法是有效的。西南大学计算机与信息科学学院的教授王文峰，刘光远，温万惠19共同进行了求解旅行商问题的自逃逸混合离散粒子群算法研究。这种算法是结合自然界中种群密度过大时，个体自动寻找栖息地的习性，提出了一种自逃逸思想：从候选边集合中吸收新边，给陷入局部区域的粒子一个变异，使其跳出局部区域。自逃逸思想提高了粒子群算法的全局搜索能力，成功地克服了早熟的缺陷。实验结果表明，自逃逸的粒子群算法比混合蚁群算法具有更好的效率和收敛速度, 尤其在较大规模的实例上更具优势。4.2 引入模糊矩阵的粒子群算法求解TSP问题4.2.1旅行商问题的解用模糊矩阵表示在用模糊矩阵16表示旅行问题的解前，我们首先引入以下几个定义：定义1：一个城市为n的旅行商问题，设集合s为旅行商问题的一个解序列，s可以表示为，其中表示旅行商问题的解即Hamilton回路中第i个结点。定义2：一个城市为n的旅行商问题，设集合M是旅行商问题的结点集合，M可以表示为：，那么表示旅行商问题中编号为i的具体结点。对上述的定义1和定义2，进行解释：集合S中的每个元素，表示旅行商问题可行解中按照访问的先后次序的第i个结点，即已访问了i-1个结点，即将访问第i个结点，还有n-i个结点需要访问；对于集合M中的元素表示的是旅行商问题中编号为i的结点(这个结点的顺序不发生改变)。则整个状态空间可以表示为S和M的笛卡尔积： S与M的模糊关系R有如下意义： (4.2.1) 是隶属度函数，表示在一个可行解中第 i 个要访问的点选择编号为j的结点的隶属度。显然，如果我们有了这个隶属度函数，那么我就可以确定一个模糊矩阵。下面介绍旅行商问题的解是怎样用模糊矩阵表示的。在上文定义中已经分别提到了集合和集合 它们的模糊关系可以用模糊矩阵来表示，因此，从S到M的模糊关系可以写成： (4.2.2)其中，它表示集合S中第i个元素与集合M中第j个元素对于关系R的隶属程度。4.2.2引入模糊矩阵的粒子群算法重新定义 基于上面提出的用模糊矩阵表示旅行商问题的解, 进而提出了一种改进的粒子群算法。首先重新定义速度和位置的更新公式(2.2.1)、(2.2.2)中的符号与操作符。粒子的位置是要用来表示旅行商问题的解，因此定义为公式（4.2.2）这种形式： （4.2.3） 粒子的速度重新定义为： （4.2.4）操作符“乘法”的重新定义: 我们使用符号“”表示新的乘法, 设a 是一个实数, 则： （4.2.5）操作符“减法”的重新定义: 我们使用符号“”表示新的减法,则： （4.2.6）操作符“加法”的重新定义: 我们使用符号“”表示新的加法,加法可以是速度之间的加法也可以是位置和速度之间的加法则分别表示为： （4.2.7） （4.2.8）根据以上对粒子群算法的重新定义，可以把公式（2.2.1）、（2.2.2）分别改写。速度更新公式为： （4.2.9）其中为惯性权重，为学习因子，为0到1之间均匀分布的随机数，表示第i个粒子第t次迭代后的速度，表示第i个粒子第t次迭代后的位置，表示第i个粒子第t次迭代后的局部最好位置，表示第i个粒子第t次迭代后的全局最好位置。位置更新公式为： （4.2.10）4.2.3引入模糊矩阵的粒子群算法求解旅行商问题的具体操作基本粒子群算法通过引入模糊矩阵把公式（2.2.1）、（2.2.2）分别改写为公式（4.2.9）、（4.2.10），为了确保改写后粒子群算法公式能够适用这种矩阵的变化，因此，在初始化时需要有许多特定的条件。下面先介绍这种改进的粒子群算法是如何初始化的。初始化位置： （4.2.11）矩阵中的元素是按照如下条件随机生成：a. （4.2.12）b. （4.2.13）速度初始化： （4.2.14）随机产生速度中元素必须也满足下面条件： （4.2.15）下面引入几个引理，能很好的说明为何会有如此的条件限制初始位置和初始速度。引理1：设a是一个实数, 如果速度V满足条件,则也满足条件。引理2：如果位置 X满足,并且位置V满足, 则也满足。引理3：如果位置和满足,则满足条件。引理4：如果速度和速度满足, 则也满足。根据上述引理可以得到如下结论，在需要公式(4.2.9)和(4.2.10)进行更新的矩阵,若矩阵满足等式(4.2.13)和(4.2.15),则在以后的更新迭代中,更新后的速度将总是满足条件(4.2.15)，并且更新后的位置也将总是满足条件(4.2.13)。这个结论可以用数学归纳法进行证明，由于证明过程比较简单，所以在此我就不详细说明。有了以上结论我们可以成功的把粒子群算法思想应用于离散的旅行商问题中。但这不能说粒子群算法已经可以解决旅行商问题了，这其中还存在有些问题需要解决。这其中最主要的问题是:在每次迭代后，位置矩阵中的元素可能产生负值，这与条件（4.2.13）是不相符的。因此，在每次迭代后都应该对元素中是否出现负数进行检测。对于不符合条件的元素可以采用如下规范化进行操作： 首先将矩阵中所有为负数的元素清零, 然后将位置矩阵(4.2.3)在不违反(4.2.12)的情况下进行如下的变化： （4.2.16）算法流程描述：在介绍算法流程前，首先介绍一个概念：非模糊化（也就是模糊化的一个逆过程）。非模糊化采用的方法为：“最大数法”，是非模糊化的常用方法, 在这种方法中, 用一个标志数组记录是否选择了矩阵中的列,并用一个路径数组来存储路径解。首先所有的列都标记为“未选择”,然后对于矩阵中的每一行,选择未被其他行选择过的并且具有最大值的那个元素,然后将这个元素所在的列标记为“选择”,并且该列的列号被记录在路径数组中,表示在本行中选择序号为该列号的节点。当所有的行都被处理完成后,就可以从路径数组中得到解路径以及解路径的费用值。采用这种方法,能够保证最终得到旅行商问题的可行解【16】 。步骤1：初始化步骤1-1：设置粒子群算法中粒子的个数，和最大迭代次数，对于解决旅行商问题的粒子算法中的迭代次数设置非常关键，因为迭代次数一般为算法终止条件，因此选择合适的迭代次数对算法的性能影响非常大。步骤1-2：应用上述初始化过程，对粒子群算法中的每个粒子进行初始化得到一个随机的位置，并且随机初始化得到一个随机速度。最后让这些初始化的粒子位置为粒子的局部最优解，并在这些初始化后粒子群中选出全局最优解。步骤2：计算粒子群算法中每个粒子的速度和位置。步骤2-1：用公式（4.2.9）更新每个粒子的速度。步骤2-2: 用公式（4.2.10）更新每个粒子的位置。步骤2-3：对新位置矩阵进行非模糊化,计算新位置的费用。如果新位置的费用比当前局部最好解的费用还要小,则用新的位置更新当前的局部最好解。步骤3：如果粒子群算法中粒子的局部最优解中存在优于当前的全局最优解时，则用此局部最优解来更新当前的全局最优解。步骤4：判断当前的迭代次数是否达到预先设定的最大值，如果大于转步骤5，否则转步骤2.步骤5：输出最好路径和费用。总结：这种改进的粒子群优化算法，其算法的流程和基本的粒子群算法的流程相似，只是在一些计算方面有些区别。该算法在解决旅行商这类离散型问题表现的不是那么高效，但它也是粒子群算法解决离散型问题的新尝试。值得注意的是,该算法不仅仅能够解决旅行商问题, 经过修改后也能够解决一般路由问题。由于旅行商问题的 特殊性,模糊矩阵的规模是n2,在一些简单的路由问题中,可以缩减矩阵的规模。另外, 能否寻找更好的非模糊化的方法, 也是今后的工作需要解决的问题16。4.3 引入交换算子和交换序的粒子群算法求解TSP问题4.3.1引入交换算子和交换序的粒子群算法定义和流程黄岚等，王康平等11通过引入交换子和交换序的概念，并对基本公式中的符号赋予新的含义，构造了一种特殊的粒子群优化算法，这种改进的粒子群算法使得用粒子群算法思想解决离散问题成为可能。后来Clerc，M12重新定义了运算符号和规则，并用于求解离散问题，重新定义后的粒子群算法相比以前的算法有了很明显的改观。下文将会把这种改进的粒子群算法应用到解决旅行商问题中。引入交换算子和交换序是另种一种改进的粒子群算法去解决旅行商这种离散型问题的方法。这种方法也是粒子群算法应用到离散型问题的第一次尝试的方法。此方法的问世，使得粒子群算法的应用领域反生巨大的改变。下面先介绍交换算子和交换序的概念。交换算子：是用来交换一个有序序列中元素的位置，一个交换算子可以使这个有序序列中两个元素位置发生调换。具体到改变旅行商问题中，表示旅行商的可行解序列发生改变，改变后的结果仍是旅行商问题的可行解。用SO（i，j）表示一个交换子，i，j就表示序列中第i个元素和序列中第j个元素的位置发生调换。例：序列S=（1，2，3，4），交换算子SO（1，2），用表示交换算子作用于序列S，即SSO变化后得到=（2，1，3，4）这里的被赋予特定含义。交换序：一个或多个交换子的有序队列就是交换序。如交换算子SO，SOO,SOOO,SOOOO.组成交换序SS，那么SS=（SO，SOO，SOOO，SOOOO.）。当SS作用一个序列就等于这个交换序中每个交换算子作用于这个序列。例：序列S=（1，2，3，4）交换序SS(SO,SOO),SO(1,2),SOO(3,4)，那么SSS=SSOSOO=（2，1，4，3）。在上边两个概念基础上再定义几个概念：交换序的等价集：不同的交换序作用于同一解上可能产生相同的新解, 所有有相同效果的交换序的集合称为交换序的等价集。基本交换序：在交换序等价集中, 拥有最少交换子的交换序称为该等价集的基本交换序。例：设给定两个解路径A =（1，2，3，4，5）和B=（4，3，2，1，5）,需要构造一个基本交换序 SS, 使得BSS= A可以看出A（1）=B（4），A（2）=B（3），A（3）=B（2），A（4）=B（1），A（5）=B（5）可以看出第一个交换算子为SO（1，4，）第二个交换算子为SO（2，3），第三个交换算子为SO（3，2），第四个交换算子为SO（4，1），第五个交换算子为SO（5，5）那么SS=（1，4），（2，3），（3，2），（4，1），（5，5），即SS=BA，这里的和被赋予新的含义。在引入交换序和交换序列后基本的粒子群算法的公式（2.2.1）需要改写，计算符号的含义也需要改变。粒子速度更新公式改写为： （4.3.1）这个公式的和的含义于上文概念介绍提到的含义相同；和为0到1之间的随机数，表示第i个粒子第t次迭代后的速度，表示第i个粒子第t次迭代后的位置，表示第i个粒子第t次迭代后的局部最好位置，表示第i个粒子第t次迭代后的全局最好位置；表示基本交换序中的所有交换子以概率 保留 ；同理表示基本交换序中的所有交换子以概率 保留 ；可以看出和的值越大保留的交换子就越多。粒子群算法思想的向局部最好解和全局最好解学习，改变移动方向在这个速度更新公式中也得到体现。粒子的位置更新公式保持原来的基本粒子群算法的公式（2.2.2），只是加法的含义发生改变，因此新位置更新公式可以改写为： （4.3.2）算法的步骤：（1）初始化粒子群, 即给群体中的每个粒子赋一个随机的初始解和一个随机的交换序；( 2) 如果满足结束条件一般为最大迭代次数, 转步骤( 5) ;( 3) 根据粒子当前位置 , 计算其下一个位置 ，即旅行商问题新的可行解；具体到一下步骤：1) 计算 和 之间的差A , A = 其中A 是一个基本交换序， 表示A 作用于得到 ；2) 同理，计算B = , 其中B 也是一基本交换序；3) 根据（4.3.1）式计算速度, 并将交换序转换为一个基本交换序 ;4) 计算搜索到的新解 （4.3.2）；5) 计算解的适应度，如果找到一个更好的解, 则更新 ；( 4) 比较每个粒子的最好适应度值，如果整个群体找到一个更好的解, 更新 ，转步骤( 2)；( 5) 显示求出的结果值（本文中对该问题实现使用图像输出结果，充分利用Matlab的强大绘图能力）。4.3.2实验结果与参数设置设10个城市的二维坐标分布为：city10=0.4 0.4439;0.2439 0.1463;0.1707 0.2293;0.2293 0.761;0.5171 0.9414; 0.8732 0.6536;0.6878 0.5219;0.8488 0.3609;0.6683 0.2536;0.6195 0.2634;这十个城市的最短Hamilton回路为2.691当粒子数为30，迭代次数取100，和都取0.25时运行结果如下：注：第二个图像中上边线表示平均距离，下边线表示最短距离，以下所有这种图像都是本规则。当粒子数为30，迭代次数取100，和都取0.5时运行结果如下：经过反复测试，得出当旅行商问题的规模比较小时，和的取值小更有利于求到最优解。当粒子数为30，迭代次数取200，和都取0.25时运行结果如下：经过反复测试，显然当粒子数和、一定时，迭代次数越多该方法求到最优解的概率就越大。当粒子数为40，迭代次数取200，和都取0.25时运行结果如下：经过反复测试，显然粒子群数越多对于求解旅行商更有利。当粒子数为40，迭代次数取400，和都取0.25时测试得到了最优解运行结果如下：这个结果就为该旅行商问题的最优解。总结：十个城市的旅行商问题由于问题的规模比较小，可以尽可能让和都取较小的值，粒子数尽可能的多，迭代次数也比较大时，求出最优解的可能性就越大 。设30个城市二维坐标分布为：city30=41 94;37 84;54 67;25 62;7 64;2 99;68 58;71 44;54 62;83 69;64 60;18 54;22 60;83 46;91 38;25 38;24 42;58 69;71 71;74 78;87 76;18 40;13 40;82 7;62 32;58 35;45 21;41 26;44 35;4 50;目前测试的最短路程为423.471.当粒子数为30，迭代次数取200，和都取0.25时运行结果如下：当粒子数为30，迭代次数取200，和都取0.85时运行结果如下：可以看出对于问题规模稍大的旅行商问题，粒子群算法的效率开始恶化。经过反复测试，还是可以得出，在其它参数不变的情况下，和的取值大，有利于对交换算子的保留，从而提高得到最优解的概率。当粒子数为30，迭代次数取400，和都取0.85时运行结果如下：当粒子数为40，迭代次数取400，和都取0.85时运行结果如下:可以看出当旅行商问题的规模比较大时，增加粒子群算法中的粒子数和迭代次数，该算法效率提高的不明显，因此该算法对于解决规模比较大的旅行商问题存在局限性。给出50个城市的二维坐标分布为： city50=31 32;32 39;40 30;37 69;27 68;37 52;38 46;31 62;30 48;21 47;25 55;16 57;17 63;42 41;17 33;25 32;5 64;8 52;12 42;7 38;5 25; 10 77;45 35;42 57;32 22;27 23;56 37;52 41;49 49;58 48;57 58;39 10;46 10;59 15;51 21;48 28;52 33;58 27;61 33;62 63;20 26;5 6;13 13;21 10;30 15;36 16;62 42;63 69;52 64;43 67;到目前为止经过大量测试最短距离为427.855当粒子数为30，迭代次数取200，和都取0.85时运行结果如下：给出75个城市的二维坐标分布为：city75=48 21;52 26;55 50;50 50;41 46;51 42;55 45;38 33;33 34;45 35;40 37;50 30;55 34;54 38;26 13;15 5;21 48;29 39;33 44;15 19;16 19;12 17;50 40;22 53;21 36;20