改进的TSP进化求解算法研究-计算机应用技术专业论文.docxVIP

HYPERLINK \l _bookmark5 4.1.8 算法步骤 36 HYPERLINK \l _bookmark6 4.2 粒子群算法解决 TSP 问题 36 HYPERLINK \l _bookmark7 4.2.1 粒子编码和初始种群的生成 36 HYPERLINK \l _bookmark8 4.2.2 适应度函数 37 HYPERLINK \l _bookmark9 4.2.3 群体更新 37 HYPERLINK \l _bookmark10 4.2.4 终止条件 37 HYPERLINK \l _bookmark11 4.2.5 算法步骤 37 HYPERLINK \l _bookmark12 4.4 小结 38 HYPERLINK \l _bookmark13 第五章 求解 TSP 问题的进化算法改进 39 HYPERLINK \l _bookmark14 5.1 常用初始种群生成方法的分析 39 HYPERLINK \l _bookmark15 5.2 改进的初始种群方法 41 HYPERLINK \l _bookmark16 5.2.1 环路插入法介绍 41 HYPERLINK \l _bookmark17 5.2.2 环路插入法的理论分析 41 HYPERLINK \l _bookmark19 5.3 实例仿真 44 HYPERLINK \l _bookmark20 5.3.1 环路插入法有效性实验 44 HYPERLINK \l _bookmark30 5.3.2 环路插入法在遗传算法中的应用 47 HYPERLINK \l _bookmark38 5.3.3 环路插入法在粒子群算法中的应用 50 HYPERLINK \l _bookmark46 5.4 小结 53 HYPERLINK \l _bookmark47 第六章 总结与展望 54 HYPERLINK \l _bookmark48 6.1 工作总结 54 HYPERLINK \l _bookmark49 6.2 工作展望 54 HYPERLINK \l _bookmark50 参考文献 56 HYPERLINK \l _bookmark51 成果目录 61 HYPERLINK \l _bookmark52 致 谢 62 I I 摘 要 遗传算法是一种模拟自然界生物进化的有哪些信誉好的足球投注网站算法，粒子群算法是群体智能的体 现，模仿鱼群和鸟群觅食行为发展起来的，均属于进化算法。两者之间有很多相似 之处，均简单易行、鲁棒性强，不需要专门的领域知识而仅用适应度函数做评价来 指导有哪些信誉好的足球投注网站过程，从而得到了广泛的应用，引起了专家学者的广泛关注，得到了很多 显著的成果。 TSP 问题是一个典型的 NP 难题，它的思想在生活生产中运用很广，提高 TSP 问题的解决效率有着现实的意义。因为 NP 问题不能在多项式时间内得到最优解。 因此设计出相应的算法尽快的得到近似解和满意解是很现实的。智能算法就是在这 样的思想指导下被运用于 TSP 问题的。 本文对遗传算法和粒子群算法的理论与运用做了一些探讨。首先介绍了两种算 法的原理和应用，其次分析了 TSP 问题的研究现状、数学模型和解决方案。接着介 绍了两种算法在求解 TSP 问题中的应用和发展。在此基础上，针对 TSP 问题、遗 传算法和粒子群算法进化求解的特点，提出了环路插入方法生成初始种群。并从遗 传算法和粒子群算法的理论基础入手证明了该方法产生的种群对算法的有效性。在 MATLAB 环境下对 UCI 标准数据库中的数据进行了实验，结果表明了该方法产生 初始群体的合理性，本文将使用该方法产生初始种群（粒子群）的算法与其他几种 初始化方法进行了比较，实例仿真证明了该算法的可行性和有效性。 关键词：遗传算法；粒子群算法；旅行商问题；初始种群 II II Research of Improved Evolutionary Resolve Algorithm for TSP ABSTRACT Genetic Algorithm (GA) is a simulation of natural biological evolution of the search algorithm and Particle Swarm Optimization (PSO) is the embodiment of swarm intelligence which also imitates the searching behavior of fishes and birds for food. Both of them are evolutionary algorithms. There