Genetic Algorithms Talk

Introduction Algorithm Examples Conclusions

Genetic algorithms and evolutionary programming Fabian J. Theis Institute of Biophysics University of Regensburg, Germany [email protected]

Regensburg 11-Jan-05

Theis

Genetic algorithms and evolutionary programming

Introduction Algorithm Examples Conclusions

Outline

Selection Reproduction

Introduction Reinforcement learning Imitate nature Genetic algorithms

Examples 2d-function optimization Genetic Mastermind Hyerplane detection

Algorithm Basic algorithm Data representation

Conclusions

Theis

Genetic algorithms and evolutionary programming

Introduction Algorithm Examples Conclusions

Reinforcement learning Imitate nature Genetic algorithms

Algorithm

Selection Reproduction

Introduction Reinforcement learning Imitate nature Genetic algorithms

Examples 2d-function optimization Genetic Mastermind Hyerplane detection

Algorithm Basic algorithm Data representation

Conclusions

Theis

Genetic algorithms and evolutionary programming

Introduction Algorithm Examples Conclusions

Reinforcement learning Imitate nature Genetic algorithms

Introduction

I

idea of genetic algorithms (GAs) I

I

I

extract optimization strategies nature uses successfully → Darwinian Evolution transform them for application in mathematical optimization theory

abstract goal: find the global optimum of a problem/function in a defined phase space

Theis

Genetic algorithms and evolutionary programming

Introduction Algorithm Examples Conclusions

Reinforcement learning Imitate nature Genetic algorithms

Introduction

I

idea of genetic algorithms (GAs) I

I

I

extract optimization strategies nature uses successfully → Darwinian Evolution transform them for application in mathematical optimization theory

abstract goal: find the global optimum of a problem/function in a defined phase space

Theis

Genetic algorithms and evolutionary programming

Introduction Algorithm Examples Conclusions

Reinforcement learning Imitate nature Genetic algorithms

Optimization

I

GA as special kind of reinforcement learning I I I I

I

no access to the full problem/function but: rewards are given for a given action/search space position goal: use rewards to find optimum this contrasts to learning by (given) examples as in supervised learning e.g. using neural networks → traverse search space manually

Theis

Genetic algorithms and evolutionary programming

Introduction Algorithm Examples Conclusions

Reinforcement learning Imitate nature Genetic algorithms

Optimization

I

simple algorithm: random sampling I I

I

I

pick a single location in the search space store it if reward is higher than at previous locations, discard it otherwise repeat

other such algorithms I I I

Markov-Chain-Monte-Carlo search (MCMC) simulated annealing if derivative of reward is available: (conjugated) gradient ascent/descent etc.

Theis

Genetic algorithms and evolutionary programming

Introduction Algorithm Examples Conclusions

Reinforcement learning Imitate nature Genetic algorithms

Optimization

I

simple algorithm: random sampling I I

I

I

pick a single location in the search space store it if reward is higher than at previous locations, discard it otherwise repeat

other such algorithms I I I

Markov-Chain-Monte-Carlo search (MCMC) simulated annealing if derivative of reward is available: (conjugated) gradient ascent/descent etc.

Theis

Genetic algorithms and evolutionary programming

Introduction Algorithm Examples Conclusions

Reinforcement learning Imitate nature Genetic algorithms

Genetic algorithms I

here: imitate nature’s robust way of evolving successful organisms I

I

I I

I

organisms ill-suited to an environment die off, whereas fit ones reproduce offspring is similar to the parents, so population fitness increases with generations mutation can randomly generate new species ‘The Origin of Species by Means of Natural Selection’, C.R. Darwin, D. Appleton and Company, NY, 1897

history: I I I

introduced by J. Holland 1975 further invesigated by his students e.g. K. DeJong 1975 more recently theoretical advances e.g. by M. Vose 1993

Theis

Genetic algorithms and evolutionary programming

Introduction Algorithm Examples Conclusions

Reinforcement learning Imitate nature Genetic algorithms

Genetic algorithms I I

what’s good for nature is good for artificial systems imagine population of individual ‘explorers’ sent into the optimization phase-space I

I

I

the struggle of ‘life’ begins I I I

I

explorer is defined by its genes, encoding his phase-space position optimization problem is given by a fitness function selection crossover mutation

