Difference between revisions of "Genetic Algorithms"
(Genetic Algorithms: Form and Function) |
|||
Line 5: | Line 5: | ||
1. Genetic algorithms (GAs): basic form | 1. Genetic algorithms (GAs): basic form | ||
− | A generic GA ( | + | 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}. | + | 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, | |
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 | + | |
− | + | 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 | |
+ | 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}} | |
− | + | 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: | Given the statements above, the optimization becomes: | ||
− | + | ||
+ | \arg\underset{S\in L}{\mathop{\min g}}\,, | ||
given the function | 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. | 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 byT:{{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. | Coello et al. define the collection μ (thenumber of individuals) via Hμ.The population transforms are denoted byT:{{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. |
Revision as of 14:17, 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 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}}\]
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 byT:{{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.
Genetic Algorithms. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Genetic_Algorithms&oldid=27537