Open Access

ARTICLE

Binary Fruit Fly Swarm Algorithms for the Set Covering Problem

Broderick Crawford1,*, Ricardo Soto1, Hanns de la Fuente Mella1, Claudio Elortegui1, Wenceslao Palma1, Claudio Torres-Rojas1, Claudia Vasconcellos-Gaete2, Marcelo Becerra1, Javier Peña1, Sanjay Misra3
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

Cite This Article

B. Crawford, R. Soto, H. De la Fuente Mella, C. Elortegui, W. Palma et al., "Binary fruit fly swarm algorithms for the set covering problem," Computers, Materials & Continua, vol. 71, no.3, pp. 4295–4318, 2022.



This work is licensed under a Creative Commons Attribution 4.0 International License , which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
  • 1002

    View

  • 649

    Download

  • 0

    Like

Share Link

WeChat scan