Optimal Parameter Choices via Precise Black-Box Analysis
It has been observed that some working principles of evolutionary algorithms, in particular, the influence of the parameters, cannot be understood from results on the asymptotic order of the runtime, but only from more precise results. In this work, we complement the emerging topic of precise runtime analysis with a first precise complexity theoretic result. Our vision is that the interplay between algorithm analysis and complexity theory becomes a fruitful tool also for analyses more precise than asymptotic orders of magnitude. As particular result, we prove that the unary unbiased black-box complexity of the OneMax benchmark function class is $n \ln(n) - cn \pm o(n)$ for a constant $c$ which is between $0.2539$ and $0.2665$. This runtime can be achieved with a simple (1+1)-type algorithm using a fitness-dependent mutation strength. When translated into the fixed-budget perspective, our algorithm finds solutions which are roughly 13\% closer to the optimum than those of the best previously known algorithms. To prove our results, we formulate several new versions of the variable drift theorems, which also might be of independent interest.
Code (0)
등록된 구현이 없습니다.
Tasks
Evolutionary AlgorithmsSimilar Papers 제목 키워드 기반
Maximizing Drift is Not Optimal for Solving OneMax
It may seem very intuitive that for the maximization of the OneMax problem $\OM(x):=\sum_{i=1}^n{x_i}$ the best that an elitist unary unbiased search algorithm can do is to store a best so far solution, and to modify it …
On the Effectiveness of Simple Success-Based Parameter Selection Mechanisms for Two Classical Discrete Black-Box Optimization Benchmark Problems
Despite significant empirical and theoretically supported evidence that non-static parameter choices can be strongly beneficial in evolutionary computation, the question how to best adjust parameter values plays only a m…
Enhancing Parameter Control Policies with State Information
Parameter control and dynamic algorithm configuration study how to dynamically choose suitable configurations of a parametrized algorithm during the optimization process. Despite being an intensively researched topic in …
Optimal Hyperparameters for Deep LSTM-Networks for Sequence Labeling Tasks
Selecting optimal parameters for a neural network architecture can often make the difference between mediocre and state-of-the-art performance. However, little is published which parameters and design choices should be e…
ChunkingEvent DetectionHyperparameter OptimizationNamed Entity Recognition (NER)+2Synthesizing Pareto-Optimal Interpretations for Black-Box Models
We present a new multi-objective optimization approach for synthesizing interpretations that "explain" the behavior of black-box machine learning models. Constructing human-understandable interpretations for black-box mo…