Genetic Algorithms

Bold textGenetic Algorithms

1. Genetic algorithms (GAs): basic form

A generic GA (also known as an evolutionary algorithm [EA]) assumes a discrete search space H and a function

                                                                                            \[f:H\to\mathbb{R}\],

where H is a subset of the Euclidean space\[\mathbb{R}\].

The general problem is to find

                                                         \[\arg\underset{X\in H}{\mathop{\min }}\,f\]

where X is avector of the decision variables and f is the objective function.

With GAs it is customary to distinguish genotype–the encoded representation of the variables–from phenotype–the set of variables themselves. The vector X is represented by a string (or chromosome) s of length l madeup of symbols drawn from an alphabet A using the mapping

                                                         \[c:{{A}^{l}}\to H\]

The mapping c is not necessarily surjective. The range of c determine the subset of Al available for exploration by a GA. The range of c, Ξ

                                                         \[\Xi\subseteq {{A}^{l}}\]

is needed to account for the fact that some strings in the image Al under c may represent invalid solutions to the original problem.

The string length l depends on the dimensions of both H and A, with the elements of the string corresponding to genes and the values to alleles. This statement of genes and alleles is often referred to as genotype-phenotype mapping.

Given the statements above, the optimization becomes:

                                                \[\arg\underset{S\in L}{\mathop{\min g}}\,\],

given the function

                                                 \[g(s)=f(c(s))\].

Finally, with GAs it is helpful if c is a bijection. The important property of bijections as they apply to GAs is that bijections have an inverse, i.e., there is a unique vector x for every string and a unique string for each x.

2. Genetic algorithms and their operator

The operators by which GAs search for the optimal solution are set out in following adapted from Coello et al. (Coello, 2002):

Let H be a nonempty set (the individual or search space), u i i∈N a sequence in Z + (the parent populations), u ′ (i) i∈N a sequence in Z + (the offspring population sizes), ϕ:H→R a fitness function, t:∪ ∞ i=1 (H u ) (i) →{true,false} (the termination criteria), χ∈{true,false} , r a sequence r (i) of recombination operators τ (i) :X (i) r →T(Ω (i) r ,T,H u (i) ,H u ′ (i) ) , m a sequence of {m (i) } of mutation operators in m i , X (i) m →T(Ω (i) m ,T,H u (i) ,H u ′ (i) ) , s a sequence of {s i } selection operators s (i) :X (i) s ×T(H,R)→T(Ω (i) s ,T((H u ′ (i)+χμ (i) ),H μ (i+1) )),Θ (i) r ∈X (i) r (the recombination parameters), Θ (i) m ∈X (i) m (the mutation parameters), and Θ (i) s ∈X (i) s (the selection parameters).

Define the collection μ (the number of individuals) via Hμ. The population transforms are denoted by

                                             \[T:{{H}^{\mu }}\to {{H}^{\mu }}\]

where

                                             \[\mu \in \mathbb{N}\]

Some GA methods generate populations whose size not equal to their predecessors’. In a more general framework

                                             \[T:{{H}^{\mu}}\to {{H}^{{{\mu }'}}}\]

can accommodate populations that contain the same or different individuals. This mapping has the ability to represent all population sizes, genetic operators, and parameters as sequences.

The execution of a GA typically begins by randomly sampling with replacement from Al. The resulting collection is the initial population, denoted by P(0). In general, a population is a collection \[P=({{a}_{1}},{{a}_{2}},...,{{a}_{\mu }})\]of individuals, where\[{{a}_{i}}\in {{A}^{l}}\], and populations are treated as n-tuples of individuals. The number of individuals (μ) is defined as the population size.

Using the work of Lamont and Merkle (Lamont, 1997) we can describe in greater detail the termination criteria and the other genetic operators (GOs).

Since H is a nonempty set,\[c:{{A}^{l}}\to H\], and\[f:H\to \mathbb{R}\], the fitness scaling function can be defined as \[{{T}_{s}}:\mathbb{R}\to \mathbb{R}\]and a related fitness function as\[\Phi \triangleq {{T}_{s}}\circ f\circ c\]. In this definition it is understood that the objective function f is determined by the application, while the specification of the decoding function c[1] and the fitness scaling function Ts are design issues.

Following initialization, execution proceeds iteratively. Each iteration consists of an application of one or more GOs. The combined effect of the GOs applied in a particular generation $t\in N$ is to transform the current population P(t) into a new population P(t+1).

In the population transformation $\mu ,{\mu}'\ in {{\mathbb{Z}}^{+}}$(the parent and offspring population sizes, respectively). A mapping $T:{{H}^{\mu }}\ to {{H}^{{{\mu }'}}}$ is called a population transformation (PT). If$T(P)={P}'$, then P is a parent population and P/ is the offspring population. If$\mu ={\mu }'$, then it is called simply the population size.

The PT resulting from an GO often depends on the outcome of a random experiment. This result is referred to as a random population transformation (RPT or random PT). To define RPT, let $\mu \in {{\mathbb{Z}}^{+}}$and $\Omega $ be a set (the sample space). A random function $R:\Omega \to T({{H}^{\mu }},\bigcup\limits_{{\mu }'\ in {{\mathbb{Z}}^{+}}}^{{}}{{{H}^{{{\mu }'}}}})$ is called an RPT. The distribution of PTs resulting from the application of a GO depends on the operator parameters; in other words, a GO maps its parameters to an RPT.

Now that both the fitness function and RPT have been defined, the GO can be defined in general: let$\mu \in {{\mathbb{Z}}^{+}}$, X be a set (the parameter space) and $\Omega $ a set. The mapping $\Zeta :X\to T\left( \Omega ,T\left[ {{H}^{\mu }},\bigcup\limits_{{\mu }'\in {{\mathbb{Z}}^{+}}}^{{}}{{{H}^{{{\mu}'}}}} \right] \right)$ is a GO. The set of GOs is denoted as $GOP\left( H,\mu ,X,\Omega \right)$.

[1] Remember that if the domain of c is total, i.e., the domain of c is all of A I,c is called a decoding function. The mapping of c isnot necessarily surjective. The range of c determines the subset of Alavailable forexploration by the evolutionary algorithm.