谢 旻

（南京工业大学 电子与信息工程学院，南京210009）

TSP（traveling salesman problem）也称旅行商问题，是一个经典的 NP（non－deterministic polynomial）问题，可以简单地描述成：已知n个城市的坐标，寻找一条走遍所有城市且路径最短的路线。其数学模型如下：设有城市集合C＝｛C1，C2，C3，…，Cn｝，其每对城市的距离为d（Ci，Cj），求一条经过C中每个城市恰好一次的路径（C1，C2，C3，…，Cn），使的值最小。

针对TSP提出的随机优化方法包括神经网络算法、模拟退火算法、遗传算法以及近年来提出的群体智能算法等。其中，粒子群算法（PSO算法）由于模型简单、参数少而得到了广泛应用。为了进一步提高算法的性能，大量研究基于PSO算法，融合了进化算法或采用混合群体优化方法。如文献［1］对离散粒子群算法分别加入逆转变异优化策略、受蚁群启示的变异优化策略以及近邻搜索变异优化策略；文献［2］通过改进离散粒子群运动方程，加入启发因子，提高算法的收敛性和稳定性；文献［3］利用遗传算法全局搜索能力强的特点对用粒子群优化算法所求解进行优化；文献［4］提出一种融合蚁群算法、遗传算法、粒子群优化算法思想的混合算法；文献［5］提出一种自适应离散PSO算法，并利用调节算子和交换序对PSO算法进行改进，等等。但已有文献大多针对整个种群进行进化操作，并未在现有种群上分类筛选优质个体，淘汰劣质个体，笔者通过对已有文献的研究，提出一种混合粒子群优化方法，加入种群分类机制，对划分后的子种群实施不同的策略达到保留优秀个体的目的，从而提高算法的性能。……