论文标题
与时间链接属性有关健身函数的进化算法的分析
Analysis of Evolutionary Algorithms on Fitness Function with Time-linkage Property
论文作者
论文摘要
在实际应用程序中，许多优化问题具有时间链接属性，即目标函数值依赖于当前解决方案以及历史解决方案。尽管近二十年来，对进化算法的严格理论分析已经迅速发展，但理论上了解时间链接问题的进化算法的行为仍然是一个开放的问题。本文采取了第一步，严格分析了时间链接函数的进化算法。基于基本的ONEMAX函数，我们提出了一个时间链接函数，其中最后一个时间步骤的第一个位值已集成，但与当前的第一位相同。我们证明，使用概率$ 1-O（1）$，随机的本地搜索和$（1+1）$ EA找不到最佳，并且概率$ 1-O（1）$（1）$，$（μ+1）$ ea可以达到最佳。
In real-world applications, many optimization problems have the time-linkage property, that is, the objective function value relies on the current solution as well as the historical solutions. Although the rigorous theoretical analysis on evolutionary algorithms has rapidly developed in recent two decades, it remains an open problem to theoretically understand the behaviors of evolutionary algorithms on time-linkage problems. This paper takes the first step to rigorously analyze evolutionary algorithms for time-linkage functions. Based on the basic OneMax function, we propose a time-linkage function where the first bit value of the last time step is integrated but has a different preference from the current first bit. We prove that with probability $1-o(1)$, randomized local search and $(1+1)$ EA cannot find the optimum, and with probability $1-o(1)$, $(μ+1)$ EA is able to reach the optimum.
