Home › UTCS Calendar

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
Date: 
Feb 24, 2006 11:00am - 12:00pm


There is a signup schedule for this event.

Spe

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

mpaign

Talk Title: The Key to Speed: How Supermultiplicative Speedu

ps Enable the Optimization of Very Large Hard Problems

Date/Time:

February 24 2006 at 11:00 a.m.

Location: ACES 2.302

Host:

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

blems
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
GAs--genetic
algorithms that solve large classes of hard problems qui

ckly
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
competent
GAs without efficiency enhancement. These results are welcom

e
in and of themselves but a number of recent studies have
broken

through the multiplicative barrier to achieve supermultiplicative
speed

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
competent
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

s
with 100s of millions or even billions of variables.

Speaker

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

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
(IlliGAL http://www-illigal.ge.uiuc.edu/).
Between 1976
to 1980 he held a number of positions at Stoner Associate

s
of Carlisle PA including Project Engineer and Marketing
Manager

. 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
International
Society for Genetic and Evolutionary Computation
(http://www.isgec.org

/) 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 (http://www-doi.ge.uiuc.edu/)
discusses (1)

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

re similar to certain processes
of human innovation.