loss of generality, that the problem requires maximization of R. Also, let a simple genetic
algorithm designed to execute on this problem have fixed population size M, let i e S be
interpreted as an unsigned integer (0 < i < 2L 1), and let a generation be represented by
m = (m(0), m(l), m(2L- 1)) where m(i) = the number of occurrences of solution i e S
in the population. Thus, in the parlance of combinatorial mathematics, m is a distribution
of M nondistinct objects over N = card(S) = 2L bins [Hall67, Rior58], and the set of all
such distributions, S' = {m}, is a suitable representation of the simple genetic algorithm
search space. The cardinality of S' is given by
N' =card(S')= M+2L1=M+N -1. Eq. 4.1
M M
Since both N and M are finite, so is N'.
Then, if mo e S' is selected as an initial population, the simple genetic algorithm
can be represented by the quadruple (S',mo, P, F) where PQ is a state transition matrix
(analogous to PT of the simulated annealing model) and F = {QJ is a finite length
sequence of parameter vectors Qk = (Pm(k), pc(k)). The algorithm parameters pm(k) and
pc(k) are respectively the mutation and crossover probabilities. In the following sections,
the mutation probability sequence is employed in a role analogous to absolute tempera-
ture in simulated annealing, and consideration is limited hereafter to monotone nonin-
creasing sequences. In general, the only limitation on the crossover probability sequence
is that its values are probabilities. However, in all of the following, consideration is
limited to constant crossover probability sequences.
The first parameter vector in F is Q0 and the final parameter vector is Q,. The solu-
tion evolves as a sequence {ink} of states mk e S' in which the conditional dependence of
mk+i on the sequence history is equivalent to its conditional dependence on in,, and thus
the solution sequence is a Markov chain. In general, the chain is inhomogeneous (Defini-
tion A5). In Section 4.3 it is shown to be time-homogeneous if the parameter vectors are
constant. As with the simulated annealing algorithm model, exhausting the sequence of