GAFest
CSE Deptartment
UC - San Diego
4 May 1998
SGOPT: A C++ Library of Stochastic Global Optimization Algorithms
William E. Hart
Applied and Numerical Mathematics Department
Sandia National Laboratories
wehart@cs.sandia.gov
Abstract:
SGOPT is a library of general global optimization algorithms that is being
developed at Sandia National Laboratories. This library
utilizes an object-oriented design which allows the
flexible construction of algorithmic hybrids between global and local search
methods. A main focus of the initial development of SGOPT was genetic
algorithms and Monte Carlo sampling, including parallel versions of these
methods. The library is currently being expanded to include a variety
of other general methods like clustering methods and simulated annealing.
This talk will describe the basic design and capabilities of SGOPT.
Several algorithmic capabilities will be highlighted, including
evolutionary hybrids with local search, pattern search methods and
evolutionary pattern search.
Sample Complexity of Model-based Search
Chris Rosin
The Scripps Research Inst.
crosin@scripps.edu
Abstract:
This talk discusses the problem of searching a domain for points that
have a desired property, in the case where the objective function that
determines the properties of points is unknown and must be learned
during search. A parallel to PAC learning theory is used to reason
about the sample complexity of this problem. The learner queries the
true objective function at selected points, and uses this information
to choose models of the objective function from a given hypothesis
class that is known to contain a correct model. These models are used
to focus the search on more promising areas of the domain. The goal
is to find a point with the desired property in a small number of
queries. An analog to VC dimension, needle dimension, is defined to
be the size of the largest sample in which any single point could have
the desired property without the other points' values revealing this
information. An upper bound shows that sample complexity of
model-based search is linear in needle dimension for a natural type of
search protocol, and a lower bound shows this is close to optimal for
a class of constrained problems.
Local Search Deception
Mark Land
Cognitive Computer Science Research Group
CSE Department
UC San Diego
mland@cs.ucsd.edu
Abstract:
It has by now been observed many times that the addition of local
search to a GA can offer a substantial benefit in terms of solution
quality and speed of search. There are several mechanisms by which
local search can affect GA dynamics. I will examine one of these
mechanisms, improved reliability of sampling, in the context of
nonLamarckian evolution, where it is most easily isolated. Intuitions
will be given about when local search should most helpful, and when it
can be harmful. I will then present experimental results on a pair
of related functions, one of which is 'LS-deceptive', and discuss attempts
to develop an LS-deceptiveness measure.
Developmental Sampling
Richard K. Belew
Cognitive Computer Science Research Group
CSE Department
UC San Diego
rik@cs.usd.edu
Abstract:
Typical bit-string representations suggest a Hamming
distance measure over the space of potential solutions
searched by an evolutionary algorithm (EA). When simple
mutation operators are applied to these representations,
there is a natural and relatively direct characterization of
how populations of samples change over time, but when
long-distance, "macro-mutations" are applied and especially
when recombination is exploited such characterizations
become much more difficult. Genomic analysis (e.g., BLAST)
often assumes an "edit distance" model of the distance of
one sequence from another that makes assumptions about the
application of genetic operators and their frequency. This
talk will attempt to apply a similar analysis to describe
the sampling behavior of developmental
representations; i.e., those in which simple representations
become both phylogenetic and ontogenetic precursors for
subsequently embellished ones.
The Race, the Hurdle, and the Sweet Spot:
Three Keys to the Design of Competent, Selectorecombinative Genetic Algorithms
David E. Goldberg
Department of General Engineering
University of Illinois at Urbana-Champaign
deg@uiuc.edu
(Currently on sabbatical at Stanford Univ., Medical Informatics)
Abstract:
Much progress has been made in selectorecombinative genetic algorithm (GA)
design methodology, design theory, and design, but much work in GA
theory, implementation, and practice continues without benefit of these
ideas. This talk captures the essence of these relatively new ideas in GA
design by focusing on (1) the {\it race} between selection and innovation
(mixing), (2) the {\it sweet spot} of a GA on its {\it control map}, and
(3) the fundamental {\it hurdle} to obtaining competent GA performance---the
solution of boundedly hard problems, quickly, reliably, and accurately.
Theoretical and computational results show that simple GAs in common use
are severely limited, but that these limitations can be overcome when
the hurdle is cleared. Theoretical and experimental results from three
different GAs that successfully overcome the hurdle are displayed,
suggesting that well-designed GAs may be subquadratic in a probably
approximately correct sense (PAC) sense.