File(s) not publicly available

A cooperative ant colony system and genetic algorithm for TSPs

conference contribution
posted on 06.12.2017, 00:00 by G Dong, Wanwu GuoWanwu Guo
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.

History

Start Page

597

End Page

604

Number of Pages

8

Start Date

01/01/2010

ISSN

0302-9743

ISBN-13

9783642134944

Location

Beijing, China

Publisher

Springer-Verlag

Place of Publication

Germany

Peer Reviewed

Yes

Open Access

No

Era Eligible

Yes

Name of Conference

International Conference on Swarm Intelligence.