Theory of Evolutionary Algorithms

Motivation

Evolutionary algorithms (EAs) are stochastic optimization methods that are based on principles derived from natural evolution. Mutation, recombination, and selection are iterated with the goal of driving a population of candidate solutions toward better and better regions of the search space. The goal of the theory of evolutionary algorithms is to develop methods to make them work more effectively, propose new principles for the design of evolutionary algorithms, and develop better insight and understanding concerning how they work.

We will leave scope for new topics to be brought forward by the participants (many of whom are young researchers who we anticipate will inject new ideas into the field). However, we expect the following key directions to play a central role at this seminar.

We need advances in some of the existing approaches to make further progress. Although there has been great progress in applying classical analysis of randomized algorithms, the existence of a population and the recombination operator make analysis difficult. New methods need to be developed and disseminated. Complexity theory is another such example. It is a corner stone of computer science; in application to randomized search heuristics it takes the form of black-box complexity. However, as currently defined it gives paradoxical results, such as assigning a low complexity to some notoriously hard problems. New definitions have been recently proposed to fix this, but it is still an open problem.

We also expect to explore new methods for designing algorithms. Recently a new principle for devising evolutionary algorithms was pro- posed, based on the idea of conducting a natural gradient descent in the space of probability distributions, a sample from which would rep- resent the population in an EA. This gives a new principled way of devising search algorithms, but also provides a new challenge to theory to understand these algorithms and demonstrate their properties.

The field needs to advance the complexity of the problems it can tackle. One of the most explosive areas of growth is multi-objective optimization, which requires the simultaneous optimization of many objectives, representing the trade-offs between different sources of cost or benefit. Evolutionary algorithms are the method of choice for multi-objective optimization; however, many fundamental questions on their working principles still remain unsolved.

Much of the advances in the theory of evolutionary algorithms has studied realistic algorithms on toy problems. The application to realistic problems is much more difficult. One promising approach is based on landscape analysis, by computing features of a search space that can be used to guide search. However, it usually takes exponential time to compute useful metrics exactly. Recent work has shown that some NP-hard problems can be decomposed and statistic moments of the search space can be computed in polynomial time. Can these be used to guide search and devise more effective search algorithms?

EA theory has gained much momentum over the last few years and has made numerous valuable contributions to the field. Much of this momentum is due to the Dagstuhl Seminars on “Theory of Evolutionary Algorithms", which has become one of the leading meetings for EA theorists in the world. We wish to sustain this momentum, but also explore new avenues for future research.