基于遗传——蚁群混合算法求解旅行商问题

Solution of Traveling Salesman Problem Based on Genetic-Ant Colony Algorithms

作为物流领域中的典型问题,旅行商问题的求解具有十分重要的理论和现实意义。在它的传统求解方法中,遗传算法和蚁群算法被广泛采用,但遗传算法收敛速度慢,蚁群算法易陷入局部最优,在求解旅行商问题上都有一定的缺陷。本文采用遗传—蚁群混合算法,充分利用遗传算法的快速全局搜索能力和蚁群算法的智能性,对旅行商问题求解,并进行了实例仿真。仿真计算结果表明,该算法可以找到最优解或近似最优解,并提高了求解效率。

As a typical question in logistics field, solution of Traveling Salesman Problem is of both theoretical significance and practical importance. Genetic Algorithms and Ant Colony Algorithms have been adopted extensively in its solving before. But they are not perfect because Genetic Algorithms converges slowly and Ant Colony Algorithms is prone to trap in local optimum. Genetic-Ant Colony Algorithms is used to solve Traveling Salesman Problem in this paper, fully utilizing quick global searching ability of Genetic algorithms intelligence of Ant Colony. Then instance simulation is proposed and the results show that optimum solution or approximate optimum solution can be gotten using the Algorithms and computational efficiency is increased.