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

..WORD格式可编辑专业知识分享毕业设计<论文>题目：基于粒子群算法的TSP问题研究院〔系理学院专业信息与计算科学班级姓名xxx学号xxx导师xxx20XX6月毕业设计<论文>题目：基于粒子群算法的TSP问题研究院〔系理学院专业信息与计算科学班级101001姓名xxx学号101001106导师xxx20XX6月WORD格式可编辑专业知识分享XX工业大学毕业设计〔论文任务书院〔系理学院专业信息与计算科学班101001姓名xxx学号1010011061.毕业设计〔论文题目：基于粒子群算法的TSP问题研究2.题目背景和意义：粒子群算法,也称粒子群优化算法〔ParticleSwarmOptimization,缩写为PSO,是近年来发展起来的一种新的进化算法〔EvolutionaryAlgorithm-EA。1995年由Eberhart博士和kennedy博士提出。PSO算法属于进化算法的一种,和遗传算法相似,它也是从随机解出发,通过迭代寻找最优解。但它比遗传算法规则更为简单,它没有遗传算法的"交叉"<Crossover>和"变异"<Mutation>操作,它通过追随当前搜索到的最优值来寻找全局最优。旅行商问题,即TSP问题〔TravelingSalesmanProblem是数学领域中著名的优化问题之一,很多现实问题可归结为TSP问题。粒子群优化算法原理简单,从算法提出的伊始,就被广泛应用于求解各类优化问题。因此用粒子群算法求解典型的优化问题—TSP问题,具有很高的理论与现实意义。3.设计<论文>的主要内容〔理工科含技术指标：1了解粒子群算法的由来,熟练掌握粒子群算法的原理；2了解TSP问题的本质,知道现实中都有哪些问题可以转化为TSP问题,知道此问题在现实生活中的广泛存在性；3用粒子群算法求解TSP问题,要求程序实现〔可以用数学软件如matlab之类的来实现,并作出理论分析。4.设计的基本要求及进度安排〔含起始时间、设计地点：第1周-第2周对相关资料进行整理并提交开题报告第2周-第8周深入了解相关内容和理论第9周-第10周完成中期报告和外文翻译第11周-第16周对相关内容进行整理,完成毕业设计论文初稿第17周-第18周修改论文,准备答辩5.毕业设计〔论文的工作量要求①实验〔时数*或实习〔天数：②图纸〔幅面和张数*：③其他要求：指导教师签名：年月日学生签名：年月日系〔教研室主任审批：年月日..专业知识分享基于粒子群算法的TSP问题研究..摘要1995年,肯尼迪〔Kennedy与埃伯哈特〔Eberhart两位学者提出了粒子群算法。粒子群算法具有易理解、易实现和全局搜索能力强等特点,因此该算法问世以后迅速得到科学与工程领域的广泛关注,已经成为发展最快的智能优化算法之一。文章介绍了基本粒子群算法的概念和原理,并介绍了旅行商问题的概念及数学定义。基本粒子群优化算法已经成功地应用于求解连续域问题,但是,对于离散域问题求解研究还很少。很不幸旅行商问题恰恰就属于离散问题,因此接下来文章介绍了几种可以解决旅行商问题的改进粒子群算法,并详细介绍了其中的两种：引入模糊矩阵的改进粒子群算法和引入交换序和交换算子的改进粒子群算法。这两种改进的粒子群算法实现了对旅行商问题的求解。实验结果表明这两种改进粒子群算法的有效性。关键词：粒子群算法；全局搜索；旅行商问题；连续；离散..Particleswarmoptimization<PSO>-basedalgorithmForthetravelingsalesmanproblem<TSP>AbstractTheParticleswarmoptimization<PSO>algorithmoriginallydevelopedbyKennedyandEberhartin1995.The

algorithm

has

the

characteristics

thateasytounderstand,easytoimplementand

global

searching

ability.Ithadgot

extensive

attention

in

the

field

of

scienceand

engineeringassoonasthealgorithmwasproposed.Bynow,PSOhas

became

one

ofthe

mostpopularoptimizationalgorithms.

