Solving the Set Covering Problem with a Shuffled Frog Leaping Algorithm

被引：0

作者：

Crawford, Broderick ^{[1
,2
,3
]}

Soto, Ricardo ^{[1
,4
,5
]}

Pena, Cristian ^{[1
]}

Palma, Wenceslao ^{[1
]}

Johnson, Franklin ^{[1
,6
]}

Paredes, Fernando ^{[7
]}

机构：

[1] Pontificia Univ Catolica Valparaiso, Valparaiso, Chile

[2] Univ Finis Terrae, Providencia, Chile

[3] Univ San Sebastian, Santiago, Chile

[4] Univ Autonoma Chile, Santiago, Chile

[5] Univ Cent Chile, Santiago, Chile

[6] Univ Playa Ancha, Valparaiso, Chile

[7] Univ Diego Portales, Escuela Ingn Ind, Santiago, Chile

来源：

INTELLIGENT INFORMATION AND DATABASE SYSTEMS, PT II | 2015年 / 9012卷

关键词：

Shuffled frog leaping algorithm; Set covering problem; Metaheuristics; Artificial and computational intelligence; GENETIC ALGORITHM; OPTIMIZATION;

D O I：

10.1007/978-3-319-15705-4_5

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

In this paper we design and evaluate a shuffled frog leaping algorithm that solves the set covering problem. The shuffled frog leaping algorithm is a novel metaheuristic inspired by natural memetics. It consists of an individual memetic evolution and a global memetic information exchange between a population of virtual frogs representing possible solutions of a problem at hand. The experimental results show the effectiveness of our approach which produces competitive results solving a portfolio of set covering problems from the OR-Library.

引用

页码：41 / 50

页数：10

共 29 条

[1] [Anonymous], 2003, INT SERIES OPERATION
[2] [Anonymous], 1990, COMPUT INTRACTABILIT
[3] [Anonymous], METAHEURISTIC ALGORI
[4] [Anonymous], 1995, 1995 IEEE INT C
[5] A dynamic subgradient-based branch-and-bound procedure for set covering
Balas, E
Carrera, MC
[J]. OPERATIONS RESEARCH, 1996, 44 (06) : 875 - 890
[6] BEASLEY JE, 1990, NAV RES LOG, V37, P151, DOI 10.1002/1520-6750(199002)37:1<151::AID-NAV3220370110>3.0.CO
[7] 2-2
[8] A genetic algorithm for the set covering problem
Beasley, JE
Chu, PC
[J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1996, 94 (02) : 392 - 404
[9] Shuffled frog leaping algorithm and its application to 0/1 knapsack problem Kaushik Kumar
Bhattacharjee, Kaushik Kumar
Sarmah, S. P.
[J]. APPLIED SOFT COMPUTING, 2014, 19 : 252 - 263
[10] A morphing procedure to supplement a simulated annealing heuristic for cost- and coverage-correlated set-covering problems
Brusco, MJ
Jacobs, LW
Thompson, GM
[J]. ANNALS OF OPERATIONS RESEARCH, 1999, 86 (0) : 611 - 627

← 1 2 3 →