基于混合粒子群算法的旅行商问题研究（毕业论文）.doc

石家庄经济学院本科生毕业论文 PAGE PAGE III 摘 要 演化计算是模拟自然界生物演化过程的一种群体导向随机搜索技术。近年来，用演化算法求解组合优化问题已经成为研究热点，旅行商问题，是一类NP完全的组合优化问题，有效地求解旅行商问题，对于组合优化问题的求解有着十分重要的意义。 标准粒子群算法 REF _Ref326846691 \r \h \* MERGEFORMAT [6]通过追随个体极值和群体极值来完成极值寻优的，虽然操作简单，且能够快速收敛，但是随着迭代次数的不断增加，在种群收敛集中的同时，各粒子也越来越相似，可能在局部解周边无法跳出。针对该算法的不足，本文在标准粒子群优化算法的基础上通过引用遗传算法思想中的交叉和变异操作来改善粒子群算法，从而避免了标准粒子群优化算法可能陷入局部最优的情况，并将其应用于求解旅行商（TSP）问题。本文将改进的粒子群算法在14城市和30城市及50城市这三个实例中进行了仿真，结果表明了基于混合粒子群优化算法对于求解组合优化问题的优越性，对小规模城市坐标精确度非常高。 关键词：粒子群算法；组合优化；遗传算法；TSP ABSTRACT The evolutionary computation simulation nature is a kind of biological evolution process group oriented random search technology. In recent years, with the evolutionary algorithm to solve combinatorial optimization problem has become the focus in the traveling salesman problem, is a kind of NP complete combinatorial optimization problem, effective solution traveling salesman problem for combinatorial optimization problem solving is very important meaning. The standard particle swarm algorithm through the following individuals and groups to complete the extreme value of extreme value optimization extreme, although the operation is simple, and can be fast convergence, but, with the increase of iteration times, in a population concentration of convergence at the same time, each particle also more and more similar, may be in local solution for peripheral could not get out. According to the deficiency of the algorithm, based on the standard particle swarm optimization algorithm based on genetic algorithm through reference thoughts of crossover and mutation operators to improve particle swarm algorithm, and avoid the standard particle swarm optimization algorithm may fall into the local optimal situation, and is applied to solving the traveling salesman problem (TSP). This paper will be improved particle swarm algorithm in 14 cities and 30 cities and 50 city the three examples of simulation. The results show that the hybrid particle swarm optimization algorithm for solving the co