according to these rules populations tend to increase overall fitness

Theis

Genetic algorithms and evolutionary programming

Introduction Algorithm Examples Conclusions

Reinforcement learning Imitate nature Genetic algorithms

Genetic algorithms I I

what’s good for nature is good for artificial systems imagine population of individual ‘explorers’ sent into the optimization phase-space I

I

I

the struggle of ‘life’ begins I I I

I

explorer is defined by its genes, encoding his phase-space position optimization problem is given by a fitness function selection crossover mutation

according to these rules populations tend to increase overall fitness

Theis

Genetic algorithms and evolutionary programming

Introduction Algorithm Examples Conclusions

Reinforcement learning Imitate nature Genetic algorithms

Genetic algorithms I I

what’s good for nature is good for artificial systems imagine population of individual ‘explorers’ sent into the optimization phase-space I

I

I

the struggle of ‘life’ begins I I I

I

explorer is defined by its genes, encoding his phase-space position optimization problem is given by a fitness function selection crossover mutation

according to these rules populations tend to increase overall fitness

Theis

Genetic algorithms and evolutionary programming

Introduction Algorithm Examples Conclusions

Reinforcement learning Imitate nature Genetic algorithms

Genetic algorithms I I

what’s good for nature is good for artificial systems imagine population of individual ‘explorers’ sent into the optimization phase-space I

I

I

the struggle of ‘life’ begins I I I

I

explorer is defined by its genes, encoding his phase-space position optimization problem is given by a fitness function selection crossover mutation

according to these rules populations tend to increase overall fitness

Theis

Genetic algorithms and evolutionary programming

Introduction Algorithm Examples Conclusions

Reinforcement learning Imitate nature Genetic algorithms

Genetic algorithms

I

advantages I I I

I

global not only local optimization simple and hence easy to implement easy parallelization possible

disadvantages I I I

how to encode phase-space position rather low speed and high computational cost parameter dependencies (population size, selection and reproduction parameters)

Theis

Genetic algorithms and evolutionary programming

Introduction Algorithm Examples Conclusions

Reinforcement learning Imitate nature Genetic algorithms

Genetic algorithms

I

advantages I I I

I

global not only local optimization simple and hence easy to implement easy parallelization possible

disadvantages I I I

how to encode phase-space position rather low speed and high computational cost parameter dependencies (population size, selection and reproduction parameters)

Theis

Genetic algorithms and evolutionary programming

Introduction Algorithm Examples Conclusions

Basic algorithm Data representation Selection Reproduction

Algorithm

Selection Reproduction

Introduction Reinforcement learning Imitate nature Genetic algorithms

Examples 2d-function optimization Genetic Mastermind Hyerplane detection

Algorithm Basic algorithm Data representation

Conclusions

Theis

Genetic algorithms and evolutionary programming

Introduction Algorithm Examples Conclusions

Basic algorithm Data representation Selection Reproduction

Basic genetic algorithm

Data : population, a set of individuals fitness-function Fitness, a function measuring fitness of an individual Result: an individual 1 2

3

repeat parents ← Selection (population, Fitness) population ← Reproduction (parents) until some individual is fit enough; return the best individual in population according to Fitness

Theis

Genetic algorithms and evolutionary programming

Introduction Algorithm Examples Conclusions

Basic algorithm Data representation Selection Reproduction

Individual I I

an individual encodes the data space position classic GA approach: representation by word (chromosome) over a finite alphabet I I I I

I

I

each letter is called gene real DNA: alphabet is {A, G , T , C } here: usually binary alphabet {0, 1} some authors speak more general of evolutionary programming if alphabet is larger finite alphabet implies discrete search space

continuous search space I

I

use continuous ‘alphabet’ i.e. genes ∈ R or bounded genes ∈ [a, b] so individual ∈ Rn respectively ∈ [a1 , b1 ] × . . . × [an , bn ]

Theis

Genetic algorithms and evolutionary programming

Introduction Algorithm Examples Conclusions

Basic algorithm Data representation Selection Reproduction

Individual I I

an individual encodes the data space position classic GA approach: representation by word (chromosome) over a finite alphabet I I I I

I

I

