A Cooperative Ant Colony System and Genetic Algorithm for TSPs

摘要

The travelling salesman problem (TSP) is a classic problem of combinatorial optimization and is unlikely to find an efficient algorithm for solving TSPs directly. In the last two decades, ant colony optimization (ACO) has been successfully used to solve TSPs and their associated applicable problems. Despite the success, ACO algorithms have been facing constantly challenges for improving the slow convergence and avoiding stagnation at the local optima. In this paper, we propose a new hybrid algorithm, cooperative ant colony system and genetic algorithm (CoACSGA) to deal with these problems. Unlike the previous studies that regarded GA as a sequential part of the whole searching process and only used the result from GA as the input to the subsequent ACO iteration, this new approach combines both GA and ACS together in a cooperative and concurrent fashion to improve the performance of ACO for solving TSPs. The mutual information exchange between ACS and GA at the end of each iteration ensures the selection of the best solution for the next round, which accelerates the convergence. The cooperative approach also creates a better chance for reaching the global optimal solution because the independent running of GA will maintain a high level of diversity in producing next generation of solutions. Compared with the results of other algorithms, our simulation demonstrates that CoACSGA is superior to other ACO related algorithms in terms of convergence, quality of solution, and consistency of achieving the global optimal solution, particularly for small-size TSPs.