A bi-objetive Cat Swarm Optimization algorithm for set covering problem

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

doi:10.1007/978-3-319-33625-1_44

A bi-objetive Cat Swarm Optimization algorithm for set covering problem

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

SCHOOL OF COMPUTER ENGINEERING

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

Abstract

In this paper, we study a classical problem in combinatorics and computer science, Set Covering Problem. It is one of Karp’s 21 NP-complete problems, using a new and original metaheuristic, Cat Swarm Optimization. This algorithm imitates the domestic cat through two states: seeking and tracing mode. The OR-Library of Beasley instances were used for the benchmark with additional fitness function, thus the problem was transformed from Mono-objective to Bi-objective. The Cat Swarm Optimization finds a set solution non-dominated based on Pareto concepts, and an external file for storing them. The results are promising for further continue in future work optimizing this problem.

Original language	English
Title of host publication	Artificial Intelligence Perspectives in Intelligent Systems - Proceedings of 5th Computer Science On-line Conference, CSOC 2016
Editors	Radek Silhavy, Roman Senkerik, Zuzana Kominkova Oplatkova, Petr Silhavy, Zdenka Prokopova
Publisher	Springer Verlag
Pages	491-500
Number of pages	10
ISBN (Print)	9783319336237
DOIs	https://doi.org/10.1007/978-3-319-33625-1_44
State	Published - 2016
Event	5th Computer Science On-line Conference, CSOC 2016 - Prague, Czech Republic Duration: 27 Apr 2016 → 30 Apr 2016

Publication series

Name	Advances in Intelligent Systems and Computing
Volume	464
ISSN (Print)	2194-5357

Conference

Conference	5th Computer Science On-line Conference, CSOC 2016
Country/Territory	Czech Republic
City	Prague
Period	27/04/16 → 30/04/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-33625-1_44

Cite this

Crawford, B., Soto, R., Caballero, H., & Olguín, E. (2016). A bi-objetive Cat Swarm Optimization algorithm for set covering problem. In R. Silhavy, R. Senkerik, Z. K. Oplatkova, P. Silhavy, & Z. Prokopova (Eds.), Artificial Intelligence Perspectives in Intelligent Systems - Proceedings of 5th Computer Science On-line Conference, CSOC 2016 (pp. 491-500). (Advances in Intelligent Systems and Computing; Vol. 464). Springer Verlag. https://doi.org/10.1007/978-3-319-33625-1_44

Crawford, Broderick ; Soto, Ricardo ; Caballero, Hugo et al. / A bi-objetive Cat Swarm Optimization algorithm for set covering problem. Artificial Intelligence Perspectives in Intelligent Systems - Proceedings of 5th Computer Science On-line Conference, CSOC 2016. editor / Radek Silhavy ; Roman Senkerik ; Zuzana Kominkova Oplatkova ; Petr Silhavy ; Zdenka Prokopova. Springer Verlag, 2016. pp. 491-500 (Advances in Intelligent Systems and Computing).

@inproceedings{8d5cce47963b4d3eb6030f24bfca3245,

title = "A bi-objetive Cat Swarm Optimization algorithm for set covering problem",

abstract = "In this paper, we study a classical problem in combinatorics and computer science, Set Covering Problem. It is one of Karp{\textquoteright}s 21 NP-complete problems, using a new and original metaheuristic, Cat Swarm Optimization. This algorithm imitates the domestic cat through two states: seeking and tracing mode. The OR-Library of Beasley instances were used for the benchmark with additional fitness function, thus the problem was transformed from Mono-objective to Bi-objective. The Cat Swarm Optimization finds a set solution non-dominated based on Pareto concepts, and an external file for storing them. The results are promising for further continue in future work optimizing this 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",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2016.; 5th Computer Science On-line Conference, CSOC 2016 ; Conference date: 27-04-2016 Through 30-04-2016",

year = "2016",

doi = "10.1007/978-3-319-33625-1_44",

language = "English",

isbn = "9783319336237",

series = "Advances in Intelligent Systems and Computing",

publisher = "Springer Verlag",

pages = "491--500",

editor = "Radek Silhavy and Roman Senkerik and Oplatkova, {Zuzana Kominkova} and Petr Silhavy and Zdenka Prokopova",

booktitle = "Artificial Intelligence Perspectives in Intelligent Systems - Proceedings of 5th Computer Science On-line Conference, CSOC 2016",

}

