Evolutionary Algorithms Workshop, October 21-25, 1996

During the week of October 21, the University of Minnesota Supercomputing Institute and Institute for Mathematics and its Applications (IMA) hosted a Workshop on Evolutionary Algorithms, held on the East Bank of the University campus. There were 66 registrants from 20 states and 9 countries, 19 plenary presentations, numerous informal discussion periods, and a banquet. The talks can be grouped roughly into applications and theory.

Applications

The first talk in the applications category was a survey of several genetic algorithm (GA) case studies by David Levine from the Argonne, Illinois offices of the Boeing Company. An example from ligand-receptor docking in biochemistry involved a 297-atom drug candidate binding to a 1564-atom protein. The problem was studied on 101 processors of an IBM SP2 with a parallel speedup of 63. A second example, involving collaboration with Paul Bash of Argonne National Laboratory and L. Ho of Yale University, involved parameter fitting in quantum chemistry to obtain system-specific parameters (SSP-also called SRP for specific range parameters) for an AM1-type ("Austin-method 1") model of small molecules. A third example involved reverse-engineering an integrated circuit. Levine also discussed the use of symmetric multi-processor (SMP) machines for island-based GAs, the advantages of coding with MPI communicators, and a general purpose parallel genetic algorithm library called PGAPack, callable from FORTRAN or C.

David Davis of Tica Technologies Inc. in Cambridge, Massachusetts described applications of GAs to the optimization of telecommunications networks. Shunji Matsumoto of Fujitsu Limited in Chiba, Japan and Peter Ross of the University of Edinburgh in Scotland presented applications of GAs in scheduling problems. A theme that emerged strongly in these talks is that cost-effective GAs have been and can be designed for practical applications by empirical means. "Theory lags behind," said one speaker, but we do not have to wait for it to catch up to solve commercial problems. In addition to scheduling, Ross discussed time tabling, pipe routing, and a host of other applications, including the optimization of catching, delivering, and slaughtering chickens raised by a meat distributor.

Emmanuel Falkenaur of the Free University of Brussels discussed applications of GAs to combinatorial problems. He found theory more useful, especially in its pointing to crossover as the most potent force in a GA. He described the advantages of Grouping GAs and illustrated their use for bin packing, load balancing, and optimizing economies of scale.

Martin Wildberger of the Electric Power Research Institute in Palo Alto, California presented several GA applications, including one in collaboration with Tariq Samad and Steve Harp of Honeywell in Minneapolis for GA optimization of a neural network based on heat rate data from a nuclear power plant.

Rogene Eichler West of the University of Minnesota discussed the application of evolutionary algorithms to parameter selection in models of biologically realistic neurons.

Zbigniew Michalewicz of the University of North Carolina discussed evolutionary algorithms for constrained parameter optimization.

Robert Meyer of the University of Wisconsin showed that GAs are effective for optimal constrained domain decomposition problems that arise in network design and analysis. John Clymer of John R. Clymer and Associates in Placentia, California discussed context-sensitive methodology for complex adaptive analysis of vehicle traffic control.

Theory

The theory talks covered genetic algorithms, evolutionary programming (EP), and evolutionary strategies (ES).

There were five theoretical talks on genetic algorithms. Darrell Whitley of Colorado State University started the workshop with an overview of GAs, focusing on selection, recombination, and mutation strategies. He was the first of many speakers to address the No Free Lunch (NFL) theorem, which states that all search algorithms are equivalent when compared over all possible discrete functions. One participant pointed out in a later discussion that the set of interesting functions has zero measure on the set of all functions, and a theme that emerged from the workshop is that the best algorithm for a given problem can generally be engineered only by building in nonartificial intelligence about the nature of the application of interest.

David Goldberg of the University of Illinois at Urbana presented his perspective on the issue of efficiency. The basic problem of GAs that he addressed is that population sizes must grow exponentially for hard problems. He advocated the empirical design of genetic algorithms to find the "sweet spot" in the 2-D strategy parameter space of mixing probability (achieved, for example, by crossover) vs. selection pressure. Goldberg placed special emphasis on the balance between critical innovation and takeover time; one tries to allow enough time for linkage recognition before the entire population is taken over by individuals optimized with the linkages recognized so far. One hopes to develop competent GAs by creative combinations of building blocks.

John Holland of the University of Michigan emphasized several issues that one should take into consideration, including time to discovery (how long do we have to wait for the first occurrence of a genotype?), NFL, premature convergence due to hitchhiking, the danger of relying on inversion if less than 10,000 generations are sampled, and the possibility that the error cone diverges exponentially in which case almost all offspring trajectories may be below average. The latter phenomenon was related to the "Petersburg Paradox," and to the best of the knowledge of this reporter, none of the participants suggested calling it the Inverse Lake Wobegon Phenomenon.

Michael Vose of the University of Tennessee gave a mathematical perspective on GAs, and Kenneth De Jong of George Mason University in Fairfax, Virginia itemized the choices one faces when parallelizing GAs. De Jong concluded that no clear winner has emerged from studies of parallelization strategy.

Heinz Mühlenbein of the German National Research Center for Information Technology presented a theory of the breeder GA, which is designed according to the science of livestock breeding. Critical new elements in the theory include response to selection and realized heritability.

The theory of EP was presented by David Fogel of Natural Selection Inc. in La Jolla, California. Fogel emphasized the simulation of evolution as a learning process to generate artificial intelligence. The goal is to optimize the variation operator by looking at the distribution function.

There were two back-to-back talks on the ES perspective, by Hans-Paul Schwefel and Thomas Bäck of the University of Dortmund and Informatik Centrum Dortmund in Germany. Schwefel emphasized learning on the fly by optimizing genetically controlled strategy parameters as well as objective variables. He illustrated this with self learning of a variable metric controlling linearly correlated mutations, which is analogous to regulatory genes controlling mutability. He pointed out that if K represents the upper limit for the generational life span of a parent, the optimum value is empirically bigger than one and less than infinity, but the former is better than the latter. Schwefel also emphasized the desirability of multiple-criteria decision making. Bäck continued with a discussion of self-adaption of strategy parameters as applied to GAs.

Concluding Remarks

The Institute is grateful to Darrell Whitley, Michael Vose, David Davis, and Ken De Jong for organizing the Workshop.

The workshop was a successful mixing of theoretical and practical cultures and it engendered a higher than average amount of discussion during and after the talks. The workshop also gets high marks in that only one speaker (who shall remain nameless) succumbed to making jokes about Minnesota weather. The next joint workshop of the Supercomputing Institute and the Institute for Mathematics and its Applications will be focused on mathematical issues in drug design and will take place in April, 1997 (see Rational Drug Design Workshop for details).

In This Issue:

International Conference on Parallel Computing

Positron Emission Tomography

Workshop on Modeling in Biochemical Engineering

Evolutionary Algorithms Workshop

Upcoming Workshop on Rational Drug Design

Seminar Synopses

Research Reports