ThRaSH'2011 Tutorials

Basic Introduction to the Theoretical Analysis of Real-Valued Evolution Strategies

Jens Jägersküpper

Abstract The basic search operator in classical real-valued evolutionary algorithms, mainly evolution strategies (ES), is the so called Gaussian mutation. This tutorial focuses on a rigorous understanding of this basic search operator. With this, lower bounds on the (expected) number of steps (or mutations) necessary to obtain a given reduction of the approximation error (in the search space) can be proved. In addition to these lower bounds, the tutorial covers some simple scenarios, for which upper bounds can be proved when a simple deterministic mechanism for mutation adaptation is used, namely Rechberg's 1/5-success rule. Also a system-analytical approach to the analysis of ES that has been put forward by, e.g., Hans-Georg Beyer is introduced. Finally, the differing aspects of these two approaches are discussed.

Biography Jens Jägersküpper studied computer science at the Technical University Dortmund, Germany, where he received his diploma and Ph.D. in 2001 and 2006, respectively. Jens worked as a scientific assistant in Ingo Wegener's evolutionary algorithms group at the Department of Computer Science of the Technical University Dortmund until 2008. Since 2009 he has worked as a research and development scientist at the Center of Computer Applications in Aerospace Science and Engineering (C2A2S2E) of the German Aerospace Center (DLR), Institute of Aerodynamics and Flow Technology.

Introduction to the Complexity Analysis of Discrete Randomized Search Heuristics

Dirk Sudholt

Abstract The complexity analysis of randomized search heuristics provides rigorous bounds on the random time until a search heuristic has found a good or optimal solution. These bounds are crucial for judging the scalability of search heuristics on a given problem. They help to compare different algorithms and they give insight into the impact of parameter settings on performance.

In the last 15 years many results of this kind have been obtained, using tools from probability theory and randomized algorithms. The purpose of this tutorial is to give an introduction into the analysis of discrete randomized search heuristics. Common methods used for their analysis are presented and accompanied by illustrative examples. Furthermore, a survey on past and ongoing work will be given.

Biography Dirk Sudholt obtained his Diplom (Master's) degree in 2004 and his PhD in computer science in 2008 from the Technische Universitaet Dortmund under the supervision of Prof. Ingo Wegener. The topic of his PhD work was the computational complexity analysis of randomized search heuristics such as evolutionary algorithms and swarm intelligence. Afterwards, he spent 12 months visiting the International Computer Science Institute in Berkeley, California, working in the Algorithms group led by Prof. Richard M. Karp. Since September 2010 he is a Research Fellow at the University of Birmingham, working with Prof. Xin Yao.

Last updated: Thu, 30 Jun 2011 23:54