## 2 Methods
### CUDA Implementation of Greedy Agglomerative Procedures
### New Algorithm

As in local search algorithms, in accordance with the general idea of (1+1)-EAs, our new algorithm successively improves the single intermediate solution. To improve it, the AGGLr procedure is applied to it (see Algorithm 3) with an additional intermediate solution randomly generated as the second parameter \(S_{2}\), which is improved by the ALA procedure. A similar idea was applied for the k-means problem in VNS algorithms with randomized neighborhoods [54], which we included in the list of algorithms for comparison. The key feature of the new algorithm is that it does not fix values of the r parameter nor does it generate r values with equal probability, but it adjusts the values of the generation probabilities for each of the possible r values in accordance with the results obtained. If the use of the AGGLr--procedure has resulted in an improvement in the value of the objective function, our algorithm increases the probability \(P_{r}\) for the used \(r\) and for values close to it. The new algorithm can be described as follows in Algorithm 8. ```
Randomly select a subset \(S\subset[A_{1},\ldots,A_{N}]\); \(S\gets ALA(S)\); assign \(P_{i}\gets 1/p\)\(\forall i=\overline{1,p}\); repeat randomly select a subset \(S_{2}\subset[A_{1},\ldots,A_{N}]\); \(S_{2}\gets ALA(S_{2})\); in proportion to the values of the probabilities \(\text{Pi}\), \(i=\overline{1,p}\), choose the value of \(\text{r}\subset\{\overline{1,p}\}\); \(S_{3}\leftarrow\text{AGGLr}(S_{3},S_{2})\); if\(F(S_{3})<F(S)\)then \(P_{i}\gets k_{1}\cdot P_{i}\)\(\forall i=\overline{\left\lceil\frac{r}{k_{2}}\right\rceil}\), \(\min\{p,k_{2}\cdot r\}\); // we used \(k_{1}=1.1\) and \(k_{2}=1.5\). \(P_{i}\leftarrow\frac{p}{\sum_{i=1}^{n}P_{i}}\forall i=\overline{1,p}\); // probability normalization \(S\gets S_{3}\); endif; until time limitation is reached. return\(S\). ```

**Algorithm 8** Aggl-EA ()

## 3 Results of Computational Experiments

In all our experiments, we used the classic datasets from the UCI Machine Learning and Clustering basic benchmark repositories [94; 95; 105]: (a) Individual Household Electric Power Consumption (IHEPC)--energy consumption data of households during several years, more than 2 million demand points (data vectors) in \(\mathbb{R}^{2}\), 0-1 normalized data, \"date\" and \"time\" columns removed; (b) BIRCH3: 100 groups of points of random size, 100,000 demand points in \(\mathbb{R}^{2}\); (c)d S1 and S4 datasets, respectively: Gaussian clusters with cluster overlap (5000 demand points in \(\mathbb{R}^{2}\)); (e) Mopsi-Joensuu: geographic locations of users (6014 data vectors, 2 dimensions) in Joensuu city; (f) Mopsi-Finland: geographic locations of users (13,467 data vectors, 2 dimensions) in Finland. For our computational experiments, we used the following test system: Intel Core 2 Duo E8400 CPU, 16 GB RAM, NVIDIA GeForce GTX1050 ti GPU with 4096 MB RAM, floating-point performance 2138 GFLOPS. This choice of the GPU hardware was made due to its prevalence, and also one of the best values of the price/performance ratio. The program code was written in C++. We used Visual C++ 2017 compiler embedded into Visual Studio v.15.9.5, NVIDIA CUDA 10.0 Wizards, and NVIDIA Nsight Visual Studio Edition CUDA Support v.6.0.0. For all datasets, 30 attempts were made to run each of algorithms (Algorithms 1-6).