目 录
摘 要 ............................................................................................................................... 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个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。目前解决旅行商问题的主要算法有：蚁群算法，免疫算法，遗传算法等等。
粒子群算法中每个粒子由一个多维向量表示, 其下一代粒子的飞行方向和速度由个体最优解和群体最优解向量来修正, 基本粒子群算法已成功应用于求解连续域问题,但解决离散问题还是存在很大困难的。为了解决诸多实际工程中的离散问题, 通过引入交换序和交换因子重构了粒子群算法并成功应用于小规模TSP问题求解。也可以通过引入模糊矩阵重构粒子群算法同样成功应用于旅行商问题求解。本文会详细介绍引入模糊矩阵的粒子群算法和引入交换序和交换因子的粒子群算法并总结各自的优缺点。
由于旅行商问题的特殊性，因此任何能使该问题的求解得以简化的方法，都将受到高度的评价和关注。因此，用粒子群算法去解决旅行商问题具有很高研究价值。
1.2 国内外研究的进展情况
1995年由肯尼迪（Kennedy）与埃伯哈特（Eberhart）两位学者在IEEE国际神经
1
西安工业大学毕业设计(论文)
网络学术会议发表了题为“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实现了一种求解旅行商问题的改进粒子群算法。在附录中给出了具体实现代码。
2
2 基本粒子群算法 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 Eberhart[1]共同提出了粒子群算法，其基本思想是受对鸟类群体行为进行建模与仿真的研究结果的启
3
西安工业大学毕业设计(论文)
发。他们的模型和仿真算法主要对Frank Heppner的模型进行了修正，以使粒子飞向解空间并在最好解处降落。Kennedy在他的书中描述了粒子群算法思想的起源。自20世纪30年代以来，社会心理学的发展揭示：我们都是鱼群或鸟群聚集行为的遵循者。在人们的不断交互过程中，由于相互的影响和模仿，他们总会变得更相似，结果就形成了规范和文明。人类的自然行为和鱼群及鸟群并不类似，而人类在高维认知空间中的思维轨迹却与之非常类似。思维背后的社会现象远比鱼群和鸟群聚集过程中的优美动作复杂的多：首先，思维发生在信念空间，其维数远远高于3；其次，当两种思想在认知空间汇聚于同一点时，称其一致，而不是发生冲突。但思维背后的社会现象还不能完全理解鸟类的社会行为。显然，我们的模仿协调性远不及鸟类自身行为的协调性。
综上，从开始的简单鸟类的社会行为模仿到复杂的鸟类社会行为模仿，最后模仿越来越接近真实的鸟类社会行为，这就是粒子群算思想诞生的过程。
2.2 算法的原理
粒子群优化算法首先初始化一群随机粒子，这些初始化的粒子都是空间搜索的潜
在解，并且每个粒子都有一个被优化函数决定的适应值（fittness），每个粒子还有一个速度决定它们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索[1]。粒子通过跟踪两个极值来更新自己；第一个就是粒子本身所找到的最优解，这个解称为个体极值（pbest）；另一个极值是整个种群目前找到的最优解，这个极值是全局极值（gbest）。
假设在一个D维的目标搜索空间中，有N个粒子组成一个群落，其中第i个粒子表示为一个D维的向量
Xi?(xi1,xi2,?,xiD)，i?1,2,?,N。
第i个粒子的“飞行”速度也是一个D维的向量，为
（vi1,vi2，?,viD) ，i?1,2,?3。 Vi?第i个粒子目前为止搜索到的最优位置称为个体极值，为
pbest?(pi1,pi2,?,piD)，i?1,2,?,N。
整个粒子群目前为止搜索到的最优位置为全局极值，为
4