A cultural algorithm for solving the set covering problem

Broderick Crawford; Carolina Lagos; Carlos Castro; Fernando Paredes

doi:10.1007/978-3-540-72432-2_41

A cultural algorithm for solving the set covering problem

Broderick Crawford, Carolina Lagos, Carlos Castro, Fernando Paredes

SCHOOL OF COMPUTER ENGINEERING

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

4 Scopus citations

Abstract

In this paper we apply a new evolutive approach for solving the Set Covering Problem. This problem is a reasonably well known NP-complete optimization problem with many real world applications. We use a Cultural Evolutionary Architecture to maintain knowledge of Diversity and Fitness learned over each generation during the search process. Our results indicate that the approach is able to produce competitive results in compare with other approximation algorithms solving a portfolio of test problems taken from the ORLIB.

Original language	English
Title of host publication	Analysis and Design of Intelligent Systems using Soft Computing Techniques
Editors	Patricia Melin, Eduardo Gomez Ramirez, Janusz Kacprzyk, Witold Pedrycz
Pages	408-415
Number of pages	8
DOIs	https://doi.org/10.1007/978-3-540-72432-2_41
State	Published - 2007

Publication series

Name	Advances in Soft Computing
Volume	41
ISSN (Print)	1615-3871
ISSN (Electronic)	1860-0794

Keywords

Cultural algorithms
Genetic and evolutionary computation.
Set Covering Problem

Access to Document

10.1007/978-3-540-72432-2_41

Cite this

@inbook{a70f2764f55c46efa902e770b0f72662,

title = "A cultural algorithm for solving the set covering problem",

abstract = "In this paper we apply a new evolutive approach for solving the Set Covering Problem. This problem is a reasonably well known NP-complete optimization problem with many real world applications. We use a Cultural Evolutionary Architecture to maintain knowledge of Diversity and Fitness learned over each generation during the search process. Our results indicate that the approach is able to produce competitive results in compare with other approximation algorithms solving a portfolio of test problems taken from the ORLIB.",

keywords = "Cultural algorithms, Genetic and evolutionary computation., Set Covering Problem",

author = "Broderick Crawford and Carolina Lagos and Carlos Castro and Fernando Paredes",

year = "2007",

doi = "10.1007/978-3-540-72432-2_41",

language = "English",

isbn = "9783540724315",

series = "Advances in Soft Computing",

pages = "408--415",

editor = "Patricia Melin and {Gomez Ramirez}, Eduardo and Janusz Kacprzyk and Witold Pedrycz",

booktitle = "Analysis and Design of Intelligent Systems using Soft Computing Techniques",

}

A cultural algorithm for solving the set covering problem. / Crawford, Broderick; Lagos, Carolina; Castro, Carlos et al.
Analysis and Design of Intelligent Systems using Soft Computing Techniques. ed. / Patricia Melin; Eduardo Gomez Ramirez; Janusz Kacprzyk; Witold Pedrycz. 2007. p. 408-415 (Advances in Soft Computing; Vol. 41).

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

TY - CHAP

T1 - A cultural algorithm for solving the set covering problem

AU - Crawford, Broderick

AU - Lagos, Carolina

AU - Castro, Carlos

AU - Paredes, Fernando

PY - 2007

Y1 - 2007

N2 - In this paper we apply a new evolutive approach for solving the Set Covering Problem. This problem is a reasonably well known NP-complete optimization problem with many real world applications. We use a Cultural Evolutionary Architecture to maintain knowledge of Diversity and Fitness learned over each generation during the search process. Our results indicate that the approach is able to produce competitive results in compare with other approximation algorithms solving a portfolio of test problems taken from the ORLIB.

AB - In this paper we apply a new evolutive approach for solving the Set Covering Problem. This problem is a reasonably well known NP-complete optimization problem with many real world applications. We use a Cultural Evolutionary Architecture to maintain knowledge of Diversity and Fitness learned over each generation during the search process. Our results indicate that the approach is able to produce competitive results in compare with other approximation algorithms solving a portfolio of test problems taken from the ORLIB.

KW - Cultural algorithms

KW - Genetic and evolutionary computation.

KW - Set Covering Problem

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

U2 - 10.1007/978-3-540-72432-2_41

DO - 10.1007/978-3-540-72432-2_41

M3 - Chapter

AN - SCOPUS:59549087506

SN - 9783540724315

T3 - Advances in Soft Computing

SP - 408

EP - 415

BT - Analysis and Design of Intelligent Systems using Soft Computing Techniques

A2 - Melin, Patricia

A2 - Gomez Ramirez, Eduardo

A2 - Kacprzyk, Janusz

A2 - Pedrycz, Witold

ER -

A cultural algorithm for solving the set covering problem

Abstract

Publication series

Keywords

Access to Document

Other files and links

Fingerprint

Cite this