Transcript GA Operation

Genetic Algorithm
-- Introduction and
Collaboration with Fuzzy Logic
魏志達 Jyh-Da Wei
1
Why Genetic Algorithms
Conventional Training Process
v.s.
 Evolutionary Computing

(John Holland, 1975)
2
GA Evolution
Population
.. (chromosomes)
.
1. Gene Encoding
Generation
GA Operators
4c. Crossover
2. Evaluation
Fitness value
4b. Mutation
4a. Reproduction
Fitness value
Environment
3
3. Selection
Outline
-- GA & Fuzzy：
Introduction to GA
Discussion on Diversity
Special Research Topics
Evolutionary Fuzzy Inference Systems
GA using Fuzzy Parameters
Genotype based on Fuzzy Polyploid
4
Outline
-- GA & Fuzzy：
Introduction to GA
Discussion on Diversity
Special Research Topics
Evolutionary Fuzzy Inference Systems
GA using Fuzzy Parameters
Genotype based on Fuzzy Polyploid
5
GA Evolution
Population
.. (chromosomes)
.
1. Gene Encoding
Generation
GA Operators
4c. Crossover
2. Evaluation
Fitness value
4b. Mutation
4a. Reproduction
Fitness value
Environment
6
3. Selection
Gene Encoding (example 1)

Microarray for RNA Identification
– 160 chromosome length
– 4 values: A, C, G, U
– Search space = 4^160 (brute force)
7
Gene Encoding (example 2)


8
Game Playing
f= w1 f1( )+ w2 f2( )+ w3 f3( )+…wnfn( )
wk in {0,0.5,1}
 search space = 3^n
Evaluation
Evaluation Function => Fitness Value
 Fitness for the Evolution Environment

– Good performance
– Elegant rules
– Specific character
9
Selection
Evaluation Ratio
 Ranking Ratio


10
Also Select the Worst Instances?
GA Operation
11

Crossover:

Mutation:
Crossover Mechanisms
(a) One-point crossover; (b) Two-point
crossover
12
GA Evolution
Population
.. (chromosomes)
.
1. Gene Encoding
Generation
GA Operators
4c. Crossover
2. Evaluation
Fitness value
4b. Mutation
4a. Reproduction
Fitness value
Environment
13
3. Selection
Outline
-- GA & Fuzzy：
Introduction to GA
Discussion on Diversity
Special Research Topics
Evolutionary Fuzzy Inference Systems
GA using Fuzzy Parameters
Genotype based on Fuzzy Polyploid
14
Fuzzy Inference System
Antecedents: (interval, velocity)
X1 = Very Close(VC), C, M, F, VF (Far)
X2 = Very Low (VL), L, A, H, VH (High)
 Consequence: (acceleration)
Y = NL, NM, NS, ZE, PS, PM, PL
 Candidate Rule Bases:
7^ 25

15
Example of Rule Base
X2
16
X1
VC
VL
ZE
L
NS
A
NS
H
NM
VH
NL
C
PS
ZE
NS
NS
NM
M
PS
PS
ZE
NS
NS
F
PM
PS
PS
ZE
NS
VF
PL
PM
PS
PS
ZE
Evolutionary Fuzzy Inference System

Gene Encoding:
– Chromosome length # (5+1)*(5+1)
– Gene Value # 7+1

Evaluation:
– Bonus for <don’t care> to simplify rule
base

Crossover and Mutation:
– As usual
17