Contributing to the theoretical understanding of Randomized Search Heuristics and their Computational Complexity
Abtract (TBA, but the research will be \(\mathcal{E}^2 \pi c\)).
Tuesdays at 16:00 CE(S)T, or one hour earlier to support speakers from East Asia and Oceania. Summer time ends on Oct, 25 (EU) and Nov, 1 (USA).
All talks use the following permanent Zoom link.
Open ZoomAbstract (TBA, but the research will be \(\mathcal{E}^2\pi c\)).
Abstract (TBA)
Abstract (TBA)
Multi-objective evolutionary algorithms (MOEAs) are popular tools for multi-objective optimization (MOO), and have been successfully applied to many real-world MOO problems. However, the theoretical study has lagged behind their practical success and remains largely confined to synthetic pseudo-Boolean functions. To close this gap, this paper–drawing inspiration from a class of popular continuous problems with real-world relevance– introduces a multi-objective benchmark defined on an integer space, featuring an analyzable landscape and the presence of local optima. We conduct a running time analysis on the proposed benchmark and derive several theoretical results. Specifically, we prove that a widely-studied MOEA, GSEMO, using unit-step mutation can be trapped in local optimal regions and fail to identify the Pareto front. Fortunately, we find that this difficulty can be overcome either by incorporating an ageing mechanism or using heavy-tailed mutations that allow multivalued changes along each dimension of an individual. In addition, we demonstrate the extendability of the proposed benchmark to more complex landscapes with numerous local optima, resembling well-established problems in the field (e.g., those from the ZDT and DTLZ suites). We hope this work is a step forward for the theoretical study of MOEAs on problems that are closely related to those commonly investigated in empirical research.
Abstract (TBA)
Abstract (TBA)
Abstract (TBA)
Abstract (TBA)
Abstract (TBA)
Randomized search heuristics such as stochastic gradient methods, simulated annealing, evolutionary algorithms, stochastic neural networks for optimization, ant colony and swarm optimization, and the cross-entropy method are frequently used across many scientific communities. They have been successfully applied in various domains, both for combinatorial and numerical optimization. Despite their success in practice, proving that such algorithms satisfy certain performance guarantees is still a difficult and widely open problem.
The mission of the Theory of Randomized Search Heuristics (ThRaSH) seminar series is to contribute to the theoretical understanding of randomized search heuristics, in particular of their computational complexity. The aim is to stimulate interactions within the research field and between people from different disciplines working on randomized algorithms. The primary focus is on discussing recent ideas and detecting challenging topics for future work, rather than on the presentation of final results.
École Polytechnique, France
Aberystwyth University, UK
Hasso Plattner Institute Potsdam, Germany
University of Birmingham, UK
Southern University of Science and Technology, China
Technical University of Denmark