Abstract
A novel evolutionary approach for the bin packing problem (BPP) is presented. A simple steady-state genetic algorithm is developed that produces results comparable to other approaches in the literature, without the need for any additional heuristics. The algorithm's design makes maximum use of the principle of natural selection to evolve valid solutions without the explicit need to verify constraint violations. Our algorithm is based upon a biologically inspired group encoding which allows for a modularisation of the search space in which individual sub-solutions may be assigned independent cost values. These values are subsequently utilised in a crossover event modelled on the theory of exon shuffling to produce a single offspring that inherits the most promising segments from its parents. The algorithm is tested on a set of hard benchmark problems and the results indicate that the method has a very high degree of accuracy and reliability compared to other approaches in the literature.
Original language | English |
---|---|
Title of host publication | GECCO '07 Proceedings of the 9th annual conference on Genetic and evolutionary computation |
Publisher | Association for Computing Machinery (ACM) |
Pages | 1365-1371 |
Number of pages | 7 |
ISBN (Print) | 978-1-59593-697-4 |
DOIs | |
Publication status | Published - 7 Jul 2007 |
Event | 9th Genetic and Evolutionary Computation Conference (GECCO 2007) - London, United Kingdom Duration: 7 Jul 2007 → 11 Jul 2007 |
Conference
Conference | 9th Genetic and Evolutionary Computation Conference (GECCO 2007) |
---|---|
Country/Territory | United Kingdom |
City | London |
Period | 7/07/07 → 11/07/07 |
Keywords
- bin packing problem
- exon shuffling
- Genetic algorithms