GA without Phenotype as Recursive Function

There are different possibilities how to describe the essential structures and properties of a genetic algorithm. Here we are looking to GAs as a recursive procedure.

Again we assume the maximal population

as a set of all possible strings of length

over an alphabet $\Sigma$ as $P = \Sigma^{n}$ , with $\vert P\vert = \vert\Sigma\vert^{n}$ . The working set

is a subset of

as $P' \subseteq P$ . The fitness function $fit: P \longmapsto F$ maps all elements of the set

into a set

of fitness values. We assume $\vert F\vert > 1$ , otherwise no discrimination would be possible (and then also no learning). We assume further that the 'goal' of an optimization process is not the 'complete' set

but some real subset $F^{+} \subset F$ where all values $f \in F^{+}$ are bigger than some threshold $\theta$ . Complementary we have the set $P^{+}$ as those elements of

whose fitness values are all in the goal-set $F^{+}$ , written as $FIT(P^{+}) = F^{+}$ or $P^{+} = \{x\vert x \in P \& fit(x) > \theta\}$ .

If we assume $f^{+} \in F^{+} \& f^{+} = upper(F^{+})$ as the maximal fitness value in $F^{+}$ and $f^{-} \in F^{+} \& f^{-} = lower(F^{+})$ as the lowest value in $F^{+}$ then we can define a 'fuzzy' goal for a genetic process: with $MAXFIT(P') = \vert P'\vert \times f^{+}$ and $MINFIT(P') = \vert P'\vert \times f^{-}$ we can define a 'goal region' like $MINFIT(P') \leq Goal(P') \leq MAXFIT(P')$ .

With these definitions one can classify the history of of genetic process with terms like approaching or not approaching the goal. In both cases - approaching or not-approaching - one can introduce additional classifications like monotone or not-monotone. The non-monotone case can further be subdivided into periodic or a-periodic, which is the same as random.

Additionally to this overall categories one can measure the velocity of an approach based on the numbers of cycles used for approaching the goal state.

Depending of the resulting classification one can then investigate which properties of the genetic algorithm are responsible for this behavior.

In the literature one can find thoughts about the convergence of a series of populations generated by a GA (cf. e.g. Ankenbrandt 1991 [3], Rylander et.al 2001 [318], Langdon and Poli 2002 [226], and Fogel 2006 [103]. Ankenbrandt presents the convergence problem in an algorithmic format (cf. [3]:54)).

The main driver of a genetic process is the overall genetic function

. This function is a concatenated function. The most usual 'format' of a genetic function

is as follows:

$\displaystyle ga(P'_{t})$	$\displaystyle =$	$\displaystyle fit(P'_{t}) \otimes sel(P''_{t}) \otimes cross(P'''_{t}) \otimes mut(P''''_{t})$	(5.1)
$\displaystyle fit$	$\displaystyle :$	$\displaystyle P'_{t} \times VAL^{<} \longmapsto P''_{t}$	(5.2)
$\displaystyle sel$	$\displaystyle :$	$\displaystyle P''_{t} \longmapsto P'''_{t}$	(5.3)
$\displaystyle cross$	$\displaystyle :$	$\displaystyle P'''_{t} \longmapsto P''''(t)$	(5.4)
$\displaystyle mut$	$\displaystyle :$	$\displaystyle P''''_{t} \longmapsto P'''''_{t}$	(5.5)

Every genetic operator {fit, sel, cross, mut} occurs in the literature with many variants. Thus one has to give the explicit definitions every time one is using one of these variants.

Furthermore different configurations of these operators are possible. Some of these are listed here.

$\displaystyle gaBase(P'_{t})$	$\displaystyle =$	$\displaystyle fit(P'_{t}) \otimes sel(P''_{t})$	(5.6)
$\displaystyle gaBaseCr(P'_{t})$	$\displaystyle =$	$\displaystyle fit(P'_{t}) \otimes sel(P''_{t}) \otimes cross(P'''_{t})$	(5.7)
$\displaystyle gaBaseMu(P'_{t})$	$\displaystyle =$	$\displaystyle fit(P'_{t}) \otimes sel(P''_{t}) \otimes mut(P'''_{t})$	(5.8)
$\displaystyle gaMuCr(P'_{t})$	$\displaystyle =$	$\displaystyle fit(P'_{t}) \otimes sel(P''_{t}) \otimes mut(P'''_{t}) \otimes cross(P''''_{t})$	(5.9)
$\displaystyle gaCrMu(P'_{t})$	$\displaystyle =$	$\displaystyle fit(P'_{t}) \otimes sel(P''_{t}) \otimes cross(P'''_{t}) \otimes mut(P''''_{t})$	(5.10)

If these different configurations have 'real' effects then one can measure these effects and one can compare the behavior directly. For these measurements one can use the terms introduced above.