Towards Running Time Analysis of Interactive Multi-Objective Evolutionary Algorithms

Evolutionary algorithms (EAs) are widely used for multi-objective optimization due to their population-based nature. Traditional multi-objective EAs (MOEAs) generate a set of solutions to approximate the Pareto front, leaving a decision maker (DM) with the task of selecting a preferred solution. However, this process can be inefficient and time-consuming, especially when there are many objectives or the subjective preference of DM is known. To address this issue, interactive MOEAs (iMOEAs) integrate decision making into the optimization process, i.e., update the population with the help of the DM. In contrast to their wide applications, there have existed only two pieces of theoretical works on iMOEAs, which considered interactive variants of the two simple single-objective algorithms, RLS and (1+1)-EA. This paper provides the first running time analysis for practical iMOEAs. Specifically, we prove that the expected running time of the well-developed interactive NSGA-II (R-NSGA-II) for solving the OneMinMax and OneJumpZeroJump problems are all asymptotically faster than the traditional NSGA-II. Meanwhile, we present a variant of OneMinMax, and prove that R-NSGA-II can be exponentially slower than NSGA-II. These results provide theoretical justification for the effectiveness of iMOEAs while identifying situations where they may fail. Experiments are also conducted to validate the theoretical results. This paper for the Hot-off-the-Press track at GECCO 2025 summarizes the work Tianhao Lu, Chao Bian, and Chao Qian. Towards Running Time Analysis of Interactive Multi-objective Evolutionary Algorithms. In: Proceedings of the AAAI Conference on Artificial Intelligence (AAAI'24), Vancouver, Canada, 2024, pp. 20777–85. [24]