A binary monkey search algorithm variation for solving the set covering problem
- PDF / 442,155 Bytes
- 17 Pages / 595.276 x 790.866 pts Page_size
- 42 Downloads / 191 Views
(0123456789().,-volV)(0123456789(). ,- volV)
A binary monkey search algorithm variation for solving the set covering problem Broderick Crawford1 • Ricardo Soto1 • Rodrigo Olivares1,2 • Gabriel Embry1 • Diego Flores1 Wenceslao Palma1 • Carlos Castro3 • Fernando Paredes4 • Jose´-Miguel Rubio5
•
Springer Nature B.V. 2019
Abstract 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 wellknown 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. Keywords Monkey search algorithm Set covering problem Metaheuristics Parameter setting Optimization problem
1 Introduction Over the years, many companies have seen the need to use their resources to meet the needs of a sector; thus, these companies try to always use their capital as efficiently as
& Broderick Crawford [email protected] & Ricardo Soto [email protected] & Rodrigo Olivares [email protected] 1
Pontificia Universidad Cato´lica de Valparaı´so, Valparaiso, Chile
2
Universidad de Valparaı´so, Valparaiso, Chile
3
Universidad Te´cnica Federico Santa Marı´a, Valparaiso, Chile
4
Escuela de Ingenierı´a Industrial, Universidad Diego Portales, Santiago, Chile
5
Universidad Tecnolo´gica de Chile INACAP, Santiago, Chile
possible, in other words, trying to minimize the costs. Such situations can be represented by the set covering problem, which is a classic problem in combinatorics, computer science (Crawford et al. 2017), and computational complexity theory. Lots of real-world problems have been modeled by the set covering, such as production planning in industry (Vasko et al. 1987), crew scheduling in airlines (Housos and Elmroth 1997), and facility location problem (Vasko and Wilson 1984), among many others. Due to the characteristics of this problem, the complexity of this begins to increase with an increasing num
Data Loading...
