文档介绍：MASSA CHUSETTS INSTITUTE OF TECHNOLOGY
AR TIFICIAL INTELLIGENCE LABORA TOR Y
. T ec hnical Rep ort No. 1569 Ma y ,1994
F rom ic Algorithms
T o Ecien t Optimization
Deniz Y uret
This publication can b e retriev ed b y anon ymous ftp to . edu.
Abstract
The w ork describ ed in this thesis b egan as an inquiry in to the nature and use of optimization
programs based on \ic algorithms." That inquiry led, ev en tually , to three p o w erful
heuristics that are broadly applicable in gradien t-ascen t programs: First, remem ber the
lo cations of lo cal maxima and restart the optimization program at a place distan tfrom
previously lo cated lo cal maxima. Second, adjust the size of probing steps to suit the lo cal
nature of the terrain, shrinking when prob es do p o orly and gro wing when prob es do w ell.
And third, k eep trac k of the directions of recen t esses, so as to prob e preferen tially in
the direction of most rapid ascen t.
These algorithms lie at the core of a no v el optimization program that illustrates the p o w er
to b e had from deplo ying them together. The ecacy of this program is demonstrated
on sev eral test problems selected from a v ariet y of elds, including De Jong's famous test-
problem suite, the tra v eling salesman problem, the problem of co ordinate registration for
image guided surgery , the energy minim ization problem for determining the shap e anic
molecules, and the problem of assessing the structure of sedimen tary dep osits using seismic
data.
c
Cop yrigh t
Massac h usetts Institute of T ec hnology ,1996
This rep ort describ es researc h done at the Arti cial In telligence Lab oratory of the Massac h usetts Institute
of T ec hnology . Supp ort for this researc hw as pro vided in part b y the Adv anced Researc h Pro jects Agency
of the Departmen t of Defense under Oce of Na v al Researc hcon tract N00014-91-J-4038.
F rom ic Algorithms
T o Ecien t Optimizati on
b y
Deniz