Scaling ant colony optimization with hierarchical reinforcement learning partitioning

ABSTRACT

This paper merges hierarchical reinforcement learning (HRL) with ant colony optimization (ACO) to produce a HRL ACO algorithm capable of generating solutions for large domains. This paper describes two specific implementations of the new algorithm: the first a modification to Dietterich's MAXQ-Q HRL algorithm, the second a hierarchical ant colony system algorithm. These implementations generate faster results, with little to no significant change in the quality of solutions for the tested problem domains. The application of ACO to the MAXQ-Q algorithm replaces the reinforcement learning, Q-learning, with the modified ant colony optimization method, Ant-Q. This algorithm, MAXQ-AntQ, converges to solutions not significantly different from MAXQ-Q in 88% of the time. This paper then transfers HRL techniques to the ACO domain and traveling salesman problem (TSP). To apply HRL to ACO, a hierarchy must be created for the TSP. A data clustering algorithm creates these subtasks, with an ACO algorithm to solve the individual and complete problems. This paper tests two clustering algorithms, k-means and G-means. The results demonstrate the algorithm with data clustering produces solutions 20 times faster with 5-10% decrease in solution quality due to the effects of clustering.

REFERENCES

• 1: Andrew G. Barto , Sridhar Mahadevan, Recent Advances in Hierarchical Reinforcement Learning, Discrete Event Dynamic Systems, v.13 n.1-2, p.41-77, January-April 2003 [doi>10.1023/A:1022140919877]
• 2: Eric Bonabeau , Marco Dorigo , Guy Theraulaz, Swarm intelligence: from natural to artificial systems, Oxford University Press, Inc., New York, NY, 1999
• 3: T. G. Dietterich. Hierarchical reinforcement learning with the maxq value function decomposition. Journal of Artificial Intelligence, (13):227--303, Nov. 2000.
• 4: M. Dorigo, M. Birattari, and T. Stutzle. Ant colony optimization. Computational Intellligence Magazine, IEEE, 1(4):28--39, 2006.
• 5: M. Dorigo and L. M. Gambardella. Ant colony system: A cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation, 1(1):53--66, April 1997.
• 6: L. M. Gambardella and M. Dorigo. Ant-q: A reinforcement learning approach to the traveling salesman problem. In International Conference on Machine Learning, pages 252--260, 1995.
• 7: G. Hamerly and C. Elkan. Learning the k in k-means. In Proceedings of the Seventeenth Annual Conference on Neural Information Processing Systems (NIPS), pages 281--288, 2003.
• 8: Tommi Jaakkola , Michael I. Jordan , Satinder P. Singh, On the Convergence of Stochastic Iterative Dynamic Programming Algorithms, Massachusetts Institute of Technology, Cambridge, MA, 1993
• 9: J. B. MacQueen. Some methods for classification and analysis of multivariate observations. In Proceedings of the Fifth Symposium on Mathematical Statistics and Probabilities, pages 281--297, 1967.
• 10: R. Parr and S. Russell. Reinforcement learning with hierarchies of machines, Jan. 17 1997.
• 11: Dan Pelleg , Andrew W. Moore, X-means: Extending K-means with Efficient Estimation of the Number of Clusters, Proceedings of the Seventeenth International Conference on Machine Learning, p.727-734, June 29-July 02, 2000
• 12: G. Reinelt. Tsplib 95, 2007.
• 13: W. D. Smart. Explicit manifold representations for value-functions in reinforcement learning. In Proceedings of the Eighth International Symposium on Artificial Intelligence and Mathematics, January 2004. Paper number AI&M 25-2004.
• 14: T. Stutzle and H. Hoos. The max-min ant system and local search for combinatorial optimization problems, 1999.
• 15: Richard S. Sutton , Andrew G. Barto, Introduction to Reinforcement Learning, MIT Press, Cambridge, MA, 1998
• 16: Richard S. Sutton , Doina Precup , Satinder Singh, Between MDPs and semi-MDPs: a framework for temporal abstraction in reinforcement learning, Artificial Intelligence, v.112 n.1-2, p.181-211, Aug. 1999 [doi>10.1016/S0004-3702(99)00052-1]
• 17: C. Walshaw. A Multilevel Approach to the Travelling Salesman Problem. Tech. Rep. 00/IM/63, Comp. Math. Sci., Univ. Greenwich, London SE10 9LS, UK, August 2000.
• 18: C. Watkins. Learning From Delayed Rewards. PhD thesis, King's College, Oxford, May 1989.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Concept learning

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

General Terms:
Algorithms

Keywords:
ant colony optimization, hierarchical reinforcement learning, swarm intelligence