Namespaces
Variants
Actions

Difference between revisions of "Genetic Algorithms"

From Encyclopedia of Mathematics
Jump to: navigation, search
Line 6: Line 6:
  
 
A generic GA (also know as an evolutionary algorithm [EA]) assumes a discrete search space H and a function
 
A generic GA (also know as an evolutionary algorithm [EA]) assumes a discrete search space H and a function
                                              \[f:H\to\mathbb{R}\],                         
+
                                                \[f:H\to\mathbb{R}\],                         
 
where H is a subsetof the Euclidean space\[\mathbb{R}\].
 
where H is a subsetof the Euclidean space\[\mathbb{R}\].
 
The general problem is to find
 
The general problem is to find
                                              \[\arg\underset{X\in H}{\mathop{\min }}\,f\]
+
                                                \[\arg\underset{X\in H}{\mathop{\min }}\,f\]
  
 
where X is avector of the decision variables and f is the objective function.
 
where X is avector of the decision variables and f is the objective function.
Line 15: Line 15:
 
With GAs it is customary to distinguish genotype–the encoded representation of the variables–from phenotype–the set of variablesthemselves. 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
 
With GAs it is customary to distinguish genotype–the encoded representation of the variables–from phenotype–the set of variablesthemselves. 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\]
+
                                                \[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 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, Ξ  
 
The range of c, Ξ  
                                              \[\Xi\subseteq {{A}^{l}}\]
+
                                                \[\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.
 
is needed to account for the fact that some strings in the image Al under c may represent invalid solutions to the original problem.
Line 27: Line 27:
 
Given the statements above, the optimization becomes:
 
Given the statements above, the optimization becomes:
  
                                      \[\arg\underset{S\in L}{\mathop{\min g}}\,\],
+
                                      \[\arg\underset{S\in L}{\mathop{\min g}}\,\],
 
given the function  
 
given the function  
  
                                      \[g(s)=f(c(s))\].
+
                                        \[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.  
 
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.  
Line 39: Line 39:
 
The following statements about the operators of GAs are adapted from Coello et al.(2002).
 
The following statements about the operators of GAs are adapted from Coello et al.(2002).
  
·        Let H be a nonempty set (the individual orsearch space)
+
·        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 parent populations)
 
·        \[{{\left\{ {{u}^{'(i)}} \right\}}_{i\in\mathbb{N}}}\] a sequence in \[{{\mathbb{Z}}^{+}}\](the offspring population sizes)
 
·        \[{{\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}  
 
·        \[\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\}\] of recombination operators τ(i) :\[X_{r}^{(i)}\to T(\Omega _{r}^{(i)}
+
·        r a sequence \[\left\{ {{r}^{(i)}} \right\}\] 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))\]
 
·        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)}}}}))\]
+
·        s a sequence of 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 _{r}^{(i)}\in X_{r}^{(i)}\] (the recombination parameters)
 
·        \[\Theta _{m}^{(i)}\in X_{m}^{(i)}\] (the mutation parameters)
 
·        \[\Theta _{m}^{(i)}\in X_{m}^{(i)}\] (the mutation parameters)
Line 55: Line 55:
 
Coello et al. define the collection μ (thenumber of individuals) via Hμ.The population transforms are denoted by
 
Coello et al. define the collection μ (thenumber of individuals) via Hμ.The population transforms are denoted by
  
                                  \[T:{{H}^{\mu }}\to {{H}^{\mu }}\]
+
                                    \[T:{{H}^{\mu }}\to {{H}^{\mu }}\]
  
 
where
 
where
  
                                  \[\mu \in \mathbb{N}\]
+
                                    \[\mu \in \mathbb{N}\]
  
 
However, some GA methods generate populationswhose size is not equal to their predecessors’. In a more general framework  
 
However, some GA methods generate populationswhose size is not equal to their predecessors’. In a more general framework  
  
                                  \[T:{{H}^{\mu}}\to {{H}^{{{\mu }'}}}\]
+
                                    \[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.
 
can accommodate populations that contain the same ordifferent individuals. This mapping has the ability to represent all populationsizes, evolutionary operators, and parameters as sequences.

Revision as of 14:53, 14 August 2012

Bold textGenetic Algorithms


1. Genetic algorithms (GAs): basic form

A generic GA (also know as an 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 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 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.


2. Genetic algorithms and their operators

The following statements about the operators of GAs are adapted from Coello et al.(2002).

· 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\}\] 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 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) · \[\Theta _{s}^{(i)}\in X_{s}^{(i)}\] (the selection 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.

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