Mittagsseminar (in cooperation with J. Lengler, A. Steger, and D. Steurer)

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)

Level-based Analysis of Evolutionary Algorithms

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.

Upcoming talks     |     All previous talks     |     Talks by speaker     |     Upcoming talks in iCal format (beta version!)

Previous talks by year:   2024  2023  2022  2021  2020  2019  2018  2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996  

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M   |   admin login