begin quote from:
Evolvability (computer science)

:

1. Evolvability (computer science) - Wikipedia

   en.wikipedia.org/.../Evolvability_(computer_scien...

   Evolvability (computer science) This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn ...

2. Talk:Evolvability (computer science) - Wikipedia

   en.wikipedia.org/wiki/Talk:Evolvability...

   Evolvability (computer science) is within the scope of WikiProject Robotics, which aims to build a comprehensive and detailed guide to Robotics on Wikipedia.

3. UCF Computer Scientist Suggests New Spin on Origins of ...

   www.cecs.ucf.edu/ucf-computer-scientist-sugge...

   College of Engineering and Computer Science . About Us. Dean’s Welcome; ... UCF Computer Scientist Suggests New Spin on Origins of Evolvability .

4. Computer scientists suggest new spin on origins of evolvability

   today.ucf.edu/computer-scientists-suggest-new-spin-on...

   Computer Scientists Suggest New Spin on Origins of Evolvability - Read more about UCF Research, Science & Technology, Orlando and Central Florida news.

5. Computer scientists suggest new spin on origins of evolvability

   • phys.org
   •   › Biology
   •   › Evolution

   But computer science researchers now say that the popular explanation of ... "Evolvability is the ability of a population of organisms to not merely generate ...

6. Computer scientists suggest new spin on origins of evolvability

   www.ecnmag.com/news/2013/04/computer-scientis...

   But computer science researchers now say that the popular explanation of competition to survive in nature may not actually be necessary for evolvability to increase.

Evolvability (computer science)

From Wikipedia, the free encyclopedia

This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages) This article relies too much on references to primary sources. (October 2016) This article is an orphan, as no other articles link to it. Please introduce links to this page from related articles; try the Find link tool for suggestions. (July 2011)

The term evolvability is used for a recent framework of computational learning introduced by Leslie Valiant in his paper of the same name and described below. The aim of this theory is to model biological evolution and categorize which types of mechanisms are evolvable. Evolution is an extension of PAC learning and learning from statistical queries.

General Framework

Let ${\displaystyle F_{n}\,}$ and ${\displaystyle R_{n}\,}$ be collections of functions on ${\displaystyle n\,}$ variables. Given an ideal function ${\displaystyle f\in F_{n}}$, the goal is to find by local search a representation ${\displaystyle r\in R_{n}}$ that closely approximates ${\displaystyle f\,}$. This closeness is measured by the performance ${\displaystyle \operatorname {Perf} (f,r)}$ of ${\displaystyle r\,}$ with respect to ${\displaystyle f\,}$.
As is the case in the biological world, there is a difference between genotype and phenotype. In general, there can be multiple representations (genotypes) that correspond to the same function (phenotype). That is, for some ${\displaystyle r,r'\in R_{n}}$, with ${\displaystyle r\neq r'\,}$, still ${\displaystyle r(x)=r'(x)\,}$ for all ${\displaystyle x\in X_{n}}$. However, this need not be the case. The goal then, is to find a representation that closely matches the phenotype of the ideal function, and the spirit of the local search is to allow only small changes in the genotype. Let the neighborhood ${\displaystyle N(r)\,}$ of a representation ${\displaystyle r\,}$ be the set of possible mutations of ${\displaystyle r\,}$.
For simplicity, consider Boolean functions on ${\displaystyle X_{n}=\{-1,1\}^{n}\,}$, and let ${\displaystyle D_{n}\,}$ be a probability distribution on ${\displaystyle X_{n}\,}$. Define the performance in terms of this. Specifically,

${\displaystyle \operatorname {Perf} (f,r)=\sum _{x\in X_{n}}f(x)r(x)D_{n}(x).}$

Note that ${\displaystyle \operatorname {Perf} (f,r)=\operatorname {Prob} (f(x)=r(x))-\operatorname {Prob} (f(x)\neq r(x)).}$ In general, for non-Boolean functions, the performance will not correspond directly to the probability that the functions agree, although it will have some relationship.
Throughout an organism's life, it will only experience a limited number of environments, so its performance cannot be determined exactly. The empirical performance is defined by ${\displaystyle \operatorname {Perf} _{s}(f,r)={\frac {1}{s}}\sum _{x\in S}f(x)r(x),}$ where ${\displaystyle S\,}$ is a multiset of ${\displaystyle s\,}$ independent selections from ${\displaystyle X_{n}\,}$ according to ${\displaystyle D_{n}\,}$. If ${\displaystyle s\,}$ is large enough, evidently ${\displaystyle \operatorname {Perf} _{s}(f,r)}$ will be close to the actual performance ${\displaystyle \operatorname {Perf} (f,r)}$.
Given an ideal function ${\displaystyle f\in F_{n}}$, initial representation ${\displaystyle r\in R_{n}}$, sample size ${\displaystyle s\,}$, and tolerance ${\displaystyle t\,}$, the mutator ${\displaystyle \operatorname {Mut} (f,r,s,t)}$ is a random variable defined as follows. Each ${\displaystyle r'\in N(r)}$ is classified as beneficial, neutral, or deleterious, depending on its empirical performance. Specifically,

• ${\displaystyle r'\,}$ is a beneficial mutation if ${\displaystyle \operatorname {Perf} _{s}(f,r')-\operatorname {Perf} _{s}(f,r)\geq t}$;
• ${\displaystyle r'\,}$ is a neutral mutation if ${\displaystyle -t<\operatorname {Perf} _{s}(f,r')-\operatorname {Perf} _{s}(f,r)$;
• ${\displaystyle r'\,}$ is a deleterious mutation if ${\displaystyle \operatorname {Perf} _{s}(f,r')-\operatorname {Perf} _{s}(f,r)\leq -t}$.

