From Genetic Algorithms
To Efficient Optimization
-
Deniz Yuret (1994)
( PS,
HTML )
-
From genetic algorithms to efficient optimization. Technical Report
1569, MIT AI Laboratory.
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.