Transcript 投影片 1 - National Sun Yat

Chapter 12
FUSION OF FUZZY SYSTEM
AND GENETIC ALGORITHMS
Chi-Yuan Yeh
Genetic Algorithms
• Proposed by John Holland (1975)
• A Genetic Algorithm (GA) is a search technique used
in computing to find exact or approximate solutions
to optimization and search problems.
• GA uses techniques inspired by evolutionary biology
such as inheritance, mutation, selection, and
crossover.
2
Genetic Algorithm Flowchart
3
Operations in Genetic Algorithms
1) Initialize a population of chromosomes (population
size = n).
2) Evaluate the fitness of each chromosome in the
population.
3) If the stop condition is satisfied, stop and return the
best chromosome in the population.
4) Select n/2 pairs of chromosomes from the
population. Chromosomes can be selected several
times.
4
Operations in Genetic Algorithms
5) Create new n chromosomes by mating the
selected pairs by applying the crossover operator.
6) Apply the mutation operator to the new
chromosomes.
7) Replace the old population with the new
chromosomes.
8) Goto (2).
5
Requirements in Genetic Algorithms
• Genetic Representation
– A way of representing solutions/individuals in evolutionary
computation methods.
• Fitness Function:
– A particular type of objective function that quantifies the
optimality of a solution
6
Encoding Scheme
• Binary encoding
– In binary encoding every chromosome is a string of bits, 0
or 1.
• Chromosome A: 101100101100101011100101
• Chromosome B: 111111100000110000011111
– Binary encoding is the most common, mainly because first
works about GA used this type of encoding.
7
Encoding Scheme
• Permutation Encoding
– In permutation encoding, every chromosome is a string of
numbers, which represents number in a sequence.
• Chromosome A: 1 5 3 2 6 4 7 9 8
• Chromosome B: 8 5 6 7 2 3 1 4 9
– Permutation encoding can be used in ordering problems,
such as travelling salesman problem or task ordering
problem.
8
Encoding Scheme
• Real-Valued Encoding
– In real-value encoding, every chromosome is a string of
some values.
• Chromosome A: 1.2324 5.3243 0.4556 2.3293 2.4545
• Chromosome B: 2.3245 2.3253 4.4656 5.2193 0.8721
– Direct value encoding can be used in problems, where
some complicated value, such as real numbers, are used.
– Use of binary encoding for this type of problems would be
very difficult.
9
Selection
• Selection is an operation which prepares reproductions.
• The selected chromosomes are called parents.
• Selection method
– Roulette wheel selection
– Rank based selection
• (0.3,0.25,0.2,0.15,0.1)
–…
10
From: http://www.edc.ncl.ac.uk/highlight/rhjanuary2007g02.php/
Crossover
• Crossover operators produce two new chromosomes
by exchanging information of the selected
chromosomes.
• Crossover method
– One-point
11
Crossover
– Two-point
–…
12
Crossover
• The crossover operations are not performed on every
selected chromosome.
• Genetic algorithm decides, based on a given
probability, whether it performs the crossover
operation on the certain pair of chromosomes or not.
• It is called the crossover probability and given by
users.
13
Mutation
• Mutation operators change some randomly selected
bits of chromosomes.
• If the chromosomes are binary strings, then ‘0’ are
changed to ‘1’, and ‘1’ to ‘0’. It plays a secondary
role after the crossover operator in genetic
algorithms.
• The changing bits means making an offspring
genetically different from its parents.
14
Replacement
• A typical genetic algorithm totally replaces the old
population with the newly created chromosomes, but
it is not mandatory.
• There could be many variations.
• For example, after reproduction, the old and new
populations are taken together, and among them the
best n chromosomes are selected as the next
population.
15
Elitist strategy
• In order to escape from a local optimum, a kind of
jump operation is needed. So, by using the mutation
operator, we can get some offsprings different from
their parents. That is, the genetic algorithms try to
jump to other place.
16
Fusion with Genetic Algorithms
• Identifying fuzzy systems with genetic algorithms
• Controlling parameters of genetic algorithms with
fuzzy systems
17
Identifying fuzzy systems with
genetic algorithms
• Schematic diagram of identifying FSs with GAs
18
Identifying fuzzy systems with
genetic algorithms
• Tuning an existing fuzzy system
• Building a fuzzy system with genetic algorithm
19
Tuning an existing fuzzy system
• Four fuzzy rules:
20
Building a fuzzy system with
genetic algorithm
• This method do not need an existing fuzzy system.
This approach determines all the parameters of a
fuzzy system by genetic algorithms without any priori
knowledge.
• Thus, the chromosomes used in this method usually
include most of the parameters such as the number
and membership functions of linguistic terms.
• So, it is very important how to effectively represent
those parameters because a long chromosome means
a wide search space.
21
Building a fuzzy system with
genetic algorithm
• If a search space is wide, we cannot expect a good
optimization result.
• So, most researches make restrictions; for example,
some fix the number of linguistic terms or restrict the
shape and position of membership functions.
22
Building a fuzzy system with
genetic algorithm
23
Building a fuzzy system with
genetic algorithm
• Determination of consequent parts
24
Building a fuzzy system with
genetic algorithm
25
Controlling parameters of genetic
algorithms with fuzzy systems
26
Thanks for your attention!
27