Learning grouping heuristics in ant colony optimization for combinatorial problems

Abstract

Ant colony optimisation (ACO) has demonstrated good performance on a number of combinatorial optimisation tasks. A recent advance demonstrated the successful addition of a grouping heuristic used information from the objective function to prioritise solutions with full bins. This method increased performance further and established grouping-ACO among the state-of-the-art approaches to bin packing. In this paper, we develop a method to learn and apply decision variable groupings during the ACO algorithm run with no additional information from the objective function. This enables the approach to be generalised to any combinatorial problems for which an ACO representation can be formulated. Experimentation is conducted on a number of instances of the bin packing, knapsack and travelling salesman problems and shows improved performance over standard ACO in all cases, and performance approaching grouping-ACO on the bin packing problem.