Adding Negative Learning to Ant ColonyOptimization: A Comprehensive Study

Ant colony optimization is a metaheuristic that is mainly used for solving hard combinatorial optimization problems. The distinctive feature of ant colony optimization is a learning mechanism that is based on learning from positive examples. Examples from nature, however, indicate that negative learning—in addition to positive learning—can beneficially be used for certain purposes. Several research papers have explored this topic over the last decades in the context of ant colony optimization, mostly with limited success. In this talk I present an alternative mechanism making use of mathematical programming for the incorporation of negative learning in ant colony optimization. The study considers two classical combinatorial optimization problems: the minimum dominating set problem and the multi dimensional knapsack problem. In both cases our approach significantly improves over standard ant colony optimization and over the competing negative learning mechanisms from the literature.