Genetic Algorithm in chip floor planning of vlsi layout




The original GA and its many variants collectively known as genetic algorithms are computational procedure that mimics the natural process of evolution. Darwin observed that as variations are introduced into a population with each new generation the less fit individuals are tend to die off in the competition for food and this survival of the fittest principle leads to improvement in the species. GAs has also applied to optimisation problems, and the applications like floorplanning in EDA tools falls into this category. The objective of the GA is then to find an optimal solution to a problem. Since Gas are heuristic procedure, they are not guaranteed to find the optimum but experience has shown that they are able to find very good solutions for wide range of problems. GAs work by evolving a population of individual in the population where the fitness computation depend s on the application. For each generation individuals are selected from the population for reproduction, the individuals are crossed to generate new individuals and the new individuals are muted with some low mutation probability. The new individual may completely replace the old individuals in the population with distinct generation evolved; alternatively the new individuals may be combined with old individuals in the population. Since selection is biased towards more highly fit individuals, the average fitness of the population tends to improve from one generation to the next. The fitness of the best individuals is also expected to improve overtime, and the best individual may be chosen as a solution after several generations.