Coevolution : Turning Adaptative Algorithms upon Themselves

Richard K. Belew and Hugues Juillé

Coevolution has now been observed within natural populations for almost 50 years, and exploited in computer simulations for a decade. Applications of coevolutionary search make it seem that some of the same mechanisms which have allowed natural evolution to achieve the complex living systems we know today can be captured in an algorithmic framework. However, it seems that coevolution has never reached the level of promise that one would have expected following the initial encouraging experiments. Also, subsequent analysis makes it appears that the reasons for successes that have been achieved are not always clearly understood.

The purpose of that workshop is twofold. First, we will compare researchers' views of coevolution and make explicit the important issues associated with the study of coevolution. Our goals are to adopt a shared system of technical definitions, and to then identify classes of problems for which a coevolutionary approach offers a definitive advantage for improving search over other approaches. Underlying this approach is the analysis of the heuristics embedded in coevolutionary frameworks that make them more effective.

Second, we will consider coevolution in the context of open-ended (a.k.a. exogenous, emergent) adaptation. Coevolution has been proposed as the solution to problems like self-learning and the generation of solutions to progressively more difficult problems. But computational learning theory seems to imply intrinsic limits on the effectiveness of any learning algorithm presented with finite data. Should coevolution be considered just one more method for controlling search, or are there opportunities for breakthroughs based on the exploitation of coevolutionary frameworks? Given evidence of coevolutionary "arms-race" in natural environments, what might this say about distributions of "natural" vs. "artificial" training sets?

Further details

Evolutionary Algorithms for Dynamic Optimization Problems

Juergen Branke and Thomas Baeck

Many real-world optimization problems are eventually dynamic. New jobs are to be added to the schedule, the quality of the raw material may be changing, new orders have to be included into the vehicle routing problem etc. In such cases, when the problem changes over the course of the optimization, the purpose of the optimization algorithm changes from finding an optimal solution to being able to contiuously track the movement of the optimum through time. Since in a sense natural evolution is a process of continuous adaptation, it seems straightforward to consider evolutionary algorithms as appropriate candidates for dynamic optimization problems.

Several attempts have been made to modify evolutionary algorithms, to tune them for optimization in a changing environment. It was observed in all these studies, that the dynamic environment requires the evolutionary algorithm to maintain sufficient diversity for a continuous adaptation to the changes of the landscape. Although the interest in evolutionary algorithms for dynamic optimization problems is growing and a number of authors have proposed an even greater number of new approaches, the field lacks a general understanding as to suitable benchmark problems, fair comparisons and measurement of algorithm quality.

The goal of the workshop would be to foster interest in the important subject of evolutionary algorithms for dynamic optimization problems, get together the researchers working on that topic, and to discuss recent trends in the area.

Further details

Optimal Structural Design using Genetic and Evolutionary Computation

Scott Burns

The optimal design of civil engineering structures has been the subject of considerable research activity for many decades. Many aspects of structural optimization are inherently discrete/combinatorial in nature, and defy solution by classical methods. These aspects include topological layout of structural members, member selection from available standard sizes or material types, placement of sensors and actuators for dynamically controlled (smart) structures, selection and orientation of layers or reinforcement in composite structural materials, multi-objective structural design, identification of multiple/alternative optimal designs, selection of support locations, conceptual design, identification of collapse mechanisms, aesthetics in structural design, and life-cycle design.

This workshop will focus on the application of genetic and evolutionary computation to the design of civil engineering structures. Specific issues, in addition to those identified above, include hybrid methods, which combine GA with structural optimization-specific local methods to improve efficiency, constraint handling techniques, and the design of unique genetic operators and schema representations.

This workshop is being co-sponsored by the American Society of Civil Engineers (ASCE) Technical Committee on Optimal Structural Design.

Further details

The Next Ten Years of Scheduling Research

Peter Cowling and Graham Kendall

