## 3 Population-Based Clustering Algorithms  
### Pg-Km  
The proposed Population-Based K-Means (PB-KM) algorithm was inspired by the operation of both Recombinator-K-Means [11; 12] and GA-K-Means [10]. The design is based on a more simple, yet effective, clustering approach. PB-KM is organized into two steps (see Algorithm 4). The first step is devoted to the initialization of the population. The second step recombines the centroids of the population toward a final accurate clustering solution. As in GA-K-Means, an elitist approach is usually used for managing the population. J solutions achieved via Lloyd's K-Means seeded by GKM++ are used to initialize the population, thus containing J \(\ast\) K points. Each initial solution is the _best_ one, which emerges after R\({}_{1}\) repetitions of the K-Means. In the case R\({}_{1}\ =\ 1\), the population is set as in Recombinator-K-Means. A value R\({}_{1}>1\) allows for the population to be preliminarily established with J \"best\" solutions, as can happen with GA-K-Means. It is worth noting that, unlike Recombinator-K-Means, PB-KM rests on the basic GKM++ seeding without using a weighting mechanism. The evolutionary iterations in the second step of PB-KM consist of \(R_{2}\) repetitions of K-Means, fed by GKM++ seeding applied to the population instead of the dataset. The clustering result is the emerging best solution among the \(R_{2}\) executions of K-Means. In other words, the crossover operation coincides with applying the GKM++ seeding followed by the optimization of K-Means. If the emerged solution has an SSE value less than that of the current best solution, it becomes the current one and the obtained centroids are replaced (_mutation_ operation) in the population by the centroid configuration which was selected by GKM++. Algorithm 4 describes the two steps of PB-KM which depend on three parameters: J, R\({}_{1}\) and R\({}_{2}\). In step 1 the writing run (K-Means, GKM++, \(X\)) expresses that K-Means is executed with the GKM++ seeding method applied to the data points of the dataset \(X\). In step 2, K-Means is seeded by GKM++ applied to the centroid points of the population \(\wp\). The \(SSE\) cost, though, is always computed on the entire \(X\) dataset, partitioned according to the candidate solution (_sand_) suggested by K-Means. ```
1. Setup population \(\wp\leftarrow\varnothing\) repeat | times[  costBest\(\leftarrow\)\(\infty\), candBest\(\leftarrow\)\(\
eg\) repeat \(R_{1}\) times[  cand\(\leftarrow\)run(K-Means,GKM++,\(X\))  cost\(\leftarrow\)SSE(cand,\(X\)) if(cost\(<\)costBest){  costBest\(\leftarrow\)cost  candBest\(\leftarrow\)\(\leftarrow\)\(\leftarrow\)\(\leftarrow



The parameters J, R\({}_{1}\) and R\({}_{2}\) depend on the handled dataset and the number of clusters \(K\). In many cases, a value J \(=~{}25\) was found to be sufficient in approaching an accurate solution. For regular datasets, e.g., with spherical clusters regularly located in the data space, even \(R_{1}~{}=~{}1\) can be adopted. A small or moderate value, e.g., \(R_{1}~{}=~{}3\), can be used in more complex datasets. Generally speaking, the greater the value of \(R_{2}\) is, the higher the chance of hitting a solution close to the optimal one is. The computational cost of the two steps of PB-KM is directly derived from the Repeated K-Means behavior and the use of GKM++. In particular, the first step has a linear cost \(O(J\ R_{1}[KSND+KNID+ND])\), whereby in the squared brackets, there is first the GKM++ cost, then the K-Means cost (\(I\) is the number of iterations for reaching the convergence) and finally the cost for computing the \(SSE\) value. The second step has a similar cost when one considers that the seeding is fed by the population, which has J \(*\) K points: \(O\big{(}R_{2}[JK^{2}SD+KNID+ND]\big{)}\). ### Pb-Rs

The setup population step of PB-RS consists of running J times the parallel version of Random Swap described in [9], each run continued for T swap iterations (e.g., T \(=~{}5000\)) and storing in the population \(\wp\) each emerged solution.