Crawford, B , Soto, R, Caballero, H & Olguín, E 2016, A bi-objetive Cat Swarm Optimization algorithm for set covering problem. in R Silhavy, R Senkerik, ZK Oplatkova, P Silhavy & Z Prokopova (eds), Artificial Intelligence Perspectives in Intelligent Systems - Proceedings of 5th Computer Science On-line Conference, CSOC 2016. Advances in Intelligent Systems and Computing, vol. 464, Springer Verlag, pp. 491-500, 5th Computer Science On-line Conference, CSOC 2016, Prague, Czech Republic, 27/04/16. https://doi.org/10.1007/978-3-319-33625-1_44

A bi-objetive Cat Swarm Optimization algorithm for set covering problem. / Crawford, Broderick ; Soto, Ricardo; Caballero, Hugo et al.
Artificial Intelligence Perspectives in Intelligent Systems - Proceedings of 5th Computer Science On-line Conference, CSOC 2016. ed. / Radek Silhavy; Roman Senkerik; Zuzana Kominkova Oplatkova; Petr Silhavy; Zdenka Prokopova. Springer Verlag, 2016. p. 491-500 (Advances in Intelligent Systems and Computing; Vol. 464).

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

TY - GEN

T1 - A bi-objetive Cat Swarm Optimization algorithm for set covering problem

AU - Crawford, Broderick

AU - Soto, Ricardo

AU - Caballero, Hugo

AU - Olguín, Eduardo

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

PY - 2016

Y1 - 2016

N2 - In this paper, we study a classical problem in combinatorics and computer science, Set Covering Problem. It is one of Karp’s 21 NP-complete problems, using a new and original metaheuristic, Cat Swarm Optimization. This algorithm imitates the domestic cat through two states: seeking and tracing mode. The OR-Library of Beasley instances were used for the benchmark with additional fitness function, thus the problem was transformed from Mono-objective to Bi-objective. The Cat Swarm Optimization finds a set solution non-dominated based on Pareto concepts, and an external file for storing them. The results are promising for further continue in future work optimizing this problem.

AB - In this paper, we study a classical problem in combinatorics and computer science, Set Covering Problem. It is one of Karp’s 21 NP-complete problems, using a new and original metaheuristic, Cat Swarm Optimization. This algorithm imitates the domestic cat through two states: seeking and tracing mode. The OR-Library of Beasley instances were used for the benchmark with additional fitness function, thus the problem was transformed from Mono-objective to Bi-objective. The Cat Swarm Optimization finds a set solution non-dominated based on Pareto concepts, and an external file for storing them. The results are promising for further continue in future work optimizing this 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=84964701642&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-33625-1_44

DO - 10.1007/978-3-319-33625-1_44

M3 - Conference contribution

AN - SCOPUS:84964701642

SN - 9783319336237

T3 - Advances in Intelligent Systems and Computing

SP - 491

EP - 500

BT - Artificial Intelligence Perspectives in Intelligent Systems - Proceedings of 5th Computer Science On-line Conference, CSOC 2016

A2 - Silhavy, Radek

A2 - Senkerik, Roman

A2 - Oplatkova, Zuzana Kominkova

A2 - Silhavy, Petr

A2 - Prokopova, Zdenka

PB - Springer Verlag

T2 - 5th Computer Science On-line Conference, CSOC 2016

Y2 - 27 April 2016 through 30 April 2016

ER -

Crawford B , Soto R, Caballero H, Olguín E. A bi-objetive Cat Swarm Optimization algorithm for set covering problem. In Silhavy R, Senkerik R, Oplatkova ZK, Silhavy P, Prokopova Z, editors, Artificial Intelligence Perspectives in Intelligent Systems - Proceedings of 5th Computer Science On-line Conference, CSOC 2016. Springer Verlag. 2016. p. 491-500. (Advances in Intelligent Systems and Computing). doi: 10.1007/978-3-319-33625-1_44

A bi-objetive Cat Swarm Optimization algorithm for set covering problem

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this