Genetic Algorithms

Bold textGenetic Algorithms

1. Genetic algorithms (GAs): basic form

A generic GA (aka evolutionary algorithm [EA]) assumes a discrete search space H and a function

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

where H is a subsetof 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 variablesthemselves. The vector X isrepresented by a string (or chromosome) s of length l madeup of symbols drawn from an alphabet Ausing the mapping

                                         \[c:{{A}^{l}}\toH\].

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}}\]

isneeded 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 thedimensions of both H and A, with the elements of the string corresponding to genes and the valuesto 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 applyto GAs is that bijections have an inverse, i.e., there is a unique vector x for every string and a unique stringfor each x. 1. Genetic algorithms and their operators The following statementsabout the operators of Gas is adopted from Coello et al. (Coello, 2002). · Let H be a nonempty set (the individual orsearch space), $${{\left\{ {{u}^{i}} \right\}}_{i\in \mathbb{N}}}$$ asequence in $${{\mathbb{Z}}^{+}}$$ (the parent populations), · $${{\left\{ {{u}^{'(i)}} \right\}}_{i\in\mathbb{N}}}$$ a sequence in $${{\mathbb{Z}}^{+}}$$ (the offspring populationsizes) · $$\phi :H\to \mathbb{R}$$ a fitness function, $$\iota:\cup _{i=1}^{\infty }{{({{H}^{u}})}^{(i)}}\to$$ {true, false} (thetermination criteria) · $$\chi \in$$ {true, false}, r a sequence $$\left\{ {{r}^{(i)}} \right\}$$ of recombinationoperators τ(i) : $$X_{r}^{(i)}\toT(\Omega _{r}^{(i)} · m asequence of {m(i)} ofmutation operators in mi · \[X_{m}^{(i)}\to T(\Omega _{m}^{(i)},T\left({{H}^{{{u}^{(i)}}}},{{H}^{u{{'}^{(i)}}}} \right))$$ , s a sequence of {si}selection operators s(i) · $$X_{s}^{(i)}\times T(H,\mathbb{R})\to T(\Omega_{s}^{(i)},T(({{H}^{u{{'}^{(i)+\chi {{\mu }^{(i)}}}}}}),{{H}^{{{\mu}^{(i+1)}}}}))$$ , $$\Theta _{r}^{(i)}\in X_{r}^{(i)}$$ (the recombinationparameters) · $$\Theta _{m}^{(i)}\in X_{m}^{(i)}$$ (themutation parameters) · $$\Theta _{s}^{(i)}\in X_{s}^{(i)}$$ (theselection parameters)

Coello et al. define the collection μ (thenumber of individuals) via Hμ.The population transforms are denoted by $$T:{{H}^{\mu }}\to {{H}^{\mu }}$$ ,where $$\mu \in \mathbb{N}$$ . However, some GA methods generate populationswhose size is not equal to their predecessors’. In a more general framework $$T:{{H}^{\mu}}\to {{H}^{{{\mu }'}}}$$ can accommodate populations that contain the same ordifferent individuals. This mapping has the ability to represent all populationsizes, evolutionary operators, and parameters as sequences.