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]\}$.
- 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.
- 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.
- 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.
- 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