Transcript Genetic Optimization of Electric Machines, a State of the Art Study.

Genetic Optimization of
Electric Machines, a State
of the Art Study
S. E. Skaar, R. Nilssen
15/06/2003
NORPIE 2004, Trondheim
1
Outline of Presentation
•Introduction
•Useful Terms in GA
•Selection of encoding
•Strategies to improve GA
•GA used in design optimization of electrical machines
•Summary
15/06/2003
NORPIE 2004, Trondheim
2
Introduction
 Since J. H. Holland introduced the first Genetic
Algorithm (GA) in 1975, GA has been used widely in
various numerical optimization problems like:
– combinatorial optimization
– circuit design
– design optimization of electrical devices
 GAs are adaptive heuristic search algorithm
premised on the evolutionary ideas of natural
selection and genetic
15/06/2003
NORPIE 2004, Trondheim
3
Useful Terms in GA
 In the following presentation a brief introduction to GA
will be given
 Some of the terms connected to GA will be presented
and given a brief description
15/06/2003
NORPIE 2004, Trondheim
4
 Flowchart of GA
15/06/2003
NORPIE 2004, Trondheim
5
 Phenotype:
– refers to the outward characteristics of an
individual
 Genotype:
– the biological term refers to the overall genetic
make up of an individual
 Practical example,
For the number 232
GA the phenotype representation is: 232
Genotype representation is: 11101000
15/06/2003
NORPIE 2004, Trondheim
6
 Allele:
The allele is the status(/value) of an individual gene
Example:
– binary representation of 11101000 (genotype)
– each bit position corresponds to a gene of the chromosome
– and each bit value corresponds to an allele
Number of states, K, for the gene:
– for a low cardinality alphabet like the binary, K=2
– each gene then can have the allele or state 0 or 1
– from genetics we know DNA is represented with a cardinality
alphabet with K=4
– the alleles here are A, C, G or T
15/06/2003
NORPIE 2004, Trondheim
7
 Encoding:
– How the parameters are converted into a chromosome string
– Some encodings are:
•
•
•
•
•
15/06/2003
binary encoding
Gray encoding
real-number encoding
integer or literal permutation encoding
general data structure encoding
NORPIE 2004, Trondheim
8
 Selection:
– used in the reproduction loop, to select the parent individuals
– can be accomplished using different strategies like:
• roulette wheel
• local tournament
• invoking of various ranking schemes
 Fitness factor:
– a factor used to evaluate selection (the first population) and
offspring (made by subsequent recombination)
– fit offspring is kept, unfit offspring rejected
– fitness factor ensures the “Survival of the fittest”- principle
laid down by Charles Darwin
15/06/2003
NORPIE 2004, Trondheim
9
 Mutation:
– creation of new individuals (based on exciting ones) by
making changes in a single gene
– mutation only - represents a “random walk” in the
neighbourhood of an accepted solution
– several mutation strategies exist
15/06/2003
NORPIE 2004, Trondheim
10
 Crossover:
– creation of new individuals by combining parts from two parent
individuals
– several crossover strategies exist
– a variant of an Arithmetical Crossover called average crossover is
illustrated in the figure above
15/06/2003
NORPIE 2004, Trondheim
11
 Hamming cliffs:
– occurs when pairs of encoding in phenotype space has a
minimal distance, like the numbers 127 and 128
– with binary encoding the genotype of these pairs would be
– to cross this Hamming cliff all bits has to change
simultaneously
– the probability that mutation and crossover will occur may be
very small
– in worst case this results in a large search space being
unexplored, giving a premature convergence
15/06/2003
NORPIE 2004, Trondheim
12
 Elitism:
– conservation of the best individuals of a generation
 Penalty:
– methods of penalizing infeasible solutions
 Niching:
– recombination within a limited sub-population
– allows GA to finish a search within a niche population (with
diverse individuals)
– make the GA capable of locating multiple optimal solutions
within a single population
15/06/2003
NORPIE 2004, Trondheim
13
Selection of Encoding
 Presence of Hamming cliffs might effect the result of
