next up previous
Next: Combined floorplanning and Up: Design of VLSI-Layouts Previous: VLSI design

Genetic Algorithms

Genetic algorithms are a very powerful technique to solve hard optimization problems. Like in the natural evolution there is the population, which is a set of individuals. In the application these are single solutions of the optimization problem. There are genetic operators, which change the population during a generation by creating new individuals and selecting some individuals for surviving to the next generation. After a certain time the fitness (solution quality) of the individuals converges to a global optimum.

Like in nature there is a mutation operator, which randomly changes an individual and so prevents the algorithm from sticking to a local optimum. The crossover operator creates an offspring out of two `parent'-individuals and thereby hereditaring their good qualities to the new individual. At the end of every generation a fixed number of individuals is selected from the grown population due to their fitness to survive to the following generation. This is done by the selection operator which together with mutation and crossover simulates Darwin's `survival of the fittest' and yields a (nearly) optimal solution even in very complex solution spaces.

Fri May 12 15:23:19 MET DST 1995