# Difference between revisions of "User talk:Tgawa63"

(typo) |
(my version of your text) |
||

Line 2: | Line 2: | ||

: Probably you need someone that knows TeX and Wiki (rather than web building). [[User:Boris Tsirelson|Boris Tsirelson]] ([[User talk:Boris Tsirelson|talk]]) 21:44, 18 September 2012 (CEST) | : Probably you need someone that knows TeX and Wiki (rather than web building). [[User:Boris Tsirelson|Boris Tsirelson]] ([[User talk:Boris Tsirelson|talk]]) 21:44, 18 September 2012 (CEST) | ||

+ | : Anyway, it would help, first to look closely at existing texts and try to do as similarly as possible. Also, below I put my version of your text. Feel free to delete it if you do not need it here. At bottom, some portion is left intact; maybe try to correct it yourself similarly to the corrected top portion. [[User:Boris Tsirelson|Boris Tsirelson]] ([[User talk:Boris Tsirelson|talk]]) 22:31, 18 September 2012 (CEST) | ||

+ | |||

+ | =Genetic Algorithms= | ||

+ | |||

+ | ==Genetic algorithms (GAs): basic form== | ||

+ | |||

+ | A generic GA (also known as an evolutionary algorithm [EA]) assumes a discrete search space $H$ and a function | ||

+ | \[f:H\to\R,\] | ||

+ | where $H$ is a subset of the Euclidean space $\R$. | ||

+ | |||

+ | The general problem is to find | ||

+ | \[\arg\underset{X\in H}{\mathop{\min }}\,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\] | ||

+ | The mapping $c$ is not necessarily surjective. The range of $c$ determine the subset of $A^l$ available for exploration by a GA. The range of $c$, $\Xi$ | ||

+ | \[\Xi\subseteq {{A}^{l}}\] | ||

+ | is needed to account for the fact that some strings in the image $A^l$ under $c$ may represent invalid solutions to the original problem. | ||

+ | |||

+ | The string length $l$ depends on the dimensions of both $H$ and $A^l$, 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 $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$. | ||

+ | |||

+ | ==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\{\text{true},\text{false}\}\] | ||

+ | (the termination criteria), | ||

+ | \[\chi\in\{\text{true},\text{false}\},\] | ||

+ | $r$ a sequence | ||

+ | \[\left\{{{r}^{(i)}} \right\}\] | ||

+ | |||

+ | Define the collection $\mu$ (the number of individuals) via $H_\mu$. The population transforms are denoted by | ||

+ | \[T:{{H}^{\mu }}\to {{H}^{\mu }}\] | ||

+ | where | ||

+ | \[\mu \in \mathbb{N}\] | ||

+ | of recombination operators $\tau(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)}\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), and | ||

+ | \[\Theta_{s}^{(i)}\in X_{s}^{(i)}\] | ||

+ | (the selection parameters). | ||

+ | |||

+ | To account for the cases where populations whose size not equal to their predecessors’, the following expression | ||

