May 06, 1994

From genetic algorithms to efficient optimization

Yuret, D. (1994) MS Thesis. Massachusetts Institute of Technology. A.I. Technical Report No. 1569 (PDF,HTML)

I developed an optimization algorithm known as Dynamic Hill Climbing (DHC) with Michael de la Maza, which is the subject of my MS Thesis, also AI Technical Report 1569. Below is the abstract and a list of papers on DHC.

Abstract: The work described in this thesis began as an inquiry into the nature and use of optimization programs based on ``genetic algorithms.'' That inquiry led, eventually, to three powerful heuristics that are broadly applicable in gradient-ascent programs: First, remember the locations of local maxima and restart the optimization program at a place distant from previously located local maxima. Second, adjust the size of probing steps to suit the local nature of the terrain, shrinking when probes do poorly and growing when probes do well. And third, keep track of the directions of recent successes, so as to probe preferentially in the direction of most rapid ascent.
These algorithms lie at the core of a novel optimization program that illustrates the power to be had from deploying them together. The efficacy of this program is demonstrated on several test problems selected from a variety of fields, including De Jong's famous test-problem suite, the traveling salesman problem, the problem of coordinate registration for image guided surgery, the energy minimization problem for determining the shape of organic molecules, and the problem of assessing the structure of sedimentary deposits using seismic data.

Related publications:

Full post...