论文标题
固定目标运行时分析
Fixed-Target Runtime Analysis
论文作者
论文摘要
运行时分析的目的是通过数学分析其运行时间来为我们对进化算法的理解做出贡献。在离散优化问题的背景下，运行时分析经典地研究找到最佳解决方案所需的时间。但是，无论是从实用的和理论上的角度来看，都需要采取更细粒度的绩效指标，以获得对主要工作原理及其由此产生的绩效影响的更详细的理解。已经提出了两种互补方法：固定预算分析和固定目标分析。 在这项工作中，我们对固定目标分析的优势和局限性进行了深入研究。我们表明，与固定预算分析不同，离散进化算法的运行时分析中的许多经典方法无需更大的努力而产生固定目标结果。我们使用它来进行许多新的固定目标分析。但是，我们还指出了示例，其中将现有运行时结果扩展到固定目标结果是高度不平凡的。
Runtime analysis aims at contributing to our understanding of evolutionary algorithms through mathematical analyses of their runtimes. In the context of discrete optimization problems, runtime analysis classically studies the time needed to find an optimal solution. However, both from a practical and from a theoretical viewpoint, more fine-grained performance measures are needed to gain a more detailed understanding of the main working principles and their resulting performance implications. Two complementary approaches have been suggested: fixed-budget analyses and fixed-target analyses. In this work, we conduct an in-depth study on the advantages and the limitations of fixed-target analyses. We show that, different from fixed-budget analyses, many classical methods from the runtime analysis of discrete evolutionary algorithms yield fixed-target results without greater effort. We use this to conduct a number of new fixed-target analyses. However, we also point out examples where an extension of existing runtime results to fixed-target results is highly non-trivial.
