沈继红，王侃

(1.哈尔滨工程大学理学院，黑龙江 哈尔滨 150001;2.哈尔滨工程大学自动化学院，黑龙江 哈尔滨 150001)

优化问题可以自然分为2类:一类是连续变量的优化问题;另一类是离散变量的优化问题，即所谓的组合优化问题.旅行商问题(travel salesman problem，TSP)是组合优化问题中的一个著名NP难题，TSP因其典型性已经成为许多启发式搜索、优化算法的间接比较标准.同时TSP也是一个具有广泛的应用背景与重要理论价值的组合优化难题，对求解该问题高效的全局优化算法的研究，一直被科学界和工程界所高度重视.

TSP问题的求解方法归纳起来可以分为得到最优解的精确算法和找到近似解的近似算法.完全枚举法、动态规划法和全局搜索算法属于精确算法.TSP问题精确算法的运行时间是指数级复杂度，难以适应大规模的实例，随着对TSP问题的认识加深，精确算法的研究越来越少.近年来受到自然界的启发，人们提出了各种各样的计算智能方法，如人工神经网络、遗传算法、蚁群优化算法、粒子群优化算法和人工免疫系统等.智能优化算法为解决TSP问题提供了新的思路，它们被广泛地应用于各种NP难题的优化问题求解，虽然不能保证获取最优解，但在问题规模较大时也可以在可行时间内找到满意的解.

粒子群优化算法(particle swarm optimization，PSO)是一种群智能优化方法，它是由美国社会心理学家Kennedy和电气工程师R.Eberhart在1995年提出的，它利用了生物群体中信息共享的思想，其概念简单、易于实现，同时……