Research Group Prof. Vornberger

Abstract: Hybrid Genetic Algorithms for Solving Constrained Packing and Placement Problems

V. Schnecke

In this thesis hybrid approaches and empirical results are presented for three constrained packing and placement problems: the two-dimensional bin-packing, the facility layout problem, and the generation of VLSI macro cell layouts. The basic problem of these three tasks is the packing of rectangular blocks on a planar site. In addition to finding a packing pattern with minimal waste, the objective in the latter two applications is also based on quantitative dependencies between the blocks, i. e. signal-nets in case of the layout generation and flow costs for each pair of blocks in case of the facility layout problem.

Genetic algorithms have proven to be a well suited technique for solving hard combinatorial optimization problems. The main task when applying genetic algorithms to these problems is to find a proper representation for the candidate solutions. Strings of elementary data-types with standard genetic operators lack the fact that infeasible individuals are generated during the search because of the discrete and mostly constrained search space. In this thesis a generally applicable representation for combinatorial placement and packing problems is introduced. Due to a tree-structured genotype representation and hybrid, problem-specific operators the proposed approach is able to deal with different constraints in one optimization step. The parallel genetic algorithms which are proposed in this thesis include a multi-parent gene-pool recombination operator and a dynamic strategy adaptation scheme. For each application empirical data is presented for a set of benchmark problems, and the obtained results are compared to those reported for other approaches.

PhD Dissertation
University of Osnabrück
Department of Mathematics/Computer Science
December 1996

Main Part (compressed Postscript 420 kB, uncompressed 1.2 MB)
Appendix (compressed Postscript 793 kB, uncompressed 24.9 MB)

Feel free to contact Oliver Vornberger to receive a hardcopy of this thesis!