This workshop will allow those attending to discuss how scheduling research can be advanced in the next ten years. There are many techniques that have been reported in the literature that have produced excellent results when applied to scheduling problems. For example the use of meta-heuristic techniques (such as tabu search and simulated annealing) and evolutionary techniques (such as genetic and memetic algorithms). One emerging research area is to develop heuristics that operate at a higher level of generality than current technology can support. This will involve advances in heuristics, meta-heuristics and an emerging technique tentatively called a hyper-heuristic. Another interesting idea is to use an "adaptive" heuristic. This uses the idea that a scheduling problem can be solved using a heuristic but, for many reasons, this heuristic can lead to solutions which, although, better than previous efforts, can be even better if the heuristic is allowed to adapt as the search progresses. Through this workshop we hope to achieve three main aims: Allow the delegates to learn about some of the latest techniques and ideas that are being applied by leading researchers in the scheduling community. Invite other researchers to present their ideas as to how the field should develop in the next ten years. We are not looking for results of their current research, rather we are looking for new, blue sky ideas that can lead the research in the near future. Promote discussion on these ideas so that the scheduling community as a whole can benefit.

Further details

Memetic algorithms

William Hart, Natalio Krasnogor, and Jim Smith

Memetic algorithms (MAs) are evolutionary algorithms (EAs) that apply a separate local search process to refine individuals (i.e. improve their fitness by hill-climbing). Under different contexts and situations, MAs are also known as hybrid EAs, genetic local searchers, Baldwinian EAs, Lamarkian EAs, etc.

Combining global and local search is a strategy used by many successful global optimization approaches, and MAs have in fact been recognized as a powerful algorithmic paradigm for evolutionary computing. In particular, the relative advantage of MAs over EAs is quite consistent on complex search spaces.

It is the purpose of this workshop to bring together researchers working on the general topic of Memetic Algorithms. This workshop will provide a forum for identifying and exploring the key issues that affect the theory, design and application of MAs.

Further details

The gene expression process in nature extracts the information coded in the DNA in order to generate the phenotype of a living organism. This process includes the production of proteins from the DNA through the construction of mRNA and the subsequent expression during the different developmental stages. It is a very important biological process. It also appears to be very important from the perspective of genetic search. The Gene expression manipulates of the genetic representation. Representation plays an important role in problem solving which is widely acknowledged in many fields such as physics, mathematics, engineering, machine learning, optimization and many others. Representation transformations are often used in these fields for solving problems efficiently. Therefore representation transformations and manipulations in gene expression allude intriguing possibilities.

This workshop will focus on exploring gene expression based on our basic understanding of genetic search, learning, and optimization. The topics of interest include, but are not limited to:

1. Theoretical and experimental analysis of representation transformations offered by the natural gene expression process.
   
2. Relation of gene expression and efficient, scalable evolutionary computation.
3. Design, implementations, and experiments of evolutionary algorithms such as genetic algorithms, genetic programming, evolutionary strategy and other algorithms that are directly motivated by the gene expression process.
   
4. Applications of gene expression-based algorithms.

Further details

Optimization by Building and Using Probabilistic Models (OBUPM) 2001

Martin Pelikan and Kumara Sastry

Algorithms that replace two-parent recombination of genetic algorithms by building and simulating a probabilistic model of promising solutions have received much attention over the past years. The proposed methods have resolved many problems of other evolutionary algorithms and are increasingly used to solve various problem of practical and theoretical importance. Theory was designed to understand the dynamics of the algorithms as well as their limits.

The purpose of this workshop is to:

• review and describe the basic principles of discussed methods
• present recent developments in the covered area of research,
• discuss current problems and future directions of research in this area
• encourage communication among active researchers in the area and other participants.
  

Further details

Evolution of Sensors in Nature, Hardware, and Simulation

Daniel Polani, Thomas Uthmann, and Kerstin Dautenhahn

In natural evolution one finds impressive examples for the principle of exploiting new sensory channels and making use of the implicit information they encode. Different senses have emerged in a vast multitude of variants, often utilizing organs not originally "intended" for the purpose they serve at present. Motivated by these observations, the topic of sensor evolution is becoming a very modern and promising direction of research between biology, robotics and Artificial Life. The workshop strives at insights into biological strategies to access new information channels, at developing new concepts for design of sensors for flexible and adaptive autonomous agents and an understanding of the relationship between the information available to an agent and the way it is processed.

