Page 373 - Numerical Methods for Chemical Engineering

362 7 Probability theory and stochastic simulation

2
1
2
−1
−2 a
− in
−
−
−
1
Figure 7.15 Partial trajectory of a simulated annealing run of a cost function with multiple minima.

Figure 7.15 shows the contour plot of this cost function, overlaid with the trajectory of the
(1)
simulation (not all points are shown). The simulation was started at ˜x , a local minimum
but not the global minimum, at which any of the deterministic optimization methods of
Chapter 5 terminate immediately. Eventually, the stochastic simulation is able to overcome
the barrier to settle finally at the global minimum. We see also that the irregular shape of
the cost function surface near the partition between points closest to ˜x (1) and those nearest
to ˜x (2) does not pose a significant problem but would for the deterministic algorithms of
Chapter 5. The program sim-anneal-ext.m generates a movie showing the progress of
simulated annealing for a 1-D cost function with multiple local minima.

Genetic programming

We mention here another method, genetic programming, to identify global minima. While
simulated annealing is based on an analogy from physics, genetic algorithms take their
inspiration from biology. The general idea is to let an initial guess of the parameter vector
evolve to improve the cost function in a manner that mimics natural selection. At each
generation of the evolutionary process, there are n p members of the population, but only
the “best” n s < n p survive to the next generation. In contrast to simulated annealing, at
each iteration, the best population member is at least as good as the initial guess, so this
algorithm is popular for those wishing merely to improve a design and not necessarily to
obtain the optimum. Genetic algorithms are easily adapted to problems with discrete-valued
parameters, although the method is presented here for a continuous parameter vector.
[1]
First, we start the calculation with some initial first member x . From this guess, the
generation is filled by creating new members through a combined process of single-member
mutation and dual-member crossing. For each k = 2, 3,..., n p , we add a new member