An Indirect Genetic Algorithm for Set Covering Problems
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 p...
| Main Author: | |
|---|---|
| Format: | Article |
| Published: |
Palgrave Macmillan
2002
|
| Subjects: | |
| Online Access: | https://eprints.nottingham.ac.uk/550/ |
| _version_ | 1848790429780148224 |
|---|---|
| author | Aickelin, Uwe |
| author_facet | Aickelin, Uwe |
| author_sort | Aickelin, Uwe |
| building | Nottingham Research Data Repository |
| collection | Online Access |
| description | 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. |
| first_indexed | 2025-11-14T18:12:29Z |
| format | Article |
| id | nottingham-550 |
| institution | University of Nottingham Malaysia Campus |
| institution_category | Local University |
| last_indexed | 2025-11-14T18:12:29Z |
| publishDate | 2002 |
| publisher | Palgrave Macmillan |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | nottingham-5502020-05-04T20:32:14Z https://eprints.nottingham.ac.uk/550/ An Indirect Genetic Algorithm for Set Covering Problems Aickelin, Uwe 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. Palgrave Macmillan 2002 Article PeerReviewed Aickelin, Uwe (2002) An Indirect Genetic Algorithm for Set Covering Problems. Journal of the Operational Research Society, 53 (10). pp. 1118-1126. Heuristics Optimisation Scheduling |
| spellingShingle | Heuristics Optimisation Scheduling Aickelin, Uwe An Indirect Genetic Algorithm for Set Covering Problems |
| title | An Indirect Genetic Algorithm for Set Covering Problems |
| title_full | An Indirect Genetic Algorithm for Set Covering Problems |
| title_fullStr | An Indirect Genetic Algorithm for Set Covering Problems |
| title_full_unstemmed | An Indirect Genetic Algorithm for Set Covering Problems |
| title_short | An Indirect Genetic Algorithm for Set Covering Problems |
| title_sort | indirect genetic algorithm for set covering problems |
| topic | Heuristics Optimisation Scheduling |
| url | https://eprints.nottingham.ac.uk/550/ |