Hyperclimbing, Genetic Algorithms, and Machine Learning

I’ve identified a promising stochastic search heuristic, called hyperclimbing, for large-scale optimization over massive 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. If 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.

Hyperclimbing, Genetic Algorithms, and Machine Learning

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. Continue reading “Back to the Future: A Science of Genetic Algorithms”

Back to the Future: A Science of Genetic Algorithms

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 \ell as input and returns a real value as output.

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 \ell which specifies the location of  four loci—let’s call them A, B, C, D—of an input bitstring that matter in the determination the bitstring’s fitness. These four loci are said to be pivotal. Continue reading “Red Dots, Blue Dots”

Red Dots, Blue Dots

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.

[Update Jan 27, 2013: SpeedyGA.py is a port of SpeedyGA to Python]

SpeedyGA v1.3