Constraint handling and stochastic ranking in ACO

Many industrial and academic optimization problems have successfully been tackled with ant colony optimization (ACO), but the ability of ACO to deal with hard constraints has not yet been investigated widely. Most real-world applications, such as fleet routing, rostering and timetabling, however, are subject to hard constraints. Extensions of ACO with hard constraint handling are thus a worthwhile field of study. Constraint handling in meta-heuristics has mostly been studied in the context of evolutionary algorithms. Many of the techniques proposed are penalty-based. A difficulty with such methods is the correct adjustment of penalty factors. Recently a different approach, termed stochastic ranking (SR), has been suggested which does not use a penalty formulation. Benchmarks indicate that SR is currently among the best performing methods for evolutionary constraint optimization. We discuss how the ideas underlying SR can be used in ACO and evaluate two different ways to achieve this integration: one derived from ACS (ACSsr) and one based on ranked ant system (ASRsr). We compare the performance of these to penalty-based ACO as well as to CPACS, an ACO algorithm hybridized with explicit constraint propagation. Initial benchmark results are encouraging.