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

毕业设计(论文)题目：基于粒子群算法的TSP问题研究院（系）理学院专业信息与计算科学班级姓名xxx学号xxx导师xxx2014年6月毕业设计(论文)题目：基于粒子群算法的TSP问题研究院（系）理学院专业信息与计算科学班级101001姓名xxx学号101001106导师xxx2014年6月西安工业大学毕业设计（论文）任务书院（系）理学院专业信息与计算科学班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.毕业设计（论文）的工作量要求①实验（时数）*或实习（天数）：②图纸（幅面和张数）*：③其他要求：指导教师签名：年月日学生签名：年月日系（教研室）主任审批：年月日I基于粒子群算法的TSP问题研究摘要1995年，肯尼迪（Kennedy）与埃伯哈特（Eberhart）两位学者提出了粒子群算法。粒子群算法具有易理解、易实现和全局搜索能力强等特点，因此该算法问世以后迅速得到科学与工程领域的广泛关注，已经成为发展最快的智能优化算法之一。文章介绍了基本粒子群算法的概念和原理，并介绍了旅行商问题的概念及数学定义。基本粒子群优化算法已经成功地应用于求解连续域问题,但是，对于离散域问题求解研究还很少。很不幸旅行商问题恰恰就属于离散问题，因此接下来文章介绍了几种可以解决旅行商问题的改进粒子群算法，并详细介绍了其中的两种：引入模糊矩阵的改进粒子群算法和引入交换序和交换算子的改进粒子群算法。这两种改进的粒子群算法实现了对旅行商问题的求解。实验结果表明这两种改进粒子群算法的有效性。关键词：粒子群算法；全局搜索；旅行商问题；连续；离散IIParticleswarmoptimization(PSO)-basedalgorithmForthetravelingsalesmanproblem(TSP)AbstractTheParticleswarmoptimization(PSO)algorithmoriginallydevelopedbyKennedyandEberhartin1995.Thealgorithmhasthecharacteristicsthateasytounderstand,easytoimplementandglobalsearchingability.Ithadgotextensiveattentioninthefieldofscienceandengineeringassoonasthealgorithmwasproposed.Bynow,PSOhasbecameoneofthemostpopularoptimizationalgorithms.WeintroducedtheconceptsandsomeprinciplesofPSOandthemathematicaldefinitionofTSP.WeknowPSOhassucceededinmanycontinuousproblems,butthereislessresearchaboutdiscreteproblems.Unfortunately,TSPjustbelongtosuchaproblem.Accordingtothis,someimprovedPSOalgorithmstosolveTSPwasintroduced,andtwoofthemwasdescribedindetail.Onealgorithmisimprovedbyintroducethefuzzymatrixandtheotherisimprovedbyintroducethepermutationconcept.WeappliedthetwoimprovedPSOalgorithmsontheproblemofTSPsuccessfully.Theresultsshowsbothofthemareavailable.Keywords:TheParticleswarmoptimization;GlobalSearch;Travelingsalesmanproblem;Continuous;DiscreteIII目录摘要...............................................................................................................................IAbstract................................................................................................................................II1绪论.................................................................................................................................11.1背景和意义...........................................................................................................11.2国内外研究的进展情况.......................................................................................11.3主要内容...............................................................................................................21.4结构安排...............................................................................................................22基本的粒子群算法...........................................................................................................32.1思想起源.................................................................................................................32.2算法的原理.............................................................................................................42.3算法的流程和流程图.............................................................................................52.4算法的优缺点分析.................................................................................................83旅行商问题.....................................................................................................................93.1TSP问题介绍........................................................................................................93.2TSP问题定义........................................................................................................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致谢..