潘 澔, 孙 俐, 高 尚*

(1.苏州建设交通高等职业技术学校，苏州 215104) (2.江苏科技大学 计算机学院，镇江 212100)

旅行商问题(traveling salesman problem,TSP)可以描述为有一个推销员从某城市出发走遍所有的城市，且每个城市只能走一次，最后返回原处，如何选择路线使所走路程最短.TSP问题是一个NP完全问题，对于一个N个城市的TSP问题，可能的路径数是一个组合数(N-1)!/2, 随着城市数目N的增大，问题的规模呈指数式增大.TSP问题是组合优化领域中的一个典型的问题，解决此问题有较大的现实意义，如印刷电路板的钻空路线方案，连锁店送货路线问题等都可简化为TSP问题.并且此问题也可作为测试新的算法的标准问题，因此一直是研究的热点.目前求解TSP问题的主要方法有模拟退火算法[1]，遗传算法[1-2]，启发式搜索法，Hopfield神经网络算法[1]，蚁群算法[3]，演化算法[4],近似多项式方法[5]等.文中依据分布估计算法的思想，提出一种蚁群分布估计混合算法来解决旅行商问题.

1 基本蚁群算法

蚂蚁个体之间是通过一种称之为外激素的物质进行信息传递，从而能相互协作，完成复杂的任务.蚂蚁在运动过程中，能够在它所经过的路径上留下该种物质，而且蚂蚁在运动过程中能够感知这种物质的存在及其强度，并以此指导自己的运动方向，蚂蚁倾向于朝着该物质强度高的方向移动.因此，由大量蚂蚁组成的蚁群的集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率……