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. 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