Skip to main content
SpringerLink
Log in

A hybrid grouping genetic algorithm for bin packing

  • Published:
Journal of Heuristics Aims and scope Submit manuscript

Abstract

The grouping genetic algorithm (GGA) is a genetic algorithm heavily modified to suit the structure of grouping problems. Those are the problems where the aim is to find a good partition of a set or to group together the members of the set. The bin packing problem (BPP) is a well known NP-hard grouping problem: items of various sizes have to be grouped inside bins of fixed capacity. On the other hand, the reduction method of Martello and Toth, based on their dominance criterion, constitutes one of the best OR techniques for optimization of the BPP to date.

In this article, we first describe the GGA paradigm as compared to the classic Holland-style GA and the ordering GA. We then show how the bin packing GGA can be enhanced with a local optimization inspired by the dominance criterion. An extensive experimental comparison shows that the combination yields an algorithm superior to either of its components.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • BelewRichard K., and LashonB. Booker (Eds.). (1991). Proceedings of the Fourth International Conference on Genetic Algorithms. University of California, San Diego, July 13–16. San Mateo, CA: Morgan Kaufmann.

    Google Scholar 

  • BhuyanJay N., VijayV. Raghavan, and VenkateshK. Elayavalli. (1991). “Genetic Algorithm for Clustering with an Ordered Representation”. In R.Belew and L.Booker (Eds.), Proceedings of the Fourth International Conference on Genetic Algorithms. San Mateo, CA: Morgan Kaufmann.

    Google Scholar 

  • DavisLawrence (Ed.). (1991). Handbook of Genetic Algorithms. New York: Van Nostrand Reinhold.

    Google Scholar 

  • DingH., A.A.El-Keib, and R.E.Smith. (1992). Optimal Clustering of Power Networks Using Genetic Algorithms. TCGA Report No. 92001, March 5, University of Alabama, Tuscaloosa, AL.

    Google Scholar 

  • FalkenauerEmanuel. (1993). “The Grouping Genetic Algorithms: Widening the Scope of the GAs.” JORBEL: Belgian Journal of Operations Research, Statistics and Computer Science 33(1,2), 79–102.

    Google Scholar 

  • FalkenauerEmanuel. (1994). “New Representation and Operators for GAs Applied to Grouping Problems.” Evolutionary Computation 2(2), 123–144.

    Google Scholar 

  • FalkenauerEmanuel. (1995). “Solving Equal Piles with a Grouping Genetic Algorithm.” In L.J.Eshelman (Ed.), Proceedings of the Sixth International Conference on Genetic Algorithms (pp. 492–497). San Francisco: Morgan Kaufmann.

    Google Scholar 

  • Falkenauer, Emanuel, and Alain Delchambre. (1992). “A Genetic Algorithm for Bin Packing and Line Balancing.” In Proceedings of the IEEE 1992 International Conference on Robotics and Automation (RA92), May 10–15, Nice, France.

  • GareyMichael R., and David S.Johnson. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. San Francisco: Freeman.

    Google Scholar 

  • GoldbergDavid E. (1989). Genetic Algorithms in Search, Optimization and Machine Learning. Reading, MA: Addison-Wesley.

    Google Scholar 

  • GoldbergDavid E., DebKalyanmoy, and BradleyKorb. (1991). “Don't Worry, Be Messy.” In R.Belew and L.Booker (Eds.), Proceedings of the Fourth International Conference on Genetic Algorithms. University of California, San Diego, July 13–16. San Mateo, CA: Morgan Kaufmann.

    Google Scholar 

  • GrefenstetteJohn J. (Ed.). (1985). Proceedings of the First International Conference on Genetic Algorithms and Their Applications. Carnegie-Mellon University, Pittsburgh, PA, July 24–26. Hillsdale, NJ: Erlbaum.

    Google Scholar 

  • Hinterding, Robert, and Lutfar Khan. (1994). “Genetic Algorithms for Cutting Stock Problems: With and Without Contiguity.” Paper accepted by the Australian AI'94 Workshop on Evolutionary Computation.

  • HollandJohn H. (1975). Adaptation in Natural and Artificial Systems. Ann Arbor, MI: University of Michigan Press.

    Google Scholar 

  • JonesDonald R., and Mark A.Beltramo. (1991). “Solving Partitioning Problems with Genetic Algorithms.” In R.Belew and L.Booker (Eds.), Proceedings of the Fourth International Conference on Genetic Algorithms. University of California, San Diego, July 13–16. San Mateo, CA: Morgan Kaufmann.

    Google Scholar 

  • Männer, Reinhard, and Bernard Manderick (Eds.). (1992). “Parallel Problem Solving from Nature, 2.” Proceedings of the Second Conference on Parallel Problem Solving from Nature (PPSN2), Brussels, Belgium, September 28–30.

  • MartelloSilvano, and PaoloToth. (1990a). “Lower Bounds and Reduction Procedures for the Bin Packing Problem.” Discrete Applied Mathematics 22, 59–70.

    Google Scholar 

  • MartelloSilvano, and PaoloToth. (1990b). “Bin-Packing Problem”. In Knapsack Problems, Algorithms and Computer Implementations (pp. 221–245). City. Wiley.

    Google Scholar 

  • RadcliffeNicholas J. (1991). “Forma Analysis and Random Respectful Recombination.” In R.Belew and L.Booker (Eds.), Proceedings of the Fourth International Conference on Genetic Algorithms. University of California, San Diego, July 13–16. San Mateo, CA: Morgan Kaufmann.

    Google Scholar 

  • Radcliffe, Nicholas. (1992). “Non-Linear Genetic Representations.” In R. Männer and B. Manderick (Eds.), Proceedings of the Second Conference on Parallel Problem Solving from Nature (PPSN2), Brussels, Belgium, September 28–30.

  • Reeves, Colin. (1995). “Hybrid Genetic Algorithms for Bin-Packing and Related Problems.” Working paper, submitted to Annals of OR Metaheuristics in Combinatorial Optimization.

  • SmithDerek. (1985). “Bin Packing with Adaptive Search.” In J.Grefenstette (Ed.), Proceedings of the First International Conference on Genetic Algorithms and Their Applications. Carnegie-Mellon University, Pittsburgh, PA, July 24–26. Hillsdale, NJ: Erlbaum.

    Google Scholar 

  • SyswerdaGilbert. (1989). “Uniform Crossover in Genetic Algorithms.” In D.J.Schaffer (Ed.), Proceedings of the Third International Conference on Genetic Algorithms. San Mateo, CA: Morgan Kaufmann.

    Google Scholar 

  • Van Driessche, Raf, and Robert Plessens. (1992). “Load Balancing with Genetic Algorithms.” In R. Männer and B. Manderick (Eds.), Proceedings of the Second Conference on Parallel Problem Solving from Nature (PPSN2), Brussels, Belgium, September 28–30.

  • Van Vliet, André. (1993). Econometric Institute, Erasmus University Rotterdam, private communication.

  • VonLaszewskiGregor. (1991). “Intelligent Structural Operators for the k-way Graph Partitioning Problem.” In R.Belew and L.Booker (Eds.), Proceedings of the Fourth International Conference on Genetic Algorithms. University of California, San Diego, July 13–16. San Mateo, CA: Morgan Kaufmann.

    Google Scholar 

  • VoseMichael D., and GunarE. Liepins. (1991). “Schema Disruption.” In R.Belew and L.Booker (Eds.), Proceedings of the Fourth International Conference on Genetic Algorithms. University of California, San Diego, July 13–16. San Mateo, CA: Morgan Kaufmann.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Industrial Management and Automation, Research Centre for the Belgian Metalworking Industry (CRIF), 50, av. F.D. Roosevelt, CP 106-P4, B-1050, Brussels, Belgium

    Emanuel Falkenauer

Authors
  1. Emanuel Falkenauer
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Falkenauer, E. A hybrid grouping genetic algorithm for bin packing. J Heuristics 2, 5–30 (1996). https://doi.org/10.1007/BF00226291

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF00226291

Key Words

Search

Navigation