Document

**Published in:** Dagstuhl Reports, Volume 12, Issue 5 (2022)

The Dagstuhl seminar 22182 Estimation-of-Distribution Algorithms: Theory and Practice on May 2-6, 2022 brought together 19 international experts in estimation-of-distribution algorithms (EDAs). Their research ranged from a theoretical perspective, e.g., runtime analysis on synthetic problems, to an applied perspective, e.g., solutions of industrial optimization problems with EDAs. This report documents the program and the outcomes of the seminar.

Josu Ceberio Uribe, Benjamin Doerr, Carsten Witt, and Vicente P. Soloviev. Estimation-of-Distribution Algorithms: Theory and Applications (Dagstuhl Seminar 22182). In Dagstuhl Reports, Volume 12, Issue 5, pp. 17-36, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@Article{uribe_et_al:DagRep.12.5.17, author = {Uribe, Josu Ceberio and Doerr, Benjamin and Witt, Carsten and Soloviev, Vicente P.}, title = {{Estimation-of-Distribution Algorithms: Theory and Applications (Dagstuhl Seminar 22182)}}, pages = {17--36}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2022}, volume = {12}, number = {5}, editor = {Uribe, Josu Ceberio and Doerr, Benjamin and Witt, Carsten and Soloviev, Vicente P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.12.5.17}, URN = {urn:nbn:de:0030-drops-174421}, doi = {10.4230/DagRep.12.5.17}, annote = {Keywords: estimation-of-distribution algorithms, heuristic search and optimization, machine learning, probabilistic model building} }

Document

**Published in:** LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)

The analysis of randomized search heuristics on classes of functions
is fundamental for the understanding of the underlying stochastic
process and the development of suitable proof techniques. Recently,
remarkable progress has been made in bounding the expected
optimization time of the simple (1+1) EA on the class of linear
functions. We improve the best known bound in this setting from
(1.39+o(1))(en ln n) to (en ln n)+O(n) in expectation and with high
probability, which is tight up to lower-order terms. Moreover, upper
and lower bounds for arbitrary mutations probabilities p are derived,
which imply expected polynomial optimization time as long as
p=O((ln n)/n) and which are tight if p=c/n for a constant c. As a
consequence, the standard mutation probability p=1/n is optimal for
all linear functions, and the (1+1) EA is found to be an optimal
mutation-based algorithm. Furthermore, the algorithm turns out to be
surprisingly robust since large neighborhood explored by the mutation
operator does not disrupt the search.

Carsten Witt. Optimizing Linear Functions with Randomized Search Heuristics - The Robustness of Mutation. In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 14, pp. 420-431, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{witt:LIPIcs.STACS.2012.420, author = {Witt, Carsten}, title = {{Optimizing Linear Functions with Randomized Search Heuristics - The Robustness of Mutation}}, booktitle = {29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)}, pages = {420--431}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-35-4}, ISSN = {1868-8969}, year = {2012}, volume = {14}, editor = {D\"{u}rr, Christoph and Wilke, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2012.420}, URN = {urn:nbn:de:0030-drops-33920}, doi = {10.4230/LIPIcs.STACS.2012.420}, annote = {Keywords: Randomized Search Heuristics, Evolutionary Algorithms, Linear Functions, Running Time Analysis} }

Document

**Published in:** Dagstuhl Seminar Proceedings, Volume 10361, Theory of Evolutionary Algorithms (2010)

From September 5 to 10, the Dagstuhl Seminar 10361 ``Theory of Evolutionary Algorithms '' was held in Schloss Dagstuhl~--~Leibniz Center for Informatics.
During the seminar, several participants presented their current
research, and ongoing work and open problems were discussed. Abstracts of
the presentations given during the seminar as well as abstracts of
seminar results and ideas are put together in this paper. The first section
describes the seminar topics and goals in general.

Anne Auger, Jonathan L. Shapiro, L. Darrell Whitley, and Carsten Witt. 10361 Abstracts Collection and Executive Summary – Theory of Evolutionary Algorithms. In Theory of Evolutionary Algorithms. Dagstuhl Seminar Proceedings, Volume 10361, pp. 1-19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{auger_et_al:DagSemProc.10361.1, author = {Auger, Anne and Shapiro, Jonathan L. and Whitley, L. Darrell and Witt, Carsten}, title = {{10361 Abstracts Collection and Executive Summary – Theory of Evolutionary Algorithms}}, booktitle = {Theory of Evolutionary Algorithms}, pages = {1--19}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2010}, volume = {10361}, editor = {Anne Auger and Jonathan L. Shapiro and L. Darrell Whitley and Carsten Witt}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.10361.1}, URN = {urn:nbn:de:0030-drops-28180}, doi = {10.4230/DagSemProc.10361.1}, annote = {Keywords: Evolutionary algorithms, bio-inspired search heuristics, theoretical analysis, optimization time} }

Document

**Published in:** Dagstuhl Seminar Proceedings, Volume 8051, Theory of Evolutionary Algorithms (2008)

From Jan. 27, 2008 to Feb. 1, 2008, the Dagstuhl Seminar 08051 ``Theory of Evolutionary Algorithms'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl.
During the seminar, several participants presented their current
research, and ongoing work and open problems were discussed. Abstracts of
the presentations given during the seminar as well as abstracts of
seminar results and ideas are put together in this paper. The first section
describes the seminar topics and goals in general.
Links to extended abstracts or full papers are provided, if available.

