Towards a Sound Theory of Adaptation for the Simple Genetic Algorithm

@misc{citeulike:2725274, abstract = {The pace of progress in the fields of Evolutionary Computation and Machine Learning is currently limited -- in the former field, by the improbability of making advantageous extensions to evolutionary algorithms when their capacity for adaptation is poorly understood, and in the latter by the difficulty of finding effective semi-principled reductions of hard real-world problems to relatively simple optimization problems. In this paper we explain why a theory which can accurately explain the simple genetic algorithm's remarkable capacity for adaptation has the potential to address both these limitations. We describe what we believe to be the impediments -- historic and analytic -- to the discovery of such a theory and highlight the negative role that the building block hypothesis (BBH) has played. We argue based on experimental results that a fundamental limitation which is widely believed to constrain the SGA's adaptive ability (and is strongly implied by the BBH) is in fact illusionary and does not exist. The SGA therefore turns out to be more powerful than it is currently thought to be. We give conditions under which it becomes feasible to numerically approximate and study the multivariate marginals of the search distribution of an infinite population SGA over multiple generations even when its genomes are long, and explain why this analysis is relevant to the riddle of the SGA's remarkable adaptive abilities.}, author = {Burjorjee, Keki }, citeulike-article-id = {2725274}, comment = {The article is a discussion on the nature of adaptation / learning within the machine learning / genetic algorithm field. Summary of the current state of progress within the field and some of the reasons as to why its not progressing much. Of interest: "Let us differentiate, in this paper, between optimization and adaptation. We define optimization as the procurement of one or more points of optimal or close-to-optimal value, and adaptation as the generation of points of increasing value over time. Given this definition, to say that the target problems of Machine Learning reductions are optimization problems is to fudge the truth somewhat. While the Mathematical Programming community indeed seems to be almost completely concerned with the procurement of optimal or close to optimal points, ML researchers aren’t interested in optimization per se but in the means by which it is achieved in most MP algorithms, i.e. adaptation. In fact optimization is often prevented in machine learning algorithms — using a “technique” named early-stopping — to prevent overfitting. In other words, robust, efficient adaptation is the modus operandi of most convex optimization algorithms, and for the most part, it is this modus operandi that makes these algorithms interesting to Machine Learning researchers."}, eprint = {0711.1401}, keywords = {adaptability, artifical\_intelligence, genetic\_algorithm, learning, optimisation}, month = {Nov}, posted-at = {2008-04-28 01:37:07}, priority = {0}, title = {Towards a Sound Theory of Adaptation for the Simple Genetic Algorithm}, url = {http://arxiv.org/abs/0711.1401}, year = {2007} }

TY - ELEC ID - citeulike:2725274 L3 - citeulike-article-id:2725274 TI - Towards a Sound Theory of Adaptation for the Simple Genetic Algorithm N2 - The pace of progress in the fields of Evolutionary Computation and Machine Learning is currently limited -- in the former field, by the improbability of making advantageous extensions to evolutionary algorithms when their capacity for adaptation is poorly understood, and in the latter by the difficulty of finding effective semi-principled reductions of hard real-world problems to relatively simple optimization problems. In this paper we explain why a theory which can accurately explain the simple genetic algorithm's remarkable capacity for adaptation has the potential to address both these limitations. We describe what we believe to be the impediments -- historic and analytic -- to the discovery of such a theory and highlight the negative role that the building block hypothesis (BBH) has played. We argue based on experimental results that a fundamental limitation which is widely believed to constrain the SGA's adaptive ability (and is strongly implied by the BBH) is in fact illusionary and does not exist. The SGA therefore turns out to be more powerful than it is currently thought to be. We give conditions under which it becomes feasible to numerically approximate and study the multivariate marginals of the search distribution of an infinite population SGA over multiple generations even when its genomes are long, and explain why this analysis is relevant to the riddle of the SGA's remarkable adaptive abilities. KW - adaptability KW - artifical_intelligence KW - genetic_algorithm KW - learning KW - optimisation N1 - The article is a discussion on the nature of adaptation / learning within the machine learning / genetic algorithm field. Summary of the current state of progress within the field and some of the reasons as to why its not progressing much. Of interest: "Let us differentiate, in this paper, between optimization and adaptation. We define optimization as the procurement of one or more points of optimal or close-to-optimal value, and adaptation as the generation of points of increasing value over time. Given this definition, to say that the target problems of Machine Learning reductions are optimization problems is to fudge the truth somewhat. While the Mathematical Programming community indeed seems to be almost completely concerned with the procurement of optimal or close to optimal points, ML researchers aren’t interested in optimization per se but in the means by which it is achieved in most MP algorithms, i.e. adaptation. In fact optimization is often prevented in machine learning algorithms — using a “technique” named early-stopping — to prevent overfitting. In other words, robust, efficient adaptation is the modus operandi of most convex optimization algorithms, and for the most part, it is this modus operandi that makes these algorithms interesting to Machine Learning researchers." AU - Burjorjee, Keki PY - 2007/Nov/09/ UR - http://arxiv.org/abs/0711.1401 ER -