Embrace by Anargyros Sarafopoulos  


1st European Workshop on Evolutionary Algorithms in Stochastic and Dynamic Environments



Handling uncertainties in evolutionary optimization has received an increasing interest in the evolutionary community. A variety of methods for addressing uncertainties have been reported from different application backgrounds. The objective of the EvoSTOC2004 workshop 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. Each accepted paper will be presented orally at the conference and published by Springer as part of EvoWorkshops2004 in the Lecture Notes in Computer Science series. Springer Lecture Notes in Computer Science series

LNCS 3005, the EvoWorkshops2004 proceedings, is now available online


Workshop PAPERS:

Multi-Swarm Optimization in Dynamic Environments
Tim Blackwell, Jürgen Branke

Many real-world problems are dynamic, requiring an optimization algorithm which is able to continuously track a changing optimum over time. In this paper, we present new variants of Particle Swarm Optimization (PSO) specifically designed to work well in dynamic environments. The main idea is to extend the single population PSO and Charged Particle Swarm Optimization (CPSO) methods by constructing interacting multi-swarms. In addition, a new algorithmic variant, which broadens the implicit atomic analogy of CPSO to a quantum model, is introduced. The multi-swarm algorithms are tested on a multi-modal dynamic function - the moving peaks benchmark - and results are compared to the single population approach of PSO and CPSO, and to results obtained by a state-of-the-art evolutionary algorithm, namely self-organizing scouts (SOS). We show that our multi-swarm optimizer significantly outperforms single population PSO on this problem, and that multi-quantum swarms are superior to multi-charged swarms and SOS.

Evolutionary Algorithms for Stochastic Arc Routing Problems
Gérard Fleury, Philippe Lacomme, Christian Prins

The Capacitated Arc Routing Problem (CARP) is a combinatorial optimization problem in which vehicles with limited capacity must treat a set of arcs in a network, to minimize the total cost of the trips. The SCARP is a stochastic version with random demands on the arcs. The management rules used for instance in waste collection enable to derive mathematical expressions for objectives like the expected total cost. A memetic algorithm (MA) for the SCARP is proposed and compared with two deterministic versions based on average demands. All solutions are evaluated by simulation, to see how they are affected by random fluctuations of demands. This evaluation confirms the expected cost computed by the MA and shows its ability to provide robust solutions, without significant enlargement of the cost of planned trips.

A Hierarchical Particle Swarm Optimizer for Dynamic Optimization Problems
Stefan Janson, Martin Middendorf

Particle Swarm Optimization (PSO) methods for dynamic function optimization are studied in this paper. We compare dynamic variants of standard PSO and Hierarchical PSO (H-PSO) on different dynamic benchmark functions. Moreover, a new type of hierarchical PSO, called Partitioned H-PSO (PH-PSO), is proposed. In this algorithm the hierarchy is partitioned into several sub-swarms for a limited number of generations after a change occurred. Different methods for determining the time when to rejoin the hierarchy and how to handle the topmost sub-swarm are discussed. The test results show that H-PSO performs significantly better than PSO on all test functions and that the PH-PSO algorithms often perform best on multimodal functions where changes are not too severe.

Constructing Dynamic Optimization Test Problems Using the Multi-Objective Optimization Concept
Yaochu Jin, Bernhard Sendhoff

Dynamic optimization using evolutionary algorithms is receiving increasing interests. However, typical test functions for comparing the performance of various dynamic optimization algorithms still lack. This paper suggests a method for constructing dynamic optimization test problems using multi-objective optimization (MOO) concepts. By aggregating different objectives of an MOO problem and changing the weights dynamically, we are able to construct dynamic single objective and multi-objective test problems systematically. The proposed method is computationally efficient, easily tunable and functionally powerful. This is mainly due to the fact that the proposed method associates dynamic optimization with multi-objective optimization and thus the rich MOO test problems can easily be adapted to dynamic optimization test functions.

Competitive Goal Coordination in Automatic Parking
Darío Maravall, Javier de Lope, Miguel Angel Patricio

This paper addresses the problem of automatic parking by a back-wheel drive vehicle, using a biomimetic model based on direct coupling between vehicle perceptions and actions. The proposed automatic parking solution leads to a dynamic multiobjective optimization problem that cannot be dealt with analytically. A genetic algorithm is therefore used. The paper ends with a discussion of the results of computer simulations.

