Page 374 - Numerical Methods for Chemical Engineering

Genetic programming 363

x [k] to the population. We define two probabilities: α m , the probability that x [k] will be
created by a mutation, and α c , the probability that it will be created by crossing. These
two probabilities must sum to 1. Here, we only present one type each of mutation and
crossing, but more complicated combinations of random offspring production are used in
practice.
[k]
To decide which process to use to add x , we generate a random number u k , uniformly
distributed on [0,1]. If u k ≤ α m , we generate x [k] by selecting at random some previous
[j]
member of the population x , with j < k, and mutating it. A simple mutation is to displace
each component randomly:

x [k] ← x [ j] (7.266)
m m + σ m g m
g m is a random number normally distributed with a standard deviation of 1 and σ m is the
standard deviation for the displacement of x m . We choose a normally distributed random
variable so that there is a finite probability of selecting even large displacements. If we
have components that take on a discrete number of values, a common mutation is to select
one discrete component randomly and to give it a new value at random from among the
possibilities.
If u k >α m and k > 2, we generate x [k] by a random crossing of two previous members
of the population. We select at random some j < k and l < k to serve as “parents.” One
simple way to perform the crossing is to select at random for each component the value of
one parent or the other:
[ j]

x m , if u ≤ 0.5
[k]
m
x m = [l] (7.267)

x m , if u > 0.5
m
Such a crossing generates a new offspring member that may be in a significantly different
region of phase space than either of the parents. This allows the genetic algorithm to take
large steps in parameter space, thus aiding the search for the global minimum.
Once a generation is filled completely, the selection of members that survive to the next
generation begins. We order the population by increasing values of the cost function F(x),
or equivalently by decreasing order of the fitness, −F(x). The best members are found at
the beginning of this list. We want to select some sub population of n s < n p survivors that
will be passed to the next generation; however, it would be a mistake to take merely the first
n s members of the list. As in biology, in-breeding is to be avoided, so before we accept a
new member as a survivor, we ensure that it is not too similar to one previously accepted.
For some positive-definite metric matrix , we define the squared distance between two
members as
2

d ≡ x [k] − x [ j] · x [k] − x [ j] (7.268)
kj
When considering a member x [k] for admittance into the set of survivors, we check to see
2
[ j]
whether for all previously identified survivors x , d ≥ d 2 . Only if x [k] is sufficiently
kj min
differentfromalloftheprevioussurvivorswillitbeaccepted.Ifwecannotfindn s sufficiently
diverse survivors, we move on to the next generation with less than n s , as propagating two
nearly identical members does little good.