an optimization using GA
 Binary encoding handles Hamming cliffs poorly
 Alternatives to binary encoding exist
 Both real number and Gray encoding has been
proposed
15/06/2003
NORPIE 2004, Trondheim
14
 Collins and Eaton claims there exists no encoding
strategy performing well on all optimization problems
 Goldberg states the selection of encoding to be far
from clear cut
– he describe the scenario of agonizing over the coding, and
recommend users to simply decide upon a prefered coding
– his experience is that GA does “something” to whatever
coding and operator given
– …and that this “something” oftentimes turns out surprisingly
good
 No clear advice on a specific coding selection is
given by GA researchers
 Adopting Goldberg's advice and keeping an overview
over pitfalls and problems for the chosen encoding
might be the better approach
15/06/2003
NORPIE 2004, Trondheim
15
Strategies to Improve GA
 Adopting GA to design
optimization of electrical
machines will result in a
multi dimensional solution
space
 For visualization let us
assume a 3D space, like a
chain of mountains
 The majority of the tops
would be local optima
 Hopefully there is only one
global optima
15/06/2003
NORPIE 2004, Trondheim
16
 With this kind of solution space one can not be sure
to have found the right or best optimum
 Using a simple GA (SGA), users will experience
optima being lost
 It is also hard to predict which optima is being chosen
at each optimization run
 The losses are due to three effects:
– selection pressure
– selection noise
– operator disruption
15/06/2003
NORPIE 2004, Trondheim
17
 Selection noise (SN)
– SN describes the variance of the generated population (example:
roulette wheel has a high SN)
– a too low SN may give lack of convergence on small populations
 Selection pressure
– probability of the best individual being selected
– can be reduced using fitness scaling
 Operator disruption
– population average should usually go up
– if it goes up for a while, then goes down, this is due to operator
disruption
– good solutions are then being replaced by worse offspring
– to reduce operator disruption probability of crossover and mutation
can be lowered
– will always exist a trade-off between diversity and convergence
15/06/2003
NORPIE 2004, Trondheim
18
– to the extreme a probability of 0 for crossover and mutation
would result in no selection pressure but also no useful
search
– crossover does not introduce new alleles to the population
– when a solution starts to converge, effect of crossover starts
to diminish
– mutation introduce new alleles
– having a high mutation rate would slow down convergence
– high mutation rate gives a random variation and increased
disruption
– this does not usually result in a useful diversity
– a too high mutation rate will move GA towards a random
search method
15/06/2003
NORPIE 2004, Trondheim
19
 To enhance GA in performing better in design
optimization, niching has proven feasible
 Niching does a local hill climbing when encountering
any “mountain” top
 The result is then stored in a pool
 Next time the same top is encountered the GA steps
away, searching for a top not already climbed
 After an optimization the designer can analyse the
pool and explore solutions in a close radius to the
different optima in the pool
 In this way information of parameter values for
several feasible solutions can be obtained
15/06/2003
NORPIE 2004, Trondheim
20
GA used in design optimization
of electrical machines
 Study of work done in this field show
changes/improvements in the use of GA
 In the mid 90’s authors tend to use SGA with binary
encoding
 Recent work show a movement in the direction of
using more complex GAs
 There is also an growing awareness of the many
aspects of GA
 Niching has recently been tested with promising
results
15/06/2003
NORPIE 2004, Trondheim
21
 Most of the papers on design optimization conclude
GA to be a promising optimization method
 Non of the papers gave GA a negative testimony
 The main advantages of GA was reported to be
– reasonable short computation time
– no need of a good initial guess or starting point
 Implementation of recombination and selective
pressure effects the convergence of GA
15/06/2003
NORPIE 2004, Trondheim
22
Summary
 An introduction to basic terms in GA has been given
 Selection of encoding and improvement strategies
has been discussed
 Using GA in design optimization of electrical
machines has been reported to be promising
 An evolution in the use of GA in this field was found
15/06/2003
NORPIE 2004, Trondheim
23
Thank you for your attention
15/06/2003
NORPIE 2004, Trondheim
24