TY - JOUR

T1 - Binary Fruit Fly Swarm Algorithms for the Set Covering Problem

AU - Crawford, Broderick

AU - Soto, Ricardo

AU - de la Fuente Mella, Hanns

AU - Elortegui, Claudio

AU - Palma, Wenceslao

AU - Torres-Rojas, Claudio

AU - Vasconcellos-Gaete, Claudia

AU - Becerra, Marcelo

AU - Peña, Javier

AU - Misra, Sanjay

N1 - Publisher Copyright:
© 2022 Tech Science Press. All rights reserved.

PY - 2022

Y1 - 2022

N2 - 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.

AB - 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.

KW - Binarization methods

KW - Combinatorial optimization problem

KW - Fruit fly swarm algorithm

KW - Metaheuristics

KW - Set covering problem

UR - http://www.scopus.com/inward/record.url?scp=85122754441&partnerID=8YFLogxK

U2 - 10.32604/cmc.2022.023068

DO - 10.32604/cmc.2022.023068

M3 - Article

AN - SCOPUS:85122754441

SN - 1546-2218

VL - 71

SP - 4295

EP - 4318

JO - Computers, Materials and Continua

JF - Computers, Materials and Continua

IS - 2

ER -