Hypomixability Elimination In Evolutionary Systems
Keki M. Burjorjee · 2015
Hypomixability Elimination is an intriguing form of computation thought to underlie general-purpose, non-local, noise-tolerant adaptation in recombinative evolutionary systems. We demonstrate that hypomixability elimination in recombinative evolutionary systems can be efficient by using it to obtain optimal bounds on the time and queries required to solve a subclass (k=7, η=1/5) of a familiar computational learning problem: PAC-learning parities with noisy membership queries; where k is the number of relevant attributes and η is the oracle's noise rate. Specifically, we show that a simple genetic algorithm with uniform crossover (free recombination) that treats the noisy membership query oracle as a fitness function can be rigged to PAC-learn the relevant variables in O(log (n/δ)) queries and O(n log (n/δ)) time, where n is the total number of attributes and δ is the probability of error. To the best of our knowledge, this is the first time optimally efficient computation has been shown to occur in, an evolutionary algorithm, on a non-trivial problem.