Evolvability (computer science)

Evolvability is a recent framework of computational learning introduced by Leslie Valiant in his paper of the same name. The aim of this theory is to model biological evolution and categorize which types of mechanisms are evolvable.

The goal of evolution is to find by local search in a reasonable number of generations a representation that approximates a given function. The performance of a representation is a measure of how well it approximates the given function. In each generation, the performance of the current representation is compared to that of its mutations, representations in a reasonably-sized neighborhood of the current representation. A beneficial (or neutral) mutation is selected at random to be the representation in the next generation. A class of functions is said to be evolvable for a class of representations if for any function and any initial representation, with high probability the evolutionary process results in a representation that has high performance.

Evolvability implies PAC learnability.

References

L.G. Valiant. Evolvability. ECCC, TR06-120, 2006. [1]