1Hybrid Genetic Algorithms for Constrained Placement Problems

Abstract — Genetic algorithms have proven to be a well-suited technique for solving selected combinatorial opti-mization problems. When solving real-world problems, of-ten the main task is to find a proper representation for the candidate solutions. Strings of elementary data types with standard genetic operators may tend to create infea-sible individuals during the search because of the discrete and often constrained search space. This article introduces a generally applicable representation for two-dimensional combinatorial placement and packing problems. Empirical results are presented for two constrained placement prob-lems, the facility layout problem and the generation of VLSI macro-cell layouts. For multi-objective optimization prob-lems, common approaches often deal with the different ob-jectives in different phases, thus are unable to efficiently solve the global problem. Due to a tree-structured genotype representation and hybrid, problem-specific operators, the proposed approach is able to deal with different constraints and objectives in one optimization step. Keywords — VLSI physical design, facility layout prob-lem, combinatorial optimization, multiparent recombina-tion, tree-structured genotype representation I