一种求解TSP问题的多策略改进蚁群算法

Research on An Improved Multi-strategy Ant Colony Algorithm for TSP Problem

蚁群算法是一种求解复杂组合优化问题的启发式仿生进化算法,并是求解TSP问题行之有效的一种随机算法.但此算法仍存在求解精度低、易陷入局部最优及求解效率低的问题,针对该问题提出一种多策略改进蚁群算法.采用最近邻法影响初始信息素的分布,达到降低算法初期较短路径上信息素浓度的目的,并在转移规则变异调整的基础上,结合路径的均值交叉进化策略,增强算法探索全局解空间和避免陷入局部最优的能力.然后,结合迭代和精英策略对信息素更新机制进行改进,进一步提高化算法的求解性能及求解效率,最后,对从TSPLIB数据库选出的8个实例进行求解并与其他算法进行对比,实验结果表明,改进算法在求解旅行商问题时的高效性,且具有较高的运算性能.

The ant colony algorithm is a heuristic bionic evolutionary algorithm for solving complex combinatorial optimization problems, and it is a kind of random algorithm to solve the TSP problem. However, this algorithm still had the problems of low solution precision, easy to fall into local optimum and low efficiency. A multi-strategy improved ant colony algorithm was proposed for this problem. The nearest neighbor method affected the distribution of initial pheromone to reduce the concentration of pheromone in the initial path of the algorithm.Based on the adjustment of the variation of the transfer rule, combined with the mean crossevolution strategy of the path, the enhanced algorithm explored the global solution space and avoided the ability to fall into local optimum. Then, the pheromone update mechanism was improved by combining iterative and elite strategies to further improved the performance and efficiency of the algorithm. Finally, the eight examples selected from the TSPLIB database were solved and compared with other algorithms. The experimental results showed that the improved algorithm was efficient in solving the traveling salesman problem and had high computational performance.