University of Konstanz
Graduiertenkolleg / PhD Program
Computer and Information Science

Colloquium of the Department and the PhD Program

title

On the computational time complexity of evolutionary algorithms

speaker

Dr. Carsten Witt, University Dortmund
Dortmund, Germany

date & place

Wednesday, 13.07.2005, 00:00 h

abstract

Evolutionary algorithms (EAs) are general, randomized search heuristics often applied to optimization problems for which no problem-specific algorithm is available. Despite surprisingly good results reported by practitioners, the theoretical foundation of the computational time complexity of EAs is still a relatively young research area.

The talk will deal with two different aspects of EAs and related randomized local search algorithms. First, the time complexity of obtaining approximate solutions to an NP-hard optimization problem is discussed. Second, so-called populations of search points are investigated. It is proven that the time complexity of EAs can crucially depend on the size of the population used.