Date of Award
9-2007
Document Type
Thesis
Degree Name
Master of Science in Computer Science
Department
Department of Electrical and Computer Engineering
First Advisor
Gilbert L. Peterson, PhD
Abstract
This research merges the hierarchical reinforcement learning (HRL) domain and the ant colony optimization (ACO) domain. The merger produces a HRL ACO algorithm capable of generating solutions for both domains. This research also provides two specific implementations of the new algorithm: the first a modification to Dietterich's MAXQ-Q HRL algorithm, the second a hierarchical ACO 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 and SARSA, 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 research 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 research tests two clustering algorithms, k-means and G-means. The results demonstrate the algorithm with data clustering produces solutions 85-95% faster but with 5-10% decrease in solution quality.
AFIT Designator
AFIT-GCS-ENG-07-16
DTIC Accession Number
ADA476631
Recommended Citation
Dries, Erik J., "Scaling Ant Colony Optimization with Hierarchical Reinforcement Learning Partitioning" (2007). Theses and Dissertations. 3119.
https://scholar.afit.edu/etd/3119