Dirk V. Arnold, Anne Auger, Carsten Witt, and Jonathan E. Rowe. 08051 Abstracts Collection – Theory of Evolutionary Algorithms. In Theory of Evolutionary Algorithms. Dagstuhl Seminar Proceedings, Volume 8051, pp. 1-15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{arnold_et_al:DagSemProc.08051.1, author = {Arnold, Dirk V. and Auger, Anne and Witt, Carsten and Rowe, Jonathan E.}, title = {{08051 Abstracts Collection – Theory of Evolutionary Algorithms}}, booktitle = {Theory of Evolutionary Algorithms}, pages = {1--15}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2008}, volume = {8051}, editor = {Dirk V. Arnold and Anne Auger and Jonathan E. Rowe and Carsten Witt}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08051.1}, URN = {urn:nbn:de:0030-drops-15242}, doi = {10.4230/DagSemProc.08051.1}, annote = {Keywords: Evolutionary Computation, Theory of Evolutionary Algorithms} }

Document

**Published in:** Dagstuhl Seminar Proceedings, Volume 8051, Theory of Evolutionary Algorithms (2008)

The 2008 Dagstuhl Seminar "Theory of Evolutionary Algorithms" was the fifth in a firmly established series of biannual events. In the week from Jan. 27, 2008 to Feb. 1, 2008, 47 researchers from nine countries discussed their recent work and trends in evolutionary computation.

Dirk V. Arnold, Anne Auger, Jonathan E. Rowe, and Carsten Witt. 08051 Executive Summary – Theory of Evolutionary Algorithms. In Theory of Evolutionary Algorithms. Dagstuhl Seminar Proceedings, Volume 8051, pp. 1-5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{arnold_et_al:DagSemProc.08051.2, author = {Arnold, Dirk V. and Auger, Anne and Rowe, Jonathan E. and Witt, Carsten}, title = {{08051 Executive Summary – Theory of Evolutionary Algorithms}}, booktitle = {Theory of Evolutionary Algorithms}, pages = {1--5}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2008}, volume = {8051}, editor = {Dirk V. Arnold and Anne Auger and Jonathan E. Rowe and Carsten Witt}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08051.2}, URN = {urn:nbn:de:0030-drops-14812}, doi = {10.4230/DagSemProc.08051.2}, annote = {Keywords: Evolutionary Algorithms, Theory of Evolutionary Algorithms} }

Document

**Published in:** Dagstuhl Seminar Proceedings, Volume 8051, Theory of Evolutionary Algorithms (2008)

We investigate the runtime of the Binary Particle Swarm Optimization (PSO) algorithm introduced by Kennedy and Eberhart (1997). The Binary PSO maintains a global best solution and a swarm of particles. Each particle consists of a current position, an own best position and a velocity vector used in a probabilistic process to update the particle's position. We present lower bounds for a broad class of implementations with swarms of polynomial size. To prove upper bounds, we transfer a fitness-level argument well-established for evolutionary algorithms (EAs) to PSO. This method is then applied to estimate the expected runtime on the class of unimodal functions. A simple variant of the Binary PSO is considered in more detail. The1-PSO only maintains one particle, hence own best and global best solutions coincide. Despite its simplicity, the 1-PSO is surprisingly efficient.
A detailed analysis for the function Onemax shows that the 1-PSO is competitive to EAs.

Dirk Sudholt and Carsten Witt. Runtime Analysis of Binary PSO. In Theory of Evolutionary Algorithms. Dagstuhl Seminar Proceedings, Volume 8051, pp. 1-22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{sudholt_et_al:DagSemProc.08051.6, author = {Sudholt, Dirk and Witt, Carsten}, title = {{Runtime Analysis of Binary PSO}}, booktitle = {Theory of Evolutionary Algorithms}, pages = {1--22}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2008}, volume = {8051}, editor = {Dirk V. Arnold and Anne Auger and Jonathan E. Rowe and Carsten Witt}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08051.6}, URN = {urn:nbn:de:0030-drops-14800}, doi = {10.4230/DagSemProc.08051.6}, annote = {Keywords: Particle swarm optimization, runtime analysis} }

Document

**Published in:** Dagstuhl Seminar Proceedings, Volume 6061, Theory of Evolutionary Algorithms (2006)

Ant Colony Optimization (ACO) has become quite popular in recent
years. In contrast to many successful applications, the theoretical foundation of
this randomized search heuristic is rather weak. Building up such a
theory is demanded to understand how these heuristics work as well as
to come up with better algorithms for certain problems. Up to now,
only convergence results have been achieved showing that optimal
solutions can be obtained in a finite amount of time. We present the
first runtime analysis of a simple ACO algorithm that
transfers many rigorous results with respect to the expected runtime
of a simple evolutionary algorithm to our algorithm. In addition,
we examine the choice of the evaporation factor, which is a crucial
parameter in such an algorithm, in greater detail and analyze its effect
with respect to the runtime.

Frank Neumann and Carsten Witt. Runtime Analysis of a Simple Ant Colony Optimization Algorithm. In Theory of Evolutionary Algorithms. Dagstuhl Seminar Proceedings, Volume 6061, pp. 1-17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{neumann_et_al:DagSemProc.06061.8, author = {Neumann, Frank and Witt, Carsten}, title = {{Runtime Analysis of a Simple Ant Colony Optimization Algorithm}}, booktitle = {Theory of Evolutionary Algorithms}, pages = {1--17}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2006}, volume = {6061}, editor = {Dirk V. Arnold and Thomas Jansen and Michael D. Vose and Jonathan E. Rowe}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06061.8}, URN = {urn:nbn:de:0030-drops-5928}, doi = {10.4230/DagSemProc.06061.8}, annote = {Keywords: Randomized Search Heuristics, Ant Colony Optimization, Runtime Analysis} }

X

Feedback for Dagstuhl Publishing

Feedback submitted

Please try again later or send an E-mail