A formal and empirical analysis of recombination for genetic algorithm-based approaches to the FPGA placement problem

To reduce the compilation times for Field Programmable Gate Arrays, genetic algorithms have been proposed for performing placement. However, the quality of solutions produced by these methods, so far, has been inferior to that produced by other search methods. In this paper, we show how traditional recombination operators, employed by the genetic algorithm when performing placement, fail to produce offspring solutions that are confined to the solution subspace defined by the parent solutions. This violates a fundamental principle that should govern the behavior of the recombination operator. We explore this flaw in detail, and propose a novel recombination operator that yields very statistically significant performance improvements, when tested with standard benchmarks.