Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Evolvability of Real Functions

Evolvability of Real Functions Evolvability of Real Functions PAUL VALIANT, Brown University We formulate a notion of evolvability for functions with domain and range that are real-valued vectors, a compelling way of expressing many natural biological processes. We show that linear and fixed-degree polynomial functions are evolvable in the following dually-robust sense: There is a single evolution algorithm that, for all convex loss functions, converges for all distributions. It is possible that such dually-robust results can be achieved by simpler and more-natural evolution algorithms. Towards this end, we introduce a simple and natural algorithm that we call wide-scale random noise and prove a corresponding result for the L2 metric. We conjecture that the algorithm works for a more general class of metrics. Categories and Subject Descriptors: F.1.1 [Computation by Abstract Devices]: Models of Computation--Self-modifying machines; G.1.6 [Numerical Analysis]: Optimization--Convex programming; I.2.6 [Artificial Intelligence]: Learning--Concept learning; J.3 [Computer Applications]: Life and Medical Sciences--Biology and genetics General Terms: Algorithms, Theory Additional Key Words and Phrases: Evolvability, optimization ACM Reference Format: Valiant, P. 2014. Evolvability of real functions. ACM Trans. Comput. Theory 6, 3, Article 12 (July 2014), 19 pages. DOI:http://dx.doi.org/10.1145/2633598 1. INTRODUCTION Since Darwin first assembled the empirical facts that pointed to evolution as http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM Transactions on Computation Theory (TOCT) Association for Computing Machinery

Evolvability of Real Functions

Download PDF
19 pages

Loading next page...
 
/lp/association-for-computing-machinery/evolvability-of-real-functions-I6NMau09fu

References

References for this paper are not available at this time. We will be adding them shortly, thank you for your patience.

Publisher
Association for Computing Machinery
Copyright
Copyright © 2014 by ACM Inc.
ISSN
1942-3454
DOI
10.1145/2633598
Publisher site
See Article on Publisher Site

Abstract

Evolvability of Real Functions PAUL VALIANT, Brown University We formulate a notion of evolvability for functions with domain and range that are real-valued vectors, a compelling way of expressing many natural biological processes. We show that linear and fixed-degree polynomial functions are evolvable in the following dually-robust sense: There is a single evolution algorithm that, for all convex loss functions, converges for all distributions. It is possible that such dually-robust results can be achieved by simpler and more-natural evolution algorithms. Towards this end, we introduce a simple and natural algorithm that we call wide-scale random noise and prove a corresponding result for the L2 metric. We conjecture that the algorithm works for a more general class of metrics. Categories and Subject Descriptors: F.1.1 [Computation by Abstract Devices]: Models of Computation--Self-modifying machines; G.1.6 [Numerical Analysis]: Optimization--Convex programming; I.2.6 [Artificial Intelligence]: Learning--Concept learning; J.3 [Computer Applications]: Life and Medical Sciences--Biology and genetics General Terms: Algorithms, Theory Additional Key Words and Phrases: Evolvability, optimization ACM Reference Format: Valiant, P. 2014. Evolvability of real functions. ACM Trans. Comput. Theory 6, 3, Article 12 (July 2014), 19 pages. DOI:http://dx.doi.org/10.1145/2633598 1. INTRODUCTION Since Darwin first assembled the empirical facts that pointed to evolution as

Journal

ACM Transactions on Computation Theory (TOCT) – Association for Computing Machinery

Published: Jul 1, 2014

There are no references for this article.