粒子群优化算法研究及其在TSP问题中的应用

粒子群优化算法是一种新型的进化计算技术，由Eberhart博士和Kennedy博士于1995年提出。PSO算法已经被证明是一种有效的全局优化方法，并且广泛应用于函数优化，神经网络训练以及模糊系统控制等领域。目前对粒子群优化算法的研究尚处于初期，它今后的发展还有许多工作需要不断充实提高。因此以粒子群优化算法为主要研究对象，寻找求解实际问题的更加有效的改进算法是很有意义的。 本文分析了粒子群优化算法的原理，根据算法的特点总结了应用粒子群优化算法的步骤，给出算法中的经验参数设置。总结目前PSO算法研究的成果，对比分析了目前对粒子群优化算法的多种改进。 粒子群优化算法的理论研究还很缺乏，还没有粒子群理论的证明。已有的研究表明，粒子群优化算法的参数设置决定了算法的性能，目前对粒子群优化算法的改进大都是建立在对参数设置问题的改进基础上。本文研究了粒子在搜索空间飞行的轨迹，分析了使粒子群收敛的参数设置。 基于对粒子群优化算法原理的分析，本文提出一种新型的模糊自适应粒子群优化算法。该算法的主要特点是：在同一种群中使用不同的惯性权值，通过提高收敛速度来提高算法性能；同时保持了群体粒子的多样性，克服使用全局惯性权值算法容易陷入局部最优值的缺陷。使用四个不同类型基准函数测试结果表明，新型算法比全局惯性权值算法性能更好。 旅行商问题是图论中一个经典的组合优化问题，是一个典型的NP难题，许多实际问题都可以转化为旅行商问题。本文分析了粒子群优化算法的离散化，设计了粒子群算法求解旅行商问题的相关操作，将新型模糊自适应粒子群优化算法应用到旅行商问题的求解。新型算法在解决旅行商问题的性能明显高于全局惯性权值算法。