populations
of
candidate solution natural
selection evolve to
a better solution 物競天擇
適者生存 Genetic Algorithms
Evolutionary Computation(演化式計算)中的一支
Evolutionary systems
optimization tool for engineering problems
History of GA(2/2)
Evolutionary Computation(cont’)
Evolutionary strategies
Evolutionary programming
Genetic Programming
Genetic Algorithms
John Holland,1975
Adaptation in Natural and Artificial Systems
population-based algorithms
evolving operators:
crossover(交換遺傳物質between gametes)
mutation（染色體突變）
inversion（染色體倒位）
The boundaries have broken
Why Evolution?(1/2)
a simple question discontinous multimodal discontinous &
multimodal Why evolution?
Many computational problems have
a huge number of possibilities for solutions
e.g. protein engineering,financial market
to be adaptive to perform well in variable environment
i.e. variable fitness function (e.g. robot)
complex solutions that are difficult to program by hand
e.g expert systems
Why Evolution?(2/2)
Why evolution?(cont’)
Evolution is a method that can
search among an enormous number of possibilities for “solution”
“生命就是解答”
be adpative around the world(環境隨時在變)
適者生存
...ATTGCAACTGAGGGCCCTAACGTTGACTCCCGGG...
...TAACGTTGACTCCCGGGATTGCAACTGAGGGCCC... chromosome(DNA) gene #1 gene #2 useless human:each DNA 數千個 genes
total: 3~4萬個genes 0 0 1 1 1 0 0 1 1 0 e a b c d 簡化 Chromosomes(染色體)/bases(鹼基)/genes(基因)
gene: function blocks of DNA(length > 800 bases)
合成特定功能的蛋白質(proteins)
Biological Terminology(3/4)
..ATTGCAACTGAGGGCCCT.. Genotype vs. phenotype
genotype: particular set of genes
phenotype:physical characteristics
棕眼,金髮,血型B型....
兩個顯性基因，一個顯性基因 phenotype相同,genotype不同
BO, BB 血型B型
for function optimization
optimize f(x,y,z)
genotype: particular set of (x,y,z)
phenotype: f(x,y,z)
Recombination(crossover)
sexual reproduction時染色體重組的動作
父母各自貢獻一股
Mutation(突變)
Biological Terminology(4/4)
0 0 1 1 1 0 0 1 1 0 Optimize F(a,b,c,d,e) e a b c d crossover In Genetic Algorithms
Chromosome a candidate solution(encoded as a bit string)
gene single bit or short blocks of adjacent bits
operators
crossover
mutation
inversion
Optimization and search methods(1/2)
Calculus-based methods
setting the gradient equal to 0
hill climbing
Enumerative methods
looking at values at every point in the search space
Random search algorithms
random choice to guide the search
Optimization and search methods(2/2)
Robust Scheme Specialized
Scheme Random walk combinatorial unimodal multimodal Problem Type Efficiency of search schemes
Efficient optimization methods :hybrid scheme
combining local search with the general robust scheme(such as GA)
What’s the difference(1/2)
x f(x) x 01101 Why GA is robust than traditional search methods?
Different from 4 ways
Working with a coding of parameter set
可以一視同仁(所有問題的參數集都變成bits,or real numbers)
Searching from a population of points, not a single point
robust(but inefficiency)
using fitness information, not derivatives
robust(不能微分的問題也能解決)
probabilistic transition
robust(guided random search)
An example
Maximize f(x)=x2 on the integer interval[0,31]
first step : encoding
What’s the difference(2/2)
The other example:black box switching problem
maximize f(s), where
s: one of setting of 5 switches(ON or OFF)
10011, 11100, ....
f(s): payoff of the switches setting s
With GA
1: encoding parameter
coding : a finite length string, such 11101
2: work with a population of strings
climbing many peaks in parallel
3: 不需額外的information(除了f(s)之外)
4: probabilistic transition rules
guided random choice toward the regions likely improvement
Comments