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.
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!