Open Access

ARTICLE

Binary Fruit Fly Swarm Algorithms for the Set Covering Problem

Broderick Crawford^1,*, Ricardo Soto¹, Hanns de la Fuente Mella¹, Claudio Elortegui¹, Wenceslao Palma¹, Claudio Torres-Rojas¹, Claudia Vasconcellos-Gaete², Marcelo Becerra¹, Javier Peña¹, Sanjay Misra³
1 Pontificia Universidad Católica de Valparaíso, Valparaíso, 2362807, Chile
2 LERIA, Université d'Angers, Angers, 49000, France
3 Department of Computer Science and Communication, Ostfold University College, Halden, Norway
* Corresponding Author: Broderick Crawford. Email:
(This article belongs to this Special Issue: Recent Advances in Metaheuristic Techniques and Their Real-World Applications)

Computers, Materials & Continua 2022, 71(3), 4295-4318. https://doi.org/10.32604/cmc.2022.023068

Received 27 August 2021; Accepted 21 October 2021; Issue published 14 January 2022

Abstract

Currently, the industry is experiencing an exponential increase in dealing with binary-based combinatorial problems. In this sense, metaheuristics have been a common trend in the field in order to design approaches to solve them successfully. Thus, a well-known strategy consists in the use of algorithms based on discrete swarms transformed to perform in binary environments. Following the No Free Lunch theorem, we are interested in testing the performance of the Fruit Fly Algorithm, this is a bio-inspired metaheuristic for deducing global optimization in continuous spaces, based on the foraging behavior of the fruit fly, which usually has much better sensory perception of smell and vision than any other species. On the other hand, the Set Coverage Problem is a well-known NP-hard problem with many practical applications, including production line balancing, utility installation, and crew scheduling in railroad and mass transit companies. In this paper, we propose different binarization methods for the Fruit Fly Algorithm, using S-shaped and V-shaped transfer functions and various discretization methods to make the algorithm work in a binary search space. We are motivated with this approach, because in this way we can deliver to future researchers interested in this area, a way to be able to work with continuous metaheuristics in binary domains. This new approach was tested on benchmark instances of the Set Coverage Problem and the computational results show that the proposed algorithm is robust enough to produce good results with low computational cost.

---

Keywords

Set covering problem; fruit fly swarm algorithm; metaheuristics; binarization methods; combinatorial optimization problem

---