An binary black hole algorithm to solve set covering problem

Álvaro Gómez Rubio, BRODERICK CRAWFORD LABRIN, RICARDO JAVIER SOTO DE GIORGIS, Adrián Jaramillo, Sebastián Mansilla Villablanca, Juan Salas, Eduardo Olguín

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

1 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 languageEnglish
Title of host publicationTrends 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
EditorsMoonis Ali, Hamido Fujita, Jun Sasaki, Masaki Kurematsu, Ali Selamat
PublisherSpringer Verlag
Pages873-883
Number of pages11
ISBN (Print)9783319420066
DOIs
StatePublished - 1 Jan 2016
Event29th International Conference on Industrial Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2016 - Morioka, Japan
Duration: 2 Aug 20164 Aug 2016

Publication series

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

Conference

Conference29th International Conference on Industrial Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2016
CountryJapan
CityMorioka
Period2/08/164/08/16

Keywords

  • Binary black hole
  • Combinatorial optimization problem
  • Methaheuristics
  • Set covering problem

Fingerprint Dive into the research topics of 'An binary black hole algorithm to solve set covering problem'. Together they form a unique fingerprint.

Cite this