Motivated by recent works showing significant untapped potential in the design of variation operators for randomized search heuristics, we take up the challenge of analyzing the power and limits of generalizing their design.
Randomized search heuristics are general-purpose optimization algorithms, designed to provide good solutions for problems that cannot be solved by exact approaches---for example, because the quality of the solution candidates can only be assessed through simulations or physical experiments or because we lack the time or the knowledge to design a problem-tailored solution. Such situations are ubiquitous in our everyday lives, so that much scientific and industrial progress depends on efficient search heuristics.
Variation operators are a key component of randomized search heuristics. They determine how new solution candidates are generated from previously evaluated ones. Variation operators differ in how they balance the trade-off between small local moves with decent probability of improving over the current-best solution and riskier sampling at larger distances, with the hope to identify more promising areas of the search space. Recent works, partially driven by the PI, indicate that state-of-the-art variation operators are too risk-averse, with severe effects on the overall performance of randomized search heuristics.
The goal of the VARIATION project is to identify optimal variation operators with proven performance guarantees. To this end, we will formulate their design as a meta-optimization problem, which we analyze through rigorous algorithm analysis and complexity-theoretic approaches. We will use our theoretical insights to derive variation operators whose performance gains will be empirically validated on diverse sets of common optimization and machine learning benchmarks as well as on real-world applications from systems biology and from the automotive industry.
Madame Carola Doerr (LIP6)
The author of this summary is the project coordinator, who is responsible for the content of this summary. The ANR declines any responsibility as for its contents.
Help of the ANR 112,971 euros
Beginning and duration of the scientific project: June 2022 - 24 Months