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


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.


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


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


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

(Currently on sabbatical at Stanford Univ., Medical Informatics)


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.