Pre-scheduled and adaptive parameter variation in MAX-MIN Ant System

MAX-MIN Ant System (MMAS) is an ant colony optimization (ACO) algorithm that was originally designed to start with a very explorative search phase and then to make a slow transition to an intensive exploitation of the best solutions found during the search. This design leads to a rather slow initial convergence of the algorithm, and, hence, to poor results if the algorithm does not run for sufficient time. This article illustrates that varying the parameter settings of MMAS while solving an instance may significantly improve the anytime search behavior of MMAS. Even rather simple pre-scheduled variations of the parameter settings that only depend on the number of iterations or the computation time show improvement over fixed parameter settings. The degree of improvement, however, is not uniform across problems. In particular, the improvement is very strong in the traveling salesman problem (TSP) but small, if at all noticeable, in the quadratic assignment problem (QAP). This paper also presents an adaptive parameter variation specifically designed for the TSP. The experimental results show that the pre-scheduled variations are comparable to the proposed adaptive variation in terms of the anytime behavior of MMAS.