Ant-Set: A Subset-Oriented Ant Colony Optimization Algorithm for the Set Covering Problem

Murilo Falleiros Lemos Schmitt (Federal University of Paraná, Brazil)

Mauro Henrique Mulati (Midwestern State University of Parana, Brazil)

Ademir Aparecido Constantino (State University of Maringá, Brazil)

Fábio Hernandes (Midwestern State University of Parana, Brazil)

Tony Alexander Hild (Midwestern State University of Parana, Brazil)

Abstract: This paper proposes an algorithm for the set covering problem based on the metaheuristic Ant Colony Optimization (ACO) called Ant-Set, which uses a lineoriented approach and a novelty pheromone manipulation based on the connections between components of the construction graph, while also applying a local search. The algorithm is compared with other ACO-based approaches. The results obtained show the effectiveness of the algorithm and the impact of the pheromone manipulation.

Keywords: ant colony optimization, ant-set, line-orientation, pheromone manipulation, set covering problem

Categories: G.1, G.1.6