EvoWorkshops2005: EvoSTOC

2nd European Workshop on Evolutionary Algorithms in Stochastic and Dynamic Environments

In Applications of Evolutionary Computing.

In many real-world optimization problems, a wide range of uncertainties has to be taken into account. Generally, uncertainties in evolutionary optimization can be categorized into four classes.

  1. Noisy fitness function. Noise in fitness evaluations may come from many different sources such as sensory measurement errors or numerical instabilities in simulation.
  2. Approximated fitness function. When the fitness function is very expensive to evaluate, or an analytical fitness function is not available, approximated fitness functions are often used instead.
  3. Robustness. Often, when a solution is implemented, the design variables or the environmental parameters are subject to perturbations or changes. Therefore, a common requirement is that a solution should still work satisfyingly either when the design variables change slightly, e.g., due to manufacturing tolerances, or when the environmental parameters vary slightly. This issue is generally known as the search for robust solutions.
  4. Dynamic fitness function. In a changing environment, it should be possible to continuously track the moving optimum rather than to repeatedly re-start the optimization process.

Handling uncertainties in evolutionary computation has received an increasing interest over the past years. A variety of methods for addressing uncertainties have been reported from different application backgrounds. The EvoSTOC workshop will be held as part of EvoWorkshops 2005, the 8th Evolutionary Computing Workshops, and in conjunction with EuroGP 2005, the 8th European Conference on Genetic Programming. The workshop objective is to foster interest in the issue of handling uncertainties, to provide a forum for researchers to meet and a platform to present and discuss latest research in the field.

Web address: http://www.evonet.info/eurogp2005

Topics include

Organising Committee

Program Chairs
Juergen Branke
branke AT aifb DOT uni-karlsruhe DOT de
Institute AIFB, University of Karlsruhe, Germany,
 
Yaochu Jin
yaochu DOT jin AT honda-ri DOT de
Honda Research Institute, Offenbach, Germany
 
EvoWorkshops2005 Chair
Franz Rothlauf
rothlauf AT uni-mannheim DOT de
University of Mannheim, Germany
 
Local Chair
Marco Tomassini
Marco.Tomassini AT hec DOT unil DOT ch
University of Lausanne, Switzerland
 
Publicity Chair
Jano van Hemert
jvhemert AT cwi DOT nl
Napier University, Edinburgh, Scotland, UK

Note: the e-mail addresses are masked for spam protection.

Programme Committee

Dirk Arnold (Canada)
Hans-Georg Beyer (Germany)
Tim Blackwell(UK)
Ernesto Costa (Portugal)
Kalyan Deb (India)
Marco Farina (Italy)
Michael Guntsch (Germany)
Martin Middendorf (Germany)
Ferrante Neri (Italy)
Markus Olhofer(Germany)
Yew Soon Ong (Singapore)
Khaled Rasheed (USA)
Christian Schmidt (Germany)
Holger Ulmer (Germany)
Sima Uyar (Turkey)
Karsten Weicker (Germany)
Lars Willmes (Germany)
Shengxiang Yang (UK)

EvoSTOC Programme

Wednesday, 30 March 2005

Session 1 (1415-1545)

14:15 Welcome
14:30 K. Parsopoulos, M. Vrahatis: Unified Particle Swarm Optimization in Dynamic Environments
15:00 D. Merkle, M. Middendorf, A. Scheidler: Dynamic Decentralized Packet Clustering in Networks

Session 2 (1600-1730)

16:00 W. Rand, R. Riolo: Shaky Ladders, Hyperplane-Defined Functions and Genetic Algorithms
16:30 A. Karaman, S. Uyar, G. Eryigit: The Memory Indexing Evolutionary Algorithm for Dynamic Environments
17:00 Overview over poster presentations

Session 3: Posters (1730-2000)

EvoSTOC: Titles and abstracts of accepted papers

Gideon Avigad
Amiram Moshaiov
Neima Brauner

MOEA-based Approach to Delayed Decisions for Robust Conceptual Design

This paper presents a modification of our multi-objective concept-based EC method for the simultaneous development of a robust conceptual front. It involves a hierarchy of abstractive descriptions of the design, and a structured EC approach. The robustness, treated here by a novel MOEA approach, is for uncertainties, which result from delaying decisions during the conceptual design stage.

Aydin Karaman
Sima Uyar
Güslen Eryigit

The Memory Indexing Evolutionary Algorithm for Dynamic Environments

There is a growing interest in applying evolutionary algorithms to dynamic environments. Different types of changes in the environment benefit from different types of mechanisms to handle the change. In this study, the mechanisms used in literature are categorized into four groups. A new EA approach (MIA) which benefits from the EDA-like approach it employs for re-initializing populations after a change as well as using different change handling mechanisms together is proposed. Experiments are conducted using the 0/1 single knapsack problem to compare MIA with other algorithms and to explore its performance. Promising results are obtained which promote further study. Current research is being done to extend MIA to other problem domains.

