109

urn:lsid:arphahub.com:pub:3dc5f44e-8666-58db-bc76-a455210e8891

JUCS - Journal of Universal Computer Science

jucs

0948-695X 0948-6968

Journal of Universal Computer Science

10.3897/jucs.2020.016

24001

Research Article

G.1.6 - Optimization G.1 - NUMERICAL ANALYSIS

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

Schmitt

Murilo Falleiros Lemos

muriloschmitt@gmail.com 1 Mulati

Mauro Henrique

2 Constantino

Ademir Aparecido

3 Hernandes

Fábio

2 Hild

Tony Alexander

Federal University of Paraná, Curitiba, Brazil

Federal University of Paraná

Curitiba

Brazil 2

Midwestern State University of Parana, Guarapuava, Brazil

Midwestern State University of Parana

Guarapuava

Brazil 3

Universidade Estadual de Maringá, Maringá, Brazil

Universidade Estadual de Maringá

Maringá

Brazil

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

Academic editor:

2020

28 02 2020

26 2 293 316 05E4DD8C-B9F5-596B-BD19-FE04193E30AC 5508499 11 12 2018 05 02 2020

Murilo Falleiros Lemos Schmitt, Mauro Henrique Mulati, Ademir Aparecido Constantino, Fábio Hernandes, Tony Alexander 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.

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.