each letter is called gene real DNA: alphabet is {A, G , T , C } here: usually binary alphabet {0, 1} some authors speak more general of evolutionary programming if alphabet is larger finite alphabet implies discrete search space

continuous search space I

I

use continuous ‘alphabet’ i.e. genes ∈ R or bounded genes ∈ [a, b] so individual ∈ Rn respectively ∈ [a1 , b1 ] × . . . × [an , bn ]

Theis

Genetic algorithms and evolutionary programming

Introduction Algorithm Examples Conclusions

Basic algorithm Data representation Selection Reproduction

Individual I I

an individual encodes the data space position classic GA approach: representation by word (chromosome) over a finite alphabet I I I I

I

I

each letter is called gene real DNA: alphabet is {A, G , T , C } here: usually binary alphabet {0, 1} some authors speak more general of evolutionary programming if alphabet is larger finite alphabet implies discrete search space

continuous search space I

I

use continuous ‘alphabet’ i.e. genes ∈ R or bounded genes ∈ [a, b] so individual ∈ Rn respectively ∈ [a1 , b1 ] × . . . × [an , bn ]

Theis

Genetic algorithms and evolutionary programming

Introduction Algorithm Examples Conclusions

Basic algorithm Data representation Selection Reproduction

Selection I I

goal: select individuals that produce the next generation probabilistic selection I I I

I

based on fitness function f better individuals have increased chance of reproduction usually selection with replacement → very fit individuals reproduce several times

selection probabilities I

roulette wheel (Holland 1975) f (i) P(choice of individual i) = P j f (j)

I

I

problem: negative f ? minimization? ranking methods, i.e. choose individuals according to fitness rank e.g. normalized geometric ranking (Joines and Houck 1994) tournament selection, i.e. select best among a randomly selected subset Theis

Genetic algorithms and evolutionary programming

Introduction Algorithm Examples Conclusions

Basic algorithm Data representation Selection Reproduction

Selection I I

goal: select individuals that produce the next generation probabilistic selection I I I

I

based on fitness function f better individuals have increased chance of reproduction usually selection with replacement → very fit individuals reproduce several times

selection probabilities I

roulette wheel (Holland 1975) f (i) P(choice of individual i) = P j f (j)

I

I

problem: negative f ? minimization? ranking methods, i.e. choose individuals according to fitness rank e.g. normalized geometric ranking (Joines and Houck 1994) tournament selection, i.e. select best among a randomly selected subset Theis

Genetic algorithms and evolutionary programming

Introduction Algorithm Examples Conclusions

Basic algorithm Data representation Selection Reproduction

Selection I I

goal: select individuals that produce the next generation probabilistic selection I I I

I

based on fitness function f better individuals have increased chance of reproduction usually selection with replacement → very fit individuals reproduce several times

selection probabilities I

roulette wheel (Holland 1975) f (i) P(choice of individual i) = P j f (j)

I

I

problem: negative f ? minimization? ranking methods, i.e. choose individuals according to fitness rank e.g. normalized geometric ranking (Joines and Houck 1994) tournament selection, i.e. select best among a randomly selected subset Theis

Genetic algorithms and evolutionary programming

Introduction Algorithm Examples Conclusions

Basic algorithm Data representation Selection Reproduction

Reproduction

I

typically consists of two stages I

I

I

crossover (or mating): selected individuals are randomly paired and (usually two) children are produced mutation: genes can be altered by random mutation to a different value according to a small probability

use genetic operators to produce and alter new offspring → basic search mechanism in GAs

Theis

Genetic algorithms and evolutionary programming

Introduction Algorithm Examples Conclusions

Basic algorithm Data representation Selection Reproduction

Reproduction

I

typically consists of two stages I

I

I

crossover (or mating): selected individuals are randomly paired and (usually two) children are produced mutation: genes can be altered by random mutation to a different value according to a small probability

use genetic operators to produce and alter new offspring → basic search mechanism in GAs

Theis

Genetic algorithms and evolutionary programming

Introduction Algorithm Examples Conclusions

Basic algorithm Data representation Selection Reproduction

Crossover I I

let x, y ∈ An be the genes of the two parents simple crossover I I

I

choose r randomly in {1, . . . , n} generate children x0 , y0 ∈ An by  xi xi0 := yi  yi yi0 := xi

