Set covering problem resolution by Biogeography-Based Optimization Algorithm

Broderick Crawford, Ricardo Soto, Luis Riquelme, Eduardo Olguín, Sanjay Misra

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

Abstract

The research on Artificial Intelligence and Operational Research has provided models and techniques to solve many industrial problems. For instance, many real life problems can be formulated as a Set Covering Problem (SCP). The SCP is a classic NP-hard combinatorial problem consisting in find a set of solutions that cover a range of needs at the lowest possible cost following certain constraints. In this work, we use a recent metaheuristic called Biogeography-Based Optimization Algorithm (BBOA) inspired by biogeography, which mimics the migration behavior of animals in nature to solve optimization and engineering problems. In this paper, BBOA for the SCP is proposed. In addition, to improve performance we provide a new feature for the BBOA, which improve stagnation in local optimum. Finally, the experiment results show that BBOA is a excellent method for solving such problems.

Original languageEnglish
Title of host publicationComputational Science and Its Applications - 16th International Conference, ICCSA 2016, Proceedings
EditorsBernady O. Apduhan, Beniamino Murgante, Sanjay Misra, David Taniar, Carmelo M. Torre, Ana Maria A.C. Rocha, Shangguang Wang, Osvaldo Gervasi, Elena Stankova
PublisherSpringer Verlag
Pages153-165
Number of pages13
ISBN (Print)9783319420844
DOIs
StatePublished - 2016
Event16th International Conference on Computational Science and Its Applications, ICCSA 2016 - Beijing, China
Duration: 4 Jul 20167 Jul 2016

Publication series

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

Conference

Conference16th International Conference on Computational Science and Its Applications, ICCSA 2016
Country/TerritoryChina
CityBeijing
Period4/07/167/07/16

Keywords

  • Biogeography-Based Optimization Algorithm
  • Metaheuristics
  • Set Covering Problem

Fingerprint

Dive into the research topics of 'Set covering problem resolution by Biogeography-Based Optimization Algorithm'. Together they form a unique fingerprint.

Cite this