An binary black hole algorithm to solve set covering problem

Álvaro Gómez Rubio; Broderick Crawford; Ricardo Soto; Adrián Jaramillo; Sebastián Mansilla Villablanca; Juan Salas; Eduardo Olguín

doi:10.1007/978-3-319-42007-3_74

An binary black hole algorithm to solve set covering problem

Álvaro Gómez Rubio, Broderick Crawford, Ricardo Soto, Adrián Jaramillo, Sebastián Mansilla Villablanca, Juan Salas, Eduardo Olguín

SCHOOL OF COMPUTER ENGINEERING

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

2 Scopus citations

Abstract

The set covering problem (SCP) is one of the most representative combinatorial optimization problems and it has multiple applications in different situations of engineering, sciences and some other disciplines. It aims to find a set of solutions that meet the needs defined in the constraints having lowest possible cost. In this paper we used an existing binary algorithm inspired by Binary Black Holes (BBH), to solve multiple instances of the problem with known benchmarks obtained from the OR-library. The presented method emulates the behavior of these celestial bodies using a rotation operator to bring good solutions. After tray this algorithm, we implemented some improvements in certain operators, as well as added others also inspired by black holes physical behavior, to optimize the search and exploration to improving the results.

Original language	English
Title of host publication	Trends in Applied Knowledge-Based Systems and Data Science - 29th International Conference on Industrial Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2016, Proceedings
Editors	Moonis Ali, Hamido Fujita, Jun Sasaki, Masaki Kurematsu, Ali Selamat
Publisher	Springer Verlag
Pages	873-883
Number of pages	11
ISBN (Print)	9783319420066
DOIs	https://doi.org/10.1007/978-3-319-42007-3_74
State	Published - 2016
Event	29th International Conference on Industrial Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2016 - Morioka, Japan Duration: 2 Aug 2016 → 4 Aug 2016

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	9799
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	29th International Conference on Industrial Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2016
Country/Territory	Japan
City	Morioka
Period	2/08/16 → 4/08/16

Keywords

Binary black hole
Combinatorial optimization problem
Methaheuristics
Set covering problem

Access to Document

10.1007/978-3-319-42007-3_74

Cite this

Rubio, Á. G., Crawford, B., Soto, R., Jaramillo, A., Villablanca, S. M., Salas, J., & Olguín, E. (2016). An binary black hole algorithm to solve set covering problem. In M. Ali, H. Fujita, J. Sasaki, M. Kurematsu, & A. Selamat (Eds.), Trends in Applied Knowledge-Based Systems and Data Science - 29th International Conference on Industrial Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2016, Proceedings (pp. 873-883). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9799). Springer Verlag. https://doi.org/10.1007/978-3-319-42007-3_74

Rubio, Álvaro Gómez ; Crawford, Broderick ; Soto, Ricardo et al. / An binary black hole algorithm to solve set covering problem. Trends in Applied Knowledge-Based Systems and Data Science - 29th International Conference on Industrial Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2016, Proceedings. editor / Moonis Ali ; Hamido Fujita ; Jun Sasaki ; Masaki Kurematsu ; Ali Selamat. Springer Verlag, 2016. pp. 873-883 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{412d69eeab9240b586f6bfb5869fc18b,

title = "An binary black hole algorithm to solve set covering problem",

abstract = "The set covering problem (SCP) is one of the most representative combinatorial optimization problems and it has multiple applications in different situations of engineering, sciences and some other disciplines. It aims to find a set of solutions that meet the needs defined in the constraints having lowest possible cost. In this paper we used an existing binary algorithm inspired by Binary Black Holes (BBH), to solve multiple instances of the problem with known benchmarks obtained from the OR-library. The presented method emulates the behavior of these celestial bodies using a rotation operator to bring good solutions. After tray this algorithm, we implemented some improvements in certain operators, as well as added others also inspired by black holes physical behavior, to optimize the search and exploration to improving the results.",

keywords = "Binary black hole, Combinatorial optimization problem, Methaheuristics, Set covering problem",

author = "Rubio, {{\'A}lvaro G{\'o}mez} and Broderick Crawford and Ricardo Soto and Adri{\'a}n Jaramillo and Villablanca, {Sebasti{\'a}n Mansilla} and Juan Salas and Eduardo Olgu{\'i}n",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2016.; 29th International Conference on Industrial Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2016 ; Conference date: 02-08-2016 Through 04-08-2016",

year = "2016",

doi = "10.1007/978-3-319-42007-3_74",

language = "English",

isbn = "9783319420066",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "873--883",

editor = "Moonis Ali and Hamido Fujita and Jun Sasaki and Masaki Kurematsu and Ali Selamat",

booktitle = "Trends in Applied Knowledge-Based Systems and Data Science - 29th International Conference on Industrial Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2016, Proceedings",

}

