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\)).
We seek to understand the optimization behavior for Vertex Coloring in two ways: By analyzing what types of local optima are present and by finding run time bounds. For a variety of graph classes each, we determine whether the induced landscapes are unimodal, plateau-unimodal (all optima are just one plateau), equimodal (all local optima are global) or truly multimodal. We do this for two different neighborhood operators, one based on making only a single change and one also allowing swaps (interchanging two parts of the solution). Further, we show that even on unimodal instances, the run time is still exponential on two simple graph classes. We introduce an improved fitness function that produces a more favourable landscape and therefore allows for a polynomial run time.
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)
Genetic Programming (GP) is a search paradigm inspired from natural evolution for the automated discovery of expressions, functions, and computer programs. Cartesian GP (CGP) is a flavor of GP that uses a graph-based model to encode candidate programs, as contrasted to the conventional Tree-based GP (TGP). Since its inception two decades ago, CGP has predominantly been analyzed empirically, thus little is known regarding its theoretical performance guarantees.
This work analyzes CGP for the MAX problem, which has been only rigorously studied for TGP with a proven expected runtime superlinear in the optimal program length \(n\). We prove that the expected time for the (\(1\)+\(1\)) CGP employing common mutation operators to evolve an equivalent optimal of the same output is polylogarithmic in \(n\), specifically at most \(O(\log^9{n})\). This is remarkable, as it shows an exponential speedup by switching to CGP. Our results shed light on the benefit and the compactness of the graph-based representation for programs, and on how CGP can navigate its search and fitness spaces efficiently. This is a first proven performance guarantee for CGP on an established benchmark problem. Experiments complement our theoretical findings.
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