if i < r otherwise if i < r otherwise

in the case of continuous genes: arithmetic crossover I I

choose r randomly in [0, 1] generate children x0 , y0 ∈ An by x0 y0 Theis

:= r x + (1 − r )y := (1 − r )x + r y Genetic algorithms and evolutionary programming

Introduction Algorithm Examples Conclusions

Basic algorithm Data representation Selection Reproduction

Crossover I I

let x, y ∈ An be the genes of the two parents simple crossover I I

I

choose r randomly in {1, . . . , n} generate children x0 , y0 ∈ An by  xi xi0 := yi  yi yi0 := xi

if i < r otherwise if i < r otherwise

in the case of continuous genes: arithmetic crossover I I

choose r randomly in [0, 1] generate children x0 , y0 ∈ An by x0 y0 Theis

:= r x + (1 − r )y := (1 − r )x + r y Genetic algorithms and evolutionary programming

Introduction Algorithm Examples Conclusions

Basic algorithm Data representation Selection Reproduction

Crossover I I

let x, y ∈ An be the genes of the two parents simple crossover I I

I

choose r randomly in {1, . . . , n} generate children x0 , y0 ∈ An by  xi xi0 := yi  yi yi0 := xi

if i < r otherwise if i < r otherwise

in the case of continuous genes: arithmetic crossover I I

choose r randomly in [0, 1] generate children x0 , y0 ∈ An by x0 y0 Theis

:= r x + (1 − r )y := (1 − r )x + r y Genetic algorithms and evolutionary programming

Introduction Algorithm Examples Conclusions

Basic algorithm Data representation Selection Reproduction

Mutation

I I

let xi ∈ A be the gene of an individual that is to be mutated binary gene: binary mutation I

I

discrete or continuous bounded A: uniform mutation I

I

xi0 := 1 − xi set xi0 to be a uniformly randomly chosen element of A

also possible: non-uniform mutation I

needs fixed distribution for element choice

Theis

Genetic algorithms and evolutionary programming

Introduction Algorithm Examples Conclusions

Basic algorithm Data representation Selection Reproduction

Mutation

I I

let xi ∈ A be the gene of an individual that is to be mutated binary gene: binary mutation I

I

discrete or continuous bounded A: uniform mutation I

I

xi0 := 1 − xi set xi0 to be a uniformly randomly chosen element of A

also possible: non-uniform mutation I

needs fixed distribution for element choice

Theis

Genetic algorithms and evolutionary programming

Introduction Algorithm Examples Conclusions

Basic algorithm Data representation Selection Reproduction

Mutation

I I

let xi ∈ A be the gene of an individual that is to be mutated binary gene: binary mutation I

I

discrete or continuous bounded A: uniform mutation I

I

xi0 := 1 − xi set xi0 to be a uniformly randomly chosen element of A

also possible: non-uniform mutation I

needs fixed distribution for element choice

Theis

Genetic algorithms and evolutionary programming

Introduction Algorithm Examples Conclusions

Basic algorithm Data representation Selection Reproduction

Mutation

I I

let xi ∈ A be the gene of an individual that is to be mutated binary gene: binary mutation I

I

discrete or continuous bounded A: uniform mutation I

I

xi0 := 1 − xi set xi0 to be a uniformly randomly chosen element of A

also possible: non-uniform mutation I

needs fixed distribution for element choice

Theis

Genetic algorithms and evolutionary programming

Introduction Algorithm Examples Conclusions

Basic algorithm Data representation Selection Reproduction

One generation example

Theis

Genetic algorithms and evolutionary programming

Introduction Algorithm Examples Conclusions

2d-function optimization Genetic Mastermind Hyerplane detection

Algorithm

Selection Reproduction

Introduction Reinforcement learning Imitate nature Genetic algorithms

Examples 2d-function optimization Genetic Mastermind Hyerplane detection

Algorithm Basic algorithm Data representation

Conclusions

Theis

Genetic algorithms and evolutionary programming

Introduction Algorithm Examples Conclusions

2d-function optimization Genetic Mastermind Hyerplane detection

Examples

I

continuous example I

I

binary example I I

I

global optimization of continuous function f : [a, b] → R genetic Mastermind select optimal guess using GA

