一种新的进化粒子群算法及其在tsp中的应用毕业设计

一种新的进化粒子群算法及其在tsp中的应用毕业设计内容摘要：

素质”的提高，比如解群体随进化代数的变化过程中存在“掉队”个体的“归队”现象，使得每代种群中的解具有“自我”学习和向“他人”学习提高的双重优点，因此其下代解具有针对性的从“先辈”那里继承的更多的信息。 在这种前提下，种群很快就达到了收敛状态，从而能在较少的代数内找到最优解。 旅行商问题 最优化问题自然而然的被分 为两类：一类是连续变量的问题，另一类是离散变量的问题，对于后者，我们称它为组合优化。 在组合优化问题里，是从一个无限集或者可数无限集里寻找一个对象，典型的是一个整数，一个集合，一个排列或一个图。 这与连续变量问题求一组实数或一个函数有着很大不同，因而求解它们的方法也很大相同。 从某种意义上讲，组合优化问题的研究是从它与连续优化问题之间的分界线上入手的。 旅行商问题 (Traveling Salesman ProblemTSP)是运筹学、图论和组合优化中的 NP难题，旅行商问题描述如下：给定 n 个城市及两两城市之间的距 离，求一条经过各城市一次且仅一次的最短路线。 其图论描述为：给定图 G=(V,A)，其中 V 为顶点集， A为各顶点相互连接组成的弧集，已知各顶点间连接距离，要求确定一条长度最短的Hamilton 回路，即遍历所有顶点一次且仅一次的最短回路。 设 ijd 为城市 i 与 j 之间的距离，即弧 (i,j)的长度。 引入决策变量： 1 , i j0 ijij xx 若 旅 行 商 访 问 城 市 后 访 问 城 市， 否 则 （ 13） 则 TSP 的目标函数为 nij iji j 1M in Z dx 。 （ 14） TSP 的描述非常简单，但求解最优化解是很困难的。 对于 N 个城市的 TSP，存在着 ( 1)!/2n 条可能的路径。 随着城市数目 N 的增长，可能路径的数目以 N 的指数倍增加，如果使用穷举法搜索，需要考虑所有的可能情况，并两两比较，找出最优解，那么可搜索的路径及其距离之和的计算量将正比于 ( !)/2N ,算法的复杂度呈指数增长，产生所谓的“组合爆 炸”，这即使是当今世界上运算最快的计算机也感到无能为力。 由于对 TSP 及与之具有类似复杂性的一些其它最优化问题现在还没有有效的算法，人们把这类问题称为“ NP 完全问题”。 因为所有的 NP 完全问题在数学上都等价于 TSP，因此研究 TSP 具有很重要的意义。 粒子群 优化 算法的国内外研究现状 粒子群优化算法概念简单，实现容易，同时又有深刻的智能背景，既适合科学研究，又特别适合工程应用。 算法一提出就吸引了广泛的注意，不断涌现了各种关于PSO 算法应用研究的成果，有力推动了 PSO 研究。 目前，其研究现状大致分为两个方向：算 法的改进，算法的应用。 由于粒子群算法提出的时间不长，算法缺乏深刻的的理论分析，数学基础相对薄弱，且存在许多不完善和未涉及到的问题。 因此，迄今已经出现了很多对粒子群优化算法的改进方法。 例如：混合 PSO(HPSO)算法、杂交 PSO 算法、协同 PSO 算法、基于模拟退火的 PSO 算法、自适应变异的 PSO 算法、离散 PS0、自适应 PSO、耗散的PSO， GAPSO 等多种粒子群优化算法。 如何利用有效的数学工具对算法的收敛性，收敛速度的估计，计算的复杂性，以及预防陷入局部最优和参数设置影响等进行分析将是今后的研究热点之一。 由于 PSO 算法概念简单，易于实现，因而在短期内得到很大发展，迅速得到了国际演化计算研究领域的认可，并在很多领域得到应用： PSO 的第一个应用是神经网络训练。 Kennedy 和 Eberhart 的报告说明 PSO 成功用于正确区分 XOR 问题，包括 13 维搜索空间的函数优化问题。 Salerno 也应用 PSO到训练神经网络学习 XOR 问题，比梯度递减算法更好。 另一个神经网络训练的例子中 Eberhart 和 Hu 用 PSO 训练神经网络以正确区分病人的颤抖行为是普通颤动或是患有帕金森氏症。 他们在 PSO 算法中使惯性权值在 2020 代中从 到 线性递减，获得很好的效果。 PSO 算法也用来优化带权神经网络的连接结构。 Zhang 和 Shao 的 PSONN 算法使用 PSO 算法优化神经网络，成功地用来评估喷气机燃料的质量。 乘法单元神经网络是带误差函数的神经网络，很难训练。 多种基于梯度的优化算法在搜索空间陷入多个局部最小值。 Engelbrecht 和 Ismail 研究了不同优化算法训练乘法单元神经网络的能力，发现在乘法单元神经网络的训练问题上， PSO 比其它随机搜索算法还要好，如GA 和 LeapFrog 算法。 Eberhart 等人在文献 [7]描述了 PSO 的一些 其他应用。 例如用训练神经网络来评估电池充电的状态； PSO 用来优化用于促进微生物的生长的化学成分配方，找到的解比之前使用其它优化算法发现的各种解有明显的改进。 PSO 的优势之一是能更加有效地对搜索空间内的大范围区域进行搜索，这使得 PSO 能够在搜索空间里发现更好的解，并且该解明显区别于使用其它已知算法发现的解。 另一个与神经网络训练 有 关的应用是 Fukuyama 和 Yoshida 发表的论文。 他们表明 PSO 优化连续和离散变量都非常有效。 在速度更新前，通过简单离散值来调整 PSO的更新公式，粒子的位置也是如此。 只要适当调整 ，这些离散变量与连续变量可以自由组合，应用到更新公式。 他们使用的是惯性权值线性递减的 PSO，结果表明比原来使用的 RTS 算法效率更高。 Fukuyama 等人把 Angeline 的混合 PSO 运用到相同问题，似乎混合 PSO 算法更有效。 进一步的研究还发现相同参数设置的 PSO 应用在不同电力系统问题上获得了高质量的解。 标准粒子群算法主要适用于连续空间函数的优化问题，如何将算法应用于离散空 间的优化问题，特别是非数值优化问题，将是粒子群算法的一个重要研究方向。 此外，充分利用其他进化算法以改善微粒群算法存在的不足，也是值得研究 的问题。 总之， PSO 算法的应用十分广泛，有着比较好的发展前景。 目前 PSO 的研究尚处于初期，还有许多问题值得做进一步的研究。 PSO 算法的理论研究还很缺乏，目前还没有粒子群理论的数学证明。 由于实际问题的多样性和复杂性，尽管目前已经有了多种不同版本的 PSO 改进算法但这些 PSO 算法不具有通用性，或者参数的设置要求使用者具备较高的经验，否则难以达到理想的效果。 开拓 PSO 算法的新的应用领域是一项很有意义的工作。 如何将 PSO 应用于组合优化问题也是一个重要的研究方向。 粒子群 优化 算法的研究 意义 粒子群算法自 1995 年被提出之后，得到了数值优化领域的广泛关注，吸引了大量的研究者。 如何加快算法的收敛速度和避免早熟收敛问题，一直是大多数研究者关注的重点，也是所有随机搜索算法共同面临的两个主要难题。 这两个问题之间本身就存在很复杂的关系，在很多情况下是互相冲突的两个目标。 在避免早熟收敛方面，现有的大量研究涉及如何让算法跳出局部最优点。 在加快收敛速度方面，主要的工作集中在如何选择最优的算法参数，以及从其他智能优化算法中借鉴一些思想对 PSO 算法的主要框架加以修改。 粒子群优化技术的应用领域己扩展到组合优化 、数据分类、数据聚类、模式识别、电信 Qos 管理、生物系统建模、流程规划、信号处理、机器人控制、决策支持以及仿真和系统辩识等方面。 由此可见，作为一类现代启发式优化算法，粒子群优化算法理论及其应用研究都具有相当重要的学术意义和现实价值。 第 2章 粒子群优化算法 粒子群算法 (PSO)是 1995 由 Kennedy 和 Eberhart[12]首先提出的一类基于群智能的演化计算方法。 PSO 源于对鸟群觅食行为的研究，研究者发现鸟群在飞行过程中经常会突然改变方向、散开、聚集，其行为不可预测，但其整体总保持一致性， 个体与个体间也保持着适宜的距离。 通过对类似生物群体的行为的研究，发现在生物群体中存在着个体与个体、个体与群体间的相互作用、相互影响的行为，这种行为体现的是一种存在于生物群体中的信息共享的机制。 它为群体的进化提供了一种优势，这也是PSO 形成的基础。 PSO 就是对这种社会行为的模拟，即利用信息共享机制，使得个体间可以相互借鉴经验，从而促进整个群体的发展。 PSO 和遗传算法 (Geic Algorithm,GA)类似，也是一种基于迭代的优化工具，系统初始化为一组随机解，通过某种方式迭代寻找最优解。 但 PSO 没有 GA 的“选择”、“交叉”、“变异”算子，编码方式也较 GA 简单。 由于 PSO 算法容易理解、易于实现，所以 PSO 算法发展很快。 在 函数优化 [14]、神经网络训练 [15]、系统控制 [10]等领域得到广泛应用。 目前粒子群算法研究已被“国际进化计算会议” (IEEE International Conferences on EvolutionaryComputation,CEC)列为一个讨论的专题。 粒子群算法的原理 粒子群优化算法的基本概念源于对鸟群觅食行为的研究。 设想这样一个场景：一群鸟在随机搜寻食物。 在 这个区域里只有一块食物。 所有的鸟都不知道食物在哪里。 但是他们知道当前的位置离食物还有多远。 那么找到食物的最优策略是什么呢。 最简单有效的就是搜寻目前离食物最近的鸟的周围区域。 PSO 从这种模型中得到启示并用于解决优化问题。 作为一种演化算法，粒子群优化算法兼有进化计算和群智能的特点。 起初Kennedy 和 Eberhart 只是设想模拟鸟群觅食的过程，但后来的研究中发现 PSO 是一种很好的优化工具。 与其他进化算法相似， PSO 算法也采取“群体”与“进化”的概念，依据个体间的协作与竞争通过对个体适应度进行评价，实现复杂空间 中最优解的搜索。 所不同的是 PSO 是将每个个体看作是在 N 维搜索空间中的没有重量和体积的微粒，并在搜索空间中以一定的速度飞行。 该飞行速度由个体的飞行经验和群体的飞行经验进行动态的调整。 PSO 首先生成初始种群，即在可行解空间中随机初始化一群粒子，每个粒子都为优化问题的一个可行解，并由目标函数为之确定一个适应值。 每个粒子将在解空间中 运动，并由一个速度决定其方向和距离。 通常粒子将追随当前的最优粒子而运动，并经逐代搜索最后得到最优解。 在每一代中，粒子将跟踪两个极值，一个为粒子本身迄今找到的最优解 bestP ，另一个为全种群迄今找到的最优解 bestg。 每个粒子都通过上述两个极值不断更新自己，从而产生新一代群体。 假设在一个 D 维的目标搜索空间中，有 m 个粒子组成一个群落，其中第 i 个粒子表示为一个 D 维的向量 12( , , ..., )i i i idX X X X ， i=1， 2，„， m，即第 i 个粒子在 D 维的搜索空间中的位置。 将 X 代入一个目标函数就可以计算出其适应值，根据其适应度值的大小衡量优劣。 第 i 个粒子的“飞行”速度也是一个 D 维的向量，记为12( , ,..., )i i i idY Y Y Y。 第 i 个粒子迄今为止搜索到的最优位置称为个体极值，记为 bestP ，整个粒子群迄今为止搜索到的最优位置为全局极值，记为 bestg。 因为 bestg 是整个粒子群的最优位置，因此上述 PSO 算法也称为全局版 PSO。 也可以把第 i 个粒子的邻居们搜索到的最优位置作为 bestg ，则上述方法又称为局部版PSO。 全局版 PSO 收敛速度快，但有时会陷入局部最优。 局部版 PSO 收敛速度慢一点，但相对的不易陷入局部最优。 在找到这两个最优值时，粒子根据如下的公式来更新自己的速度和新的位置： 39。 12( ) ( ) ( ) ( )id id id id g d idV V c ra n d P X c ra n d P X     （ 21） 39。 39。 id id idX X V （ 22） 式中 idv 表示第 i 个粒子在第 d 维上的速度；  为惯性权重，控制粒子的每一代速度更新有多少以前的速度保留下来； 1c 和 2c 为调节 idP 和 gdP 相对重要性的参数，根据经验通常取 122cc； ()rand 为随机数生成函数，生成介于 (0,1)之间的随机数；。 图 21 粒子位置的改进 图 21 表示了 PSO 中粒子位置改进，其中： tX ： 目前搜索到的点 1tX ：改进后的搜索点 tV ：当前速度 1tV ：改进后的速度 pbestV：基于个体 极值的速度 pbestV：基于全局极值的速度 以下是粒子群优化算法程序的伪代码： For each particle Do{ Initialize particle } %初始化粒子群 While maximum iterations or minimum criteria is not attained %满足循环条件 Do{ For each particle{ Calculate fitness value %计算适应值 If the fitness。