JUCS - Journal of Universal Computer Science 26(2): 293-316, doi: 10.3897/jucs.2020.016
Ant-Set: A Subset-Oriented Ant Colony Optimization Algorithm for the Set Covering Problem
expand article infoMurilo Falleiros Lemos Schmitt‡, Mauro Henrique Mulati§, Ademir Aparecido Constantino|, Fábio Hernandes§, Tony Alexander Hild§
‡ Federal University of Paraná, Curitiba, Brazil§ Midwestern State University of Parana, Guarapuava, Brazil| Universidade Estadual de Maringá, Maringá, Brazil

Corresponding author: Murilo Falleiros Lemos Schmitt ( muriloschmitt@gmail.com )

© Murilo Falleiros Lemos Schmitt, Mauro Mulati, Ademir Constantino, Fábio Hernandes, Tony Hild.
This is an open access article distributed under the terms of the Creative Commons Attribution License (CC BY-ND 4.0). This license allows reusers to copy and distribute the material in any medium or format in unadapted form only, and only so long as attribution is given to the creator. The license allows for commercial use.
Citation: Schmitt MFL, Mulati MH, Constantino AA, Hernandes F, Hild TA (2020) Ant-Set: A Subset-Oriented Ant Colony Optimization Algorithm for the Set Covering Problem. JUCS - Journal of Universal Computer Science 26(2): 293-316. https://doi.org/10.3897/jucs.2020.016
Open Access
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, set covering problem, pheromone manipulation, line-orientation