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.
  
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 Ausing 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}}\toH\].
+
 
 +
                                            \[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 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 23: Line 25:
 
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 34: Line 36:
 
The following statements about the operators of GAs are adopted from Coello et al.(2002).
 
The following statements about the operators of GAs are adopted from Coello et al.(2002).
  
·       Let H be a nonempty set (the individual orsearch space)
+
·                               Let H be a nonempty set (the individual orsearch 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
+
·                               \[\phi :H\to \mathbb{R}\] a fitness function
·       \[\iota:\cup _{i=1}^{\infty }{{({{H}^{u}})}^{(i)}}\to \] {true, false} (the termination criteria)
+
·                               \[\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)}\toT(\Omega _{r}^{(i)}
+
·                               \[\chi \in \]{true, false}, r a sequence \[\left\{ {{r}^{(i)}} \right\}\] of recombination operators τ(i) : \[X_{r}^{(i)}\toT(\Omega _{r}^{(i)}
·       m a sequence of {m(i)} of mutation operators in mi
+
·                               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_{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 recombination parameters)
+
·                               \[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 _{m}^{(i)}\in X_{m}^{(i)}\] (the mutation parameters)
+
                                \[\Theta _{r}^{(i)}\in X_{r}^{(i)}\] (the recombination parameters)
·       \[\Theta _{s}^{(i)}\in X_{s}^{(i)}\] (the selection 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 }'}}}\]
  
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.
+
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:22, 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}}\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}}\]

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 adopted from Coello et al.(2002).

· Let H be a nonempty set (the individual orsearch 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)}\toT(\Omega _{r}^{(i)} · 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)}\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 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=27537