Analyzing the effects of binarization techniques when solving the set covering problem through swarm optimization. (15th March 2017)

• Record Type: Journal Article
• Authors: Lanza-Gutierrez, Jose M.; Crawford, Broderick; Soto, Ricardo; Berrios, Natalia; Gomez-Pulido, Juan A.; Paredes, Fernando
• Is Part Of: Expert systems with applications. Volume 70(2017)
• Page Start: 67
• Page End: 82
• Publication Date: 2017-03-15
• Subjects: Binarization technique -- Cat swarm optimization -- Continuous optimization -- Discrete optimization -- Set covering problem -- Swarm intelligence; Expert systems (Computer science) -- Periodicals; Systèmes experts (Informatique) -- Périodiques; Electronic journals; 006.33
• DOI: 10.1016/j.eswa.2016.10.054
• Languages: English
• ISSNs: 0957-4174

Abstract

Highlights: We study the impact of binarization methods when solving the set covering problem. We apply a metaheuristic inspired by the behavior of cats for solving the problem. We consider forty binarization methods and a freely available dataset. We conclude that it is crucial to select an adequate binarization method. 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.