Evolutionary Bayesian Network Dynamic Planner for Game RISK
James Vaccaro, Clark Guest

Many artificial intelligence problems are susceptible to a goal-directed solution. For some problems, such as dynamic planning and execution, a goal-directed approach may be the only option. Using information available about a desirable state or a measure of acceptability of possible future states, a goal-directed approach determines routes or plans to reach these desirable states. These problems can be categorized as game problems. One such game is RISK. RISK is complex, multi-scaled, and provides a good application for testing a variety of goal-directed approaches. A goal-directed hybrid evolutionary program that plays the RISK game effectively has been developed. This approach advances an understanding of: (1) how to use Bayesian probability to prune combinatorial explosive planning spaces; (2) how to incorporate temporal planning cost in an objective function; and (3) provides a procedure for mapping a problem (i.e., data and knowledge) into a dynamic planning and execution framework.

EvoSTOC programme committee:

Co-chair: Jürgen Branke, University of Karlsruhe <branke@aifb.uni-karlsruhe.de>
Co-chair: Yaochu Jin, Honda Research Institute Europe <yaochu.jin@honda-ri.de>
Hans-Georg Beyer (Germany)
Dirk Bueche (Switzerland)
Ernesto Costa (Portugal)
Kalyan Deb (India)
Ken DeJong (USA)
Anna I Esparcia-Alcazar (Spain)
Marco Farina (Italy)
Michael Guntsch (Germany)
Hajime Kita (Japan)
Dirk Mattfeld (Germany)
Daniel Merkle (Germany)
Markus Olhofer(Germany)
Khaled Rasheed (USA)
Christopher Ronnewinkel (Germany)
Lutz Schoenemann (Germany)
Stephen Smith (USA)
Jürgen Teich (Germany)
Lars Willmes (USA)

EvoWorkshops chairs:

Günther Raidl, Vienna University of Technology <raidl@ads.tuwien.ac.at>
Stefano Cagnoni, Universita' di Parma <cagnoni@ce.unipr.it>
Local chair : Ernesto Costa, University of Coimbra <ernesto@dei.uc.pt>

Workshop Background:

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 three classes.

  1. The fitness function is stochastic. Uncertainties may be either biased or unbiased. Noise in fitness evaluations may result from many different sources such as sensory measurement errors or numerical instabilities in simulation.Large biases often occur when the fitness function has to be estimated, e.g., if approximate models are used or fitness inheritance is adopted in order to save costly fitness evaluations.
  2. The design variables or the environmental parameters are subject to perturbations or deterministic changes. It is very common that a system to be designed needs to still work satisfyingly even when the design variables change slightly, e.g. due to manufacturing tolerances, or it has to work well in a variety of possible environmental conditions. This issue is often known as the search for robust solutions.
  3. The fitness function is time-varying, in other words, the optimum of the system changes with time, requiring a repeated re-optimization or even continuous tracking.

Handling uncertainties in evolutionary optimization has received an increasing interest in the evolutionary community. A variety of methods for addressing uncertainties have been reported from different application backgrounds. The objective of this workshop 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.

Topics of interest may include but are not limited to:

  • handling noisy fitness functions
  • searching for robust optimal solutions
  • tracking moving optima
  • sophisticated real-world applications
Submission procedure (NOW CLOSED)

Manuscripts should be up to 12 pages long and must be received no later than 21 November (extended deadline) 2004. Electronic submission in either PostScript or PDF format is highly encouraged. Please send your electronic submission to branke@aifb.uni-karlsruhe.de. In case you can not submit electronically, please contact one of the program chairs. The format of the paper should adhere to the standard Springer LNCS style. Formatting instructions can be found at http://www.springer.de/comp/lncs/authors.html.

The paper will be reviewed by at least three members of the program committee. Authors will be notified via email on the results of the review by 19 December 2003. Authors of accepted papers will have to improve their paper on the basis of the reviewers' comments and will be asked to send a camera-ready version of their manuscripts by 16 January 2004. By submitting a camera-ready paper, the author(s) agree that at least one author will attend and present the paper at the workshop. Accepted papers will be included in the proceedings of the EvoWorkshops. Authors of selected papers will be invited to submit an extended version to a special issue of IEEE Transactions on Evolutionary Computation (see http://www.soft-computing.de/CFP_TEC.htm).

Springer Lecture Notes in Computer Science series The EvoWorkshops2004 proceedings will be
published by Spinger as part of their
Lecture Notes in Computer Science series.