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

粒子群算法中每个粒子由一个多维向量表示, 其下一代粒子的飞行方向和速度由个体最优解和群体最优解向量来修正, 基本粒子群算法已成功应用于求解连续域问题,但解决离散问题还是存在很大困难的。为了解决诸多实际工程中的离散问题, 通过引入交换序和交换因子重构了粒子群算法并成功应用于小规模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