A hybrid genetic algorithm for a variant of two-dimensional packing problem

ABSTRACT

A variant of two-dimensional packing problem was given in the GECCO'2008 competition. This paper describes the genetic algorithm that produced the best result and thus won the No. 1 prize. As the problem is naturally represented by a two-dimensional chromosome, two-dimensional crossovers are used to generate more diverse chromosomes and effectively maintain geographical linkage among genes. We developed a local search heuristic based on the breadth-first search algorithm; we describe how to implement the heuristic efficiently using problem-specific knowledge. The local search was combined with a steady-state genetic algorithm and the combination showed strong synergy.

REFERENCES

• 1: C. A. Anderson, K. F. Jones, and J. Ryan. A two-dimensional genetic algorithm for the Ising problem. Complex Systems, 5:327--333, 1991.
• 2: Thang Nguyen Bui , Byung Ro Moon, On Multi-Dimensional Encoding/Crossover, Proceedings of the 6th International Conference on Genetic Algorithms, p.49-56, July 15-19, 1995
• 3: J. P. Cohoon and W. Paris. Genetic placement. In IEEE International Conference on Computer-Aided Design, pages 422--425, 1986.
• 4: C.-H. Im, H.-K. Jung, and Y.-J. Kim. Hybrid genetic algorithm for electromagnetic topology optimization. IEEE Transactions on Magnetics, 39(5): 2163--2169, 2003.
• 5: Andrew B. Kahng , Byung Ro Moon, Toward More Powerful Recombinations, Proceedings of the 6th International Conference on Genetic Algorithms, p.96-103, July 15-19, 1995
• 6: B.-R. Moon, Y.-S. Lee, and C.-K. Kim. GEORG: VLSI circuit partitioner with a new genetic algorithm framework. Journal of Intelligent Manufacturing, 9(5):401--412, 1998.
• 7: Eun-Jong Park , Yong-Hyuk Kim , Byung Ro Moon, Genetic Search For Fixed Channel Assignment Problem With Limited Bandwidth, Proceedings of the Genetic and Evolutionary Computation Conference, p.1172-1179, July 09-13, 2002
• 8: Gilbert Syswerda, Uniform Crossover in Genetic Algorithms, Proceedings of the 3rd International Conference on Genetic Algorithms, p.2-9, June 01, 1989

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Constrained optimization

General Terms:
Algorithms, Experimentation

Keywords:
breadth-first search, geographic crossover, hybrid genetic algorithm, local search, packing, two-dimensional