If there are any beneficial mutations, then ${\displaystyle \operatorname {Mut} (f,r,s,t)}$ is equal to one of these at random. If there are no beneficial mutations, then ${\displaystyle \operatorname {Mut} (f,r,s,t)}$ is equal to a random neutral mutation. In light of the similarity to biology, ${\displaystyle r\,}$ itself is required to be available as a mutation, so there will always be at least one neutral mutation.
The intention of this definition is that at each stage of evolution, all possible mutations of the current genome are tested in the environment. Out of the ones who thrive, or at least survive, one is chosen to be the candidate for the next stage. Given ${\displaystyle r_{0}\in R_{n}}$, we define the sequence ${\displaystyle r_{0},r_{1},r_{2},\ldots }$ by ${\displaystyle r_{i+1}=\operatorname {Mut} (f,r_{i},s,t)}$. Thus ${\displaystyle r_{g}\,}$ is a random variable representing what ${\displaystyle r_{0}\,}$ has evolved to after ${\displaystyle g\,}$ generations.
Let ${\displaystyle F\,}$ be a class of functions, ${\displaystyle R\,}$ be a class of representations, and ${\displaystyle D\,}$ a class of distributions on ${\displaystyle X\,}$. We say that ${\displaystyle F\,}$ is evolvable by ${\displaystyle R\,}$ over ${\displaystyle D\,}$ if there exists polynomials ${\displaystyle p(\cdot ,\cdot )}$, ${\displaystyle s(\cdot ,\cdot )}$, ${\displaystyle t(\cdot ,\cdot )}$, and ${\displaystyle g(\cdot ,\cdot )}$ such that for all ${\displaystyle n\,}$ and all ${\displaystyle \epsilon >0\,}$, for all ideal functions ${\displaystyle f\in F_{n}}$ and representations ${\displaystyle r_{0}\in R_{n}}$, with probability at least ${\displaystyle 1-\epsilon \,}$,

${\displaystyle \operatorname {Perf} (f,r_{g(n,1/\epsilon )})\geq 1-\epsilon ,}$

where the sizes of neighborhoods ${\displaystyle N(r)\,}$ for ${\displaystyle r\in R_{n}\,}$ are at most ${\displaystyle p(n,1/\epsilon )\,}$, the sample size is ${\displaystyle s(n,1/\epsilon )\,}$, the tolerance is ${\displaystyle t(1/n,\epsilon )\,}$, and the generation size is ${\displaystyle g(n,1/\epsilon )\,}$.
${\displaystyle F\,}$ is evolvable over ${\displaystyle D\,}$ if it is evolvable by some ${\displaystyle R\,}$ over ${\displaystyle D\,}$.
${\displaystyle F\,}$ is evolvable if it is evolvable over all distributions ${\displaystyle D\,}$.

Results

The class of conjunctions and the class of disjunctions are evolvable over the uniform distribution for short conjunctions and disjunctions, respectively.
The class of parity functions (which evaluate to the parity of the number of true literals in a given subset of literals) are not evolvable, even for the uniform distribution.
Evolvability implies PAC learnability.

References

1. Valiant, L. G. (2006), Evolvability, ECCC TR06-120.

Categories:

• Machine learning

Navigation menu

• Not logged in
• Talk
• Contributions
• Create account
• Log in

• Article
• Talk

• Read
• Edit
• View history

Search

• Main page
• Contents
• Featured content
• Current events
• Random article
• Donate to Wikipedia
• Wikipedia store

Interaction

• Help
• About Wikipedia
• Community portal
• Recent changes
• Contact page

Tools

• What links here
• Related changes
• Upload file
• Special pages
• Permanent link
• Page information
• Wikidata item
• Cite this page

Print/export

• Create a book
• Download as PDF
• Printable version

Languages

Add links

• This page was last modified on 13 October 2016, at 16:12.