Ant-Q: A Reinforcement Learning Approach to the Traveling Salesman Problem
Abstract
In this paper we introduce Ant-Q, a family of algorithms which present many similarities with Q-learning (Watkins, 1989), and which we apply to the solution of symmetric and asymmetric instances of the traveling salesman problem (TSP). Ant-Q algorithms were inspired by work on the ant system (AS), a distributed algorithm for combinatorial optimization based on the metaphor of ant colonies which was recently proposed in (Dorigo, 1992; Dorigo, Maniezzo and Colorni, 1996). We show that AS is a particular instance of the Ant-Q family, and that there are instances of this family which perform better than AS. We experimentally investigate the functioning of Ant-Q and we show that the results obtained by Ant-Q on symmetric TSP's are competitive with those obtained by other heuristic approaches based on neural networks or local search. Finally, we apply Ant-Q to some difficult asymmetric TSP's obtaining very good results: Ant-Q was able to find solutions of a quality which usually can be found only by very specialized algorithms.
Cite
Text
Gambardella and Dorigo. "Ant-Q: A Reinforcement Learning Approach to the Traveling Salesman Problem." International Conference on Machine Learning, 1995. doi:10.1016/B978-1-55860-377-6.50039-6Markdown
[Gambardella and Dorigo. "Ant-Q: A Reinforcement Learning Approach to the Traveling Salesman Problem." International Conference on Machine Learning, 1995.](https://mlanthology.org/icml/1995/gambardella1995icml-ant/) doi:10.1016/B978-1-55860-377-6.50039-6BibTeX
@inproceedings{gambardella1995icml-ant,
title = {{Ant-Q: A Reinforcement Learning Approach to the Traveling Salesman Problem}},
author = {Gambardella, Luca Maria and Dorigo, Marco},
booktitle = {International Conference on Machine Learning},
year = {1995},
pages = {252-260},
doi = {10.1016/B978-1-55860-377-6.50039-6},
url = {https://mlanthology.org/icml/1995/gambardella1995icml-ant/}
}