Further details

The purpose of this workshop is to discuss and report on work related to:

• The roles of evolutionary algorithms in various stages of a problem solving process.
  
• Coevolution of problems and solutions.
  
• Emergence of features and functionalities in solutions.
  
• Principles drawn from evolutionary systems which address non-routine design.
  
• Models, architectures, genetic operators which bring forth creativity.
  
• Interactive evolution.
  
• Evolutionary algorithms to assist human designers in producing non-routine and creative
  design.
  
• Evolutionary algorithms to generate non-routine and creative design automatically.

Further details

Representations and Operators for Network Problems

Franz Rothlauf

Finding good solutions for network design problems is important in many fields such as telecommunications, computer, backbone access, transportation and distribution networks. Over the last years genetic algorithms have been applied with success to a wide variety of these different problems. One of the major design issues is how the network could be represented as an artificial chromosome and what kind of operators could be defined on the chromosome.

The workshop is intended to give an overview over the existing approaches and to discuss various representations and operators in the context of genetic and evolutionary computation. It should compare theoretical properties and empirical performance characteristics of different representations and operators and try to find explanations for performance differences of a genetic algorithm. The workshop will be focused on representations and operators for network problems, but it welcomes interesting contributions to encoding issues that are meaningful for network representations.

Further details

Real-life Evolutionary Design Optimisation

Rajkumar Roy, Graham Jared, Ashutosh Tiwari and Olivier Munaux

The aim of this workshop is to explore the use of evolutionary computation techniques for solving real-life design optimisation problems. These problems pose additional challenges for the optimisation techniques due to their following characteristics:

• The principal feature of most real-life problems is the presence of multiple measures of performance, or objectives, which should be optimised simultaneously.
• In most of these problems, there is no prior knowledge regarding the shape of search space. There is also no prior information about the performance and location of the optimal and sub-optimal points in the search space.
• The complexity of these problems is also increased due to the qualitative issues, like manufacturability and designers' special preferences, invariably associated with real-life problems.
• Most of these problems are computationally expensive and difficult to solve due the presence of multiple interacting dimensions and several optimal solutions.
• Further, most of these problems require some constraints to be satisfied.
• Finally, the model development for the solution of real-life optimisation problems is a very complex task.

This workshop provides a forum for identifying and exploring the key issues that affect the industrial application of evolutionary-based computation techniques.

Further details

Evolutionary COmputation and Multi-Agent Systems (ECOMAS)

Robert E. Smith, Claudio Bonacina, Cefn Hoile and Paul Marrow

Multi-agent systems (MAS) are collections of interacting autonomous entities. The behaviour of the MAS is a result of the repeated asynchronous action and interaction of the agents. Understanding how to engineer adaptation and self-organisation is thus central to the application of agents on a large scale. Moreover, multi-agent simulations can also be used to study emergent behaviour in real systems.

Desirable self-organisation is observed in many biological, social and physical systems. However, fostering these conditions in artificial systems proves to be difficult and offers the potential for undesirable behaviours to emerge. Thus, it is vital to be able to understand and shape emergent behaviours in agent based systems. Current mathematical and empirical tools give only a partial insight into emergent behaviour in large, agent-based societies. EC provides on paradigm for addressing this need. Moreover, EC techniques are inherently based on a distributed paradigm (natural evolution), making them particularly well suited for adaptation in agents.

At the same time, ideas from natural ecosystems or economies, such as resource flows, niches, and spatial context or neighbourhood can contribute both to the development of MAS and to the improvement of EC techniques. The interaction between these different sources of natural inspiration and the two computing disciplines of MAS and EC is beginning to stimulate a range of systems with properties that extend the MAS and EC concepts in new and interesting directions.

Further details

-A roundtable discussion to be held Sunday afternoon from 2:00 - 5:30

Further details