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算法的收敛性进行了研究，证明采用收敛因子能够确保算法的收敛。同年，Suganthan P N.在发表的文章《优化与邻域》第一次提到带邻域操作的SO模型，克服了PSO模型在优化搜索后期随迭代次数增加和搜索结果无明显改进的缺点。

2001年来自普度大学工程与技术院的Parsopoulos K E.提出将拉伸技术用于PSO最小化问题的求解，力图避免PSO算法易陷于局部最小值的缺点。

2004年由来自中国江苏科技大学电子信息学院的高尚、韩斌、吴小俊、杨静宇等学者结合了遗传算法、蚁群算法和模拟退火算法的思想，对粒子群算法进行了优化并提出了混合粒子群算法，通过这种优化的粒子群算法使得组合优化问题很容易解决。