GALLO: a Genetic Algorithm for Floorplan Area Optimization

The paper describes a Genetic Algorithm for the Floorplan Area Optimization problem. The algorithm is based on suitable techniques for solution encoding and evaluation function definition, effective cross-over and mutation operators, and heuristic operators which further improve the method's effectiveness. An adaptive approach automatically provides the optimal values for the activation probabilities of the operators. Experimental results show that the proposed method is competitive with the most effective ones as far as the CPU time requirements and the result accuracy is considered, but it presents some advantages: it requires a limited amount of memory, it is not sensible to special structures which are critical for other methods, and has a complexity which grows linearly with the number of implementations; finally, we demonstrate that the method is able to handle floorplans much larger (in terms of number of basic rectangles) than any benchmark previously considered in the literature.