example from our research I

I I

perform overcomplete blind source separation by sparse component analysis key problem: hyperplane detection solution: optimize cost function using GAs

Theis

Genetic algorithms and evolutionary programming

Introduction Algorithm Examples Conclusions

2d-function optimization Genetic Mastermind Hyerplane detection

Examples

I

continuous example I

I

binary example I I

I

global optimization of continuous function f : [a, b] → R genetic Mastermind select optimal guess using GA

example from our research I

I I

perform overcomplete blind source separation by sparse component analysis key problem: hyperplane detection solution: optimize cost function using GAs

Theis

Genetic algorithms and evolutionary programming

Introduction Algorithm Examples Conclusions

2d-function optimization Genetic Mastermind Hyerplane detection

Examples

I

continuous example I

I

binary example I I

I

global optimization of continuous function f : [a, b] → R genetic Mastermind select optimal guess using GA

example from our research I

I I

perform overcomplete blind source separation by sparse component analysis key problem: hyperplane detection solution: optimize cost function using GAs

Theis

Genetic algorithms and evolutionary programming

Introduction Algorithm Examples Conclusions

2d-function optimization Genetic Mastermind Hyerplane detection

2d-function optimization multipeak 50

50 45

45

40 35 40

30 25

35

20 30

15 10

25

5

−10

−8

−6

−4

−2

0 x

2

4

6

8

10

f

20

0

10

20

30

40

50

60

70

80

90

100

performance (optimal individual and mean)

Theis

Genetic algorithms and evolutionary programming

Introduction Algorithm Examples Conclusions

2d-function optimization Genetic Mastermind Hyerplane detection

Genetic Mastermind

Theis

Genetic algorithms and evolutionary programming

Introduction Algorithm Examples Conclusions

2d-function optimization Genetic Mastermind Hyerplane detection

Hyerplane detection

1

1 0.5

0.5

0 0

−0.5 1

−1 1 0.5

−0.5

1

−1 −1

0.5 0

0.5 0

−0.5

0

0

−0.5

−0.5

−0.5

0.5

−1

−1

1

−1

I

perform overcomplete blind source separation by sparse component analysis Georgiev et al. [2004], Theis et al. [2004]

I

key problem: hyperplane detection

I

solution: optimize cost function using GAs

Theis

Genetic algorithms and evolutionary programming

Introduction Algorithm Examples Conclusions

Algorithm

Selection Reproduction

Introduction Reinforcement learning Imitate nature Genetic algorithms

Examples 2d-function optimization Genetic Mastermind Hyerplane detection

Algorithm Basic algorithm Data representation

Conclusions

Theis

Genetic algorithms and evolutionary programming

Introduction Algorithm Examples Conclusions

Conclusions

I

genetic algorithms perform global optimization

I

they mimic nature by letting a population evolve according to their fitness algorithm

I

I I

I

selection reproduction: by crossover and mutation

simple applicability in real-world situations

Theis

Genetic algorithms and evolutionary programming

Introduction Algorithm Examples Conclusions

I

I

I

1 2

Resources I books: Goldberg [1989], Sch¨oneburg et al. [1994] I Matlab GA optimization toolbox: http://www.ie.ncsu.edu/ mirage/GAToolBox/gaot Details and papers on my website http://fabian.theis.name This research was supported by the DFG1 and BMBF2 .

I

References P. Georgiev, F. Theis, and A. Cichocki. Sparse component analysis and blind source separation of underdetermined mixtures. IEEE Trans. on Neural Networks in print, 2004. D. Goldberg. Genetic Algorithms in Search Optimization and Machine Learning. Addison Wesley Publishing, 1989. E. Sch¨ oneburg, F. Heinzmann, and S. Feddersen. Genetische Algorithmen und Evolutionsstrategien. Addison Wesley Publishing, 1994. F. Theis, P. Georgiev, and A. Cichocki. Robust overcomplete matrix recovery for sparse sources using a generalized hough transform. In Proc. ESANN 2004, pages 343–348, Bruges, Belgium, 2004. d-side, Evere, Belgium.

graduate college: Nonlinearity and Nonequilibrium in Condensed Matter project ’ModKog’ Theis

Genetic algorithms and evolutionary programming