Automatically configuring ACO using multilevel ParamILS to solve transportation planning problems with underlying weighted networks

摘要

Configuring parameter settings for ant colony optimisation (ACO) based algorithms is a challenging and time consuming task, because it usually requires evaluating a large number of parameter combinations to find the most appropriate setting. In this study, a multilevel ParamILS (MParamILS) technique, that combines a graph coarsening method and the ParamILS framework, has been developed for configuring ACO algorithms to solve transportation planning problems with underlying weighted networks. The essential idea is to first use the graph coarsening method to recursively produce a set of increasingly coarser level problems from the original problem, and then apply ParamILS sequentially to the coarser level problems to select high-quality settings from a parameter combination domain. From the coarsest level to the finest (original) level problem, the parameter domain is refined by removing the low-quality settings identified by ParamILS. The size of the combination domain continues to decrease, resulting in fewer number of parameter combinations evaluated at finer level problems, hence the computing time is reduced. The performance of MParamILS was compared with ParamILS. Experimental results showed that MParamILS matches ParamILS in solution quality with significant reduction in computing time for all test cases.