TY - JOUR
T1 - A binary monkey search algorithm variation for solving the set covering problem
AU - Crawford, Broderick
AU - Soto, Ricardo
AU - Olivares, Rodrigo
AU - Embry, Gabriel
AU - Flores, Diego
AU - Palma, Wenceslao
AU - Castro, Carlos
AU - Paredes, Fernando
AU - Rubio, José Miguel
N1 - Funding Information:
Broderick Crawford is supported by Grant CONICYT/FONDECYT/REGULAR/1171243. Ricardo Soto is supported by Grant CONICYT/FONDECYT/REGULAR/1190129. Rodrigo Olivares is supported by CONICYT/FONDEF/IDeA/ID16I10449, STIC-AMSUD/17STIC- 03, FONDECYT/MEC/MEC80170097 and Postgraduate Grant Pontificia Universidad Cat?lica de Valpara?so (INF-PUCV 2015-2019).
Funding Information:
Broderick Crawford is supported by Grant CONICYT/FONDECYT/REGULAR/1171243. Ricardo Soto is supported by Grant CONICYT/FONDECYT/REGULAR/1190129. Rodrigo Olivares is supported by CONICYT/FONDEF/IDeA/ID16I10449, STIC-AMSUD/17STIC- 03, FONDECYT/MEC/MEC80170097 and Postgraduate Grant Pontificia Universidad Católica de Valparaíso (INF-PUCV 2015-2019).
Publisher Copyright:
© 2019, Springer Nature B.V.
PY - 2020/12/1
Y1 - 2020/12/1
N2 - In complexity theory, there is a widely studied grouping of optimization problems that belongs to the non-deterministic polynomial-time hard set. One of them is the set covering problem, known as one of Karp’s 21 NP-complete problems, and it consists of finding a subset of decision variables for satisfying a set of constraints at the minimum feasible cost. However, due to the nature of the problem, this cannot be solved using traditional complete algorithms for hard instances. In this work, we present an improved binary version of the monkey search algorithm for solving the set covering problem. Originally, this approximate method was naturally inspired by the cognitive behavior of monkeys for climbing mountains. We propose a new climbing process with a better exploratory capability and a new cooperation procedure to reduce the number of unfeasible solutions. For testing this approach, we present a detailed computational results section, where we illustrate how this variation of the monkey search algorithm is capable of reaching various global optimums for a well-known instance set from the Beasley’s OR-Library and how it outperforms many other heuristics and meta-heuristics addressed in the literature. Moreover, we add a complete statistical analysis to show the effectiveness of the proposed approach with respect to the original version.
AB - In complexity theory, there is a widely studied grouping of optimization problems that belongs to the non-deterministic polynomial-time hard set. One of them is the set covering problem, known as one of Karp’s 21 NP-complete problems, and it consists of finding a subset of decision variables for satisfying a set of constraints at the minimum feasible cost. However, due to the nature of the problem, this cannot be solved using traditional complete algorithms for hard instances. In this work, we present an improved binary version of the monkey search algorithm for solving the set covering problem. Originally, this approximate method was naturally inspired by the cognitive behavior of monkeys for climbing mountains. We propose a new climbing process with a better exploratory capability and a new cooperation procedure to reduce the number of unfeasible solutions. For testing this approach, we present a detailed computational results section, where we illustrate how this variation of the monkey search algorithm is capable of reaching various global optimums for a well-known instance set from the Beasley’s OR-Library and how it outperforms many other heuristics and meta-heuristics addressed in the literature. Moreover, we add a complete statistical analysis to show the effectiveness of the proposed approach with respect to the original version.
KW - Metaheuristics
KW - Monkey search algorithm
KW - Optimization problem
KW - Parameter setting
KW - Set covering problem
UR - http://www.scopus.com/inward/record.url?scp=85068911869&partnerID=8YFLogxK
U2 - 10.1007/s11047-019-09752-8
DO - 10.1007/s11047-019-09752-8
M3 - Article
AN - SCOPUS:85068911869
VL - 19
SP - 825
EP - 841
JO - Natural Computing
JF - Natural Computing
SN - 1567-7818
IS - 4
ER -