  Evolutionary algorithms (EAs) are widely used for multi-objective
optimization due to their population-based nature. Traditional multi-objective
EAs (MOEAs) generate a large 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 preferences of DM is known. To
address this issue, interactive MOEAs (iMOEAs) combine decision making into the
optimization process, i.e., update the population with the help of the DM. In
contrast to their wide applications, there has existed only two pieces of
theoretical works on iMOEAs, which only considered interactive variants of the
two simple single-objective algorithms, RLS and (1+1)-EA. This paper provides
the first running time analysis (the essential theoretical aspect of EAs) for
practical iMOEAs. Specifically, we prove that the expected running time of the
well-developed interactive NSGA-II (called R-NSGA-II) for solving the OneMinMax
and OneJumpZeroJump problems is $O(n \log n)$ and $O(n^k)$, respectively, which
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.
