https://www.dagstuhl.de/19431

October 20 – 25 , 2019, Dagstuhl Seminar 19431

Theory of Randomized Optimization Heuristics

Organizers

Carola Doerr (University Pierre & Marie Curie – Paris, FR)
Carlos M. Fonseca (University of Coimbra, PT)
Tobias Friedrich (Hasso-Plattner-Institut – Potsdam, DE)
Xin Yao (University of Birmingham, GB)

For support, please contact

Susanne Bach-Bernhard for administrative matters

Michael Gerke for scientific matters

Motivation

Efficient optimization techniques affect our personal, industrial, and academic environments through the supply of well-designed processes that enable a best-possible use of our limited resources. Despite significant research efforts, most real-world problems remain too complex to admit exact analytical or computational solutions. Therefore, heuristic approaches that trade the accuracy of a solution for a simple algorithmic structure, fast running times, or an otherwise efficient use of computational resources are required. Randomized optimization heuristics form a highly successful and thus frequently applied class of such problem solvers. Among the best-known representatives of this class are stochastic local search methods, Monte Carlo techniques, genetic and evolutionary algorithms, and swarm intelligence techniques.

The theory of randomized optimization heuristics strives to set heuristic approaches on firm ground by providing a sound mathematical foundation for this important class of algorithms. Key challenges in this research area comprise optimization under uncertainty, parameter selection (most randomized optimization heuristics are parametrized), the role and usefulness of so-called crossover operations (i.e., the idea of creating high-quality solution candidates by recombining previously evaluated ones) and, more generally, performance guarantees for advanced heuristics such as population-based techniques, estimation-of-distribution algorithms, differential evolution, and others.

The present Dagstuhl Seminar is a continuation of the seminar series on "Theory of Evolutionary Algorithms". Today the field extends far beyond evolutionary algorithms – a development that previous Dagstuhl Seminars have significantly influenced. This seminar aims at continuing this highly beneficial exchange by addressing, in particular, two strongly linked research communities not previously represented in the seminar series: stochastic control theory and empirical benchmarking of randomized optimization heuristics.

Recent work has shown that there is a very close link between the theory of randomized optimization heuristics and stochastic control theory, both regarding the nature of the "systems" of interest and the analytical techniques that have been developed in the two communities. Exploring these affinities and how the two communities can work together to mutual benefit is one of the focus topics to be addressed with this seminar. The second focus topic is benchmarking, which plays a central role in empirical performance assessment. Benchmarking can be an essential tool for theoreticians to develop their mathematically-derived ideas into practical algorithms. It thereby encourages a principled discussion between empirically-driven and theoretically-driven researchers.

Discussing the mathematical challenges arising in the performance analysis of randomized heuristics has always been a central topic in this Dagstuhl Seminar series. Among other achievements, important connections between continuous and discrete optimization have been established. Theoretical performance guarantees will continue to play an important role, fostering innovative ideas and the systematic transfer of knowledge between the research communities represented in the seminar.

License
  Creative Commons BY 3.0 DE
  Carola Doerr, Carlos M. Fonseca, Tobias Friedrich, and Xin Yao

Dagstuhl Seminar Series

Classification

  • Soft Computing / Evolutionary Algorithms

Keywords

  • Heuristic optimization
  • Black-box optimization
  • Evolutionary algorithms
  • Randomized search algorithms
  • Theoretical computer science
  • Control theory
  • Benchmarking

Book exhibition

Books from the participants of the current Seminar 

Book exhibition in the library, ground floor, during the seminar week.

Documentation

In the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.

 

Download overview leaflet (PDF).

Publications

Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.

NSF young researcher support