Ant colony optimization for dynamic combinatorial optimization problems

Abstract

The ant colony optimization (ACO) meta-heuristic was inspired from the foraging behaviour of real ant colonies. In particular, real ants communicate indirectly via pheromone trails and find the shortest path. Although real ants proved that they can find the shortest path when the available paths are known a prior, they may face serious challenges when some paths are made available after the colony has converged to a path. This is because the colony may continue to follow the current path rather than exploring the new paths in case a shorter path is available. For the ACO meta-heuristic, the challenges are similar when applied to dynamic optimization problems (DOPs). Once the algorithm converges, it loses its adaptation capabilities and may have poor performance in DOPs. Several strategies have been integrated with ACO to address difficult combinatorial DOPs. Their performance proved that ACO is a powerful computational technique for combinatorial DOPs once enhanced. This chapter investigates the applications of ACO for combinatorial DOPs.