## 1 Introduction  
Clustering is a fundamental machine learning [1] approach for extracting useful information from the data of such application domains as pattern recognition, image segmentation, text analysis, medicine, bioinformatics, and Artificial Intelligence. K-Means [2; 3; 4] is a classical clustering algorithm often used due to its simplicity and efficiency. The aim of K-Means is to partition \(N\) data points \(X~{}=~{}\left\{x_{i}\right\}_{i=1}^{N}\), e.g., \(x_{i}\in R^{D}\), in \(K\), with \(2\leq K\ll N\), subsets (said clusters) by ensuring that points belonging to the same cluster are similar to one another, and points in different clusters are dissimilar. The Euclidean distance between data points usually expresses the similarity. Every cluster is represented by its central point or _centroid_. K-Means aims to optimize (minimize) the _Sum-of-Squared Errors_ (_SSE_) cost, a sort of internal variance (or distortion) in clusters. Recently, K-Means properties have been studied in depth [5; 6; 7]. A crucial aspect is the procedure which initializes the centroids (_seeding_ method). In fact, the accuracy of a clustering solution strongly depends on the initial centroids. A basic limitation of K-Means is the adoption of a _local strategy_ for managing centroids, which determines the algorithm often blocks in a sub-optimal solution. Random Swap [8; 9] and genetic/evolutionary approaches [10; 11; 12] are examples of more sophisticated clustering algorithms that try to remedy this situation by adopting a _global strategy_ of centroid management. At each iteration of Random Swap, a centroid is randomly selected and replaced by a randomly chosen data point of the dataset. The \(SSE\) of the new configuration is then compared to that of the previous centroids' configuration and, if it is diminished, the configuration becomes current for the next iteration. The algorithm can be iterated a maximum number of times. Random Swap has been demonstrated to approach, in many cases, the obtainment of a solution _close_ to the optimal one, even with a possible increase in the computational time. The contribution of this paper is the development of two new clustering algorithms by extending the K-Means and Random Swap through an evolutionary technique [10; 13] and careful seeding. The two algorithms are Population-Based K-means (PB-KM) and Population-Based Random Swap (PB-RS). They borrow ideas from the evolutionary algorithms underlying GA-K-Means [10] and Recombator-K-Means [11; 12] and consist of two steps. In the first step, a population of candidate centroid solutions is initially built, by executing \(J\) times the Lloyd's K-Means or Random Swap along with the Greedy-K-Means++ (GKM++) [11; 12; 14] seeding method, which is effective for producing a careful configuration of centroids with a reduced \(SSE\) cost. In the second step, PB-KM and PB-RS start from a configuration of centroids extracted by using GKM++ on the candidate centroids of the population. Then, they recombine centroids until a satisfying solution minimizes the \(SSE\) cost. The greater the number of repetitions is during the second step (independent restarts of PB-KM, the number of swap iterations of PB-RS), the higher the possibility of getting a combined solution near the best one is. Regarding reliability and accuracy, PB-KM significantly enhances the classical Lloyd's repeated K-Means in globular, spherical, and Gaussian-shaped clusters [5; 6]. PB-RS is better suited for studying general datasets with an irregular distribution of points. A common issue of PB-KM and PB-RS, though, is the assumption that good clustering follows by minimizing the \(SSE\) cost. Unfortunately, this is not true for some challenging datasets [9] which can only be approximated through the proposed and similar tools. To cope with large datasets, PB-KM and PB-RS systematically use parallel computing. Currently, the two algorithms are developed in Java using lambda expressions and parallel streams [15; 16].