Bayesian Parameter Tuning of the Ant Colony Optimization Algorithm : Applied to the Asymmetric Traveling Salesman Problem

Abstract: The parameter settings are vital for meta-heuristics to be able to approximate the problems they are applied to. Good parameter settings are difficult to find as there are no general rules for finding them. Hence, they are often manually selected, which is seldom feasible and can give results far from optimal. This study investigated the potential of tuning meta-heuristics using a hyper- parameter tuning algorithm from the field of machine learning, where parameter tuning is a common and well-explored area. We used Bayesian Optimization, a state-of-the-art black-box optimization method, to tune the Ant Colony Optimization meta-heuristic. Bayesian Optimization using the three different acquisition functions Expected Improvement, Probability of Improvement and Lower Confidence Bound, as well as the three functions combined using softmax, were evaluated and compared to using Random Search as an optimization method. The Ant Colony Optimization algorithm with its parameters tuned by the different methods was applied to four Asymmetric Traveling Salesman problem instances. The results showed that Bayesian Optimization both leads to better solutions and does so in significantly fewer iterations than Random Search. This suggests that Bayesian Optimization is preferred to Random Search as an optimization method for the Ant Colony Optimization metaheuristic, opening for further research in tuning meta-heuristics with Bayesian Optimization.