When Does the Time-Linkage Property Help Optimization by Evolutionary Algorithms?

Recent theoretical works show that the time-linkage property challenges evolutionary algorithms to optimize. Here we consider three positive circumstances and give the first runtime analyses to show that the time-linkage property can also help the optimization of evolutionary algorithms. The problem is easier to optimize if the time-linkage property changes the optimal function value to an easy-to-reach one. We construct a time-linkage variant of the CLIFF_d problem with this feature and prove that conditional on an event that happens with Ω(1) probability, the (1+1) EA reaches the optimum in expected O(nlnn) iterations. It is much better than the expected runtime of Θ(n^d) for the original CLIFF_d. If the time-linkage property does not change the optimal function value but enlarges the optimal solution set, the problem is also possible to be easier to optimize. We construct another time-linkage variant of the CLIFF_d problem with this feature, and also prove an expected runtime of O(nlnn) (conditional on an event happening with Ω(1) probability), compared with the expected runtime of Ω(n^d-2) for the corresponding problem without the time-linkage property. Even if the time-linkage property neither changes the optimal function value nor the optimal solution set, it is still possible to ease this problem if the intermediate solution, from which the optimum is easier to reach, is more prone to be maintained. We construct a time-linkage variant of the Jump problem, and proved that the expected runtime is reduced from O(n^k) to O(n^k-1). Our experiments also verify the above theoretical findings.