TY - GEN
T1 - A comparison of three recent nature-inspired metaheuristics for the set covering problem
AU - Crawford, Broderick
AU - Soto, Ricardo
AU - Peña, Cristian
AU - Riquelme-Leiva, Marco
AU - Torres-Rojas, Claudio
AU - Misra, Sanjay
AU - Johnson, Franklin
AU - Paredes, Fernando
N1 - Publisher Copyright:
© Springer International Publishing Switzerland 2015.
PY - 2015
Y1 - 2015
N2 - 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.
AB - 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.
KW - Firefly algorithm
KW - Fruit fly algorithm
KW - Metaheuristics
KW - Set Covering Problem
KW - Shuffled Frog Leaping Algorithm
UR - http://www.scopus.com/inward/record.url?scp=84949035299&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-21410-834
DO - 10.1007/978-3-319-21410-834
M3 - Conference contribution
AN - SCOPUS:84949035299
SN - 9783319214092
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 431
EP - 443
BT - Computational Science and Its Applications - ICCSA 2015 - 15th International Conference, Proceedings
A2 - Gavrilova, Marina L.
A2 - Gervasi, Osvaldo
A2 - Murgante, Beniamino
A2 - Misra, Sanjay
A2 - Torre, Carmelo
A2 - Taniar, David
A2 - Apduhan, Bernady O.
A2 - Rocha, Ana Maria A.C.
A2 - Misra, Sanjay
PB - Springer Verlag
T2 - 15th International Conference on Computational Science and Its Applications, ICCSA 2015
Y2 - 22 June 2015 through 25 June 2015
ER -