Hyperclimbing and Decimation
In recent years, probabilistic inference algorithms such as survey propagation and belief propagation have been shown to be remarkably effective at tackling large, random instances of SAT, and other combinatorial optimization problems that lie beyond the reach of previous approaches. These inference algorithms belong to a class of techniques called decimation strategies. Decimation strategies monotonically reduce the size of a problem instance by iteratively fixing partial solutions (partial variable assignments in the case of SAT).
The generative fixation hypothesis essentially states that genetic algorithms work by efficiently implementing a decimation strategy called hyperclimbing.
Hyperclimbing, Genetic Algorithms, and Machine Learning
I’ve identified a promising stochastic search heuristic, called hyperclimbing, for large-scale optimization over huge attribute product spaces (e.g., the set of all binary strings of some length N, where N is very large) with rugged fitness functions. Hyperclimbing works by progressively limiting sampling to a series of nested subsets with increasing expected fitness. At any given step, this heuristic sifts through vast numbers of coarse partitions of the subset it “inhabits”, and identifies ones that partition this set into subsets whose expected fitness values are significantly variegated. Because hyperclimbing is sensitive, not to the local features of a search space, but to certain more global statistics, it is not susceptible to the kinds of issues that waylay local search heuristics.
The chief barrier to the wide and enthusiastic use of hyperclimbing is that it seems to scale very poorly with the number of attributes. When one heeds the seemingly high cost of applying hyperclimbing to large search spaces, this heuristic quickly looses its shine. A key conclusion of my doctoral work is that this seemingly high cost is illusory. I have uncovered evidence that strongly suggests that genetic algorithms can implement hyperclimbing extraordinarily efficiently.
As readers of this blog probably know, genetic algorithms are search algorithms that mimic natural evolution. These algorithms have been used in a wide range of engineering and scientific fields to quickly procure useful solutions to poorly understood (i.e. black-box) optimization problems. Unfortunately, despite the routine use of genetic algorithms for over three decades, their adaptive capacity has not been adequately accounted for. Given the evidence that genetic algorithms can implement efficient hyperclimbing, I’ve proposed a new explanation for the adaptive capacity of these algorithms. This new account—the generative fixation hypothesis—promises to spark significant advances in the fields of genetic algorithmics and discrete optimization.
The discovery that hyperclimbing is efficiently implementable also promises to have a non-negligible impact on the ecology of machine learning research. Optimization and machine learning are, after all, intimately related. Overlooking a few exceptions, the practice of machine learning research, can be characterized as the effective reduction of difficult learning problems to optimization problems for which efficient algorithms exist. In other words, the machine learning problems that can effectively be tackled are in large part those that can in practice be reduced to optimization problems that can be tackled efficiently. Currently, this largely limits the class of tractable machine learning problems to the class of learning problems that can in practice be reduced to convex optimization problems [1] . The identification of general-purpose non-convex optimization heuristics with efficient implementations (e.g. hyperclimbing), thus, has the potential to significantly extend the reach of machine learning.
For a description of hyperclimbing, and evidence that genetic algorithms can implement this heuristic efficiently, please see my dissertation
[1] Kristin P. Bennett and Emilio Parrado-Hernandez. The interplay of optimization and machine learning research. Journal of Machine Learning Research, 7:1265–1281, 2006.
Google Group for Generative Fixation
The generative fixation hypothesis now has a Google group—a place to ask questions and share your insights. If you’re intrigued by the idea of generative fixation, please sign up.
Dissertation Deposition
I deposited my dissertation today.
Click here to see the final version (single spaced for easy reading).
Back to the Future: A Science of Genetic Algorithms
From the preface to my dissertation:
The foundations of most computer engineering disciplines are almost entirely mathematical. There is, for instance, almost no question about the soundness of the foundations of such engineering disciplines as graphics, machine learning, programming languages, and databases. An exception to this general rule is the field of genetic algorithmics, whose foundation includes a significant scientific component.
The existence of a science at the heart of this computer engineering discipline is regarded with nervousness. Science traffics in provisional truth; it requires one to adopt a form of skepticism that is more nuanced, and hence more difficult to master than the radical sort of skepticism that suffices in mathematics and theoretical computer science. Many, therefore, would be happy to see science excised from the foundations of genetic algorithmics. Indeed, over the past decade and a half, much effort seems to have been devoted to turning genetic algorithmics into just another field of computer engineering, one with an entirely mathematical foundation.
Broadening one’s perspective beyond computer engineering, however, one cannot help wondering if much of this effort is not a little misplaced. Read the rest of this entry »
Red Dots, Blue Dots
In this blog entry I’d like to showcase just one of a number of remarkable findings that comprise the basis for the generative fixation hypothesis—a new explanation for the adaptive capacity of recombinative genetic algorithms.
Consider the following stochastic function which takes a bitstring of length 
fitness(bitstring)
accum = 0
for i = 1 to 4
accum = accum + bitstring[pivotalLoci[i]]
end
if accum is odd
return a random value from normal distribution N(+0.25,1)
else
return a random value from normal distribution N(-0.25,1)
end
The variable pivotalLoci is an array of four distinct integers between 1and
Thanks!
Thanks everyone for your good wishes. My defense went smoothly, and I got some excellent suggestions from my committee.
Dissertation Defense
My dissertation defense is scheduled for Friday June 19, 2009. I’m currently working on my presentation. Wish me luck :-)
SpeedyGA v1.3
Download the latest version of SpeedyGA (version 1.3) from Matlab Central’s File Exchange or from Google Code.
Version 1.3 of speedyGA is faithful to the specification for a simple GA given on page 10 of Melanie Mitchell’s book “Introduction to Genetic Algorithms”; that is if none of the bells and whistles (mask repositories, stochastic universal sampling, and sigma scaling) are used. SpeedyGA has also been changed from a function to a script. This makes it easier to inspect variables and plot data after a run has completed.
