A Genetic Algorithm with Exon Shuffling Crossover for Hard Bin Packing Problems

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Colleges, School and Institutes

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.

Details

Original languageEnglish
Title of host publicationGECCO '07 Proceedings of the 9th annual conference on Genetic and evolutionary computation
Publication statusPublished - 7 Jul 2007
Event9th Genetic and Evolutionary Computation Conference (GECCO 2007) - London, United Kingdom
Duration: 7 Jul 200711 Jul 2007

Conference

Conference9th Genetic and Evolutionary Computation Conference (GECCO 2007)
Country/TerritoryUnited Kingdom
CityLondon
Period7/07/0711/07/07

Keywords

  • bin packing problem, exon shuffling, Genetic algorithms