This paper describes the implementation of the Genetic Algorithm for Standard-cell Placement (GASP). Unlike the other placement algorithms that apply transformations on the physical layout, the genetic algorithm applies transformations on the chromosomal representation of the physical layout. The algorithm works on a set of configurations constituting a constant size population. The transformations are performed through crossover operators that generate a new configuration assimilating the characteristics of a pair of configurations existing in the current population (similar to biological reproduction). Mutation and inversion operators are also used to increase the diversity of the population, and avoid premature convergence at local optima. Due to the simultaneous optimization of a large population of configurations, there is a logical concurrency in the search of the solution space which makes the genetic algorithm an extremely efficient optimizer. Three efficient crossover techniques have been compared, and the algorithm parameters, namely mutation rate, crossover rate, and inversion rate have been optimized for the cell placement problem by using a meta-genetic process. The resulting algorithm was tested against TimberWolf 3.3 on five industrial circuits consisting of 100-800 cells. The results indicate that a placement comparable in quality can be obtained in about the same execution time as TimberWolf, but the genetic algorithm needs to explore 20-50 times less configurations compared to TimberWolf, which illustrates the efficiency of the search process. © 1990 IEEE
