Philipp Rohlfshagen
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.
- A. C. F. Alvim, C. C. Ribeiro, F. Glover, and D. J. Aloise. A hybrid improvment heuristic for the one-dimensional bin packing problem. Journal of Heuristics 10:205--229, 2004. Google Scholar
Digital Library
- 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.Google Scholar
- 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.Google Scholar
- E. Falkenauer. A hybrid grouping genetic algorithm for bin packing. Journal of Heuristics 2:5--30, 1996.Google ScholarCross Ref
- K. Fleszar and K. S. Hindi. New heuristics for one-dimensional bin-packing. Computers & operations research 29:821--839, 2002. Google ScholarDigital Library
- 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.Google Scholar
- J. H. Holland. Adaptation in Natural and Artifical Systems University of Michigan Press, Ann Arbor, MI, 1975. Google ScholarDigital Library
- 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.Google Scholar
- J. A. Kolkman and W. P. C. Stemmer. Directed evolution of proteins by exon shuffling. Nature Biotechnology 19:423--428, 2001.Google ScholarCross Ref
- 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.Google Scholar
- M. Mitchell. An Introduction to Genetic Algorithms MIT Press, 1996. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- A. Scholl, R. Klein, and C. Juergens. Bison: A fast hybrid procedure for exactly solving the one-dimensional bin packing problem. Computers & Operations Research 24(7):627--645, 1997. Google ScholarDigital Library
- 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.Google Scholar
Index Terms
- A genetic algorithm with exon shuffling crossover for hard bin packing problems
Recommendations
A parameter-less genetic algorithm with customized crossover and mutation operators
GECCO '11: Proceedings of the 13th annual conference on Genetic and evolutionary computationGenetic algorithm is one of the well-known population based meta-heuristics. The reasonable performance of the algorithm on a wide variety of problems as well as its simplicity made this algorithm a first choice in lots of cases. However, the algorithm ...
Real-polarized genetic algorithm for the three-dimensional bin packing problem
GECCO '17: Proceedings of the Genetic and Evolutionary Computation ConferenceThis article presents a non-deterministic approach to the Three-Dimensional Bin Packing Problem, using a genetic algorithm. To perform the packing, an algorithm was developed considering rotations, size constraints of objects and better utilization of ...
Genetic algorithm with adaptive elitism-based immigrants for dynamic optimization problems
GECCO '09: Proceedings of the 11th Annual conference on Genetic and evolutionary computationWe propose a genetic algorithm with adaptive elitism-based immigrants which tunes the balance between elitism-based immigrants and random immigrants by itself. Experimental results show that our genetic algorithm with adaptive elitism-based immigrants ...
Comments