Genetic and Evolutionary Floorplanning

The idea

Where annealing walks one solution through the search space, a genetic algorithm maintains a population. Each generation: evaluate everyone (area, wirelength), select parents biased toward the fit, produce children by crossover (splice two parents' encodings) and mutation (the same local moves annealers use), and replace the weak. Diversity in the population plays the role temperature plays in annealing.

All the floorplan encodings on these pages have been used as genomes: Polish expressions, sequence pairs, trees. The recurring difficulty is crossover. Splicing two permutations naively produces duplicates and omissions, so permutation-preserving operators (order crossover, partially matched crossover) are required; even then, half of parent A's packing logic rarely means anything glued to half of parent B's, so offspring often decode to poor floorplans and the algorithm degenerates into parallel mutation-only search, which annealing does with less overhead.

Assessment

Population methods are worthwhile when evaluations parallelize across a cluster trivially, when multi-objective trade-off fronts are the goal (area versus wirelength versus temperature Pareto sets fall out naturally from a population), or when hybridized: memetic designs that apply local annealing to each offspring have posted respectable results. As a straight replacement for annealing on single-objective packing, the published record says: comparable at best, usually behind.

Where you meet it today

Multi-objective floorplanning research, thermal-aware and 3D-integration studies with exotic cost mixtures, and as the standard "other metaheuristic" baseline in papers. Its population viewpoint also prefigured today's approach of sampling many reinforcement-learning rollouts in parallel.