Namespaces
Variants
Actions

Difference between revisions of "Genetic Algorithms"

From Encyclopedia of Mathematics
Jump to: navigation, search
(a lot better TeX)
 
(112 intermediate revisions by 3 users not shown)
Line 1: Line 1:
'''Bold text Genetic Algorithms'''
+
{{TEX|done}}
 +
{{MSC|90C99,60H25,68Q87}}
  
 +
$\newcommand{\argmin}[1]{\operatorname{argmin}_{#1}}$
 +
Genetic algorithms (GAs) (also known as evolutionary algorithms [EAs]) assume a discrete search space $H$ and a function $f:H\to \R$.  The general problem is to find $\argmin{x\in H}f$, where $x$ is a vector 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$ made up of symbols drawn from an alphabet $A$ using the mapping $c:A^l\to H$.  In practice we may need a search space $\Xi\subseteq A^l$ to reflect the fact that some strings in the image  $A^l$ under $c$ may represent invalid solutions to the 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 one of finding $\argmin{S\in L}$, where the function  $g(s)=f(c(s))$.  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$.
  
 +
The execution of an GA typically begins by randomly sampling with replacement from $A^l$. 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 ($\mu$) is defined as the population size.  Following initialization, execution proceeds iteratively.  Each iteration consists of an application of one or more of the genetic operators (GOs): recombination, mutation and selection. 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\Z^+$ (the parent and offspring population sizes, respectively). A mapping $T:H^\mu\to H^{\mu'}$ is called a PT.  If $T(P)=P'$ then $P$ is a parent population and $P'$ is the offspring population.  If $\mu=\mu'$ it is simply the population size.  The PT resulting from a GO often depends on the outcome of a random experiment. In Lamont and Merkel this result is referred to as a random population transformation (RPT or random PT). To define RPT, let $\mu \in \Z^+$and $\Omega $ be a set (the sample space).  A random function $R:\Omega \to T(H^\mu,\bigcup\limits_{\mu'\in\Z^+} H^{\mu'})$ is called a 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.  Since H is a nonempty set where $c:A^l\to H$, and $f:H\to\R$, the fitness scaling function can be defined as $T_s:\R\to\R$ and a related fitness function $\Phi \triangleq T_s\circ f\circ c$. In this definition it is understood that the objective function $f$ is determined by the application.
  
1.       Genetic algorithms (GAs): basic form
+
Now that both the fitness function and RPT have been defined, the GOs can be defined in general: let $\mu \in \Z^+$, $\aleph$ be a set (the parameter space) and $\Omega $ a set (the sample space). The mapping $X:\aleph \to T\left( \Omega ,T\left[ H^\mu,\bigcup\limits_{\mu'\in \Z^+} H^{\mu'} \right] \right)$ is a GO.  The set of GOs is denoted as $GOP( H,\mu ,\aleph ,\Omega)$.  There are three common GOs: recombination, mutation, and selection. These three operators are roughly analogous to their similarly named counterparts in genetics. The application of them in GAs is strictly Darwin-like in nature, i.e., “survival of the fittest.”  In defining the GOs, we will start with recombination.  Let $r\in GOP( H,\mu ,\aleph ,\Omega)$. If there exist $P\in H^\mu$, $\Theta \in \aleph $ and $\omega\in \Omega $ such that one individual in the offspring population $r_\Theta (P)$ depends on more than one individual of $P$ then $r$ is referred to as a recombination operator.  A mutation is defined in the following manner: let $m\in GOP( H,\mu ,\aleph ,\Omega)$. If for every $P\in H^\mu $, for every $\Theta \in X$, for every $\omega \in \Omega $, and if each individual in the offspring population $m_\Theta(P)$ depends on at most one individual of $P$ then $m$ is called a mutation operator.  Finally, for a selection operator let $s\in GOP( H,\mu ,\aleph \times T(H,\R),\Omega ) )$.  If $P\in H^\mu$, $\Theta \in \aleph $, $f:H\to \R $ in all cases, and $s$ satisfies $a\in s_{( \Theta,\Phi)}(P) \Rightarrow a\in P$, then $s$ is a selection operator.
  
  
A generic GA (also known as an evolutionary algorithm [EA]) assumes a discrete search space "'Italic text H" and a function
+
'''References'''
                                                                                                                          \[f:H\to\mathbb{R}\],
 
where H is a subset of the Euclidean space ''Italic text''R.
 
  
 +
[1] Back, T., Evolutionary Algorithms in Theory and Practice, Oxford University Press, 1996
  
The general problem is to find
+
[2] Coello Coello, C.A., Van Veldhuizen, D.A. and Lamont, G.B., Evolutionary Algorithms for Solving Multi-Objective Problems, Kluwer Academic Publishers, 2002
                                                                                        \[\arg\underset{X\in H}{\mathop{\min }}\,f\]
 
  
where ''Italic text''X
+
[3] Goldberg, D.E., Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley Professional, 1989
is a vector of the decision variables and ''Italic text'' 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 ''Italic text'' X  is represented by a string (or chromosome) ''Italic text'' s of length ''Italic text'' l  madeup of symbols drawn from an alphabet ''Italic text'' A using the mapping
+
[4] Holland, J.H., Adaptation in Natural and Artificial Systems, A Bradford Book, 1992
  
                                                                                        \[c:{{A}^{l}}\to H\]
+
[5] Lamont, L. and Merkle, J.D., "A Random Based Framework for Evolutionary Algorithms", in: T. Back, Proceedings of the Seventh International Conference on Genetic Algorithms, 1997.
  
The mapping ''Italic text'' c is not necessarily surjective. The range of ''Italic text'' c determine the subset of ''Italic text''<sup>Superscript text</sup> Al available for exploration by a GA.  The range of ''Italic text'' c, ''Italic text'' Ξ 
+
[6] Surry, Patrick D. and Radcliffe, N.J., "Formal Algorithms + Formal Representations = Search Strategies", Parallel Problem Solving from Nature IV, Springer-Verlag LNCS 1141, pp 366-375, 1996.
 
 
                                                                                        \[\Xi\subseteq {{A}^{l}}\]
 
 
 
is needed to account for the fact that some strings in the image ''Italic text''<sup>Superscript text</sup> Al under ''Italic text'' c may represent invalid solutions to the original problem.
 
 
 
The string length ''Italic text'' l depends on the dimensions of both ''Italic text'' H and ''Italic text''<sup>Superscript text</sup> Al, 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 ''Italic text'' 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 ''Italic text'' x for every string and a unique string for each ''Italic text'' x.
 
 
 
 
 
 
 
2.      Genetic algorithms and their Operators
 
 
 
Let H be a nonempty set (the individual or search space)\[{{\left\{{{u}^{i}} \right\}}_{i\ in \mathbb{N}}}\] a sequence in \[{{\mathbb{Z}}^{+}}\] (the parent populations).  \[{{\left\{ {{u}^{'(i)}} \right\}}_{i\in \mathbb{N}}}\] a sequence in \[{{\mathbb{Z}}^{+}}\](the offspring population sizes), \[\phi:H\to \mathbb{R}\]a fitness function, \[\iota :\cup _{i=1}^{\infty}{{({{H}^{u}})}^{(i)}}\to\]{true,false} (the termination criteria), \[\chi\in\]{true, false}, r a sequence \[\left\{{{r}^{(i)}} \right\}\]
 
 
 
Define the collection ''Italic text''μ (the number of individuals) via <sub>Subscript text</sub>''Italic text''Hμ. The population transforms are denoted by
 
 
 
                                                                            \[T:{{H}^{\mu }}\to {{H}^{\mu }}\]
 
 
 
where \[\mu \in \mathbb{N}\ of recombination operators τ(i) : \[X_{r}^{(i)}\ to T(\Omega _{r}^{(i)},T\left( {{H}^{{{u}^{(i)}}}},{{H}^{u{{'}^{(i)}}}} \right))\], m a sequence of {m(i)} of mutation 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)}\timesT(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 recombination parameters), \[\Theta _{m}^{(i)}\\in X_{m}^{(i)}\] (the mutation parameters), and \[\Theta _{s}^{(i)}\ in X_{s}^{(i)}\] (the selection parameters).
 
 
 
 
 
 
 
Some GA methods generate populations whose size not equal to their predecessors’. The following expression
 
 
 
                                                                            \[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 <sup>Superscript text</sup>''Italic text''
 
Al.  The resulting collection is the initial population, denoted by ''Italic text'' 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 describe the termination criteria and the other genetic operators (GOs).
 
 
 
Since ''Italic text''
 
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 ''Italic text''f is determined by the application, while the specification of the decoding function ''Italic text''c[1] and the fitness scaling function <sup>Subscript text</sup>''Italic text''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 ''Italic text''
 
P(t) into a new population ''Italic text''
 
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 (''Italic text''
 
PT). If $T(P)={P}'$, then ''Italic text''P is a parent population and <sup>Superscript text</sup>''Italic text''P/ is the offspring population. If $\mu ={\mu }'$,then it is called simply the population size.
 
 
 
The ''Italic text''
 
PT resulting from an GO often depends on the outcome of a random experiment. This result is referred to as a random population transformation (''Italic text''RPT or random PT). To define ''Italic text''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 ''Italic text''RPT. The distribution of ''Italic text''PTs resulting from the application of a GO depends on the operator parameters; in other words, a GO maps its parameters to an ''Italic text''RPT.
 
 
 
Now that both the fitness function and ''Italic text''
 
RPT have been defined, the GO can be defined in general once again, this time in more detail: let$\mu \in {{\mathbb{Z}}^{+}}$, ''Italic text''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 $GAOP\left( H,\mu ,X,\Omega  \right)$.
 
 
 
 
 
There are three common GOs: recombination,mutation, and selection. These three operators are roughly analogous to their similarly named counterparts in genetics. The application of them in GAs is strictly Darwin-like in nature, i.e., “survival of the fittest.”
 
 
 
For the recombination operator let $r\in GAOP\left( H,\mu ,X,\Omega  \right)$. If there exists $P\in {{H}^{\mu }},\Theta \in X$, and $\omega \in \Omega $, such that one individual in the offspring population ${{r}_{\Theta }}\left( P \right)$ depends on more than one individual of P,then r is referred to as a recombination operator.
 
 
 
For the mutation operator let $m\in GAOP\left( H,\mu ,X,\Omega\right)$. If for every $P\in {{H}^{\mu }}$, for every $\Theta \in X$, for every $\omega\in \Omega $, and if each individual in the offspring population ${{m}_{\Theta}}\left( P \right)$ depends on at most one individual of P,  then m is called a mutation operator.
 
 
 
Finally, for the selection operator let $s\in EVOP\left( H,\mu ,X\times T\left(H,\mathbb{R}),\Omega  \right) \right)$. If $P\in {{H}^{\mu }}$,$\Theta \in X$,$\Phi :H\to\mathbb{R}$in all cases, and satisfies $a\in {{s}_{\left( \Theta ,\Phi \right)}}(P)\Rightarrow a\in P$, then s is a selection operator.
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
'''Bold text'''Endnotes
 
 
 
[1] 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 is not necessarily surjective. The range of c determines the subset of Al available for exploration by the evolutionary algorithm.
 

Latest revision as of 06:10, 19 April 2013

2020 Mathematics Subject Classification: Primary: 90C99,60H25,68Q87 [MSN][ZBL]

$\newcommand{\argmin}[1]{\operatorname{argmin}_{#1}}$ Genetic algorithms (GAs) (also known as evolutionary algorithms [EAs]) assume a discrete search space $H$ and a function $f:H\to \R$. The general problem is to find $\argmin{x\in H}f$, where $x$ is a vector 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$ made up of symbols drawn from an alphabet $A$ using the mapping $c:A^l\to H$. In practice we may need a search space $\Xi\subseteq A^l$ to reflect the fact that some strings in the image $A^l$ under $c$ may represent invalid solutions to the 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 one of finding $\argmin{S\in L}$, where the function $g(s)=f(c(s))$. 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$.

The execution of an GA typically begins by randomly sampling with replacement from $A^l$. 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 ($\mu$) is defined as the population size. Following initialization, execution proceeds iteratively. Each iteration consists of an application of one or more of the genetic operators (GOs): recombination, mutation and selection. 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\Z^+$ (the parent and offspring population sizes, respectively). A mapping $T:H^\mu\to H^{\mu'}$ is called a PT. If $T(P)=P'$ then $P$ is a parent population and $P'$ is the offspring population. If $\mu=\mu'$ it is simply the population size. The PT resulting from a GO often depends on the outcome of a random experiment. In Lamont and Merkel this result is referred to as a random population transformation (RPT or random PT). To define RPT, let $\mu \in \Z^+$and $\Omega $ be a set (the sample space). A random function $R:\Omega \to T(H^\mu,\bigcup\limits_{\mu'\in\Z^+} H^{\mu'})$ is called a 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. Since H is a nonempty set where $c:A^l\to H$, and $f:H\to\R$, the fitness scaling function can be defined as $T_s:\R\to\R$ and a related fitness function $\Phi \triangleq T_s\circ f\circ c$. In this definition it is understood that the objective function $f$ is determined by the application.

Now that both the fitness function and RPT have been defined, the GOs can be defined in general: let $\mu \in \Z^+$, $\aleph$ be a set (the parameter space) and $\Omega $ a set (the sample space). The mapping $X:\aleph \to T\left( \Omega ,T\left[ H^\mu,\bigcup\limits_{\mu'\in \Z^+} H^{\mu'} \right] \right)$ is a GO. The set of GOs is denoted as $GOP( H,\mu ,\aleph ,\Omega)$. There are three common GOs: recombination, mutation, and selection. These three operators are roughly analogous to their similarly named counterparts in genetics. The application of them in GAs is strictly Darwin-like in nature, i.e., “survival of the fittest.” In defining the GOs, we will start with recombination. Let $r\in GOP( H,\mu ,\aleph ,\Omega)$. If there exist $P\in H^\mu$, $\Theta \in \aleph $ and $\omega\in \Omega $ such that one individual in the offspring population $r_\Theta (P)$ depends on more than one individual of $P$ then $r$ is referred to as a recombination operator. A mutation is defined in the following manner: let $m\in GOP( H,\mu ,\aleph ,\Omega)$. If for every $P\in H^\mu $, for every $\Theta \in X$, for every $\omega \in \Omega $, and if each individual in the offspring population $m_\Theta(P)$ depends on at most one individual of $P$ then $m$ is called a mutation operator. Finally, for a selection operator let $s\in GOP( H,\mu ,\aleph \times T(H,\R),\Omega ) )$. If $P\in H^\mu$, $\Theta \in \aleph $, $f:H\to \R $ in all cases, and $s$ satisfies $a\in s_{( \Theta,\Phi)}(P) \Rightarrow a\in P$, then $s$ is a selection operator.


References

[1] Back, T., Evolutionary Algorithms in Theory and Practice, Oxford University Press, 1996

[2] Coello Coello, C.A., Van Veldhuizen, D.A. and Lamont, G.B., Evolutionary Algorithms for Solving Multi-Objective Problems, Kluwer Academic Publishers, 2002

[3] Goldberg, D.E., Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley Professional, 1989

[4] Holland, J.H., Adaptation in Natural and Artificial Systems, A Bradford Book, 1992

[5] Lamont, L. and Merkle, J.D., "A Random Based Framework for Evolutionary Algorithms", in: T. Back, Proceedings of the Seventh International Conference on Genetic Algorithms, 1997.

[6] Surry, Patrick D. and Radcliffe, N.J., "Formal Algorithms + Formal Representations = Search Strategies", Parallel Problem Solving from Nature IV, Springer-Verlag LNCS 1141, pp 366-375, 1996.

How to Cite This Entry:
Genetic Algorithms. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Genetic_Algorithms&oldid=27681