WeintroducedtheconceptsandsomeprinciplesofPSOandthemathematicaldefinitionofTSP.WeknowPSOhassucceededinmanycontinuousproblems,butthereislessresearchaboutdiscreteproblems.Unfortunately,TSPjustbelongtosuchaproblem.Accordingtothis,someimprovedPSOalgorithmstosolveTSPwasintroduced,andtwoofthemwasdescribedindetail.Onealgorithmisimprovedbyintroducethefuzzymatrixandtheotherisimprovedbyintroducethepermutationconcept.WeappliedthetwoimprovedPSOalgorithmsontheproblemofTSPsuccessfully.Theresultsshowsbothofthemareavailable.Keywords:TheParticleswarmoptimization;GlobalSearch;Travelingsalesmanproblem;Continuous;Discrete..WORD格式可编辑专业知识分享目录摘TOC\o"1-3"\h\u648要I30476AbstractII51431绪论1242851.1背景和意义191631.2国内外研究的进展情况111421.3主要内容2139551.4结构安排2155842基本的粒子群算法3189892.1思想起源380162.2算法的原理4200232.3算法的流程和流程图516022.4算法的优缺点分析8247863旅行商问题956923.1TSP问题介绍9325403.2TSP问题定义9245304改进的粒子群算法求解TSP问题1119494.1改进的粒子群算法简介1178454.2引入模糊矩阵的粒子群算法求解TSP问题12106944.2.1旅行商问题的解用模糊矩阵表示12259634.2.2引入模糊矩阵的粒子群算法重新定义13292654.2.3引入模糊矩阵的粒子群算法求解旅行商问题的具体操作15182554.3引入交换算子和交换序的粒子群算法求解TSP问题18255214.3.1引入交换算子和交换序的粒子群算法定义和流程18207714.3.2实验结果与参数设置20171425结论2731027致谢2917611毕业设计〔论文知识产权声明308902毕业设计〔论文独创性声明3125471参考文献3231371附录1程序3411827附录2外文翻译原文45..WORD格式可编辑专业知识分享1绪论1.1背景和意义粒子群算法〔ParticleSwarmOptimization,缩写为PSO。1995年由肯尼迪〔Kennedy与埃伯哈特〔Eberhart两位学者所提出,他们发明PSO灵感来源于对鸟群捕食行为的研究。粒子群算法的理论基础是把每一只鸟看作为一个粒子,并赋予该粒子〔个体拥有记忆性,并能通过与粒子群体中的其他粒子之间的通信而寻求到最适解。目前,粒子群算法在函数优化,神经网络训练,模糊系统控制,组合优化入侵检测,以及决策调度等多个领域得到广泛的应用。粒子群算法有较强的全局搜索能力,但也容易陷入局部极值导致早熟。旅行商问题〔TravellingSalesmanProblem,英文缩写为TSP,是数学领域中著名问题之一,也是一个典型的NP完全问题。问题描述为：假设有一个旅行商人要拜访n个城市,他必须选择所要走的路径,路径的限制是每个城市只能拜访一次,而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。目前解决旅行商问题的主要算法有：蚁群算法,免疫算法,遗传算法等等。粒子群算法中每个粒子由一个多维向量表示,其下一代粒子的飞行方向和速度由个体最优解和群体最优解向量来修正,基本粒子群算法已成功应用于求解连续域问题,但解决离散问题还是存在很大困难的。为了解决诸多实际工程中的离散问题,通过引入交换序和交换因子重构了粒子群算法并成功应用于小规模TSP问题求解。也可以通过引入模糊矩阵重构粒子群算法同样成功应用于旅行商问题求解。本文会详细介绍引入模糊矩阵的粒子群算法和引入交换序和交换因子的粒子群算法并总结各自的优缺点。由于旅行商问题的特殊性,因此任何能使该问题的求解得以简化的方法,都将受到高度的评价和关注。因此,用粒子群算法去解决旅行商问题具有很高研究价值。1.2国内外研究的进展情况1995年由肯尼迪〔Kennedy与埃伯哈特〔Eberhart两位学者在IEEE国际神经网络学术会议发表了题为"ParticleSwarmOptimization"的论文,标志着PSO算法诞生。1999年美国的ClercM.发表的文章《自适应粒子群优化算法》对PSO算法的收敛性进行了研究,证明采用收敛因子能够确保算法的收敛。1999年SuganthanPN.在发表的文章《优化与邻域》第一次提到带邻域操作的SO模型,克服了PSO模型在优化搜索后期随迭代次数增加和搜索结果无明显改进的缺点。20XX来自普度大学工程与技术院的ParsopoulosKE.提出将拉伸技术用于PSO最小化问题的求解,力图避免PSO算法易陷于局部最小值的缺点。20XX由来自中国XX科技大学电子信息学院的高尚,韩斌,吴小俊,杨静宇等学者,他们结合了遗传算法、蚁群算法和模拟退火算法的思想,对粒子群算法进行了优化并提出了混合粒子群算法,通过这种优化的粒子群算法使得组合优化问题很容易解决。1.3主要内容清楚基本的粒子群算法的原理并知道如何应用；了解旅行商问题的本质及生活中哪些问题都可以转化为旅行商问题；了解有哪些改进的方法可以求解旅行商问题,并选择几种改进的粒子群算法详细介绍。使用Matlab实现引入交换序和交换算子的改进粒子群算法并解决旅行商问题。并对粒子群算法的参数进行研究,选出粒子群算法解决旅行商问题效率比较高的参数。最后,总结各种改进粒子群算法解决旅行商问题的优点和缺点。1.4结构安排第一章绪论中分别介绍了基本粒子群算法和旅行商问题,以及国内外研究现状和论文所研究的主要内容。第二章详细介绍了基本粒子群算法思想起源和算法具体流程。第三章详细介绍了旅行商问题概念,数学定义和应用领域。第四章中,首先,介绍了几种可以求解旅行商问题的改进粒子群算法,并详细介绍了其中的两种。然后,使用Matlab实现了一种求解旅行商问题的改进粒子群算法。在附录中给出了具体实现代码。..WORD格式可编辑2基本的粒子群算法2.1思想起源1995年IEEE国际神经网络学术会议发表了题为"ParticleSwarmOptimization"的论文,标志着粒子群优化<ParticleSwarmOptimization,PSO>算法[1]诞生。粒子群算法是一种基于迭代的优化工具。系统初始化一组随机解,粒子在解空间通过个体间的协作与竞争,实现复杂空间最优解的搜索。同时,粒子群算法又不像其他进化算法那样对个体进行交叉、变异、选择等进化算子操作,而是把个体看作是在D维搜索空间中没有质量和体积的粒子,每个粒子被随机初始化位置和初速度,粒子通过参考全局最佳位置和局部最佳位置,进行进化也就是改变他的位置和速度。通过这样不断的迭代来求解问题。粒子群算法具有很好的生物社会背景[2]而且易理解、参数少、易实现。目前在科学研究与工程实践中得到了广泛关注[3-10]。人工生命的主要研究领域之一是探索自然界生物的群体行为,从而在计算机上构建其群体模型。生物仿真学给人类的生活带来了巨大的改变,因此科学家对研究此课题有很大的兴趣,生物学家CraigReynolds在1987年提出了一个非常有影响的鸟群聚集模型[7],在他的仿真中,每一个个体遵循：<1>避免与邻域个体相冲撞；<2>匹配邻域个体的速度；<3>飞向鸟群中心,且整个群体飞向目标。仿真中仅利用上面三条简单的规则,就可以非常接近的模拟出鸟群飞行的现象。1990年,生物学家FrankHeppner也提出了鸟类模型[8],它的不同之处在于：鸟类被吸引飞到栖息地。在仿真中,一开始每一只鸟都没有特定的飞行目标,只是使用简单的规则确定自己的飞行方向和飞行速度〔每一只鸟都试图留在鸟群中而又不相互碰撞,当有一只鸟飞到栖息地时,它周围的鸟也会跟着飞向栖息地,这样,整个鸟群都会落在栖息地。1995年,美国社会心理学家JamesKennedy和电气工程师RussellEberhart[1]共同提出了粒子群算法,其基本思想是受对鸟类群体行为进行建模与仿真的研究结果的启发。他们的模型和仿真算法主要对FrankHeppner的模型进行了修正,以使粒子飞向解空间并在最好解处降落。Kennedy在他的书中描述了粒子群算法思想的起源。自20世纪30年代以来,社会心理学的发展揭示：我们都是鱼群或鸟群聚集行为的遵循者。在人们的不断交互过程中,由于相互的影响和模仿,他们总会变得更相似,结果就形成了规范和文明。人类的自然行为和鱼群及鸟群并不类似,而人类在高维认知空间中的思维轨迹却与之非常类似。思维背后的社会现象远比鱼群和鸟群聚集过程中的优美动作复杂的多：首先,思维发生在信念空间,其维数远远高于3；其次,当两种思想在认知空间汇聚于同一点时,称其一致,而不是发生冲突。但思维背后的社会现象还不能完全理解鸟类的社会行为。显然,我们的模仿协调性远不及鸟类自身行为的协调性。综上,从开始的简单鸟类的社会行为模仿到复杂的鸟类社会行为模仿,最后模仿越来越接近真实的鸟类社会行为,这就是粒子群算思想诞生的过程。2.2算法的原理粒子群优化算法首先初始化一群随机粒子,这些初始化的粒子都是空间搜索的潜在解,并且每个粒子都有一个被优化函数决定的适应值〔fittness,每个粒子还有一个速度决定它们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索[1]。粒子通过跟踪两个极值来更新自己；第一个就是粒子本身所找到的最优解,这个解称为个体极值〔pbest；另一个极值是整个种群目前找到的最优解,这个极值是全局极值〔gbest。假设在一个维的目标搜索空间中,有个粒子组成一个群落,其中第个粒子表示为一个维的向量,。第个粒子的"飞行"速度也是一个维的向量,为,。第个粒子目前为止搜索到的最优位置称为个体极值,为,。整个粒子群目前为止搜索到的最优位置为全局极值,为在找到这两个最优值时,粒子根据如下的公式<1>和<2>来更新自己的速度和位置[12]：<2.2.1><> 其中为惯性权重,为学习因子,为0到1之间均匀分布的随机数。 粒子群算法的性能很大程度上取决于算法参数的选择,选取较好的参数,不仅能缩短算法执行的时间,而且可以提高解决问题的准确性。这其中决定算法性能的参数有：粒子数、惯性权重、学习因子、等,各个参数的选择一般情况下可以参考如下：粒子数：粒子数的多少选择一般是根据问题的复杂性决定的。对于一般优化问题取20到40个粒子完全可以得到很好的结果。粒子的维度：这是由优化问题决定,就是问题解的维度。学习因子：学习因子使粒子具有自我总结和向群体中优秀个体的学习能力,一般取值范围为0到4。惯性权重：决定了粒子对当前速度继承多少,合适的选择可以使粒子具有均衡的探索能力和开发能力。惯性权重越大粒子的全局搜索能力越强,反之惯性权重越小粒子的局部搜索能力越强。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.1>对粒子的速度进行进化根据方程<2.2.2>对粒子的位置进行进化根据方程<2.2.2>对粒子的位置进行进化是否满足条件否是否满足条件是输出结果总结：对于这种连续性的问题,用粒子群算法求解,只要随着粒子数和迭代步数的增加,求解的结果会不断趋近最优解。2.4算法的优缺点分析粒子群算法的优点：粒子群优化算法<PSO>是模拟鸟群觅食过程中的行为提出的一种基于群体智能的演化计算方法。该算法易于描述,在求解过程中只有非常少的参数需要调整并且无集中控制约束,不会因个体的故障影响整个问题的求解,确保了系统具备很强的鲁棒性,相比其它演化算法,只需要较少的函数计算次数就可达到收敛,因此能以较大概率找到问题的全局最优解。最后该算法最大的优势也在于编程简单,易实现。粒子群算法的缺点：在求解全局最优解的过程中对于有多个局部极值点的函数,容易陷入到局部极值点中,得不到正确的结果。此外,由于粒子群算法问世时间不长在搜索纠结过程中缺乏精密搜索方法的配合,导致使用粒子群算法这种方法往往不能得到精确的结果。再则,PSO方法提供了全局搜索的可能,但并不能严格证明它在全局最优点上的收敛性。因此,PSO一般适用于存在多个局部极值点而并不需要得到很高精度的优化问题。对于本文而言,基本粒子群算法有一个致命的的缺点,它速度更新和位置更新都是由特定的连续函数决定的,所以它只能解决连续性优化问题,对于求解离散问题存在困难。..WORD格式可编辑3旅行商问题3.1TSP问题介绍旅行商问题<TravelingSalesmanProblem,简称TSP>是一个典型的NP问题也是一个典型的组合优化问题。旅行商问题描述如下：给定n个城市及两两城市之间的距离,求一条经过各城市一次且仅一次的最短路线。对于n个城市的TSP问题,存在着〔n-1!/2条可能的路径,随着城市数目n的增长,可能路径的数目以n的指数倍增加。如果使用穷举法搜索,需要考虑所有可能的情况,并两两比较,找出最优解,那么可搜索的路径及距离之和的计算量将正比于n!/2,算法的复杂度呈指数增长,要求出旅行商问题的最优化解是很困难的,这也是该问题被认为是NP问题的原因。同样不幸的是,旅行商问题为离散问题,使得可以解决该问题的方法更少。因此,任何可以求解旅行商问题的方法都应被高度关注。在生产生活中许多问题都可以转化为旅行商这类问题的模型,因此旅行商问题具有很高的实际应用价值,例如：城市管道铺设优化、物流行业中的车辆调度优化、制造业中的切割路径优化以及电力系统配电网络重构等现实生活中的很多优化问题都可以归结为旅行商模型来求解,目前旅行商问题应用的一个非常重要方面就是无人飞机的航路设计问题,即事先针对敌方防御区内的威胁部署和目标的分布情况,对无人作战飞机的飞行航路进行整体规划设计,可以综合减小被敌方发现和反击的可能性降低耗油量,从而显著提高UCAV〔无人战斗机执行对地攻击〔或侦察任务的成功率。3.2TSP问题定义设n为城市数目为n*n阶距离矩阵,代表从城市i到城市j的距离,,。问题是要找出访问每个城市且每个城市恰好只访问一次的一条Hamilton回路,且其路径的总长度是最短的。这条Hamilton回路可以表示为<1,2,...,n>的所有循环排列的集合,即为<1,2,...,n>的排列,表示访问第i个城市后访问第j个城市。目标函数〔在粒子群算法中也可以叫做适应值函数：城市Hamilton回路总长度为：<3.2.1>引入决策变量：<3.2.2>旅行商问题定义虽然非常简单,使用穷举法可以让旅行商得到确定的最优解,但随着需要访问城市数目的增加,会出现所谓的组合爆炸现象。所以,城市数目比较多的时候使用穷举搜索策略几乎是不可能做到的。..WORD格式可编辑4改进的粒子群算法求解TSP问题4.1改进的粒子群算法简介由第二章的基本粒子群算法介绍,我们可以看出基本的粒子群算法对适应度函数是有连续的要求。因此,基本粒子群算法在很多连续优化问题中得到成功应用,但粒子群算法不能直接应用到离散问题中,那么,如果非要用它解决离散问题,就必须对算法进行改进。我们需要对方程<2.2.1>和方程<2.2.2>进行改写并且重新定义方程中加法和乘法的含义。下面我将介绍几种改进的粒子群算法,这些算法可以比较好的解决旅行商这种离散型问题。王翠茹,张江维,王等[13][14]对粒子群优化算法进行了改进后,粒子不仅根据自身和同伴中最好的个体调整自己的飞行速度,而且按照一定的概率向其他个体学习,这种强化后的学习行为更符合自然界生物的学习规律,更有利于粒子发现问题的全局最优解。同时借鉴单点调整算法思想,提出了调整因子和调整序概念用以重构粒子群算法。傅刚[15]认为,用粒子群算法解决旅行商问题时,调整因子的先后顺序决定下一代种子的优劣,以及能否很快地收敛到最优值,如何恰当地解决惯性权重个体间的协作和个体历史最优以及群体最优对个体的影响是快速高效解决这一问题的关键。旁巍,王康平,周春光等[16]通过引入模糊矩阵提出了一种改进的粒子群优化算法,采用模糊矩阵来表示粒子的位置和速度,并重新定义速度和位置更新公式中的各种运算符号,这种改进的粒子群算法给求解旅行商问题提供了一种新思路。基于这种思路下文将会介绍详细的实现过程。郭文忠等[17]在介绍目前已经有多种针对惯性权值的研究的基础上,提出引入模糊技术,并提出了佳粒子距的概念,并给出了一种惯性权值的模糊自适应调整模型及其相应的粒子群优化算法,使用不同的惯性权值更新同一代种群,用于TSP问题的求解。实验结果表明改进后的算法不仅在求解组合优化问题中的有效性,而且同时提高了算法的性能,加快了收敛速度。20XX中国学者易云飞,陈国鸿[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.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次迭代后的全局最好位置。位置更新公式为：〔.3引入模糊矩阵的粒子群算法求解旅行商问题的具体操作基本粒子群算法通过引入模糊矩阵把公式〔2.2.1、〔2.2.2分别改写为公式〔4.2.9、〔4.2.10,为了确保改写后粒子群算法公式能够适用这种矩阵的变化,因此,在初始化时需要有许多特定的条件。下面先介绍这种改进的粒子群算法是如何初始化的。初始化位置：〔4.2.11矩阵中的元素是按照如下条件随机生成：〔4.2.12〔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,M[12]重新定义了运算符号和规则,并用于求解离散问题,重新定义后的粒子群算法相比以前的算法有了很明显的改观。下文将会把这种改进的粒子群算法应用到解决旅行商问题中。引入交换算子和交换序是另种一种改进的粒子群算法去解决旅行商这种离散型问题的方法。这种方法也是粒子群算法应用到离散型问题的第一次尝试的方法。此方法的问世,使得粒子群算法的应用领域反生巨大的改变。下面先介绍交换算子和交换序的概念。交换算子：是用来交换一个有序序列中元素的位置,一个交换算子可以使这个有序序列中两个元素位置发生调换。具体到改变旅行商问题中,表示旅行商的可行解序列发生改变,改变后的结果仍是旅行商问题的可行解。用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.40.4439;0.24390.1463;0.17070.2293;0.22930.761;0.51710.9414;0.87320.6536;0.68780.5219;0.84880.3609;0.66830.2536;0.61950.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=[4194;3784;5467;2562;764;299;6858;7144;5462;8369;6460;1854;2260;8346;9138;2538;2442;5869;7171;7478;8776;1840;1340;827;6232;5835;4521;4126;4435;450];目前测试的最短路程为423.471.当粒子数为30,迭代次数取200,和都取0.25时运行结果如下：当粒子数为30,迭代次数取200,和都取0.85时运行结果如下：可以看出对于问题规模稍大的旅行商问题,粒子群算法的效率开始恶化。经过反复测试,还是可以得出,在其它参数不变的情况下,和的取值大,有利于对交换算子的保留,从而提高得到最优解的概率。当粒子数为30,迭代次数取400,和都取0.85时运行结果如下：当粒子数为40,迭代次数取400,和都取0.85时运行结果如下:可以看出当旅行商问题的规模比较大时,增加粒子群算法中的粒子数和迭代次数,该算法效率提高的不明显,因此该算法对于解决规模比较大的旅行商问题存在局限性。给出50个城市的二维坐标分布为：city50=[3132;3239;4030;3769;2768;3752;3846;3162;3048;2147;2555;1657;1763;4241;1733;2532;564;852;1242;738;525;1077;4535;4257;3222;2723;5637;5241;4949;5848;5758;3910;4610;5915;5121;4828;5233;5827;6133;6263;2026;56;1313;2110;3015;3616;6242;6369;5264;4367];到目前为止经过大量测试最短距离为427.855当粒子数为30,迭代次数取200,和都取0.85时运行结果如下：给出75个城市的二维坐标分布为：city75=[4821;5226;5550;5050;4146;5142;5545;3833;3334;4535;4037;5030;5534;5438;2613;155;2148;2939;3344;1519;1619;1217;5040;2253;2136;2030;2629;4020;3626;6248;6741;6235;6527;6224;5520;3551;3050;4542;2145;366;625;1128;2659;3060;2222;2724;3020;3516;5410;5015;4413;3560;4060;4066;3176;4766;5070;5772;5565;238;743;956;1556;1070;1764;5557;6257;7064;644;595;504;6015;6614;668;4326];该旅行商问题目前测试的最短距离为549.18。当粒子数为30,迭代次数取200,和都取0.85时运行结果如下：可以看出不管是50个城市的旅行商问题还是75个城市的旅行商问题,用这种粒子群算法的效率已经非常低了。总结：引入交换算子和交换序的改进粒子群算法,对于问题规模比较小的旅行商问题,其算法可以表现出很高的效率,但是随着问题规模的增加该算法在解决旅行商问题的效率急剧恶化。..WORD格式可编辑5结论粒子群优化<PSO>是一种新兴的基于群体智能的启发式全局随机搜索算法,具有易理解、易实现、全局搜索能力强等特点,为各个领域的研究人员提供了一种有效的全局优化技术。本文对粒子群算法的原理和思想做了详细的介绍,目前粒子群优化算法从所解决的问题上分类可以分为解决连续问题的粒子群算法和解决离散问题的粒子群算法。解决连续问题的粒子群算法对所解决问题连续性有要求,并且在连续问题上具有很高的效率。在解决连续的问题时,随着粒子群算法中的参数〔粒子数和参数迭代次数增加,所求问题的结果是可以不断趋近最优解。后来也有许多学者基于基本粒子群算法的思想提出许多改进的粒子群算法,比如,带压缩因子的粒子群算法,权重改进的粒子群算法,变学习因子的粒子群算法,混合粒子群算法等。这些改进的粒子群算法的提出,使得求解连续问题的效率更高。作者认为,这些改进的解决连续问题的粒子群算法对解决离散问题的粒子群算法有很高的参考价值。解决离散问题的粒子群算法也是基于基本粒子群算法的思想改进而来的,原始的粒子群算法是不能解决离散问题的,更不要说旅行商这类NP问题,但后来随着学者的不断研究,通过引入一些概念并对符号的含义做了重新定义,使得粒子群算法的思想在离散问题上应用成为可能。本文主要介绍了两种改进的粒子群算法在离散问题上的应用,第一种就是引入模糊矩阵的粒子群算法,采用模糊矩阵来表示粒子的位置和速度,并对速度更新公式和位置更新公式中的各种运算符号〔加法,减法和乘法重新定义,该算法是求解旅行商问题的新尝试。值得注意的是,该算法不仅仅能够解决旅行商问题,经过修改后也能够解决一般的路由问题。由于旅行商问题的特殊性,模糊矩阵的规模是n2,在一些简单的路由问题中,可以缩减矩阵的规模。另外,能否寻找更好的非模糊化的方法,也是今后的工作需要解决的问题。另一种就是引入交换算子和交换序的粒子群算法,这种方法是实现了粒子群算法在离散问题上应用的第一次尝试。该方法在旅行商问题规模比较小时表现出很高的效率,但是随问题规模的增大算法的性能急剧下降。加上旅行商问题特殊性,决定了该算法很难求出较大规模旅行商问题的最优解。作者认为改进的粒子群算法求解旅行商问题的过程不像求解连续问题,会不断的接近最优解,而是,存在一定的概率向最优解的靠近。当对于规模比较小旅行商问题选取较大的迭代数和粒子群规模,粒子群算法表现出很高的效率。但问题规模比较大时,有可能很快就求出了较优的解,也有可能很久都求不出较优解。因此要使粒子群算法在规模较大旅行商问题表现出很高的优越性,还有待于研究粒子间新的配合方案。..WORD格式可编辑专业知识分享致谢历时将近三个月的时间终于将这篇论文写完,在论文的写作过程中遇到了无数的困难和障碍,都在同学和老师的帮助下度过了。感谢所有帮助过我的人,尤其要强烈感谢我的论文指导老师—xxx老师,她对我进行了无私的指导和帮助,不厌其烦的帮助进行论文的改进。其中开题报告给我改了九遍,外文翻译给我改了六遍,老师对我写的每篇文章都仔细检查,甚至连标点符号都给我指出来,老师对学术的精益求精,深深的影响着我,我想这是我跟着xxx老师学到最有价值的东西。另外,在校图书馆查找资料的时候,图书馆的老师也给我提供了很多方面的支持与帮助。在此向他们表示最衷心的感谢！也感谢学校给我们开放的机房方便我们下载资料。感谢这篇论文所涉及到的各位学者。本文引用了数位学者的研究文献,如果没有各位学者的研究成果的帮助和启发,我将很难完成本篇论文。光阴似箭,白驹过隙。转眼间四年大学本科生活即将结束,我在这里必须感谢我的学校——XX工业大学和这四年给我们孜孜不倦上课的老师们,是你们教会了我知识,是你们教会了我该怎样做学问和怎样做人。我还必须感谢所有101001班的所有同学们,谢谢你们给我帮助,陪我成长,尤其要感谢陪我度过无数日日夜夜的舍友们,谢谢！最后,由于作者的学术水平有限,所写论文难免有不足之处,恳请各位老师和学友批评和指正！..WORD格式可编辑专业知识分享毕业设计〔论文知识产权声明本人完全了解XX工业大学有关保护知识产权的规定,即：本科学生在校攻读学士学位期间毕业设计〔论文工作的知识产权属于XX工业大学。本人保证毕业离校后,使用毕业设计〔论文工作成果或用毕业设计〔论文工作成果发表论文时署名单位仍然为XX工业大学。学校有权保留送交的毕业设计〔论文的原文或复印件,允许毕业设计〔论文被查阅和借阅；学校可以公布毕业设计〔论文的全部或部分内容,可以采用影印、缩印或其他复制手段保存毕业设计〔论文。〔保密的毕业设计〔论文在解密后应遵守此规定毕业设计〔论文作者签名：指导教师签名：日期：..WORD格式可编辑专业知识分享毕业设计〔论文独创性声明秉承学校严谨的学风与优良的科学道德,本人声明所呈交的毕业设计〔论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知,除了文中特别加以标注和致谢的地方外,毕业设计〔论文中不包含其他人已经发表或撰写过的成果,不包含他人已申请学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了致谢。毕业设计〔论文与资料若有不实之处,本人承担一切相关责任。毕业设计〔论文作者签名：指导教师签名：日期：..WORD格式可编辑专业知识分享参考文献[1]KennedyJ,EberhartR.Particleswarmoptimization[A].in:Proceedingsofthe4thIEEEInternationalConferenceonNeuralNetworks[C],Piscataway:IEEEServiceCenter,1995,pp.1942-1948.[2]GarnierS,GautraisJ,TheraulazG.Thebiologicalprinciplesofswarmintelligence[J].SwarmIntelligence,vol.30,no.1,2007,pp.3-31.[3]EberhartR,ShiY.Particleswarmoptimization:Developments,applicationsandresources[A].in:Proc.IEEECongr.Evol.Comput.[C],vol.1,no.1,2001,pp.81-86.[4]ParsopoulosK,VrahatisM.Recentapproachestoglobaloptimizationproblemsthroughparticleswarmoptimization[J].NaturalComputing,vol.40,no.1,2002,pp.235-306.[5]谢晓锋,张文俊,杨之廉.微粒群算法综述[J].控制与决策,vol.18,no.2,2003:129-134.[6]HuX,ShiY,EberhartR.Recentadvancesinparticleswarm[A].in:Proc.IEEECongr.Evol.Comput.[C],vol.1,2004,pp.90-97.[7]BanksA,VincentJ,AnyakohaC.Areviewofparticleswarmoptimization.PartI:backgroundanddevelopment[J].NaturalComputing,vol.45,no.6,2007,pp.467-484.[8]王万良,唐宇.微粒群算法的研究现状与展望[J].XX工业大学学报,vol.35,no.2,2007:136-141.[9]PoliR,KennedyJ,BlackwellT.Particleswarmoptimization:Anoverview[J].SwarmIntelligence,vol.1,no.1,2007,pp.33-57.[10]JelmerVanA,RobertB,BartDeS.Particleswarmsinoptimizationandcontrol[A].in:Proceedingsofthe17thWorldCongressTheInternationalFederationofAutomaticControl[C],Seoul,Korea,2008,pp.5131-5136.[11]黄岚,王康平,周春光,等.粒子群优化算法求解旅行商问题[J].XX大学学报〔理学版,2003〔4.[12]Clerc,M.DiscreteParticleSwarmOptimization,illustratedbytheTravelingSalesmanProblem.Newoptimizationtechniqueinengineering[C].Springer-Verlag,2004.[13]王翠茹,张江维,王,等.改进粒子群优化算法求解旅行商问题[J].华北电力大学学报,2005〔6.[14]王翠茹,冯海迅,张江维,等.基于改进粒子群优化算法求解旅行商问题[J].微计算机信息,2006〔22.[15]傅刚.PSO-TSP问题综述XX职业技术学院,XXXX350001科技论坛,2013.[16]庞巍,王康平,周春光,等.模糊离散粒子群优化算法求解旅行商问题[J].小型微型计算机系统,2005〔8.[17]郭文忠,陈国龙.求解TSP问题的模糊自适应粒子群算法[J].计算机科学,2006〔6.[18]易云飞陈国鸿,基于k-means的改进粒子群算法求解旅行商问题<XX学院>2012<6>.[19]王文峰,刘光远,温万惠求解TSP问题的自逃逸混合离散粒子群算法研究西南大学计算机与信息科学学院XX400715,2007<6>...WORD格式可编辑专业知识分享附录1程序程序1函数1function[xm,fv]=PSO<fitness,N,c1,c2,w,M,D>formatlong;%初始化种群的个体fori=1:Nforj=1:Dx<i,j>=randn;%随机初始化位置v<i,j>=randn;%随机初始化速度endend%先计算各个粒子的适应度,并初始化Pi和Pgfori=1:Np<i>=fitness<x<i,:>>;y<i,:>=x<i,:>;endpg=x<N,:>;%Pg为全局最优fori=1:<N-1>iffitness<x<i,:>><fitness<pg>pg=x<i,:>;endend%进入主要循环,按照公式依次迭代fort=1:Mfori=1:Nv<i,:>=w*v<i,:>+c1*rand*<y<i,:>-x<i,:>>+c2*rand*<pg-x<i,:>>;x<i,:>=x<i,:>+v<i,:>;iffitness<x<i,:>><p<i>p<i>=fitness<x<i,:>>;y<i,:>=x<i,:>;endifp<i><fitness<pg>pg=y<i,:>;endendPbest<t>=fitness<pg>;endxm=pg';fv=fitness<pg>;函数2：functionF=fitness<x>F=0;fori=1:30F=F+x<i>^2;end程序2城市的位置输入到计算机中用下面的函数：function[DLn,cityn]=tsp<n>ifn==10city10=[0.40.4439;0.24390.1463;0.17070.2293;0.22930.761;0.51710.9414;0.87320.6536;0.68780.5219;0.84880.3609;0.66830.2536;0.61950.2634];%10citiesd'=2.691fori=1:10forj=1:10DL10<i,j>=<<city10<i,1>-city10<j,1>>^2+<city10<i,2>-city10<j,2>>^2>^0.5;endendDLn=DL10;cityn=city10;end适应度函数：functionF=SumDistance<dislist,s>DistanV=0;n=size<s,2>;fori=1:<n-1>DistanV=DistanV+dislist<s<i>,s<i+1>>;%此函数用来计算总路程endDistanV=DistanV+dislist<s<n>,s<1>>;F=DistanV;绘图：functionm=plotTSP10<Clist,BSF,bsf,p,f>CityNum=size<Clist,1>;fori=1:CityNum-1axis<[0,1,0,1]>;%绘制点的连线图plot<[Clist<BSF<i>,1>,Clist<BSF<i+1>,1>],[Clist<BSF<i>,2>,Clist<BSF<i+1>,2>],'rs-','LineWidth',2,'MarkerEdgeColor','k','MarkerFaceColor','g'>;holdon;%'rs-','LineWidth',3,'MarkerEdgeColor','','MarkerFaceColor','g'-表示线为红色实线线宽为2,点为方形绿点边缘为黑色endaxis<[0,1,0,1]>;%绘制最后一个点和起始点的连线plot<[Clist<BSF<CityNum>,1>,Clist<BSF<1>,1>],[Clist<BSF<CityNum>,2>,Clist<BSF<1>,2>],'ms-','LineWidth',2,'MarkerEdgeColor','k','MarkerFaceColor','g'>;%'ms-','LineWidth',3,'MarkerEdgeColor','','MarkerFaceColor','g'-表示线为洋红色实线线宽为2,点为方形绿点边缘为黑色title<[num2str<CityNum>,'TSP']>;iff==0text<0.1,0.1,['迭代次数',int2str<p>,'最短距离',num2str<bsf>]>;endholdoff;pause<0.05>;初始化和变换：functionBasePSOforTSP%初始化w1=0.5;%个体经验保留概率w2=0.5;%全局经验保留概率M=200;%最大迭代次数m=30;%微粒数CityNum=10;%问题的规模〔城市个数[dislist,Clist]=tsp<CityNum>;%返回dislist可以求出两城市间的距离,Clist表示城市的列表NC=1;%迭代计数器R_best=zeros<M,CityNum>;%各代最佳路线L_best=inf.*ones<M,1>;%各代最佳路线的长度L_ave=zeros<M,1>;%各代路线的平均长度%产生微粒的初始位置fori=1:mx<i,:>=randperm<CityNum>;%产生30个微粒要走的30各城市的列表L<i>=SumDistance<dislist,x<i,:>>;%产生这30个微粒各自按上边路径走的总路程endp=x;%p为个体最好解pL=L;%用数组表示每个个体目前的最短路径,也是由于这也是初始化,以后这个距离也要不断更新[L_best<1,1>,n_best]=min<L>;%L_best<1,1>表示初始化中30个粒子中最优总距离,n_best表示第几个粒子是最优解R_best<1,:>=x<n_best,:>;%R_best<1,:>表示当前最优微粒所走城市的路径L_ave<1,1>=mean<L>;%L_ave<1,1>,30个微粒走的总路程的平均值%初始交换序v=ones<CityNum-1,2,m>;figure<1>;whileNC<=M%停止条件之一：达到最大迭代次