This paper presents two novel deterministic initialization procedures for
K-means clustering based on a modified crowding distance. The procedures, named
CKmeans and FCKmeans, use more crowded points as initial centroids.
Experimental studies on multiple datasets demonstrate that the proposed
approach outperforms Kmeans and Kmeans++ in terms of clustering accuracy. The
effectiveness of CKmeans and FCKmeans is attributed to their ability to select
better initial centroids based on the modified crowding distance. Overall, the
proposed approach provides a promising alternative for improving K-means
clustering.

提出两种新的确定性初始聚类方法，名为 CKmeans 和 FCKmeans，基于修改后的拥挤距离，实验研究表明，该方法在聚类准确性方面优于 Kmeans 和 Kmeans ++，其中 CKmeans 和 FCKmeans 的有效性归因于它们基于修改后的拥挤距离选择更好的初始聚类中心的能力。总体而言，该方法为提高 K-means 聚类提供了一种有前途的选择。

CKmeans 和 FCKmeans：使用拥挤距离的 Kmeans 算法两种确定性初始化程序

CKmeans and FCKmeans : Two Deterministic Initialization Procedures For  Kmeans Algorithm Using Crowding Distance

The NSGA-II is one of the most prominent algorithms to solve multi-objective
optimization problems. Despite numerous successful applications, several
studies have shown that the NSGA-II is less effective for larger numbers of
objectives. In this work, we use mathematical runtime analyses to rigorously
demonstrate and quantify this phenomenon. We show that even on the simple
OneMinMax benchmark, where every solution is Pareto optimal, the NSGA-II also
with large population sizes cannot compute the full Pareto front (objective
vectors of all Pareto optima) in sub-exponential time when the number of
objectives is at least three. Our proofs suggest that the reason for this
unexpected behavior lies in the fact that in the computation of the crowding
distance, the different objectives are regarded independently. This is not a
problem for two objectives, where any sorting of a pair-wise incomparable set
of solutions according to one objective is also such a sorting according to the
other objective (in the inverse order).

本文使用数学运行时分析严格证明和量化了 NSGA-II 算法在多目标问题中呈现的困难现象，并表明在计算拥挤距离时，不同目标被视为独立。

NSGA-II 算法的运行时分析：多目标问题的低效性证明、量化与解释

Runtime Analysis for the NSGA-II: Proving, Quantifying, and Explaining the Inefficiency For Many Objectives

A recent runtime analysis (Zheng, Liu, Doerr (2022)) has shown that a variant
of the NSGA-II algorithm can efficiently compute the full Pareto front of the
OneMinMax problem when the population size is by a constant factor larger than
the Pareto front, but that this is not possible when the population size is
only equal to the Pareto front size. In this work, we analyze how well the
NSGA-II approximates the Pareto front when it cannot compute the whole front.
We observe experimentally and by mathematical means that already when the
population size is half the Pareto front size, relatively large gaps in the
Pareto front remain. The reason for this phenomenon is that the NSGA-II in the
selection stage computes the crowding distance once and then repeatedly removes
individuals with smallest crowding distance without updating the crowding
distance after each removal. We propose an efficient way to implement the
NSGA-II using the momentary crowding distance. In our experiments, this
algorithm approximates the Pareto front much better than the previous version.
We also prove that the gaps in the Pareto front are at most a constant factor
larger than the theoretical minimum.

本研究分析了 NSGA-II 算法在无法计算完整 Pareto 前沿时的逼近情况，使用瞬时拥挤距离的算法要比以前版本更好地逼近了 Pareto 前沿。