The diversity optimization is the class of optimization problems, in which we
aim at finding a diverse set of good solutions. One of the frequently used
approaches to solve such problems is to use evolutionary algorithms which
evolve a desired diverse population. This approach is called evolutionary
diversity optimization (EDO).
In this paper, we analyse EDO on a 3-objective function LOTZ$_k$, which is a
modification of the 2-objective benchmark function (LeadingOnes,
TrailingZeros). We prove that the GSEMO computes a set of all Pareto-optimal
solutions in $O(kn^3)$ expected iterations. We also analyze the runtime of the
GSEMO$_D$ (a modification of the GSEMO for diversity optimization) until it
finds a population with the best possible diversity for two different diversity
measures, the total imbalance and the sorted imbalances vector. For the first
measure we show that the GSEMO$_D$ optimizes it asymptotically faster than it
finds a Pareto-optimal population, in $O(kn^2\log(n))$ expected iterations, and
for the second measure we show an upper bound of $O(k^2n^3\log(n))$ expected
iterations. We complement our theoretical analysis with an empirical study,
which shows a very similar behavior for both diversity measures that is close
to the theory predictions.

本研究分析了进化多目标优化算法在多样性优化问题中的应用，并证明了一种算法能够在预期的迭代次数下计算出所有 Pareto 最优解。同时，还分析了该算法找到具有最佳多样性的种群所需的迭代次数，并通过实证研究验证了理论预测的准确性。

多目标问题（前导 1，尾随 0）的进化多样性优化的运行时分析

Runtime Analysis of Evolutionary Diversity Optimization on the  Multi-objective (LeadingOnes, TrailingZeros) Problem

We consider whether conditions exist under which block-coordinate descent is
asymptotically efficient in evolutionary multi-objective optimization,
addressing an open problem. Block-coordinate descent, where an optimization
problem is decomposed into $k$ blocks of decision variables and each of the
blocks is optimized (with the others fixed) in a sequence, is a technique used
in some large-scale optimization problems such as airline scheduling, however
its use in multi-objective optimization is less studied. We propose a
block-coordinate version of GSEMO and compare its running time to the standard
GSEMO algorithm. Theoretical and empirical results on a bi-objective test
function, a variant of LOTZ, serve to demonstrate the existence of cases where
block-coordinate descent is faster. The result may yield wider insights into
this class of algorithms.

存在一种条件，使得块坐标下降在进化多目标优化中达到渐近效率，我们考虑了这个开放问题并提出了块坐标版本的 GSEMO 算法来与标准 GSEMO 算法的运行时间进行比较，理论和实证结果表明了块坐标下降更快的情况的存在，这一结果可能对此类算法产生更广泛的见解。