2013/07/15 by Keki M. Burjorjee, Burjorjee, Keki M. · 1 citation
Computer Science · #Algorithm #Artificial Intelligence (cs.AI) #Artificial intelligence #Computational Complexity (cs.CC) #Computer science #Constraint Satisfaction and Optimization #Crossover #Discrete Mathematics (cs.DM) #Evolutionary Algorithms and Applications #F.2 #FOS: Computer and information sciences #Genetic algorithm #I.2.6 #I.2.8 #Machine Learning (cs.LG) #Machine learning #Metaheuristic Optimization Algorithms Research #Neural and Evolutionary Computing (cs.NE) #cs.AI #cs.CC #cs.DM #cs.LG #cs.NE
paper · pdf · doi:10.48550/arxiv.1307.3824
published in arXiv (Cornell University) (Cornell University) · For an easy introduction to implicit concurrency (with animations), visit http://blog.hackingevolution.net/2013/03/24/implicit-concurrency-in-genetic-algorithms/
arxiv created 2013/07/15 · openalex publication_date 2013/07/15 · arxiv updated 2013/07/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This paper establishes theoretical bonafides for implicit concurrent multivariate effect evaluation--implicit concurrency for short---a broad and versatile computational learning efficiency thought to underlie general-purpose, non-local, noise-tolerant optimization in genetic algorithms with uniform crossover (UGAs). We demonstrate that implicit concurrency is indeed a form of efficient learning by showing that it can be used to obtain close-to-optimal bounds on the time and queries required to approximately correctly solve a constrained version (k=7, η=1/5) of a recognizable computational learning problem: learning parities with noisy membership queries. We argue that a UGA that treats the noisy membership query oracle as a fitness function can be straightforwardly used to approximately correctly learn the essential attributes in O(log1.585 n) queries and O(n log1.585 n) time, where n is the total number of attributes. Our proof relies on an accessible symmetry argument and the use of statistical hypothesis testing to reject a global null hypothesis at the 10-100 level of significance. It is, to the best of our knowledge, the first relatively rigorous identification of efficient computational learning in an evolutionary algorithm on a non-trivial learning problem.