基于粒子群算法的TSP问题研究 - 图文(2)

目 录

摘 要 ............................................................................................................................... I Abstract ................................................................................................................................ II 1 绪 论 ................................................................................................................................. 1

1.1 背景和意义 ........................................................................................................... 1 1.2 国内外研究的进展情况 ....................................................................................... 1 1.3 主要内容 ............................................................................................................... 2 1.4 结构安排 ............................................................................................................... 2 2 基本的粒子群算法 ........................................................................................................... 3

2.1 思想起源 ................................................................................................................. 3 2.2 算法的原理 ............................................................................................................. 4 2.3 算法的流程和流程图 ............................................................................................. 5 2.4 算法的优缺点分析 ................................................................................................. 8 3 旅行商问题 ..................................................................................................................... 9

3.1 TSP问题介绍 ........................................................................................................ 9 3.2 TSP问题定义 ........................................................................................................ 9 4 改进的粒子群算法求解TSP问题 .............................................................................. 11

4.1 改进的粒子群算法简介 ..................................................................................... 11 4.2 引入模糊矩阵的粒子群算法求解TSP问题 ..................................................... 12

4.2.1旅行商问题的解用模糊矩阵表示 .............................................................. 12 4.2.2引入模糊矩阵的粒子群算法重新定义 ...................................................... 13 4.2.3引入模糊矩阵的粒子群算法求解旅行商问题的具体操作 ...................... 15 4.3 引入交换算子和交换序的粒子群算法求解TSP问题 ..................................... 18

4.3.1引入交换算子和交换序的粒子群算法定义和流程 18

4.3.2实验结果与参数设置 .................................................................................. 20

5 结 论 ....................................................................................................................... 27 致 谢 ............................................................................................................................. 29 毕业设计（论文）知识产权声明 ..................................................................................... 30 毕业设计（论文）独创性声明 ......................................................................................... 31 参考文献 ............................................................................................................................. 32 附 录 1 程序 ................................................................................................................. 34 附 录 2 外文翻译原文 ................................................................................................. 45

II I

1 绪论 1 绪 论

1.1 背景和意义

粒子群算法（Particle Swarm Optimization）,缩写为PSO。1995年由肯尼迪（Kennedy）与埃伯哈特（Eberhart）两位学者所提出，他们发明PSO灵感来源于对鸟群捕食行为的研究。粒子群算法的理论基础是把每一只鸟看作为一个粒子，并赋予该粒子（个体）拥有记忆性，并能通过与粒子群体中的其他粒子之间的通信而寻求到最适解。目前，粒子群算法在函数优化，神经网络训练，模糊系统控制，组合优化入侵检测，以及决策调度等多个领域得到广泛的应用。粒子群算法有较强的全局搜索能力，但也容易陷入局部极值导致早熟。

旅行商问题（Travelling Salesman Problem），英文缩写为TSP，是数学领域中著名问题之一，也是一个典型的NP完全问题。问题描述为：假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。目前解决旅行商问题的主要算法有：蚁群算法，免疫算法，遗传算法等等。 …… 此处隐藏：2064字，全部文档内容请下载后查看。喜欢就下载吧 ……