Analysis of Multiobjective Evolutionary Algorithms on Fitness Function With Time-Linkage Property
研究了多目标进化算法在具有时间链接性质的优化问题上的表现，构造了基准问题COCZTL，证明了GSEMO无法找到帕累托前沿，而NSGA-II和提出的GSEMO/Ps算法能成功找到，后者期望运行时间为O(n^3)。
The time-linkage property, which means that the optimization problem not only relies on the current solution but also on historical solutions, is common in real-world applications. Although the theoretical studies on multi-objective evolutionary algorithms (MOEAs) have been rapidly developed in decades, there exists no theoretical analyses for MOEAs on time-linkage problems. This paper aims to take the first step towards rigorously analyzing MOEAs on time-linkage problems. To be specific, we constructed a multi-objective optimization problem with the time-linkage property based on the benchmark COCZ problem, called COCZTL. For this problem, we proved that GSEMO cannot find the Pareto front, but NSGA-II can find it with a probability of at least Ω(1n). Furthermore, we proposed an algorithm with auxiliary populations called GSEMO/Ps that is based on GSEMO. The results show that GSEMO/Ps can find the Pareto front of COCZTL and the expected runtime is at most O(n3). This paper provides insight into understanding the optimization behaviors of MOEAs in the multi-objective optimization problems with the time-linkage property.