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

作者：Lanza Gutierrez Jose M; Crawford Broderick; Soto Ricardo; Berrios Natalia; Gomez Pulido Juan A; Paredes Fernando

来源：Expert Systems with Applications, 2017, 70: 67-82.

DOI：10.1016/j.eswa.2016.10.054

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

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.

• 出版日期2017-3-15