Solving biobjective set covering problem using binary cat swarm optimization algorithm

Broderick Crawford; Ricardo Soto; Hugo Caballero; Eduardo Olguín; Sanjay Misra

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

Solving biobjective set covering problem using binary cat swarm optimization algorithm

Broderick Crawford, Ricardo Soto, Hugo Caballero, Eduardo Olguín, Sanjay Misra

SCHOOL OF COMPUTER ENGINEERING

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

2 Scopus citations

Abstract

The set cover problem is a classical question in combinatorics, computer science and complexity theory. It is one of Karp’s 21 NP-complete problems shown to be NP-complete in 1972. Several algorithms have been proposed to solve this problem, based on genetic algorithms (GA), Particle Swarm Optimizer (PSO) and in recent years algorithms based in behavior algorithms based groups or herds of animals, such as frogs, bats, bees and domestic cats. This work presents the basic features of the algorithm based on the behavior of domestic cats and results to solve the SCP bi-objective, experimental results and opportunities to improve results using adaptive techniques applied to Cat Swarm Optimization. For this purpose we will use instances of SCP OR-Library of Beasley by adding an extra function fitness to transform the Beasly instance to Bi-Objective problem.

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	220-231
Number of pages	12
ISBN (Print)	9783319420844
DOIs	https://doi.org/10.1007/978-3-319-42085-1_17
State	Published - 2016
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

Cat swarm optimization
Evolutionary algorithm
Multiobjective cat swarm optimization
Multiobjective problems
Pareto dominance
Swarm optimization

Access to Document

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

Cite this

Crawford, B., Soto, R., Caballero, H., Olguín, E., & Misra, S. (2016). Solving biobjective set covering problem using binary cat swarm 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. 220-231). (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_17

Crawford, Broderick ; Soto, Ricardo ; Caballero, Hugo et al. / Solving biobjective set covering problem using binary cat swarm 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. 220-231 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{6f00fa2c31f442cd9aa3d6f7fbe12235,

title = "Solving biobjective set covering problem using binary cat swarm optimization algorithm",

abstract = "The set cover problem is a classical question in combinatorics, computer science and complexity theory. It is one of Karp{\textquoteright}s 21 NP-complete problems shown to be NP-complete in 1972. Several algorithms have been proposed to solve this problem, based on genetic algorithms (GA), Particle Swarm Optimizer (PSO) and in recent years algorithms based in behavior algorithms based groups or herds of animals, such as frogs, bats, bees and domestic cats. This work presents the basic features of the algorithm based on the behavior of domestic cats and results to solve the SCP bi-objective, experimental results and opportunities to improve results using adaptive techniques applied to Cat Swarm Optimization. For this purpose we will use instances of SCP OR-Library of Beasley by adding an extra function fitness to transform the Beasly instance to Bi-Objective problem.",

keywords = "Cat swarm optimization, Evolutionary algorithm, Multiobjective cat swarm optimization, Multiobjective problems, Pareto dominance, Swarm optimization",

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

note = "Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2016.; 16th International Conference on Computational Science and Its Applications, ICCSA 2016 ; Conference date: 04-07-2016 Through 07-07-2016",

year = "2016",

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

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 = "220--231",

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, Caballero, H, Olguín, E & Misra, S 2016, Solving biobjective set covering problem using binary cat swarm 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. 220-231, 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_17

Solving biobjective set covering problem using binary cat swarm optimization algorithm. / Crawford, Broderick ; Soto, Ricardo; Caballero, Hugo 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. 220-231 (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 - Solving biobjective set covering problem using binary cat swarm optimization algorithm

AU - Crawford, Broderick

AU - Soto, Ricardo

AU - Caballero, Hugo

AU - Olguín, Eduardo

AU - Misra, Sanjay

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

PY - 2016

Y1 - 2016

N2 - The set cover problem is a classical question in combinatorics, computer science and complexity theory. It is one of Karp’s 21 NP-complete problems shown to be NP-complete in 1972. Several algorithms have been proposed to solve this problem, based on genetic algorithms (GA), Particle Swarm Optimizer (PSO) and in recent years algorithms based in behavior algorithms based groups or herds of animals, such as frogs, bats, bees and domestic cats. This work presents the basic features of the algorithm based on the behavior of domestic cats and results to solve the SCP bi-objective, experimental results and opportunities to improve results using adaptive techniques applied to Cat Swarm Optimization. For this purpose we will use instances of SCP OR-Library of Beasley by adding an extra function fitness to transform the Beasly instance to Bi-Objective problem.

AB - The set cover problem is a classical question in combinatorics, computer science and complexity theory. It is one of Karp’s 21 NP-complete problems shown to be NP-complete in 1972. Several algorithms have been proposed to solve this problem, based on genetic algorithms (GA), Particle Swarm Optimizer (PSO) and in recent years algorithms based in behavior algorithms based groups or herds of animals, such as frogs, bats, bees and domestic cats. This work presents the basic features of the algorithm based on the behavior of domestic cats and results to solve the SCP bi-objective, experimental results and opportunities to improve results using adaptive techniques applied to Cat Swarm Optimization. For this purpose we will use instances of SCP OR-Library of Beasley by adding an extra function fitness to transform the Beasly instance to Bi-Objective problem.

KW - Cat swarm optimization

KW - Evolutionary algorithm

KW - Multiobjective cat swarm optimization

KW - Multiobjective problems

KW - Pareto dominance

KW - Swarm optimization

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

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

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

M3 - Conference contribution

AN - SCOPUS:84978795422

SN - 9783319420844

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

SP - 220

EP - 231

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

T2 - 16th International Conference on Computational Science and Its Applications, ICCSA 2016

Y2 - 4 July 2016 through 7 July 2016

ER -

Crawford B , Soto R, Caballero H, Olguín E, Misra S. Solving biobjective set covering problem using binary cat swarm 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. 220-231. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-42085-1_17

Solving biobjective set covering problem using binary cat swarm optimization algorithm

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this