Trying Out Different Angles of Approach
I’m trying out different angles to take on my doctoral work when submitting it to AI and ML journals. Here’s one that shows promise:
| The Hyperclimbing Hypothesis: An explanation for the adaptive capacity of genetic algorithms with uniform crossover
It is generally accepted that the adaptive capacity of genetic algorithms with uniform crossover (UGAs) cannot be explained within the rubric of the building block hypothesis. Nevertheless, to date, an alternate explanation has not been proposed. We describe a promising non-local stochastic search heuristic, called hyperclimbing, for optimizing over attribute product spaces (e.g., the set of all binary strings of some fixed length) with rugged objective functions. Hyperclimbing works by decimating the search space, i.e. by progressively limiting sampling to a series of nested subsets. At each step, this heuristic sifts through potentially 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. The hyperclimbing hypothesis holds that UGAs work by implementing hyperclimbing extraordinarily efficiently. The evidence for this hypothesis comes from the use of a novel analytic technique involving the exploitation of “algorithmic symmetry”. In addition to this evidence, we present the results of a relatively demanding test of validity—one involving the application of a UGA with a simple tweak to large, random instances of the MAX-3SAT problem. |
The supporting evidence, as well as the test of validity mentioned above can be found in my dissertation.
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.
