标题： 利用状态信息增强参数控制策略 显示英文标题

标题： Enhancing Parameter Control Policies with State Information

摘要： 参数控制和动态算法配置研究如何在优化过程中动态选择参数化算法的合适配置。 尽管这是进化计算中被广泛研究的主题，但已知的最优控制策略仅限于非常少的情况，这限制了实现这些策略的自动化方法的发展。 通过这项工作，我们提出了四个新的基准，我们推导出了最优或接近最优的控制策略。 更具体地说，我们考虑通过RLS$_{k}$对\LeadingOnes 函数进行优化，这是一种允许动态选择突变强度$k$的局部搜索算法。 这些基准的不同之处在于算法可以利用哪些信息来设置其参数并选择后代。 在现有的运行时间结果中，可利用的信息通常仅限于当前最优解的质量。 在这项工作中，我们考虑关于算法当前状态的额外信息如何帮助做出更好的参数选择，以及这些选择如何影响性能。 具体来说，我们允许算法使用关于当前\OneMax 值的信息，并发现这使得参数选择更加有效，尤其是在边缘状态下。 尽管这些状态很少被算法访问，但这样的策略在预期运行时间方面带来了显著的加速。 这使得所提出的基准成为分析丰富状态空间中参数控制方法以及它们通过捕捉正确参数选择带来的性能改进来找到最优策略能力的具有挑战性但有前景的测试平台。 显示英文摘要

摘要： 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 evolutionary computation, optimal control policies are known only for very few cases, limiting the development of automated approaches to achieve them. With this work we propose four new benchmarks for which we derive optimal or close-to-optimal control policies. More precisely, we consider the optimization of the \LeadingOnes function via RLS$_{k}$, a local search algorithm allowing for a dynamic choice of the mutation strength $k$. The benchmarks differ in which information the algorithm can exploit to set its parameters and to select offspring. In existing running time results, the exploitable information is typically limited to the quality of the current-best solution. In this work, we consider how additional information about the current state of the algorithm can help to make better choices of parameters, and how these choices affect the performance. Namely, we allow the algorithm to use information about the current \OneMax value, and we find that it allows much better parameter choices, especially in marginal states. Although those states are rarely visited by the algorithm, such policies yield a notable speed-up in terms of expected runtime. This makes the proposed benchmarks a challenging, but promising testing ground for analysis of parameter control methods in rich state spaces and of their ability to find optimal policies by catching the performance improvements yielded by correct parameter choices.