ICGA-97 will begin with three parallel sessions of tutorials on Saturday. Conference attendees may attend up to three tutorials (one from each session) for a supplementary fee (see registration form).
Click on any title to go to the associated abstract.
Some Alternative Viewpoints
Basic Genetic Algorithm
Messy Genetic Algorithms
Self-adaptation in Evolutionary
Advanced Genetic Algorithm
Niching methods and
for CAD of Integrated Circuits
Ian Parmee Plymouth Engineering Design Centre - UK
The objective of the proposed tutorial is to illustrate the utility of various characteristics of evolutionary and adaptive search (ES/AS) algorithms during each stage of the design process. There are many examples of the application of evolutionary and adaptive search algorithms to specific well-defined problems from the engineering design domain . Little research effort, however, has been expended in moving from these well-defined problems to investigate the generic integration of ES/AS with each stage (ie conceptual, embodiment and detailed) of the engineering design process as a whole. The key word here is integration as opposed to application where a major requirement for success is the development of systems that can capture design heuristics through extensive designer interaction. Evolutionary and adaptive search techniques and strategies best suited to the differing requirements of the various design stages will be fully described and their performance illustrated upon real- world design problems.
Some knowledge of Evolutionay Computing would be useful, though not required. The tutorial, especially the design related aspects, should be of interest to a wide range of delegates irrespective of their level of skills.
Pete Angeline Natural Selection Inc. - NY, US
Genetic programming is a popular form of evolutionary computation that evolves symbolic structures often interpreted as computer programs. After a brief introduction, this tutorial will concentrate on the many distinct techniques used to augment the basic genetic programming method to address a variety of issues. Topics include methods for creating modular programs, methods for minimizing evolved program size, evolving machine code, alternative evolvable representations, and various augmentations to the basic subtree manipulation operators. Special emphasis will be given to adaptive and self-adaptive techniques. Published applications that employ the various techniques will be provided where possible.
No a priori knowledge required.
Hillol Kargupta Los Alamos National Laboratory - NM, US
Messy genetic algorithms (mGAs) are search algorithms that pay serious attention to linkage learning. They are motivated by the observation that unless linked sets of genes are correctly detected, neither crossover nor mutation can be used for efficient black box search. This tutorial will review early work in mGAs and lay the foundation in the context of the SEARCH (Search Envisioned As Relation and Class Hierarchizing) framework. The traditional perspective of linkage learning will be presented in an extended context. This will be followed by a discussion on possible mechanisms of linkage learning using the transformations DNA->RNA->Protein in natural evolution. Some recent experimental results will be presented. Finally we shall discuss potential applications in data mining, distributed AI, and optimization.
No a priori knowledge is required, except familiarity with elementary notions of set and probability theory.
Michael Vose University of Tenessee - US
This tutorial begins from the foundation laid out by Soraya Rana's
tutorial (I.B: Basic GA theory). The first objective is to introduce a
formal framework in which results about GAs can be obtained in a mathematically
rigorous way. In passing, a few examples will be given indicating why this
may be desirable/necessary.
The framework is rather flexible, encompassing a wide variety of generational style GAs as well as many non-genetic search paradigms. It is Markovian in its stochastic details and dynamical systems like in how the underlying bias of the stochasticity is dealt with. A specific goal is to be able to say, exactly, how a GA behaves and to uncover what it is, from a mathematical perspective, that determines its behavior.
Next, we'll illustrate a way in which the formalism can be reduced, in a provable way, to a more manageable form (at the price of having to settle for a restricted class of objective functions). The tutorial will close with an outline of what sorts of qualitative results have been established (i.e., proved) and also include some empirical data. A brief mention of chaotic behavior is included, together with recent results concerning complex long period limit cycles.
A good knowledge of basic GA theory (e.g. as given by Soraya Rana's tutorial above) is necessary.
Sam Mahfoud Advanced Investment Technology - FL, US
Niching methods extend evolutionary algorithms (EAs) to domains that require the location or maintenance of multiple solutions. Such domains include classification and machine learning, multimodal function optimization, multiobjective function optimization, and simulation of complex and adaptive systems. This tutorial covers popular niching EAs, the existing theory of niching, and specific applications in machine learning, financial forecasting, artificial life, multiobjective optimization, and multimodal function optimization.
Basic knowledge of Genetic Algorithms will be assumed.
Takashi Gomi Applied AI Systems, Inc. - ON, CA
The field of Evolutionary Robotics (ER) emerged as an important recent addition to intelligent robotic research. It currently deals mostly with the evolution of control software for mobile robots with the goal of developing competent robots that perform tasks well adapted to the requirements in a given operational environment. A survey of key Evolutionary Robotic research activities conducted worldwide today will be given, including research activities in such places as Sussex University, Stanford University, Case Western Reserve University, University of Zurich, Sterling University, (UK), Massachusetts Institute of Technology (MIT), and Ecole Polytechnique Federale de Lausanne (EPFL). The latest information on Evolutionary Hardware will be included. The tutorial highlights the principles of evolving complete software for intelligent robots; differences in the ways various methods of Evolutionary Computation are applied to create robots which evolve in their operational environment; recent noteworthy achievements in the field; and prognosis for the application of the technology to industry, business, and life in general in the near future. Applications of evolutionary computation to software robots or softbots to cope with general information processing requirements will be briefly discussed. Such robots are being considered in the U.S. as a solution to the massive software needed for Information Superhighway applications.
A good knowledge in EC is required. Beginners in robotics are welcome.
Colin Reeves Coventry University - UK
The genetic algorithm (GA), as the very name suggests, has most often been viewed from a biological perspective. The metaphors of natural selection, cross-breeding and mutation have been helpful in providing a framework in which to explain how and why they work. However, most practical applications of GAs are in the context of optimization, where alternative approaches may (and indeed in many cases do) prove more effective. In attempting to understand how GAs function as optimizers, several alternative viewpoints have been suggested. This tutorial will cover two of these in some detail. The first views GAs as as a form of sequential experimental design, the other as a generalization of neighbourhood search methods. It is hoped that participants will thereby gain some understanding of some other fields of research of relevance to optimization, and of how they relate to genetic algorithms.
A basic knowledge of GA theory (schema-processing) will be assumed, but the level of treatment will not be mathematically advanced.
Jeff Horn Northern Michigan University - US
Many, if not most, optimization problems have multiple objectives. Historically, multiple objectives have been combined ad hoc to form a scalar objective function, usually through a linear combination (weighted sum) of the multiple attributes, or by turning objectives into constraints. Evolutionary computation (EC) methods, however, are uniquely suited to deal with multiple objectives explicitly: since multiple, conflicting objectives imply multiple solutions (i.e., alternative compromises), the population based approach of EC can be used find the entire optimal "tradeoff set" simultaneously. Applying EC to multiobjective optimization addresses two difficult problems: (1) searching intractably large and complex spaces and (2) deciding among multiple objectives. Both of these problems are open areas of research, but relatively little work has been done on the COMBINED problem of searching large spaces to meet multiple objectives. We review the recent explosion of successful multiobjective EC approaches, categorizing them into a logical hierarchy of alternatives. We illustrate the common issues in implementing, tailoring, and applying multiobjective evolutionary algorithms by examining one simple algorithm in some detail: the niched Pareto GA. We investigate its ability to find and maintain a diverse ``Pareto optimal population'' on two artificial problems and an open problem in groundwater monitoring.
Good knowledge of (at least one type of) Evolutionary Algorithms is necessary. No knowledge about multi-objective optimization is required.
Gusz Eiben Leiden University -- NL
EAs have been primarily developed and applied for optimization and machine learning tasks. Their ability to handle constraints have been limited and although constrained optimization problems (with continuous domains) have received considerable attention, constraint satisfaction problems (with discrete domains), where no optimization criterion is given in the problem description, is a field that has began its development only recently. EAs that have a `basic instinct' to optimize are for the first glance not applicable to such problems. We will give a formal characterization of problem types, from pure optimization to constraint satisfaction problems (CSPs) and points out the (im)possibilities of handling different problem types by EAs. Thereafter we will concentrate on the main topics of the tutorial: solving CSPs by EAs. We will review existing approaches to this area, guided by recent publications. Examples and reported figures on EA performance will be given to illustrate the practicability of the proposed techniques. Later on, works of various researchers will be categorized by distinguishing the main features of their approach. This will lead to a systematic overview of what had been done. Finally, we will sketch open issues and promising areas of further research.Basic knowledge of Evolutionary Algorithms will be assumed.
Edmund Ronald Ecole Polytechnique - FRNeural Networks (NNs) are now well a established paradigm both in academic and industrial research. However, their optimization, when it comes to actually design a NN, asks more questions than it solves: from the choice of the type of NN (multi-layered Perceptrons, recurrent NN, Kohonen maps, ...) to that of its topology and of the different weights on its connections.
Rolf Drechsler Albert-Ludwigs-University Freiburg - DE
An increasing number of successful applications of Evolutionary Algorithms
(EAs) within Computer Aided Design (CAD) of Integrated Circuits (ICs) is
reported in the literature. The problems dealt with in this field consist
of sequences of sub-problems, which are characterized by being NP-hard,
large and mutually dependent. This very high level of complexity should
make the EA a well suited approach, at least in principle.
However, the EA is of practical interest to the CAD community if and only if it is competitive to the existing approaches with respect to performance. With this fact as the starting point, the purpose of this tutorial is to discuss how to develop high-performance EAs for CAD of ICs.
After reviewing a number of recent, performance competitive EAs for key problems in CAD of ICs, the common characteristics of these algorithms are discussed. They all exploit problem specific knowledge in various ways or are integrated with other heuristics. We also discusses performance evaluation principles. To make an impact, it is crucial that performance is evaluated using the measures commonly applied in the CAD field. The practical implications hereof for EA-based applications are addressed.
Return to ICGA-97 home page.