EvoWorkshops2006: EvoSTOC

3rd European Workshop on Evolutionary Algorithms in Stochastic and Dynamic Environments

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 2006. 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/eurogp2006

Topics include

Organising Committee

Program Chairs
Juergen Branke
branke AT aifb DOT uni-karlsruhe DOT de
Institute AIFB, University of Karlsruhe, Germany,
Ernesto Costa
ernesto AT dei DOT uc DOT pt
Department of Informatics Engineering, University of Coimbra, Portugal
EvoWorkshops2006 Chair
Franz Rothlauf
rothlauf AT uni-mannheim DOT de
University of Mannheim, Germany
Local Chair
Anikó Ekárt
ekart AT sztaki DOT hu
Hungarian Academy of Sciences
Publicity Chair
Steven Gustafson
smg AT cs DOT nott DOT ac DOT uk
University of Nottingham, UK

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

Programme Committee

Dirk Arnold, Canada
Hans-Georg Beyer, Austria
Tim Blackwell, UK
Kalyanmoy Deb, India
Yaochu Jin, Germany
Stephan Meisel, Germany
Daniel Merkle, Germany
Martin Middendorf, Germany
Ron Morrison, USA
Ferrante Neri, Italy
Qew Soon Ong, Singapore
William Rand, USA
Christian Schmidt, Germany
Sima Uyar, Turkey
Shengxiang Yang, UK

Accepted Papers: titles and abstracts

A Preliminary Study On Handling Uncertainty in Indicator-Based Multiobjective Optimization
Matthieu Basseur, Eckart Zitzler

Real-world optimization problems are often subject to uncertainties, which can arise regarding stochastic model parameters, objective functions and decision variables. These uncertainties can take different forms in terms of distribution, bound and central tendency. In the multiobjective context, several studies have been proposed to take uncertainty into account, and most of them propose an extension of Pareto dominance to the stochastic case. In this paper, we pursue a slightly different approach where the optimization goal is defined in terms of a quality indicator, i.e., an objective function on the set of Pareto set approximations. We consider the scenario that each solution is inherently associated with a probability distribution over the objective space, without assuming a 'true' objective vector per solution. We propose different algorithms which optimize the quality indicator, and preliminary simulation results indicate advantages over existing methods such as averaging, especially with many objective functions.

The Role of Representations in Dynamic Knapsack Problems
J¨urgen Branke, Merve Orbayŭ, S¸ima Uyar

The effect of different representations has been thoroughly analyzed for evolutionary algorithms in stationary environments. However, the role of representations in dynamic environments has been largely neglected so far. In this paper, we empirically compare and analyze three different representations on the basis of a dynamic multi-dimensional knapsack problem. Our results indicate that indirect representations are particularly suitable for the dynamic multi-dimensional knapsack problem, because they implicitly provide a heuristic adaptation mechanism that improves the current solutions after a change.

Bayesian Optimization Algorithms for Dynamic Problems
MiloĦs Kobliha, Josef Schwarz, JiĦr´ŭ OĦcen´aĦsek

Abstract. This paper is an experimental study investigating the capability of Bayesian optimization algorithms to solve dynamic problems. We tested the performance of two variants of Bayesian optimization algorithms - Mixed continuous-discrete Bayesian Optimization Algorithm (MBOA), Adaptive Mixed Bayesian Optimization Algorithm (AMBOA) - and new proposed modifications with embedded Sentinels concept and Hypervariance. We have compared the performance of these variants on a simple dynamic problem - a time-varying function with predefined parameters. The experimental results confirmed the benefit of Sentinels concept and Hypervariance embedded into MBOA algorithm for tracking a moving optimum.

Prudent-Daring vs Tolerant Survivor Selection Schemes in Control Design of Electric Drives
Ferrante Neri, Giuseppe L. Cascella, Nadia Salvatore, Anna V.Kononova, Giuseppe Acciani

Abstract. This paper proposes and compares two different approaches to defeat the noise due the measurement errors in control design of elec- tric drives. The former is based on a penalized fitness and two cooperative- competitive survivor selection schemes, the latter is based on a survivor selection scheme which makes use of the tolerance interval related to the noise distribution. These approaches use adaptive rules in parameter set- ting to execute both the explicit and the implicit averaging in order to obtain the noise defeating in the optimization process with a relatively low number of fitness evaluations. The results show that the two ap- proaches differently bias the population diversity and that the first can outperform the second but requires a more accurate parameter setting.

The Effect of Building Block Construction on the Behavior of the GA in Dynamic Environments: A Case Study Using the Shaky Ladder Hyperplane-Defined Functions
William Rand, Rick Riolo

The shaky ladder hyperplane-defined functions (sl-hdf's) are a test suite utilized for exploring the behavior of the genetic algorithm (GA) in dynamic environments. We present three ways of constructing the sl-hdf's by manipulating the way building blocks are constructed, combined, and changed. We examine the effect of the length of elementary building blocks used to create higher building blocks, and the way in which those building blocks are combined. We show that the effects of building block construction on the behavior of the GA are complex. Our results suggest that construction routines which increase the roughness of the changes in the environment allow the GA to perform better by preventing premature convergence. Moreover, short length elementary building blocks permit early rapid progress.

Fluctuating Crosstalk as a Source of Deterministic Noise and its Effects on GA Scalability
Kumara Sastry, Paul Winward, David E. Goldberg, Cl´audio Lima

This paper explores how fluctuating crosstalk in a deterministic fitness function introduces noise into genetic algorithms. We model fluctuating crosstalk or nonlinear interactions among building blocks via higher-order Walsh coefficients. The fluctuating crosstalk behaves like exogenous noise and can be handled by increasing the population size and run duration. This behavior holds until the strength of the crosstalk far exceeds the underlying fitness variance by a certain factor empirically observed. Our results also have implications for the relative performance of building-block-wise mutation over crossover.

Integrating Techniques from Statistical Ranking into Evolutionary Algorithms
Christian Schmidt, J¨urgen Branke, Stephen E. Chick

Many practical optimization problems are subject to uncertain fitness evaluations. One way to reduce the noise is to average over multiple samples of the fitness function in order to evaluate a single individual. This paper proposes a general way to integrate statistical ranking and selection procedures into evolutionary algorithms. The proposed procedure focuses sampling on those individuals that are crucial for the evolutionary algorithm, and distributes samples in a way that efficiently reduces uncertainty. The goal is to drastically reduce the number of evaluations required for a proper operation of the evolutionary algorithm in noisy environments.

Associative Memory Scheme for Genetic Algorithms in Dynamic Environments
Shengxiang Yang

In recent years dynamic optimization problems have attracted a growing interest from the community of genetic algorithms with several approaches developed to address these problems, of which the memory scheme is a major one. In this paper an associative memory scheme is proposed for genetic algorithms to enhance their performance in dynamic environments. In this memory scheme, the environmental information is also stored and associated with current best individual of the population in the memory. When the environment changes the stored environmental information that is associated with the best re-evaluated memory solution is extracted to create new individuals into the population. Based on a series of systematically constructed dynamic test environments, experiments are carried out to validate the proposed associative memory scheme. The environmental results show the efficiency of the associative memory scheme for genetic algorithms in dynamic environments.