Franz J. Vesely > CompPhys Tutorial > Stochastics  

< >
Ch. 3 Sec. 4

3.4 Stochastic Optimization

Finding the global extremum of a function of many variables:
- Nonlinear fit to a set of table values
- improvement of complex electronic circuits ("travelling salesman problem")
- find the most stable (i. e. lowest energy) configuration of microclusters or biopolymers.
- $\dots$

Two methods:

3.4.1 Simulated Annealing

Consider a Metropolis walk through the space of "states" $x_{\alpha}$ with

$ \begin{eqnarray} p_{\alpha} &=& A \exp{- \beta U(x)} \end{eqnarray} $

where $U(x_{1},\dots x_{M})$ is a "cost function" to be minimized, and $\beta$ a tunable parameter (a reciprocal "temperature".)

- Low $\beta$ $\Longrightarrow$ smaller variation of $p_{\alpha}$; higher $U(x)$ are accessible

- High $\beta$ $\Longrightarrow$ $x$ will tend to go "downhill"

Simulated Annealing:

Do a Monte Carlo walk according to the following rules:
  • Draw a starting vector $x^{0}\equiv \{x_{1}^{0},\dots x_{M}^{0} \}$ at random, and choose a high initial "temperature" $kT$.

  • Carefully lower the temperature: $\Longrightarrow$ regions with lower $U(x)$ will be visited more frequently than the higher ranges.

  • Finally, for $kT \rightarrow 0$ the system point will come to rest in a minimum that very probably (not with certainty!) will be the global minimum.

EXERCISE: (See also here)
Create (yes, fake!) a table of "measured values with errors" according to

$ y_{i}=f(x_{i};c_{1},\dots c_{6})+\xi_{i},\;\;\; i=1,20 $

with $\xi_{i}$ coming from a Gauss distribution with suitable variance, and with the function $f$ defined by

$ f(x;c)\equiv c_{1}e^{\textstyle - c_{2}(x-c_{3})^{2}} +c_{4}e^{\textstyle - c_{5}(x-c_{6})^{2}} $

($c_{1} \dots c_{6}$ being a set of arbitrary coefficients).

Using these data, try to reconstruct the parameters $c_{1}\dots c_{6}$ by fitting the theoretical function $f$ to the table points $(x_{i},y_{i})$. The cost function is

$ U(c)\equiv \sum \limits_{i}\left[ y_{i}-f(x_{i};c)\right]^{2} $

Choose an initial vector $c^{0}$ and perform an MC random walk through $ c$-space, slowly lowering the temperature.

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

Here is a simple procedure that mimicks evolution to find the minimum of a function:

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 \}$, where $N$ will be 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: (See also here)
Apply the simple genetic algorithm to find the minimum of the function $[2sin(10x-1)]^{2}+10(x-1)^{2}$ within the interval $[0,2]$.

vesely 2005-10-10

< >