An ant colony optimization meta-heuristic for subset selection problems

Subset selection problems involve finding an optimal feasible subset of an initial set of objects with respect to an objective function and/or some constraints. Many well-known combinatorial problems are members of this class, e.g., maximum clique problems, knapsack problems, boolean satisfiability problems, constraint satisfaction problems, and graph matching problems. In this chapter we define a generic ant colony optimization (ACO) algorithm for this class of problems. Basically, this algorithm successively generates subsets through the repeated selection of objects, and uses "pheromone trails" as a greedy heuristic to choose, at each step, the next object to be selected. Our algorithm unifies existing, different ACO algorithms for subset selection problems. It provides a generic framework that can be instantiated to solve different subset selection problems and to accommodate different strategies for finding solutions to those problems. In particular, the algorithm is parameterized by a pheromonal strategy and we propose and compare two different instantiations of it: a first one where pheromone is laid on objects and a second one where pheromone is laid on cliques of objects. The proposed algorithm is also parameterized by problem-specific features, and we present and evaluate instantiations of it for solving maximum clique problems, knapsack problems and constraint satisfaction problems.