next up previous
Next: II. Differential Equations Everywhere Up: 3.4 Stochastic Optimization Previous: 3.4.1 Simulated Annealing


3.4.2 Genetic Algorithms

Evolution of biological systems:
- Adaptation of species to external conditions: optimization

- Adaptation strategy itself has evolved over time: sexual reproduction



$\Longrightarrow$More sex:

Consider some oscillatory function $f(x)$ of a single variable, having one global minimum within the range of definition, $x \epsilon [a,b]$. Find $x^{*}$ with $f(x^{*}) = min \{f(x), \, x \epsilon [a,b]\}$.
  1. Start with a population of randomly chosen numbers (individuals), $\{x_{i}^{0} \epsilon [a,b],$ $i=1, \dots N \}$. ($N$ is kept constant.)
    - ``Gene'': bit string of $x_{i}^{0}$
    - ``Fitness'': low $f_{i} \equiv f(x_{i}^{0})$ = high fitness and vice versa
    - Relative fitness (probability of reproduction): $p_{i} \equiv f_{i}/\sum_{i=1}^{N}f_{i}$. This is a probability density, and $P(x_{i}) \equiv P_{i} \equiv \sum_{j=1}^{i}p_{j}$ is its cumulative distribution function.
  2. Draw $N$ individuals in accordance with their reproduction probability (Transformation method!).

    The new population $\{x_{i}', \,$ $i=1, \dots N \}$ is fitter than the original one. However, thus far we have remained at the level of primitive selective reproduction without mutation or sexual crossover.
  3. Pick pairs of individuals at random and submit their genetic strings are to crossover:
    () Draw a position $m$ within the bit strings; () swap the bits following $m$ between the two strings. The number of such pairings, the ``crossover rate'', should be around $0.6 \, N$. The resulting set $\{x_{i}'', \,$ $i=1, \dots N \}$ is called the offspring population.
  4. Finally, mutation comes into play: within each string $x_{i}''$ every single bit is reversed with a probability $p_{mut} \approx 0.01$.

    The resulting population is regarded as the next generation, $\{x_{i}^{1}, \,$ $i=1, \dots N \}$, and we are back at step 2.



EXERCISE: Apply the simple genetic algorithm to find the minimum of the function $[2\,sin(10\,x-1)]^{2}+10\,(x-1)^{2}$ within the interval $[0,2]$.

next up previous
Next: II. Differential Equations Everywhere Up: 3.4 Stochastic Optimization Previous: 3.4.1 Simulated Annealing
Franz J. Vesely Oct 2005
See also:
"Computational Physics - An Introduction," Kluwer-Plenum 2001