A genetic algorithm with exon shuffling crossover for hard bin packing problems

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.

REFERENCES

• 1: Adriana C. F. Alvim , Celso C. Ribeiro , Fred Glover , Dario J. Aloise, A Hybrid Improvement Heuristic for the One-Dimensional Bin Packing Problem, Journal of Heuristics, v.10 n.2, p.205-229, March 2004 [doi>10.1023/B:HEUR.0000026267.44673.ed]
• 2: E. G. Co . man, M. R. Garey, and D. S. Johnson. An application of bin-packing to multimachine scheduling. Journal of Computing 7:1--17, 1978.
• 3: J. M. Daida, S. P. Yalcin, P. M. Litvak, G. A. Eickhoff, and J. A. Polit. Of metaphors and darwinism: Deconstructing genetic programming's chimera. In P. J. Angeline, Z. Michalewicz, M. Schoenauer, X. Yao, and A. Zalzala, editors, Proceedings of the Congress on Evolutionary Computation volume 1, pages 453--462, 1999.
• 4: E. Falkenauer. A hybrid grouping genetic algorithm for bin packing. Journal of Heuristics 2:5--30, 1996.
• 5: Krzysztof Fleszar , Khalil S. Hindi, New heuristics for one-dimensional bin-packing, Computers and Operations Research, v.29 n.7, p.821-839, June 2002 [doi>10.1016/S0305-0548(00)00082-4]
• 6: J. N. D. Gupta and J. C. Ho. A new heuristic algorithms of the one-dimensional bin-packing problem. Production planning & control 10(6):598--603, 1999.
• 7: John H. Holland, Adaptation in natural and artificial systems, MIT Press, Cambridge, MA, 1992
• 8: C. -Y. Kao and F. -T. Lin. A stochastic approach for the one-dimensional bin-packing problems. In Systems, Man and Cybernetics, 1992 volume 2, pages 1545--1551, 1992.
• 9: J. A. Kolkman and W. P. C. Stemmer. Directed evolution of proteins by exon shuffling. Nature Biotechnology 19:423--428, 2001.
• 10: H. Lima and T. Yakawa. A new design of genetic algorithm for bin packing. In Evolutionary Computation, 2003. CEC '03. The 2003 Congress on Evolutionary Computation volume 2, pages 1044--1049, 2003.
• 11: Melanie Mitchell, An introduction to genetic algorithms, MIT Press, Cambridge, MA, 1996
• 12: B. Modrek and C. J. Lee. Alternative splicing in the human, mouse and rat genomes is associated with an increased frequency of exon creation and/or loss. Nature Genetics 34(2):177--180, 2003.
• 13: Armin Scholl , Robert Klein , Christian Jürgens, BISON: a fast hybrid procedure for exactly solving the one-dimensional bin packing problem, Computers and Operations Research, v.24 n.7, p.627-645, July 1997 [doi>10.1016/S0305-0548(96)00082-2]
• 14: M. Silvano and T. Paolo. Knapsack Problems, Algorithms and Computer Implementations chapter Bin-packing problem, pages 221--245. John Wiley and Sons Ltd., England, 1990.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

General Terms:
Algorithms, Experimentation, Performance

Keywords:
bin packing problem, exon shuffling, genetic algorithms