+ | \[T:{{H}^{\mu}}\to {{H}^{{{\mu }'}}}\] | ||

+ | accommodates 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 random 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 upon the work of Lamont and Merkle (Lamont, 1997) and others, the termination criteria and the other genetic operators(GOs)will be defined in more detail. | ||

+ | |||

+ | Since $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 $f$ is determined by the application, while the specification of the decoding function $c[1]$ and the fitness scaling function $T_s$ are design issues. | ||

+ | |||

+ | |||

+ | After initialization, the 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 a transformation of 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 the parent population and <sup>Superscript text</sup>''Italic text''P/ the offspring population. If $\mu ={\mu }'$,then it is called the population size. | ||

+ | |||

+ | The ''Italic text''PT resulting from a 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 a ''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 a ''Italic text''RPT. | ||

+ | |||

+ | Now that both the fitness function and ''Italic text''RPT have been defined, 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. |

## Revision as of 20:31, 18 September 2012

Hi, Welcome aboard of EoM on behalf of the editorial board. Please find here our working conditions.--Ulf Rehmann 11:37, 25 May 2012 (CEST): I wonder, what for did you upload File:Encyclopedia EAs v10 alt versionEdit ac edit2a.docx? --Boris Tsirelson 18:25, 13 August 2012 (CEST)== Upload ==The upload was an error. I am surprised the upload occured as there was an error message on my side saying it had failed.:I see. You can ask Ulf to delete it, here. --Boris Tsirelson 22:25, 13 August 2012 (CEST):Also it could be more convenient to create your personal sandbox and use it for drafts (rather than your user page). --Boris Tsirelson 22:28, 13 August 2012 (CEST)== Sandbox and a thank you ==Txs for the heads-up about the sandbox. I have found it very useful this morning. And I will contact Ulf about the misposted items.:Nice, but I see that you did not use my redlink, but instead typed in a different name. I just moved it. Now it is called User:Tgawa63/sandbox, thus it belongs to your userspace. The old name Tgawa63/sandbox belongs formally to the mainspace, and means formally "a supplement to the article on Tgawa63", which was not intended. --Boris Tsirelson 18:30, 14 August 2012 (CEST)== MathJax ==I have the genetic algorithm paper in the sandbox and it is complete but for 2 very important things: 1)I cannot make certain symbols appear as bold or italics for example, how to do so is my question 2)all of the formulas are coming over in TEX format with some appearing ok but others getting broken into multiple pieces so one part of the formula is on 1 line while the continuation is on the next, how to fix this. Pls excuse my inexperience and naviete in asking these questions.: Unfortunately, in many cases I really do not guess which effect do you try to produce. Anyway, I did some changes on my copy of your text here. Please look *(to this end, click the blue word "here")* and, if you like, copy it back into your sandbox. I did not finish this work, but probably you can continue it yourself. Do not hesitate to ask. It seems, you did not use TeX before; really? --Boris Tsirelson 22:49, 20 August 2012 (CEST): And please sign your messages (on talk pages) by four tildas: ~~~~. --Boris Tsirelson 22:53, 20 August 2012 (CEST): There are several problems here -- you are putting displayed math in the middle of a line, but Wiki syntax interprets 4 space indentation as being a quote. I have fixed the first to cases of this in your sandbox, please look at the source --Jjg 19:33, 24 August 2012 (CEST)== GA entry ==Hello,My apologies for needing all the help you have given so far. As to Boris' question about TeX, no I have never used it. At to the other question about Wiki use, I have not done that either. Pls know I will be contacting a pro in web building who will make the necessary entries and will hopefully not need as much help as I have so far. Again my apologies for my deficiences. User:Andrew Clark (talk) 16:45, 18 September 2012 (CEST)Andrew Clark

- Probably you need someone that knows TeX and Wiki (rather than web building). Boris Tsirelson (talk) 21:44, 18 September 2012 (CEST)
- Anyway, it would help, first to look closely at existing texts and try to do as similarly as possible. Also, below I put my version of your text. Feel free to delete it if you do not need it here. At bottom, some portion is left intact; maybe try to correct it yourself similarly to the corrected top portion. Boris Tsirelson (talk) 22:31, 18 September 2012 (CEST)

# Genetic Algorithms

## Genetic algorithms (GAs): basic form

A generic GA (also known as an evolutionary algorithm [EA]) assumes a discrete search space $H$ and a function \[f:H\to\R,\] where $H$ is a subset of the Euclidean space $\R$.

The general problem is to find \[\arg\underset{X\in H}{\mathop{\min }}\,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\] The mapping $c$ is not necessarily surjective. The range of $c$ determine the subset of $A^l$ available for exploration by a GA. The range of $c$, $\Xi$ \[\Xi\subseteq {{A}^{l}}\] is needed to account for the fact that some strings in the image $A^l$ under $c$ may represent invalid solutions to the original problem.

The string length $l$ depends on the dimensions of both $H$ and $A^l$, 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 $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$.

## 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\{\text{true},\text{false}\}\] (the termination criteria), \[\chi\in\{\text{true},\text{false}\},\] $r$ a sequence \[\left\{{{r}^{(i)}} \right\}\]

Define the collection $\mu$ (the number of individuals) via $H_\mu$. The population transforms are denoted by \[T:{{H}^{\mu }}\to {{H}^{\mu }}\] where \[\mu \in \mathbb{N}\] of recombination operators $\tau(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)}\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), and \[\Theta_{s}^{(i)}\in X_{s}^{(i)}\] (the selection parameters).

To account for the cases where populations whose size not equal to their predecessors’, the following expression \[T:{{H}^{\mu}}\to {{H}^{{{\mu }'}}}\] accommodates 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 random 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 upon the work of Lamont and Merkle (Lamont, 1997) and others, the termination criteria and the other genetic operators(GOs)will be defined in more detail.

Since $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 $f$ is determined by the application, while the specification of the decoding function $c[1]$ and the fitness scaling function $T_s$ are design issues.

After initialization, the 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 a transformation of 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 the parent population and ^{Superscript text}*Italic text*P/ the offspring population. If $\mu ={\mu }'$,then it is called the population size.

The *Italic text*PT resulting from a 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 a *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 a *Italic text*RPT.

Now that both the fitness function and *Italic text*RPT have been defined, 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.

**How to Cite This Entry:**

Tgawa63.

*Encyclopedia of Mathematics.*URL: http://encyclopediaofmath.org/index.php?title=Tgawa63&oldid=28030