Set covering problem resolution by Biogeography-Based Optimization Algorithm

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

doi:10.1007/978-3-319-42085-1_12

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 proceeding › Conference contribution › peer-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 language	English
Title of host publication	Computational Science and Its Applications - 16th International Conference, ICCSA 2016, Proceedings
Editors	Bernady O. Apduhan, Beniamino Murgante, Sanjay Misra, David Taniar, Carmelo M. Torre, Ana Maria A.C. Rocha, Shangguang Wang, Osvaldo Gervasi, Elena Stankova
Publisher	Springer Verlag
Pages	153-165
Number of pages	13
ISBN (Print)	9783319420844
DOIs	https://doi.org/10.1007/978-3-319-42085-1_12
State	Published - 2016
Externally published	Yes
Event	16th International Conference on Computational Science and Its Applications, ICCSA 2016 - Beijing, China Duration: 4 Jul 2016 → 7 Jul 2016

Publication series

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

Conference

Conference	16th International Conference on Computational Science and Its Applications, ICCSA 2016
Country/Territory	China
City	Beijing
Period	4/07/16 → 7/07/16

Keywords

Biogeography-Based Optimization Algorithm
Metaheuristics
Set Covering Problem

Access to Document

10.1007/978-3-319-42085-1_12

Cite this

Crawford, B., Soto, R., Riquelme, L., Olguín, E., & Misra, S. (2016). Set covering problem resolution by Biogeography-Based Optimization Algorithm. In B. O. Apduhan, B. Murgante, S. Misra, D. Taniar, C. M. Torre, A. M. A. C. Rocha, S. Wang, O. Gervasi, & E. Stankova (Eds.), Computational Science and Its Applications - 16th International Conference, ICCSA 2016, Proceedings (pp. 153-165). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9786). Springer Verlag. https://doi.org/10.1007/978-3-319-42085-1_12

Crawford, Broderick ; Soto, Ricardo ; Riquelme, Luis et al. / Set covering problem resolution by Biogeography-Based Optimization Algorithm. Computational Science and Its Applications - 16th International Conference, ICCSA 2016, Proceedings. editor / Bernady O. Apduhan ; Beniamino Murgante ; Sanjay Misra ; David Taniar ; Carmelo M. Torre ; Ana Maria A.C. Rocha ; Shangguang Wang ; Osvaldo Gervasi ; Elena Stankova. Springer Verlag, 2016. pp. 153-165 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{e2f466d6a9ee43baa269480444342a80,

title = "Set covering problem resolution by Biogeography-Based Optimization Algorithm",

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.",

keywords = "Biogeography-Based Optimization Algorithm, Metaheuristics, Set Covering Problem",

author = "Broderick Crawford and Ricardo Soto and Luis Riquelme and Eduardo Olgu{\'i}n and Sanjay Misra",

note = "Funding Information: The author Broderick Crawford is supported by grant CONICYT/FONDE-CYT/REGULAR/1140897 and Ricardo Soto is supported by grant CONICYT/FONDECYT/REGULAR/1160455. Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2016.; null ; Conference date: 04-07-2016 Through 07-07-2016",

year = "2016",

doi = "10.1007/978-3-319-42085-1_12",

language = "English",

isbn = "9783319420844",

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

publisher = "Springer Verlag",

pages = "153--165",

editor = "Apduhan, {Bernady O.} and Beniamino Murgante and Sanjay Misra and David Taniar and Torre, {Carmelo M.} and Rocha, {Ana Maria A.C.} and Shangguang Wang and Osvaldo Gervasi and Elena Stankova",

booktitle = "Computational Science and Its Applications - 16th International Conference, ICCSA 2016, Proceedings",

}

Crawford, B , Soto, R, Riquelme, L, Olguín, E & Misra, S 2016, Set covering problem resolution by Biogeography-Based Optimization Algorithm. in BO Apduhan, B Murgante, S Misra, D Taniar, CM Torre, AMAC Rocha, S Wang, O Gervasi & E Stankova (eds), Computational Science and Its Applications - 16th International Conference, ICCSA 2016, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9786, Springer Verlag, pp. 153-165, 16th International Conference on Computational Science and Its Applications, ICCSA 2016, Beijing, China, 4/07/16. https://doi.org/10.1007/978-3-319-42085-1_12

Set covering problem resolution by Biogeography-Based Optimization Algorithm. / Crawford, Broderick ; Soto, Ricardo; Riquelme, Luis et al.

Computational Science and Its Applications - 16th International Conference, ICCSA 2016, Proceedings. ed. / Bernady O. Apduhan; Beniamino Murgante; Sanjay Misra; David Taniar; Carmelo M. Torre; Ana Maria A.C. Rocha; Shangguang Wang; Osvaldo Gervasi; Elena Stankova. Springer Verlag, 2016. p. 153-165 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9786).

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

TY - GEN

T1 - Set covering problem resolution by Biogeography-Based Optimization Algorithm

AU - Crawford, Broderick

AU - Soto, Ricardo

AU - Riquelme, Luis

AU - Olguín, Eduardo

AU - Misra, Sanjay

N1 - Funding Information: The author Broderick Crawford is supported by grant CONICYT/FONDE-CYT/REGULAR/1140897 and Ricardo Soto is supported by grant CONICYT/FONDECYT/REGULAR/1160455. Publisher Copyright: © Springer International Publishing Switzerland 2016.

PY - 2016

Y1 - 2016

N2 - 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.

AB - 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.

KW - Biogeography-Based Optimization Algorithm

KW - Metaheuristics

KW - Set Covering Problem

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

U2 - 10.1007/978-3-319-42085-1_12

DO - 10.1007/978-3-319-42085-1_12

M3 - Conference contribution

AN - SCOPUS:84978790733

SN - 9783319420844

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

SP - 153

EP - 165

BT - Computational Science and Its Applications - 16th International Conference, ICCSA 2016, Proceedings

A2 - Apduhan, Bernady O.

A2 - Murgante, Beniamino

A2 - Misra, Sanjay

A2 - Taniar, David

A2 - Torre, Carmelo M.

A2 - Rocha, Ana Maria A.C.

A2 - Wang, Shangguang

A2 - Gervasi, Osvaldo

A2 - Stankova, Elena

PB - Springer Verlag

Y2 - 4 July 2016 through 7 July 2016

ER -

Crawford B , Soto R, Riquelme L, Olguín E, Misra S. Set covering problem resolution by Biogeography-Based Optimization Algorithm. In Apduhan BO, Murgante B, Misra S, Taniar D, Torre CM, Rocha AMAC, Wang S, Gervasi O, Stankova E, editors, Computational Science and Its Applications - 16th International Conference, ICCSA 2016, Proceedings. Springer Verlag. 2016. p. 153-165. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-319-42085-1_12

Set covering problem resolution by Biogeography-Based Optimization Algorithm

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this