Lecture: kartičky | evolutionary-algorithms1

new slides! (remade)

though the old slides are good enough

Introduction

population of solutions, not just one solution

opposed to NNs – gradient descent maintains only one solution

Introduction

black-box optimization

we only need to tell good and bad solutions apart
we don't need to know the structure of $f(x)$ , it can be very general

Introduction

Charles Darwin

theory of natural selection
there are some hereditary traits, there is some variation
× Lamarck theory
- individuals improve in their lifetime
- faster convergence, higher risk of getting stuck in local optima

Introduction

Gregor Mendel

experiments on plant hybridization
“we're not mixing, we're transferring discrete units of information”

Introduction

genes

human genome has 0.8 GB (fits on a CD)

Introduction

genotype vs. fenotype

variation works on the genotype
evaluation is performed on the fenotype

Introduction

diploidy … organisms often carry two chromosome sets (one from each parent)

there's no good implementation in evolutionary algorithms yet

Introduction

evolutionary cycle

current population $P_t$
parent selection
variation – generates new candidates
evaluation
survivor selection
next population $P_{t+1}$

Introduction

notation

$\mu$ … number of individuals in a population
$\lambda$ … number of offspring

Introduction

selection pressure

how strongly the differences in fitness affect the parent selection
“does everyone mate with the best individual?”

Introduction

who survives?

do we kill the parents?
generational replacement × overlapping replacement
elitist replacement – we keep the best-so-far solution

Introduction

composition of the population serves as the memory of the search

it may be useful to keep it diverse

Introduction

genetic drift

some change in the population may be caused just by the stochasticity of the process (not by the differences in fitness)
because of the finite sampling (we don't have infinitely many individuals)

Introduction

how to represent the genotype (and how to mutate/combine)

bit string → flip bits
real vector → perturb coordinates
permutation → swap/reorder
tree / program → change structure

Introduction

representation affects how the neighborhood looks like

standard binary vs. Gray code
in standard binary encoding, a single bit flip may easily change the order of the number (for Gray code, it does not happen that easily)

Introduction

when is evolution attractive?

awkward search space
black-box evaluation
we want more than one optimum

Genetic Algorithms

simple genetic algorithm

representation: fixed-length bit string
variation: one-point crossover + bit mutation
survivor selection: generational replacement (we kill the parents)

Genetic Algorithms

John Holland

studied the adaptation in natural and artificial systems
introduced the simple genetic algorithm

Genetic Algorithms

chromosome

locus … position $i$ in the chromosome
allele … the value $x_i\in\set{0,1}$ at that locus
chromosome/genotype … the complete string

Genetic Algorithms

selection

roulette-wheel selection
in the real-world problems, we may need to somehow transform the objective value to get a useful fitness function
we can use ranking-based selection
- tournament selection

Genetic Algorithms

uniform crossover

does it make sense?
is there any linkage between alleles? → we should use one-point crossover

Genetic Algorithms

schema theory

it's been over-dramatized :)
schema describes a family of strings
important: to evaluate a fitness of a schema, we only consider only the individuals in the population
schema → building blocks
schema theorem does not prove that…
- a GA converges to the global optimum
- useful building blocks exist
- crossover is generally superior to mutation