Transcript 오토메타형식언어 - Soft Computing Lab.

5. Implementing a GA
 학습목표
GA를 사용해 실제 문제를 해결할 때 고려해야 하는
사항에 대해 이해한다
Huge number of choices with little theoretical guidance
Implementation issues + sophisticated GA techniques
Outline
 When should a GA be used?
 Encoding a problem for a GA
 Adapting the encoding
 Selection methods
 Genetic operators
 Parameters for GAs
When should a GA be Used?
 Search space
 large
 known not perfectly smooth and unimodal
 not well understood
 Fitness function
 noisy
 Task
not require global optimum
Fixed-length, fixed-order bit strings
Encoding a Problem for a GA (1)
 Binary encodings: historical but unnatural for many problems
 Extensions
 Bethke’s gray coding
 Hillis’s diploid binary encoding scheme
 Holland’s theoretical justification for binary encoding
 Small number of alleles and long strings  higher
implicit parallelism
 Large number of alleles and short strings
Encoding a Problem for a GA (2)
 Many-character and Real-valued encodings
 Kitano’s many-character rep for graph-generation grammar
 Meyer’s real-valued rep for condition sets
 Montana’s real-valued rep for neural-network weights
 Schultz-Kremer’s real-valued rep for torsion angles in
proteins
 Tree encodings
 Koza’s scheme for representing computer programs
 open-ended search space
 Guessing at an appropriate encodings and trying out a GA
Trial and Error!!
 Adapting the encoding!!
Adapting the Encoding (1)
Linkage problem (how best to order the bits ahead of time)
Functionally related loci be more likely to stay together
on the string under crossover
 Deal with the inkage problem in fixed-length strings
 Inversion
 Reordering operator: each allele be given an index
indicating its “real” position
 No change of fitness but linkages
 produce orderings where beneficial schemas are more
likely to survive
 Full set of loci after crossover?
 permit crossover only between chromosomes with the
same permutation of the loci
 employ a “master/slave” approach
 Applications: ordering problems like DNA fragment
assembly
Adapting the Encoding (2)
 Evolving crossover “Hot Spots”
 evolve not the order of bits but the positions where
crossover was allowed
 mutation on both chromosomes and attached crossover
templates  coevolve good crossover templates
 Messy GAs
 explicitly building up increasingly longer, highly fit strings
from well-tested shorter building blocks
 each bit is tagged with its “real” locus
 Overspecification problem: left-to-right, first-come-first-
served scheme  candidate schema
 evolve candidate schemas, gradually building up longer
ones until a solution is formed
Selection Methods
 Exploitation / exploration balance
 Selection has to be balanced with variation from crossover
and mutation
 Too strong selection: suboptimal highly fit individuals 
reducing diversity
 Too-weak selection: too slow evolution
 Fitness-proportionate Selection
 Expected value of an individual = its fitness / average
fitness
 Roulette wheel sampling: bad in small populations
 Stochastic universal sampling: spin the wheel once, but
with N equally spaced pointers for N parents
 Problem: premature convergence (some multiply quickly in
population)  too much emphasis on exploitation of highly fit
Selection Methods (2)
 Sigma Scaling
 mapping raw fitness values to expected values to prevent
premature convergence
 Elitism
 retain some number of best individuals at each generation
 Boltzmann Selection
 different amounts of selection pressure for different times in
a run
 Rank Selection
 expected value of individual depends on rank
 Tournament Selection
 Steady-state Selection
Genetic Operators
 Crossover
 single point, two-point crossover, …
 recombine highly fit schemas
 Mutation
 known as less important, but balance among crossover,
mutation, and selection is important
 Other Operators and Mating Strategies
 Crowding operator: newly formed offspring replaced the
existing individual most similar to itself  preventing too
many similar individuals (crowds)
 Fitness sharing: each individual’s fitness was decreased by
the presence of other population members  Speciation!
 Restrictions on mating for diversity: only sufficiently similar
individuals are allowed to mate  mating tag approach
Parameters for GAs
 population size, crossover rate, mutation rate
 typically interact with one another nonlinearly  no way to
optimize one at a time
 De Jong’s guideline
 population size: 50~100 individuals
 crossover rate: ~0.6
 mutation rate: 0.001
 Meta-level GA
 population size: 30
 crossover rate: 0.95
 mutation rate: 0.01
 elitist selection
 self-adaptation methods required!
 Parameter values adapt in real time to the ongoing search
Schedule for Remaining Lectures
 11/5: Co-Evolution and Speciation
11/10: Interactive Evolutionary Computation
11/12: 정태민, 차옥균
11/17: 이승현
11/19: 황주원, 윤종원
11/24: 박지인
11/26: 고유선, 오근현
12/1: 안재균
12/3: 박수상, 이영설
12/10: Term Project 최종발표