07-04-2012, 04:03 PM
CIRCUIT DESIGN OPTIMIZATION USING GENETIC ALGORTIHM WITH DIFFERENT CROSSOVER
[attachment=19722]
INTRODUCTION:
An evolutionary algorithm (EA) is a
population-based metaheuristic
The common idea behind all these algorithms is that given a
environmental pressure causes natural selection and this causes a rise in the fitness of the
population. Based on the fitness some of th
applying recombination or mutation to them. thi
with sufficient quality is formed.
Inspired by Biological Evolution
Search and Optimization Procedures
Good in Rugged Search Spaces
Good for Multimodal Environments
Genetic Algorithms (GAs) are adaptive heuristic search algorithm based on the
evolutionary ideas of natural selection and genetics. As such they represent an
intelligent exploitation of a random search used to solve optimization problems.
Although randomised, GAs are by no means random, instead they exploit historical
information to direct the search into the region of better performance within the
search space. The basic techniques of the GAs are designed to simulate processes in
natural systems necessary for evolution, specially those follow the principles first laid
down by Charles Darwin of "survival of the fittest.". Since in nature, competition
among individuals for scanty resources results in the fittest individuals dominating
over the weaker ones.
Brief History
Genetic Algorithms were invented to mimic some of the processes observed in natural
evolution. Many people, biologists included, are astonished that life at the level of complexity
that we observe could have evolved in the relatively short time suggested by the fossil record.
The idea with GA is to use this power of evolution to solve optimization problems. The father
of the original Genetic Algorithm was John Holland who invented it in the early 1970's.
Parameters of GA
• Crossover probability: pc: How often will crossover be performed.
– If crossover probability is 100%, then all offspring is made by crossover.
– If it is 0%, whole new generation is made from exact copies of chromosomes
from old population (but this does not mean that the new generation is the
same!).
– Crossover is made in hope that new chromosomes will have good parts of old
chromosomes and maybe the new chromosomes will be better. However it is
good to leave some part of population survive to next generation.
• Mutation probability : pm: How often will be parts of chromosome mutated.
– If there is no mutation, offspring are taken after crossover (or copied) without
any change.
– If mutation is performed, part of chromosome is changed.
– If mutation probability is 100%, whole chromosome is changed,
– If mutation probability is 0%, nothing is changed.
– Mutations prevent the GA from getting trapped into a local extremum
– Too much mutation means the GA will degenerate into a random search.
MUTATION:
Mutation is executed in one parent and a new individual is generated. Mutation involves
randomly changing genes in chromosomes, in order to create diversity within the pool of
individuals.
The procedure of mutation is as follows.
(1) Select one individual as a parent using tournament selection.
(2) Some genes are selected with the probability of Pm. The selected genes are changed
randomly and the new individual is generated.
(3) The new individual becomes the individual of the next generation.
Inversion operator
-The inversion operator takes the random segment in a solution string and inverts it end to
end. It modifies the representation of the solution.
[attachment=19722]
INTRODUCTION:
An evolutionary algorithm (EA) is a
population-based metaheuristic
The common idea behind all these algorithms is that given a
environmental pressure causes natural selection and this causes a rise in the fitness of the
population. Based on the fitness some of th
applying recombination or mutation to them. thi
with sufficient quality is formed.
Inspired by Biological Evolution
Search and Optimization Procedures
Good in Rugged Search Spaces
Good for Multimodal Environments
Genetic Algorithms (GAs) are adaptive heuristic search algorithm based on the
evolutionary ideas of natural selection and genetics. As such they represent an
intelligent exploitation of a random search used to solve optimization problems.
Although randomised, GAs are by no means random, instead they exploit historical
information to direct the search into the region of better performance within the
search space. The basic techniques of the GAs are designed to simulate processes in
natural systems necessary for evolution, specially those follow the principles first laid
down by Charles Darwin of "survival of the fittest.". Since in nature, competition
among individuals for scanty resources results in the fittest individuals dominating
over the weaker ones.
Brief History
Genetic Algorithms were invented to mimic some of the processes observed in natural
evolution. Many people, biologists included, are astonished that life at the level of complexity
that we observe could have evolved in the relatively short time suggested by the fossil record.
The idea with GA is to use this power of evolution to solve optimization problems. The father
of the original Genetic Algorithm was John Holland who invented it in the early 1970's.
Parameters of GA
• Crossover probability: pc: How often will crossover be performed.
– If crossover probability is 100%, then all offspring is made by crossover.
– If it is 0%, whole new generation is made from exact copies of chromosomes
from old population (but this does not mean that the new generation is the
same!).
– Crossover is made in hope that new chromosomes will have good parts of old
chromosomes and maybe the new chromosomes will be better. However it is
good to leave some part of population survive to next generation.
• Mutation probability : pm: How often will be parts of chromosome mutated.
– If there is no mutation, offspring are taken after crossover (or copied) without
any change.
– If mutation is performed, part of chromosome is changed.
– If mutation probability is 100%, whole chromosome is changed,
– If mutation probability is 0%, nothing is changed.
– Mutations prevent the GA from getting trapped into a local extremum
– Too much mutation means the GA will degenerate into a random search.
MUTATION:
Mutation is executed in one parent and a new individual is generated. Mutation involves
randomly changing genes in chromosomes, in order to create diversity within the pool of
individuals.
The procedure of mutation is as follows.
(1) Select one individual as a parent using tournament selection.
(2) Some genes are selected with the probability of Pm. The selected genes are changed
randomly and the new individual is generated.
(3) The new individual becomes the individual of the next generation.
Inversion operator
-The inversion operator takes the random segment in a solution string and inverts it end to
end. It modifies the representation of the solution.