Forum for AI: David Goldberg/University of Illinois at Urbana-Champaign The Key to Speed: How Supermultiplicative Speedups Enable the Optimization of Very Large Hard Problems in ACES 2.302

Contact Name: 
Jenna Whitney
Feb 24, 2006 11:00am - 12:00pm

There is a signup schedule for this event.


aker Name/Affiliation: David Goldberg/University of Illinois at Urbana-Cha


Talk Title: The Key to Speed: How Supermultiplicative Speedu

ps Enable the Optimization of Very Large Hard Problems


February 24 2006 at 11:00 a.m.

Location: ACES 2.302


Risto Miikkulainen

Talk Abstract:
Genetic algorithms (GAs)--searc

h procedures based on the
mechanics of natural selection and genetics--

have been used
across the spectrum of human endeavor especially in pro

that defy solution by traditional methods of search optimization

and machine learning. The folklore of GAs suggests that
they can

often be effective performers but they are rarely
considered to be spe

ed demons and some authors complain
that they are notoriously slow. Re

cent work has established
a design theory and methodology for competent
algorithms that solve large classes of hard problems qui

reliably and accurately--and those studies have been augmented by a growing literature GA efficiency enhancement that explores
a var

iety of methods for speeding GA solutions. The news
of competence and e

fficiency study has been good suggesting
that nearly decomposable prob

lems can be solved in subquadratic
times and that efficiency enhancemen

t modes such as parallelism
time continuation hybridization and eval

uation relaxation
can be combined to yield multiplicative speedups over
GAs without efficiency enhancement. These results are welcom

in and of themselves but a number of recent studies have

through the multiplicative barrier to achieve supermultiplicative

ups to hard problems through the tight integration
of model building an

d efficiency enhancement. These results
are just now being understood a

nd fully explored but they
offer the promise of optimizing very large
hard problems
day in and day out. This talk explores the foundations

principles and promise of supermultiplicative speedup of
procedures. Examples will be given of the integration
of distribution

estimation with evaluation relaxation and
time continuation and a fina

l discussion will suggest how
these results are leading to the near-ter

m possibility of
using these techniques to effectively optimize problem

with 100s of millions or even billions of variables.


David E. Goldberg (BSE 1975 MSE 1976 PhD 1983 Civil

eering University of Michigan Ann Arbor) is the Jerry
S. Dobrovolny D

istinguished Professor of Entrepreneurial
Engineering at the University
of Illinois at Urbana-Champaign
(UIUC) and director of the Illinois Ge

netic Algorithms Laboratory
Between 1976
to 1980 he held a number of positions at Stoner Associate

of Carlisle PA including Project Engineer and Marketing

. Following his doctoral studies he joined the Engineering
Mechanics fa

culty at the University of Alabama Tuscaloosa
in 1984 and he moved t

o the University of Illinois in 1990.
Professor Goldberg was a 1985 rec

ipient of a U.S. National
Science Foundation Presidential Young Investi

gator Award
and in 1995 he was named an Associate of the Center for Advanced Study at UIUC. He was founding chairman of the
Society for Genetic and Evolutionary Computation

/) and his book Genetic Algorithms
in Search Optimization and Machine
Learning (Addison-Wesley
1989) is one of the most widely cited texts

in computer
science. His research focuses on the design analysis and

application of genetic algorithms-computer procedures based
on the

mechanics of natural genetics and selection-and other
innovating machin

es. His recent book The Design of Innovation:
Lessons from and for Com

petent Genetic Algorithms (
discusses (1)

how to design scalable genetic algorithms
and (2) how such procedures a

re similar to certain processes
of human innovation.