A comparison of three recent nature-inspired metaheuristics for the set covering problem

BRODERICK CRAWFORD LABRIN, RICARDO JAVIER SOTO DE GIORGIS, Cristian Peña, Marco Riquelme-Leiva, Claudio Torres-Rojas, Sanjay Misra, Franklin Johnson, Fernando Paredes

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

6 Scopus citations

Abstract

The Set Covering Problem (SCP) is a classic problem in combinatorial optimization. SCP has many applications in engineering, including problems involving routing, scheduling, stock cutting, electoral redistricting and others important real life situations. Because of its importance, SCP has attracted attention of many researchers. However, SCP instances are known as complex and generally NP-hard problems. Due to the combinatorial nature of this problem, during the last decades, several metaheuristics have been applied to obtain efficient solutions. This paper presents a metaheuristics comparison for the SCP. Three recent nature-inspired metaheuristics are considered: Shuffled Frog Leaping, Firefly and Fruit Fly algorithms. The results show that they can obtainn optimal or close to optimal solutions at low computational cost.

Original languageEnglish
Title of host publicationComputational Science and Its Applications - ICCSA 2015 - 15th International Conference, Proceedings
EditorsMarina L. Gavrilova, Osvaldo Gervasi, Beniamino Murgante, Sanjay Misra, Carmelo Torre, David Taniar, Bernady O. Apduhan, Ana Maria A.C. Rocha, Sanjay Misra
PublisherSpringer Verlag
Pages431-443
Number of pages13
ISBN (Print)9783319214092
DOIs
StatePublished - 1 Jan 2015
Event15th International Conference on Computational Science and Its Applications, ICCSA 2015 - Banff, Canada
Duration: 22 Jun 201525 Jun 2015

Publication series

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

Conference

Conference15th International Conference on Computational Science and Its Applications, ICCSA 2015
CountryCanada
CityBanff
Period22/06/1525/06/15

Keywords

  • Firefly algorithm
  • Fruit fly algorithm
  • Metaheuristics
  • Set Covering Problem
  • Shuffled Frog Leaping Algorithm

Fingerprint Dive into the research topics of 'A comparison of three recent nature-inspired metaheuristics for the set covering problem'. Together they form a unique fingerprint.

Cite this