Analysis of Evolutionary Algorithms on Fitness Function with Time-linkage Property
It addresses a foundational open problem in theoretical evolutionary computation by providing the first rigorous analysis for time-linkage functions, which is incremental as it builds on basic OneMax functions.
This paper tackles the theoretical analysis of evolutionary algorithms on optimization problems with time-linkage properties, where the objective function depends on historical solutions, and proves that randomized local search and (1+1) EA fail to find the optimum with high probability, while (μ+1) EA succeeds with high probability.
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.