Lecture

• let's make it interactive!
• new slides! (remade)
  • though the old slides are good enough

Introduction

• population-based stochastic search
• two principles: variation + selection
• population of solutions, not just one solution
  • opposed to NNs – gradient descent maintains only one solution
• search … finding a candidate satisfying some requirements
• optimization … we have some objective function $f(x)$
• learning … use observations to improve future decisions
• 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
• “searching without knowing where to go”
• example: airfoil (wing profile) optimization
• in the second semester, we'll discuss how the search algorithms can adapt (learn)
• 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
• Gregor Mendel
  • experiments on plant hybridization
  • “we're not mixing, we're transferring discrete units of information”
• genes
  • human genome has 0.8 GB (fits on a CD)
• genotype vs. fenotype
  • variation works on the genotype
  • evaluation is performed on the fenotype
• diploidy … organisms often carry two chromosome sets (one from each parent)
  • there's no good implementation in evolutionary algorithms yet
• evolutionary cycle
  • current population $P_t$
  • parent selection
  • variation – generates new candidates
  • evaluation
  • survivor selection
  • next population $P_{t+1}$
• notation
  • $\mu$ … number of individuals in a population
  • $\lambda$ … number of offspring
• objective value is not always the fitness
• selection pressure
  • how strongly the differences in fitness affect the parent selection
  • “does everyone mate with the best individual?”
• who survives?
  • do we kill the parents?
  • generational replacement × overlapping replacement
  • elitist replacement – we keep the best-so-far solution
• composition of the population serves as the memory of the search
  • it may be useful to keep it diverse
• the step from one to the next generation is stochastic
• 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)
• 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
• 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)
• computational cost
• when is evolution attractive?
  • awkward search space
  • black-box evaluation
  • we want more than one optimum
• sometimes, we can combine evolution with other approaches

Genetic Algorithms

• simple genetic algorithm
  • representation: fixed-length bit string
  • variation: one-point crossover + bit mutation
  • survivor selection: generational replacement (we kill the parents)
• John Holland
  • studied the adaptation in natural and artificial systems
  • introduced the simple genetic algorithm
• chromosome
  • locus … position $i$ in the chromosome
  • allele … the value $x_i\in\set{0,1}$ at that locus
  • chromosome/genotype … the complete string
• 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
• uniform crossover
  • does it make sense?
  • is there any linkage between alleles? → we should use one-point crossover
• 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