Skip to main content

Research Repository

Advanced Search

An indirect genetic algorithm for set covering problems

Aickelin, Uwe

An indirect genetic algorithm for set covering problems Thumbnail


Authors

Uwe Aickelin



Abstract

This paper presents a new type of genetic algorithm for the set covering problem. It differs from previous evolutionary approaches first because it is an indirect algorithm, i.e. the actual solutions are found by an external decoder function. The genetic algorithm itself provides this decoder with permutations of the solution variables and other parameters. Second, it will be shown that results can be further improved by adding another indirect optimisation layer. The decoder will not directly seek out low cost solutions but instead aims for good exploitable solutions. These are then post optimised by another hill-climbing algorithm. Although seemingly more complicated, we will show that this three-stage approach has advantages in terms of solution quality, speed and adaptability to new types of problems over more direct approaches. Extensive computational results are presented and compared to the latest evolutionary and other heuristic approaches to the same data instances.

Citation

Aickelin, U. (2002). An indirect genetic algorithm for set covering problems. Journal of the Operational Research Society, 53(10), 1118-1126. https://doi.org/10.1057/palgrave.jors.2601317

Journal Article Type Article
Acceptance Date Oct 1, 2001
Online Publication Date Dec 21, 2017
Publication Date Jan 1, 2002
Deposit Date Oct 30, 2007
Publicly Available Date Dec 4, 2007
Journal Journal of the Operational Research Society
Print ISSN 0160-5682
Electronic ISSN 1476-9360
Publisher Taylor and Francis
Peer Reviewed Peer Reviewed
Volume 53
Issue 10
Pages 1118-1126
DOI https://doi.org/10.1057/palgrave.jors.2601317
Keywords Heuristics, Optimisation, Scheduling
Public URL https://nottingham-repository.worktribe.com/output/1022624
Publisher URL https://www.tandfonline.com/doi/abs/10.1057/palgrave.jors.2601317
Additional Information This is a post-peer-review, pre-copyedit version of an article published in Journal of the Operational Research Society. The definitive publisher-authenticated version Aickelin, Uwe (2002) 'An Indirect Genetic Algorithm for Set Covering Problems'. Journal of the Operational Research Society, 53(10) . pp. 1118-1126. is available online via the offical url given here.
Contract Date Oct 30, 2007

Files





Downloadable Citations