Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, April 21, 2015, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Per Kristian Lehre (University of Nottingham)
Evolutionary algorithms have been applied for decades to tackle hard, real-world optimisation problems in logistics, the automotive industry, the pharmaceutical industry, and elsewhere. Despite their wide-spread use, the theoretical understanding of evolutionary algorithms is still relatively poorly developed. Partly due to lack of methods, time-complexity analysis of evolutionary algorithms have mainly focused on simple algorithms, such as the (1+1) EA which do not use a population and sophisticated genetic operators.
This talk introduces a new method for time-complexity analysis of evolutionary algorithms, the level-based method (Corus et al, PPSN'2014). This method provides upper bounds on the expected hitting times of a wide class of stochastic population models from easy to verify conditions. The level-based theorem simplifies the analysis of complex evolutionary algorithms significantly.
We give an overview of recent applications of the level-based method, including analyses of genetic algorithms using the crossover operator, and estimation of distribution algorithms. We also briefly discuss studies of how evolutionary algorithms cope with different forms of uncertainty in pseudo-Boolean optimisation. It is shown that with appropriate settings of mutation rate, selective pressure, and population size, an evolutionary algorithm can cope with surprisingly high levels of uncertainty.
Automatic MiSe System Software Version 1.4803M | admin login