Abstract: It can restrain premature of ant colony algorithms and accelerate the convergence rate of the algorithms, combining ant colony algorithms with heuristic algorithms. The solution quality and efficiency of heuristic algorithms can be improved through establishing reference optimization edge set used by local search algorithms. The strategy of path exchanging can improve convergence rate and capacity of searching optimal solution. The results of experiments indicate that new hybrid ant colony algorithm can find global optimal solution of TSP whose scale is less than 2000.

Key words: traveling salesman problem, ant colony algorithm, path exchanging, global optimal solution, reference optimization edge set

摘要： 将蚁群算法与局部搜索优化算法结合，可抑制蚁群算法早熟收敛问题，并能提高蚁群算法的收敛速度。通过建立有效的局部搜索优化算法的参照优化边集，提高其求解质量和效率；引入路径交换策略提高蚁群算法的收敛速度和寻优能力。实验结果表明改进的混合蚁群算法能求解规模在2000个城市以内的旅行商问题的全局最优解。

关键词: 旅行商问题, 蚁群算法, 路径交换, 全局最优解, 参照优化边集