Solving the Set Covering Problem with a Binary Black Hole Inspired Algorithm
There are multiple problems in several industries that can be solved with combinatorial optimization. In this sense, the Set Covering Problem is one of the most representative of them, being used in various branches of engineering and science, allowing fi
- PDF / 1,038,772 Bytes
- 13 Pages / 439.37 x 666.142 pts Page_size
- 113 Downloads / 186 Views
ificia Universidad Cat´ olica de Valpara´ıso, 2362807 Valpara´ıso, Chile {alvaro.gomez.r,adrian.jaramillo.s, sebastian.mansilla.v,juan.salas.f}@mail.pucv.cl, {broderick.crawford,ricardo.soto}@pucv.cl 2 Universidad Central de Chile, 8370178 Santiago, Chile 3 Universidad Aut´ onoma de Chile, 7500138 Santiago, Chile 4 Universidad Esp´ıritu Santo, Guayaquil, Ecuador 5 Facultad de Ingenier´ıa y Tecnolog´ıa, Universidad San Sebasti´ an, Bellavista 7, 8420524 Santiago, Chile [email protected] 6 Covenant University, 110001 Ogun, Nigeria [email protected]
Abstract. There are multiple problems in several industries that can be solved with combinatorial optimization. In this sense, the Set Covering Problem is one of the most representative of them, being used in various branches of engineering and science, allowing find a set of solutions that meet the needs identified in the restrictions that have the lowest possible cost. This paper presents an algorithm inspired by binary black holes (BBH) to resolve known instances of SPC from the OR-Library. Also, it reproduces the behavior of black holes, using various operators to bring good solutions. Keywords: Set Covering Problem · Binary black hole heuristics · Combinatorial optimization problem
1
·
Meta
Introduction
The SCP is one of 21 NP-Hard problems, representing a variety of optimization strategies in various fields and realities. Since its formulation in the 1970 s has been used, for example, in minimization of loss of materials for metallurgical industry [1], preparing crews for urban transportation planning [2], safety and robustness of data networks [3], focus of public policies [4], construction structural calculations [5]. This problem was introduced in 1972 by Karp [6] and it is used to optimize problems of elements locations that provide spatial coverage, such as community services, telecommunications antennas and others. c Springer International Publishing Switzerland 2016 O. Gervasi et al. (Eds.): ICCSA 2016, Part I, LNCS 9786, pp. 207–219, 2016. DOI: 10.1007/978-3-319-42085-1 16
208
´ A.G. Rubio et al.
The present work applied a strategy based on a binary algorithm inspired by black holes to solve the SCP, developing some operators that allow to implement an analog version of some characteristics of these celestial bodies to support the behavior of the algorithm and improve the processes of searching for the optimum. This type of algorithm was presented for the first time by Abdolreza Hatamlou in September 2012 [7], registering some later publications dealing with some applications and improvements. In this paper it will be detailed methodology, developed operators, experimental results and execution parameters and handed out some brief conclusions about them, the original version for both the proposed improvements. The following section explains in detail the Set Covering Problem (SPC) and will be defined and briefly explain the black holes and their behavior. Then, in Sect. 3 the algorithm structure and behavior will be reviewed. Secti
Data Loading...
