On the Workings of Genetic Algorithms

The Genoclique Fixing Hypothesis

 

The Fundamental Problem with the Building Block Hypothesis

Download latest revision

Abstract:  Skepticism of the building block hypothesis has previously been expressed on account of the weak theoretical foundations of this hypothesis and anomalies in the empirical record of the simple genetic algorithm. In this paper we focus on a more fundamental cause for skepticism---the extraordinary strength of some of the assumptions undergirding the building block hypothesis. As many of these assumptions have been embraced by the designers of so called ``competent" genetic algorithms, our critique is relevant to an appraisal of such algorithms. We argue that these assumptions are too strong to be acceptable without additional evidence. We then point out weaknesses in the arguments that have been provided in lieu of such evidence.

 


Two Remarkable Computational Competencies of the Simple Genetic Algorithm

Download latest revision

Abstract:  Since the inception of genetic algorithmics the identification of computational efficiencies of the simple genetic algorithm (SGA) has been an important goal. In this paper we distinguish between a computational competency of the SGA---an efficient, but narrow computational ability---and a computational proficiency of the SGA---a computational ability that is both efficient and broad. Till date, attempts to deduce a computational proficiency of the SGA have been unsuccessful. It may, however, be possible to infer a computational proficiency of the SGA from a set of related computational competencies that have been deduced. With this in mind we deduce two computational competencies of the SGA. These competencies, when considered together, point toward a remarkable computational proficiency of the SGA. This proficiency is pertinent to a general problem that is closely related to a well-known data-mining problem at the cutting edge of computational genetics.

 


On the Workings of Genetic Algorithms: The Genoclique Fixing Hypothesis

Download latest revision

Download full version (with animations)  (Note: ~92Mb)

Abstract:   We recently reported that the simple genetic algorithm (SGA) is capable of performing a remarkable form of sublinear computation which has a straightforward connection to the general problem of identifying interacting attributes in data-mining. In this paper we explain how the SGA can leverage this computational proficiency to perform efficient adaptation on a broad class of fitness functions. Based on the relative ease with which a practical fitness function might belong to this broad class, we submit a new hypothesis about the workings of genetic algorithms, and explain why our hypothesis is superior to the building block hypothesis. By way of empirical validation for our hypothesis we present the results of an experiment in which the use of a simple mechanism called clamping dramatically improved the performance of an SGA with uniform crossover on large randomly generated instances of the MAX 3-SAT problem.

 

See also: Latest draft of my dissertation