Analyzing the effects of binarization techniques when solving the set covering problem through swarm optimization

Jose M. Lanza-Gutierrez, Broderick Crawford, Ricardo Soto, Natalia Berrios, Juan A. Gomez-Pulido, Fernando Paredes

Research output: Contribution to journalArticlepeer-review

32 Scopus citations

Abstract

The Set Covering Problem (SCP) is one of the classical Karp's 21 NP-complete problems. Although this is a traditional optimization problem, we find many papers assuming metaheuristics for solving the SCP in the current literature. However, while the SCP is a discrete problem, most metaheuristics are defined for solving continuous optimization problems, specially Swarm Intelligence Algorithms (SIAs). Hence, such algorithms should be adapted for working on the discrete scope, but most authors did not perform any study to select a concrete binarization approach. This situation might lead to the conclusion that selecting a concrete binarization technique does not influence the behavior of the algorithm, but rather the general approach of the metaheuristic. This circumstance led us to write this paper focusing on the inherent difficulty in binarization of metaheuristics designed for continuous optimization, when solving a discrete optimization problem, concretely the SCP. To this end, we consider a recent SIA inspired by the behavior of cats and adapted to the discrete scope, which is called Binary Cat Swarm Optimization (BCSO). We replace the binarization technique assumed in the original BCSO by forty different approaches from the current literature. The results obtained while solving a standard SCP benchmark are analyzed through a widely accepted statistical method, concluding that it is crucial to select an adequate binarization approach to ensure that the solving algorithm reaches its full potential. Thus, the task of adapting a metaheuristic to the discrete scope is not a simple matter and should be carefully studied. To this end and as a result of this study, we give some recommendations to perform this task.

Original languageEnglish
Pages (from-to)67-82
Number of pages16
JournalExpert Systems with Applications
Volume70
DOIs
StatePublished - 15 Mar 2017
Externally publishedYes

Keywords

  • Binarization technique
  • Cat swarm optimization
  • Continuous optimization
  • Discrete optimization
  • Set covering problem
  • Swarm intelligence

Fingerprint

Dive into the research topics of 'Analyzing the effects of binarization techniques when solving the set covering problem through swarm optimization'. Together they form a unique fingerprint.

Cite this