Nature Inspired Genetic Algorithms for Hard Packing Problems

Research output: Contribution to journalArticle

Colleges, School and Institutes

Abstract

This paper presents two novel genetic algorithms (GAs) for hard industrially relevant packing problems. The design of both algorithms is inspired by aspects of molecular genetics, in particular, the modular exon-intron structure of eukaryotic genes. Two representative packing problems are used to test the utility of the proposed approach: the bin packing problem (BPP) and the multiple knapsack problem (MKP). The algorithm for the BPP, the exon shuffling GA (ESGA), is a steady-state GA with a sophisticated crossover operator that makes maximum use of the principle of natural selection to evolve feasible solutions with no explicit verification of constraint violations. The second algorithm, the Exonic GA (ExGA), implements an RNA inspired adaptive repair function necessary for the highly constrained MKP. Three different variants of this algorithm are presented and compared, which evolve a partial ordering of items using a segmented encoding that is utilised in the repair of infeasible solutions. All algorithms are tested on a range of benchmark problems, and the results indicate a very high degree of accuracy and reliability compared to other approaches in the literature.

Details

Original languageEnglish
Pages (from-to)393-419
Number of pages27
JournalAnnals of Operations Research
Volume179
Issue number1
Early online date15 Nov 2008
Publication statusPublished - 1 Sep 2010

Keywords

  • Multiple knapsack problem, Bin packing problem, Decoders, RNA editing, Repair algorithms, Genetic algorithms, Exon shuffling