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

Diversity optimization seeks to discover a set of solutions that elicit
diverse features. Prior work has proposed Novelty Search (NS), which, given a
current set of solutions, seeks to expand the set by finding points in areas of
low density in the feature space. However, to estimate density, NS relies on a
heuristic that considers the k-nearest neighbors of the search point in the
feature space, which yields a weaker stability guarantee. We propose Density
Descent Search (DDS), an algorithm that explores the feature space via gradient
descent on a continuous density estimate of the feature space that also
provides stronger stability guarantee. We experiment with DDS and two density
estimation methods: kernel density estimation (KDE) and continuous normalizing
flow (CNF). On several standard diversity optimization benchmarks, DDS
outperforms NS, the recently proposed MAP-Annealing algorithm, and other
state-of-the-art baselines. Additionally, we prove that DDS with KDE provides
stronger stability guarantees than NS, making it more suitable for adaptive
optimizers. Furthermore, we prove that NS is a special case of DDS that
descends a KDE of the feature space.

多样性优化研究中，使用密度下降搜索（DDS）算法通过连续密度估计的特征空间梯度下降进行特征空间的探索，并通过核密度估计（KDE）和连续标准化流（CNF）两种密度估计方法，在多个标准多样性优化基准测试中优于 Novelty Search（NS）和其他先进对照算法。

密度下降用于多样性优化

Density Descent for Diversity Optimization

Finding and selecting new and interesting problems to solve is at the heart
of curiosity, science and innovation. We here study automated problem
generation in the context of the open-ended space of python programming
puzzles. Existing generative models often aim at modeling a reference
distribution without any explicit diversity optimization. Other methods
explicitly optimizing for diversity do so either in limited hand-coded
representation spaces or in uninterpretable learned embedding spaces that may
not align with human perceptions of interesting variations. With ACES
(Autotelic Code Exploration via Semantic descriptors), we introduce a new
autotelic generation method that leverages semantic descriptors produced by a
large language model (LLM) to directly optimize for interesting diversity, as
well as few-shot-based generation. Each puzzle is labeled along 10 dimensions,
each capturing a programming skill required to solve it. ACES generates and
pursues novel and feasible goals to explore that abstract semantic space,
slowly discovering a diversity of solvable programming puzzles in any given
run. Across a set of experiments, we show that ACES discovers a richer
diversity of puzzles than existing diversity-maximizing algorithms as measured
across a range of diversity metrics. We further study whether and in which
conditions this diversity can translate into the successful training of puzzle
solving models.

通过使用大型语言模型（LLM）生成的语义描述符直接优化有趣的多样性，我们提出了一种新的自动创作生成方法（ACES），用于在 Python 编程难题的无限空间中生成新颖且可行的目标，从而发现多样化的可解编程难题，并研究其对难题求解模型训练的影响。