A GENETIC ALGORITHM FOR THE SET COVERING PROBLEM

Authors
BEASLEY JE CHU PC
Citation
Je. Beasley et Pc. Chu, A GENETIC ALGORITHM FOR THE SET COVERING PROBLEM, European journal of operational research, 94(2), 1996, pp. 392-404
Citations number
19
Categorie Soggetti
Management,"Operatione Research & Management Science","Operatione Research & Management Science
Journal title
European journal of operational research → ACNP
ISSN journal
03772217
Volume
94
Issue
2
Year of publication
1996
Pages
392 - 404
Database
ISI
SICI code
0377-2217(1996)94:2<392:AGAFTS>2.0.ZU;2-Y
Abstract
In this paper we present a genetic algorithm-based heuristic for non-u nicost set covering problems. We propose several modifications to the basic genetic procedures including a new fitness-based crossover opera tor (fusion), a variable mutation rate and a heuristic feasibility ope rator tailored specifically for the set covering problem. The performa nce of our algorithm was evaluated on a large set of randomly generate d problems. Computational results showed that the genetic algorithm-ba sed heuristic is capable of producing high-quality solutions.