Rubio, ÁG, Crawford, B , Soto, R, Jaramillo, A, Villablanca, SM, Salas, J & Olguín, E 2016, An binary black hole algorithm to solve set covering problem. in M Ali, H Fujita, J Sasaki, M Kurematsu & A Selamat (eds), Trends in Applied Knowledge-Based Systems and Data Science - 29th International Conference on Industrial Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2016, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9799, Springer Verlag, pp. 873-883, 29th International Conference on Industrial Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2016, Morioka, Japan, 2/08/16. https://doi.org/10.1007/978-3-319-42007-3_74

An binary black hole algorithm to solve set covering problem. / Rubio, Álvaro Gómez; Crawford, Broderick ; Soto, Ricardo et al.
Trends in Applied Knowledge-Based Systems and Data Science - 29th International Conference on Industrial Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2016, Proceedings. ed. / Moonis Ali; Hamido Fujita; Jun Sasaki; Masaki Kurematsu; Ali Selamat. Springer Verlag, 2016. p. 873-883 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9799).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - An binary black hole algorithm to solve set covering problem

AU - Rubio, Álvaro Gómez

AU - Crawford, Broderick

AU - Soto, Ricardo

AU - Jaramillo, Adrián

AU - Villablanca, Sebastián Mansilla

AU - Salas, Juan

AU - Olguín, Eduardo

N1 - Publisher Copyright: © Springer International Publishing Switzerland 2016.

PY - 2016

Y1 - 2016

N2 - The set covering problem (SCP) is one of the most representative combinatorial optimization problems and it has multiple applications in different situations of engineering, sciences and some other disciplines. It aims to find a set of solutions that meet the needs defined in the constraints having lowest possible cost. In this paper we used an existing binary algorithm inspired by Binary Black Holes (BBH), to solve multiple instances of the problem with known benchmarks obtained from the OR-library. The presented method emulates the behavior of these celestial bodies using a rotation operator to bring good solutions. After tray this algorithm, we implemented some improvements in certain operators, as well as added others also inspired by black holes physical behavior, to optimize the search and exploration to improving the results.

AB - The set covering problem (SCP) is one of the most representative combinatorial optimization problems and it has multiple applications in different situations of engineering, sciences and some other disciplines. It aims to find a set of solutions that meet the needs defined in the constraints having lowest possible cost. In this paper we used an existing binary algorithm inspired by Binary Black Holes (BBH), to solve multiple instances of the problem with known benchmarks obtained from the OR-library. The presented method emulates the behavior of these celestial bodies using a rotation operator to bring good solutions. After tray this algorithm, we implemented some improvements in certain operators, as well as added others also inspired by black holes physical behavior, to optimize the search and exploration to improving the results.

KW - Binary black hole

KW - Combinatorial optimization problem

KW - Methaheuristics

KW - Set covering problem

UR - http://www.scopus.com/inward/record.url?scp=84978829330&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-42007-3_74

DO - 10.1007/978-3-319-42007-3_74

M3 - Conference contribution

AN - SCOPUS:84978829330

SN - 9783319420066

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 873

EP - 883

BT - Trends in Applied Knowledge-Based Systems and Data Science - 29th International Conference on Industrial Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2016, Proceedings

A2 - Ali, Moonis

A2 - Fujita, Hamido

A2 - Sasaki, Jun

A2 - Kurematsu, Masaki

A2 - Selamat, Ali

PB - Springer Verlag

T2 - 29th International Conference on Industrial Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2016

Y2 - 2 August 2016 through 4 August 2016

ER -

Rubio ÁG, Crawford B , Soto R, Jaramillo A, Villablanca SM, Salas J et al. An binary black hole algorithm to solve set covering problem. In Ali M, Fujita H, Sasaki J, Kurematsu M, Selamat A, editors, Trends in Applied Knowledge-Based Systems and Data Science - 29th International Conference on Industrial Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2016, Proceedings. Springer Verlag. 2016. p. 873-883. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-42007-3_74

An binary black hole algorithm to solve set covering problem

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this