Daniel Merkle
Martin Middendorf
Alexander Scheidler

Dynamic Decentralized Packet Clustering in Networks

In this paper we study a dynamic version of the Decentralized Packet Clustering (DPC) Problem. For a network consisting of routers and application servers the DPC problem is to find a good clustering for packets that are sent between the servers through the network. The clustering is done according to a data vector in the packets. In the dynamic version of DPC the packets data vector can change. The proposed algorithms to solve the dynamic DPC are inspired by the odor recognition system of ants. We analyze the new algorithms for situations with different strengths of dynamic change and for different number of routers in the network.

Ferrante Neri
Anna V. Kononova
Giuseppe Delvecchio
Marcello Sylos Labini
Alexey V. Uglanov

A Hierarchical Evolutionary Algorithm with Noisy Fitness in Structural Optimization Problems

The authors propose a hierarchical evolutionary algorithm (HEA) to solve structural optimization problems. The HEA is composed by a lower level evolutionary algorithm (LLEA) and a higher level evolutionary algorithm (HLEA). The HEA has been applied to the design of grounding grids for electrical safety. A compact representation to describe the topology of the grounding grid is proposed. An analysis of the decision space is carried out and its restriction is obtained according to some considerations on the physical meaning of the individuals. Due to the algorithmic structure and the specific class of problems under study, the fitness function of the HLEA is noisy. A statistical approach to analyze the behavior and the reliability of the fitness function is done by applying the limit theorems of the probability theory. The comparison with the other method of grounding grid design shows the validity and the efficiency of the HEA.

Gabriela Ochoa
Christian Mädler-Kron
Ricardo Rodriguez
Klaus Jaffe

Assortative Mating in Genetic Algorithms for Dynamic Problems

Non-random mating seems to be the norm in nature among sexual organisms. A common mating criteria among animals is assortative mating, where individuals mate according to their phenotype similarities (or dissimilarities). This paper explores the effect of including assortative mating in genetic algorithms for dynamic problems. A wide range of mutation rates was explored, since comparative results were found to change drastically for different mutation rates. The strategy for selecting mates was found to interact with the mutation rate value: low mutation rates were the best choice for dissortative mating, medium mutation values for the standard GA, and higher mutation rates for assortative mating. Thus, GA efficiency is related to mate selection strategies in connection with mutation values. For low mutation rates typically used in GA, dissortative mating was shown to be a robust and promising strategy for dynamic problems.

Konstantinos E. Parsopoulos
Michael N. Vrahatis

Unified Particle Swarm Optimization in Dynamic Environments

A first investigation of the recently proposed Unified Particle Swarm Optimization algorithm on dynamic environments is provided and discussed on widely used test problems. Results are very promising compared to the corresponding results of the standard Particle Swarm Optimization algorithm, indicating the superiority of the new scheme.

William Rand
Rick Riolo

Shaky Ladders, Hyperplane-Defined Functions and Genetic Algorithms: Systematic Controlled Observation in Dynamic Environments

Though recently there has been interest in examining genetic algorithms (GAs) in dynamic environments, work still needs to be done in investigating the fundamental behavior of these algorithms in changing environments. When researching the GA in static environments, it has been useful to use test suites of functions that are designed for the GA so that the performance can be observed under systematic controlled conditions. One example of these suites is the hyperplane-defined functions (hdfs) designed by Holland [Holland00]. We have created an extension of these functions, specifically designed for dynamic environments, which we call the shaky ladder functions. In this paper, we examine the qualities of this suite that facilitate its use in examining the GA in dynamic environments, describe the construction of these functions and present some preliminary results of a GA operating on these functions.

Claudio M. Rocco S.

A Hybrid Approach based on Evolutionary Strategies and Interval Arithmetic to perform Robust Designs

This paper proposes an approach based on the use of Cellular Evolu-tionary Strategies (CES) and Interval Arithmetic (IA) as an alternative tech-nique to obtain robust system design. CES are an approach that combines the Evolution Strategy techniques with concepts from Cellular Automata in order to optimise a given function, while IA is used as a checking technique that guar-antees the feasibility of the design. IA is able to consider simultaneously the ef-fects of uncertainty of all of the parameters on a performance function and to provide strict bounds (minimum and maximum values) with only one evalua-tion. CES and IA are used to obtain, by an iterative process, a robust design, that is, the maximum size of each variable deviation that allow to comply with a set of specifications. The proposed approach is an indirect method based on op-timisation instead of a direct method based on mapping from the output into the input space. A numerical example, related to an electronic circuit system de-sign, illustrates the application of the approach.