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 a theoretical viewpoint, more fine-grained performance measures are needed. Two complementary approaches have been suggested: fixed-budget analysis and fixed-target analysis. In this work, we conduct an in-depth study on the advantages and 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 the existing runtime result to a fixed-target result is highly non-trivial.
翻译:运行时间分析的目的是通过对运行时间进行数学分析,促进我们对进化算法的理解。在离散优化问题的背景下,运行时间分析典型地研究了找到最佳解决方案所需的时间。然而,从实践和理论的角度来看,都需要更细微的绩效衡量方法。建议了两种补充方法:固定预算分析和固定目标分析。在这项工作中,我们深入研究固定目标分析的优势和局限性。我们表明,与固定预算分析不同的是,与对离散进化算法的运行时间分析不同的是,许多传统方法不同于对离散进化算法的运行时间分析,在没有更大努力的情况下产生固定目标结果。我们用这种方法进行一些新的固定目标分析。然而,我们还指出了将现有运行时间结果扩大到固定目标结果的高度非三重的例子。