# K-Means Genetic Algorithms with Greedy Genetic Operators

Authors: Lev Kazakovtsev; Ivan Rozhnov; Guzel Shkaberina; Viktor Orlov
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

Thek-means problem is one of the most popular models of cluster analysis. The problem is NP-hard, and modern literature offers many competing heuristic approaches. Sometimes practical problems require obtaining such a result (albeit notExact), within the framework of the k-means model, which would be difficult to improve by known methods without a significant increase in the computation time or computational resources. In such cases, genetic algorithms with greedy agglomerative heuristic crossover operator might be a good choice. However, their computational complexity makes it difficult to use them for large-scale problems. The crossover operator which includes the k-means procedure, taking the absolute majority of the computation time, is essential for such algorithms, and other genetic operators such as mutation are usually eliminated or simplified. The importance of maintaining the population diversity, in particular, with the use of a mutation operator, is more significant with an increase in the data volume and available computing resources such as graphical processing units (GPUs). In this article, we propose a new greedy heuristic mutation operator for such algorithms and investigate the influence of new and well-known mutation operators on the objective function value achieved by the genetic algorithms for large-scale k-means problems. Our computational experiments demonstrate the ability of the new mutation operator, as well as the mechanism for organizing subpopulations, to improve the result of the algorithm.


---

## Body

## 1. Introduction

Thek-means problem is a continuous unconstrained global optimization problem which has become a classic clustering model. This problem is proved to be NP-hard [1, 2], so it is necessary to find a compromise between the computation time and the solution preciseness. The aim of the problem is to find set S=X1,…,Xk of k points and X1,…,Xk∈ℝd called centroids in a d-dimensional space that minimizes the sum of squared distances from N known points (data vectors) A1,…,AN∈ℝd to the nearest centroid [3]:(1)FX1,…,Xk=FS=∑i=1NminX∈X1,…,XkLAi,X2⟶minX1,…Xk∈ℝd,where L· is the distance between two points (usuallyEuclidean) and k is given.Data vector indexes for which thejth centroid is the nearest one form a set (cluster) Cj, j=1,k¯. An equivalent problem setting is as follows:(2)FX1,…,Xk=∑j=1k∑i∈CjLAi,Xj2⟶min,where Xj is the centroid of the jth cluster.The simplest and most popular local search algorithm is thek-means algorithm [4, 5] also called Alternate Location and Allocation (ALA) procedure [6, 7] or Lloyd algorithm. Similar procedure called EM (Expectation Maximization) [8, 9] and its modifications [10–12] are the most popular algorithms for separating the mix probability distribution. The k-means algorithm improves an intermediate solution sequentially, which enables us to find a local minimum.Technically, this is not a true local search algorithm in terms of continuous optimization, as it searches for a new solution not necessarily in theε-neighborhood of an existing solution. Nevertheless, it enables us a solution which is locally optimal in ε-neighborhood.If we use distances instead of squared distances in (1), we deal with the continuous p-median problem. The similarity of these NP-hard problems [13, 14] allows us to use similar approaches to solving them. However, unlike the p-median problem with Euclidean distances, finding the exact solution of a 1-means problem (k-means problem with k=1 or the centroid search problem) in accordance with Algorithm 1 is trivial, and finding a local minimum of the k-means problem takes less computational resources. This allows the local search to be integrated into various effective global search strategies.Algorithm 1:kMeans().
Require: Set of k initial centroids X1,…,Xk.(1)
ForEach centroidXi, i=1,k¯, define its cluster Ci⊂A1,…,AN as the subset of data vectors having closest centroid Xi.(2)
ForEach clusterCi, i=1,k¯, recalculate its centroid as follows: Xi=∑j∈CiAj⋅Ci−1.(3)
Repeat from Step 1 if Steps 1, 2 made any changes.In the early attempts to solve thep-median problem by exact methods (its discrete modifications), the authors used a branch and bound algorithm [15–17] for solving very small problems. In [18–20], the authors reviewed various heuristic solution techniques for k-means and p-median problems. In [21–23], the authors presented local search approaches including the Variable Neighborhood Search (VNS) and concentric search. In [22], Drezner et al. proposed heuristic procedures including the genetic algorithm (GA), for rather small datasets.Many approaches, based on the data reducing [24], simplify the problem by selection of some part of the initial dataset and then use these results as an initial solution to the k-means algorithm on the complete dataset [25–28]. Such aggregating as well as reducing the number of the data vectors [29] enables us to solve large-scale problems within a reasonable time. However, such approaches lead to a reduction in preciseness. In our research aimed at obtaining the most precise solutions, we consider only the methods which estimate the objective function (1) directly, without aggregation or approximation approaches.Modern publications offer many heuristic procedures [19, 30] for setting the initial centroids for the k-means algorithm, most of them belong to various evolutionary and random search methods. Local search algorithms and their randomized versions are widely presented. For instance, Variable Neighborhood Search (VNS) algorithms [23, 31, 32] or agglomerative algorithms [33, 34] sometimes show good results. A large number of articles are devoted to the initialization procedures for local search algorithms, such as random seeding and estimating the distribution of the data vectors [30]. The challenge is that, in many cases, even multiple runs of simple local search algorithms from various randomly generated solutions do not lead to a solution that is close to the global optimum. More advanced algorithms enable us to get the objective function (1) values many times better than the local search methods [32].The use of genetic algorithms and other evolutionary approaches to improve the results of the local search is a widely used idea [35–38]. Such algorithms recombine the local minima obtained by the k-means algorithm. GAs operate with a certain set (population) of candidate solutions and include special genetic operators (algorithms) of initialization, selection, crossover, and mutation. The mutation operator randomly changes the resulting solutions and provides some diversity in the population.However, in genetic algorithms, as the number of iterations increases, the population degenerates into a certain set of solutions close to each other. Larger populations as well as dynamically growing populations improve this situation. However, simpler algorithms based on the use of the same greedy agglomerative procedures [32, 39] often show better results within the same computation time.In this research, we do not discuss the adequacy of thek-means clustering model, which is actually questionable. We only focus on the preciseness and stability of the obtained objective function value (1) within the framework of the k-means model.There are situations when the cost of error is high [9]. In these cases, as well as when comparing the accuracy of an algorithm with a certain standard solution (not necessarily globally optimal), we need to get a result that would be difficult to enhance by other known methods without meaningful increase of the computation time. Evolution of parallel processing systems such as graphics processing units (GPUs) makes multiple runs of local search algorithms very cheap. In this case, large-scale problems (up to several millions of data vectors) can be solved with the use of the most advanced algorithms providing the highest preciseness. As our study shows, for large-scale problems, further improvement in the results of the genetic algorithms with greedy heuristic crossover can be achieved by using a special mutation operator and partially isolated solution subpopulations.The aim of this paper is to introduce a newk-Means Genetic Algorithm with the greedy agglomerative crossover operator, a special greedy agglomerative mutation operator, and subpopulations.The rest of this article is organized as follows. In Section2, we propose a brief overview of known approaches to the development of k-means genetic algorithms. In Section 3, we give an overview of known mutation genetic operators used in k-median genetic algorithms in accordance with various approaches to chromosome encoding as well as other instruments for increasing the population diversity. In Section 4, we propose new modifications to the genetic algorithms with greedy heuristic crossover operator. Such modifications include partially isolated subpopulations and the use of a new mutation operator based on the greedy heuristic procedure. In Section 5, we describe the results of our computational experiments which demonstrate the efficiency of our new modifications on large datasets.


## 2.K-Means Genetic Algorithms

The idea of various genetic algorithms is based on a recombination (interchange) of elements in a set (“population”) of candidate solutions (“individuals”) encoded by “chromosomes.” Such elements of the chromosomes are called “genes” or “alleles.” Each chromosome is a vector of genes (bits, integers, or real numbers) representing a solution. The goal of gene recombination is achieving the best value of an objective function called “fitness function.” The appearance of the first genetic algorithms for solving the discretep-median problem [40] preceded the genetic algorithms for the k-means problem (k-Means Genetic Algorithms). Alp et al. [41] proposed a rather fast and precise algorithm with a special “greedy” (agglomerative) heuristic procedure used as the crossover genetic operator for the network p-median problem. Such algorithms solve discrete network problems and use a very simple binary chromosome encoding (1 for the network nodes selected as the centers of the clusters, and 0 for those not selected).In the genetic algorithms for thek-means and similar problems with binary-encoded chromosomes, many mutation techniques can be used. For example, in [42], the authors represent the chromosome with binary strings composed from binary-encoded features (coordinates) of the centroids. The mutation operator arbitrarily alters one or more components (binary substrings) of a selected chromosome.If the centers or centroids are searched for in a continuous space, some genetic algorithms still use the binary encoding [38, 43, 44]. In the k-means algorithm, its initial solutions are usually subsets of the dataset A1,…,AN. In such chromosome code, 1 means that the corresponding data vector must be selected as an initial centroid and 0 for those not selected. In this case, some local search algorithm (k-means algorithm or similar) is used at each iteration of the GA to estimate the final value (local minimum) of the objective function (1).In [45], the authors refer to their algorithm as “Evolutionary k-Means.” However, they actually solved an alternative problem which aimed to increase the clustering stability instead of minimizing (1). Their algorithm operates with binary consensus matrices and uses two types of mutation genetic operators: cluster split (dissociative) and cluster merge (agglomerative) mutation. In [46], the chromosomes are strings of integers representing the cluster number for each of the clustered objects, and the authors solve the k-means problem with simultaneous determining the number of clusters based on the silhouette [47] and Davies and Bouldin criteria [48], which are used as the fitness functions. Thus, in [46], the authors also solve a problem with the mathematical statement other than (1). Similar encoding is used in [37] where the authors propose a mutation operator which changes the assignment of individual data vectors to the clusters.In [49], the authors described the mutation operator as a procedure that guarantees population diversity (variability). Usually, for the k-means and p-median problems, the mutation randomly changes one or many chromosomes, replacing some centroids [36, 37]. Mutation and crossover are the most important genetic operators playing different roles: the crossover seeks to preserve the features of parent solutions, while the mutation tries to cause small local changes in the solutions. Compared to a crossover, a mutation is usually regarded as a secondary operator with a low probability μ [50]. High frequency of mutations makes a genetic algorithm to search randomly and chaotically. Nevertheless, many studies have shown that evolutionary algorithms without a crossover can work better than a standard genetic algorithm if the mutation is combined with an effective selection operator [51–54]. Mutation is performed on a single parent solution.In [36], the authors encode the solutions (chromosomes) in their GA as sets of centroids represented by their coordinates (real vectors or arrays). The genetic algorithms with the greedy heuristic crossover operator use the same principle [55].Thus, various genetic algorithms for thek-means and similar problems can be classified into three categories in accordance with the chromosome encoding method:(a)
Integer encoding each gene represents a data vectorA1,…,AN, and the value is its cluster number. Such algorithms are declared for solving the k-means or p-median problem; however, they may use other objective function than (1). A local search for the minimum of (1) is sometimes declared their mutation operator.(b)
Integer or binary encoding each gene corresponds to a centroid (cluster) and describes the data vector index1,N¯ selected as the initial centroid for the local search method. Such algorithms may use a wide variety of crossover and mutation operators.(c)
Real (direct) encoding each gene is a centroid encoded by its coordinates. Such algorithms are able to demonstrate the most precise results. However, the modern literature offers a very limited variety of mutation operators for such algorithms. Usually, they do not use any mutation [38, 41, 43].The greedy heuristic crossover operator can be described as a two step algorithm. The first step combines two known (“parent”) solutions (chromosomes) into one intermediate invalid solution with an excessive number of centroids (clusters). At the second step (the greedy agglomerative procedure), the algorithm removes excessive centroids in each iteration so that the removal of the centroid results in the least significant growth of the objective function (1) [41, 43], see Algorithm 2.Algorithm 2:Greedy(): greedy (agglomerative) heuristic procedure.
Require: Final number of centroids k, initial solution S=X1,…,XK, K>k(1)
ImproveS with the local search algorithm if possible: S⟵kMeansS(2)
whileK>k(3)
for alli′∈1,K¯(4)
AssignS′⟵S\Xi′(5)
CalculateFi′′⟵FS′ //where F· is the objective function (1)(6)
end for(7)
Select a subsetSelim of nelim centroids, Selim⊂S,Selim=nelim, with the minimal values of the corresponding variables Fi′′.Here, nelim=max1,0.2⋅S−k(8)
Obtain the new solutionS⟵S∖Selim, K⟵S, and improve this newsolution with the local search algorithm:S⟵kMeansS(9)End while(10)return Solution SAlgorithms3 and 4 are known heuristic procedures [32, 41, 43], which implement the first step of the greedy heuristic crossover operator and run Greedy heuristic procedure.Algorithm 3:GreedyFULL.
Require: Two solutions (sets of centers) S′=X1′,…,Xk′ and S″=X1′′,…,Xk′′returnGreedyS′∪S″Algorithm 4:GreedyONE.
Require: Two solutions (sets of centers) S′=X1′,…,Xk′ and S″=X1′′,…,Xk′′for alli′∈1,p¯MergeS′ and one item of S″: S←S′∪Xi′′′; Si′←GreedySend forreturn the best of solutions S1,…,SpThese algorithms can be included in various global search strategies. Combining items (centroids) of solutionS′ with the items of the other solution S″ and running Algorithm 1, we get a set of “child” solutions. These solutions are used as the neighborhoods, in which a better solution is sought for. Thus, the second solution S″ is a parameter of the neighborhood [32].The general framework of the GA for thek-means and similar location problems can be described as Algorithm 5.Algorithm 5: GA with real chromosome encoding for the k-means and p-median problems.
Require: Initial population size NPOP (in ourExperiments, NPOP=10).(1)
AssignNiter⟵0. Generate NPOP initial solutions S1,…,SNPOP⊂A1,…,AN where Si=k∀i=1,NPOP¯. ForEach initial solution, run the kMeans algorithm: Sl⟵kMeansSl; fk⟵FfitnessSl,l=1,NPOP¯(2)
loop(3)
Niter⟵Niter+1(4)
if stop condition is satisfied(5)
return solution Si∗ from the population with minimal value of fi∗(6)
end if(7)
Selection: Randomly choose two indexesi1,i2∈1,NPOP¯,i1≠i2(8)
Run chosen crossover operator:SC⟵CrossoverSi1,Si2(9)
Run chosen mutation operator:SC⟵MutationSC(10)
Run chosen procedure to replace a solution in the population(11)
End loopThe objective functionFfitness is (1). We used the tournament selection (tournament replacement, see Algorithm 6) for Step 10 of Algorithm 5:Algorithm 6:Tournament (Step 10 of Algorithm 4).
Randomly choose two indexesi4,i5∈1,NPOP¯iffi4>fi5i3⟵i4Elsei3⟵i5End ifSk3⟵SC;fk3⟵FfitnessSCSuch algorithms usually operate with a very small population, and other selection procedures do not improve the results significantly [41, 43, 46].In the GAs with greedy heuristic crossover [43, 44], Algorithms 2 and 3 are used as the crossover genetic operator. These operators are computationally expensive due to multiple runs of the KMeans algorithm. In the case of large-scale problems and very strict time limitation, GAs with greedy heuristic crossover operator performs only few iterations for large-scale problems. The population size is usually small, 10–25 chromosomes. Dynamically growing populations [43, 44] are able to improve the results. In this case, Step 7 of Algorithm 5 is replaced by the following procedure (see Algorithm 7).Algorithm 7: Dynamic population size adjustment (replacement for Step 7 of Algorithm 4).
Niter←Niter+1; NPOP←maxNPOP,⌈1+Niter⌉ifNPOP has changedinitialize the new individualSNPOP: generate randomly, S=p; SNPOP←kMeansSend ifThus, in this paper, we intend to improve the GAs with greedy heuristic crossover operator which can be described as follows [43, 46]:k-GA-ONE: GA framework (Algorithm 5) with GreedyONE as the crossover operator, Tournament selection (Algorithm 6), dynamic population size adjustment (Algorithm 7), and empty mutation operator.k-GA-FULL: the same but GreedyFULL crossover operator.k-GA-RND: the same but the crossover operator GreedyFULL or GreedyONE is selected randomly with equal probability.The empty mutation operator can be replaced with a known or new procedure described in Section3.


## 3. Known Methods of Increasing Population Diversity in the Genetic Algorithms

Despite the widespread use of various genetic algorithms for thek-means problems in the modern literature, there is practically no systematization of the approaches used [56–59]. For various methods of chromosome encoding, various mutation operators have been developed: bit inversion for binary encoding [50], exchange, insert, inverse, and offset permutation [60] for variable length chromosomes, Gaussian mutation [61], and polynomial mutation for real coding [62, 63]. Some studies suggest a combination of the mutation operators [64] or the self-adaptive mutation operators [65–67]. The efficiency of various mutation operators depends on the GA parameters [53, 68, 69] and problem type [70, 71]. However, the number of various mutation operators with real encoding for continuous problems is very limited.The GA for the networkp-median problem described in [72] includes the hypermutation operator, which consists in an attempt to replace each gene in the chromosome with each gene from the set of genes that were not originally part of the processed chromosome. After each replacement, the algorithm checks for the improvement of the objective function value. The operator is computationally expensive due to numerous checks of the objective function and actually similar to the local search principle embedded in the j-means algorithm [73]. In [74], the hypermutation algorithm was further developed as the nearest four neighbors’ algorithm. The idea is to reduce computational costs by reducing the set of genes used for the replacement to the nearest neighbors of the gene being replaced. In several works [37, 75, 76], the authors propose using the kMeans algorithm as a mutation operator.Each of these algorithms declares a local search as a mutation operator. The GA framework allows us to use a wide variety of genetic operator options. However, the local search is designed to improve an arbitrary solution by transforming it into a local optimum and thereby reducing, rather than increasing, the variety of chromosomes (solutions).In [36, 42], the mutation operator is as follows (uniform random mutation). Randomly generate r∼U0,1. If r<μ (where μ is mutation probability), then the chromosome will mutate. Randomly generate b∼U0,1. If the current position of a centroid is Xj=xj,1,…,xx,d, the mutation operator modifies it as follows:(3)xj,l⟵xj,l±2bxj,l,xj,l≠0,±2b,xj,l=0.Signs “+” and “–” are used with the same probability [42]. This mutation operator shifts the centroid coordinates randomly. A similar technique with an “amplification factor” was used in [44, 77]. However, the local minima distribution among the search space is not uniform [49]: the new local minima of (1) can be found with higher probability in some neighborhood of a known local minimum than in a neighborhood of a randomly chosen point (here, by a neighborhood, we do not necessarily mean an ε-neighborhood but any subset of solutions which can be obtained by application of some defined procedure to the current solution). Combining local minima (subsets of centroids from two locally minimal solutions) must usually outperform the random shift of the centroid coordinates. The idea of combining local minima is the basic idea of the greedy heuristic crossover operator in genetic algorithms [38, 43] and other algorithms [21]. The greedy heuristic crossover operator for the discrete p-median problem proposed in [41] and adapted for continuous p-median and k-means problems in [38, 43] was used in the GAs without any mutation operator. Such algorithms demonstrate more accurate results in comparison with many other algorithms for practically important middle-size problems.The other common approach to increasing the diversity in a population is to create subpopulations that develop more or less autonomously. Algorithms that produce subpopulations containing individuals gathered around optima are a wide class of such methods. The fitness sharing method [78] allows the evolutionary algorithm to search simultaneously in different areas (niches) corresponding to different local (or global) optima, i.e., this method allows one to identify and localize multiple optima in search space. The group of crowding methods [79–81] also uses a niche approach. The general concept of crowding is for individuals to fight for survival with similar offspring and apply tournament selection to a high-likeness parent-child pair. The main idea of the genetic chromodynamics [82] is to force the formation and maintenance of stable subpopulations. The proposed scheme of local interaction provides stabilization of the subpopulation in the early stages of the search. Subpopulations co-develop and converge to several optimal solutions.In [83], the authors present the roaming optimization method. By using subpopulations developing in isolation, multiple optima are found. This method uses the tendency of evolutionary algorithms to premature convergence, turning this disadvantage into an advantage in the process of detecting local optima.


## 4. New Modifications to the Genetic Algorithms

The essence of our new mutation operator (greedy heuristic mutation, GHM) is as follows. We perform the crossover operator to the single parent chromosome and a randomly generated chromosome improved by thekMeans algorithm. In Step 9 of Algorithm 5, the mutation operator is replaced with Algorithm 8.Algorithm 8:GHM: version of Mutation operator.
Require: Solution SC.Randomly generate new solutionS′, S=p; S′⟵kMeansS′S′C⟵CrossoverS,S′ifFSC′<FSCSC⟵SC′end ifreturnSCDespite small populations in the genetic algorithms with the greedy agglomerative crossover, the application of a simple approach with two subpopulations allows us to improve the result of the algorithm. In our research, within the population, we organized two subpopulations of equal volume. For the crossover and tournament, both chromosomes are mainly selected within the same subpopulation. If one of the subpopulations during a certain number of iterations does not provide an improvement in solutions and its record (the best solution) is inferior to the record of the second subpopulation, its individuals are replaced by new ones (reinitialization of the population). We assumed that chromosomes in the same subpopulation tend to develop in a similar way under the influence of crossover. Mutation of a separate chromosome increases the population diversity; however, under the influence of the crossover, the differences are gradually levelled. Reinitialization of a subpopulation is a substitute for a complete restart of the algorithm while maintaining the record. Thus, Step 7 of Algorithm4 (selection) is transformed as Algorithm 9.Algorithm 9: Interpopulation selection (replacement for Step 7 of Algorithm 4 with subpopulations).
Randomly choosepintersubpop∈0,1ifpintersubpop<0.1Randomly choose two indexesk1,k2∈1,NPOP¯,k1≠k2; PopNum⟵0else ifpintersubpop<0.55Randomly choose two indexesk1,k2∈1,NPOP/2−1¯,k1≠k2; PopNum⟵1ElseRandomly choose two indexesk1,k2∈NPOP/2,NPOP¯,k1≠k2; PopNum⟵2End ifSimilarly, Step 10 of Algorithm5 changes (see Algorithm 10).Algorithm 10:Tournament (Step 10 of Algorithm 4 with subpopulations).
Randomly choosepintersubpop∈0,1ifPopNum=0Randomly choose two indexesk3,k4∈1,NPOP¯,k3≠k4Else ifPopNum=1Randomly choose two indexesk3,k4∈1,NPOP/2−1¯,k3≠k4ElseRandomly choose two indexesk3,k4∈NPOP/2,NPOP¯,k3≠k4End ififfk4>fk5k3⟵k4Elsek3⟵k5End ifSk3⟵SC;fk3⟵FfitnessSCAn additional Step is added to Algorithm5 (see Algorithm 11).Algorithm 11: Additional step of Algorithm 4 with subpopulations (Step 10a).
if the algorithm gave no improvement during 2NPOP iterationsReinitialize all solutions in the subpopulation with indexes1,NPOP/2−1¯ or NPOP/2,NPOP¯.end ifThe idea of the Variable Neighborhood Search with randomized neighborhoods (see [32]) is also based on applying the greedy heuristic procedures (Algorithms 2 and 3) to a current solution and a randomly generated one transformed into a local minimum by Algorithm 1. Our computational experiments (see Section 5) show that the new genetic algorithms with GHM as the mutation operator outperform both the original genetic algorithms with greedy agglomerative crossover operator (Algorithm 4 with empty mutation) and the Variable Neighborhood Search with randomized neighborhoods.As mentioned before, the greedy agglomerative crossover operator is a computationally expensive algorithm. In Algorithm2, the objective function calculation Fi′′←FS′ is performed more than K−k·k times. Therefore, such algorithms are traditionally considered as methods for solving comparatively small problems (hundred thousands of data points and hundreds of centers). However, the rapid development of the massive parallel processing systems (GPUs) allows us to solve the large-scale problems with reasonable time expenses (minutes).One of the most important issues of the GAs is the convergence of the entire population into some narrow area (population degeneration) around some local minimum. On the first crossover iterations, the “child” solutions usually have significant advantages in the objective function value in comparison with their “parents” due to the ability of the greedy agglomerative crossover operator to choose much better solutions in comparison with thek-means procedure. On a single central processor unit, such GAs manage to perform only few crossover operations due to the computationally expensive Greedy, and the population diversity problem is not important. Our computational experiments show that, with an increase in the computational capacities and increase of the population size (which grows dynamically with the iteration number), the mutation operator plays more important role.


## 5. Computational Experiments

Parallel (CUDA) implementations of thekMeans algorithm are known [84, 85], and we used this approach in our experiments. All other algorithms were realized on the central processor unit.For our experiments, we used the classic datasets from the UCI and Clustering basic benchmark repositories:(a)
Individual Household Electric Power Consumption (IHEPC): energy consumption data of households during several years (more than 2 million data vectors, 7 dimensions), 0–1 normalized data; “date” and “time” columns removed.(b)
SUSY (5·106 data vectors, 18 dimensions), 0–1 normalized data. Here, we do not take into account the true labelling provided by the database, and use this dataset to search for internal structure in the data.(c)
Chess (King-Rook vs. King-Pawn, 3196 Boolean data vectors, 36 dimensions).(d)
BIRCH3 [10]: groups of points of random size on a plane (100000 data vectors, 2 dimensions).(e)
Europe (map of Europe, 169308 data vectors, 2 dimensions).(f)
Mopsi-Joensuu: locations of users (6014 data vectors, 2 dimensions).The test system consisted of Intel Core 2 DuoE8400 CPU, 16GB RAM, NVIDIA GeForce GTX1050ti GPU with 4096 MB RAM, floating-point performance 2,138 g flops. For all datasets, 30 attempts were made to run each of 32 algorithms (Tables1–6).Table 1
Comparative results for SUSY dataset,k=25 clusters and time limitation 500 seconds.
AlgorithmObjective function valueSummarized after 30 attemptsMin (record)Max (worst)Avg.Median ValueStd. dev(A)Known algorithmsk-Means (multistart)924115.13925244.06924548.63924317.69419.9655j-Means926428.75928250.50927328.31927256.00741.0420k-GH-VNS1924227.38924317.56924276.83924265.2541.0833k-GH-VNS2924115.13925141.50924822.84924994.22410.9538k-GH-VNS3924712.69925243.88924997.23925141.50222.6291k-GA-FULL925134.50925243.88925198.99925243.8156.0092k-GA-RND924227.38925141.50924635.38924265.31473.6178k-GA-ONE924115.13924317.50924251.27924265.2563.1124(B)Genetic algorithms with new combinations of known genetic operatorsk-GA-FULL-m1, μ=0.001924712.69925243.81925109.47925141.50181.4919k-GA-FULL-m1, μ=0.01924265.25925243.88925032.71925141.50344.9659k-GA-FULL-m1, μ=0.1924265.25925243.88925015.63925141.50341.6232k-GA-FULL-m2, μ=0.001924227.38925243.81925021.54925141.50352.6434k-GA-FULL-m2, μ=0.01924877.00925141.56925096.58925141.5098.6034k-GA-FULL-m2, μ=0.1924115.13925243.88924864.72925141.50485.5295k-GA-RND-m1, μ=0.001924265.25925243.88924714.60924877.00424.5925k-GA-RND-m1, μ=0.01924115.06925141.50924457.88924227.38461.0992k-GA-RND-m1, μ=0.1924227.38925243.81924539.75924317.50448.1161k-GA-RND-m2,μ=0.001⇓924115.13925243.81924516.25924265.25467.2019k-GA-RND-m2, μ=0.01924115.06925051.50924357.08924317.50319.4935k-GA-RND-m2, μ=0.1↑924115.06924265.25924200.90924265.2580.2563k-GA-ONE-m1, μ=0.001⇕924227.38924317.63924282.27924265.2535.6455k-GA-ONE-m1, μ=0.01924115.13925864.13924626.94924317.50661.5964k-GA-ONE-m1, μ=0.1⇕924115.06924317.56924231.88924265.2585.8271k-GA-ONE-m2, μ=0.001924227.38925925.75924933.53924876.94709.7990k-GA-ONE-m2, μ=0.01924115.06925243.81924518.29924317.50466.6610k-GA-ONE-m2, μ=0.1924265.25924891.75924384.63924317.50224.9720(C)Genetic algorithms with a new mutation operatork-GA-FULL-GHM924115.13924994.00924381.57924227.38383.1728k-GA-FULL-SUBPOP924265.25925243.81924905.77925141.50439.1485k-GA-RND-GHM924227.38925243.88924804.63925140.75486.4890k-GA-RND-SUBPOP924115.13924227.38924131.16924115.1342.4265k-GA-ONE-GHM924115.06924265.25924184.66924227.3866.4470k-GA-ONE-SUBPOP↑⇑924115.06924115.13924115.07924115.060.0236Note (for all tables): “↑⇑” denotes the advantage of the best algorithm in this group over known algorithms (group A) is statistically significant (“↑” for t-test and“⇑” for Mann–Whitney U test); “↓⇓” denotes the disadvantage of the best algorithm in this group over known algorithms is statistically significant; “↕⇕” denotes the advantage or disadvantage is statistically insignificant. Significance level is 0.99.Table 2
Comparative results for IHEPC dataset,k=100 clusters and time limitation 1000 seconds.
AlgorithmObjective function valueSummarized after 30 attemptsMin (record)Max (worst)Avg.Median valueStd. dev(A)Known algorithmsk-Means (multistart)3609.03223767.36993682.97033702.038166.0620j-Means3222.00243469.19043330.86283308.466395.1764k-GH-VNS13194.37303218.30423200.57523194.912610.2875k-GH-VNS23192.34913193.99513193.47113193.25630.7125k-GH-VNS33192.92533195.67313194.78553195.65411.2618k-GA-FULL3194.56713196.05103195.51923195.65920.5586k-GA-RND3193.82303194.91653194.69583194.91330.4879k-GA-ONE3194.29863194.91413194.79073194.91360.2751(B)Genetic algorithms with new combinations of known genetic operatorsk-GA-FULL-m1, μ=0.0013195.10613196.84823196.01253196.21460.8129k-GA-FULL-m1, μ=0.013195.10553195.66163195.33213195.11910.2999k-GA-FULL-m1, μ=0.13195.10503197.38113196.22533196.34180.8776k-GA-FULL-m2, μ=0.0013194.21423197.01433195.42573195.51420.9382k-GA-FULL-m2, μ=0.013194.30913197.03273195.58083195.66311.0298k-GA-FULL-m2, μ=0.13194.00443196.32573195.23963195.10740.8542k-GA-RND-m1, μ=0.0013194.01253196.05123195.02213194.92870.7481k-GA-RND-m1, μ=0.013193.82323196.17993194.94873194.91330.8346k-GA-RND-m1, μ=0.13193.98683195.07323194.39113194.29830.4045k-GA-RND-m2, μ=0.0013194.04183195.91753194.98193194.71050.8723k-GA-RND-m2, μ=0.01↓⇓3193.09423194.91363194.06283193.82400.8194k-GA-RND-m2, μ=0.13194.29793194.91363194.61183194.47610.2839k-GA-ONE-m1, μ=0.0013194.72473196.42713195.56923195.12890.7018k-GA-ONE-m1, μ=0.013194.54593196.29833195.34593195.07370.7263k-GA-ONE-m1, μ=0.13194.54493213.13533198.73823195.07478.0666k-GA-ONE-m2, μ=0.0013194.30813195.42853194.89053194.88570.4765k-GA-ONE-m2, μ=0.013194.29793195.07373194.73103194.91260.3341k-GA-ONE-m2, μ=0.13194.29863194.91413194.70273194.91260.2949(C)Genetic algorithms with a new mutation operatork-GA-FULL-GHM3195.08743196.74563195.89833195.66160.6483k-GA-FULL-SUBPOP3195.09023196.56213195.63193195.52580.6157k-GA-RND-GHM↕⇕3193.27253194.91433193.49963193.82400.7473k-GA-RND-SUBPOP3193.27253195.07743194.14283193.82400.6876k-GA-ONE-GHM3194.91313195.07743195.04263195.07370.0724k-GA-ONE-SUBPOP↓⇕3193.27253195.07373194.67583193.82400.2959Table 3
Comparative results for Chess dataset,k=50 clusters and time limitation 10 seconds.
AlgorithmObjective function valueSummarized after 30 attemptsMin (record)Min (worst)Avg.Median valueStd. dev(A)Known algorithmsk-Means (multistart)6926.226958.366941.136939.6411.2781j-Means6938.976987.536962.716961.9618.6573k-GH-VNS16851.116855.666853.086853.211.5482k-GH-VNS26851.076857.086853.966854.352.4912k-GH-VNS36851.156859.066854.826855.943.5286k-GA-FULL6864.336867.146865.686865.661.2282k-GA-RND6851.416858.326854.646854.562.9540k-GA-ONE6851.446860.756856.016856.164.0019(B)Genetic algorithms with new combinations of known genetic operatorsk-GA-FULL-m1, μ=0.0016860.046870.226867.096867.792.6577k-GA-FULL-m1, μ=0.016858.876870.856866.836867.133.3960k-GA-FULL-m1, μ=0.16861.896871.426868.576868.842.3854k-GA-FULL-m2, μ=0.0016863.436872.636868.376867.972.4871k-GA-FULL-m2, μ=0.016865.956871.796868.406868.341.9573k-GA-FULL-m2, μ=0.16863.016869.636867.216867.821.9583k-GA-RND-m1, μ=0.0016851.296856.306853.516853.351.6152k-GA-RND-m1, μ=0.016851.676860.166854.676854.232.7174k-GA-RND-m1, μ=0.16851.316859.336853.836853.312.3047k-GA-RND-m2, μ=0.0016852.116859.696855.236854.352.4314k-GA-RND-m2, μ=0.016851.686858.656854.496853.681.9113k-GA-RND-m2, μ=0.16851.236860.696854.176853.342.7578k-GA-ONE-m1, μ=0.0016851.356859.786853.796852.972.4321k-GA-ONE-m1, μ=0.016851.186857.686853.486853.411.7505k-GA-ONE-m1,μ=0.1↕⇑6851.176858.906852.826852.022.0071k-GA-ONE-m2, μ=0.0016851.196860.026854.866854.323.2739k-GA-ONE-m2, μ=0.016851.356857.286854.096853.671.9327k-GA-ONE-m2, μ=0.16851.266854.556852.876853.181.0231(C)Genetic algorithms with a new mutation operatork-GA-FULL-GHM6852.406857.806855.436855.781.7635k-GA-FULL-SUBPOP6852.816858.476855.486855.641.7971k-GA-RND-GHM↑⇑6851.126853.196851.616851.180.8080k-GA-RND-SUBPOP6851.116855.986852.396852.121.4238k-GA-ONE-GHM6851.116853.816852.046851.341.0307k-GA-ONE-SUBPOP6851.096853.896851.846851.251.1297Table 4
Comparative results for BIRCH3 dataset,k=100 clusters and time limitation 10 seconds.
AlgorithmObjective function valueSummarized after 30 attemptsMin (record)Max (worst)Avg.Median valueStd. dev(A)Known algorithmsk-Means (multistart)7.83252E + 139.52953E + 138.93284E + 139.02011E + 1352.9723E + 11j-Means4.03770E + 136.59148E + 134.78407E + 134.69827E + 1358.1576E + 11k-GH-VNS13.71492E + 133.74385E + 133.72471E + 133.72063E + 130.76473E + 11k-GH-VNS23.71530E + 133.72899E + 133.72045E + 133.71994E + 130.27407E + 11k-GH-VNS33.71558E + 133.73439E + 133.72163E + 133.72011E + 130.50354E + 11k-GA-FULL3.72086E + 133.73018E + 133.72411E + 133.72413E + 130.25040E + 11k-GA-RND3.71538E + 133.72083E + 133.71998E + 133.72071E + 130.16590E + 11k-GA-ONE3.71526E + 133.72083E + 133.71925E + 133.72072E + 130.24657E + 11(B)Genetic algorithms with new combinations of known genetic operatorsk-GA-FULL-m1, μ=0.0013.72566E + 133.77255E + 133.74320E + 133.74355E + 131.10195E + 11k-GA-FULL-m1, μ=0.013.72566E + 133.79192E + 133.74764E + 133.74532E + 131.61443E + 11k-GA-FULL-m1, μ=0.13.72893E + 133.84583E + 133.76484E + 133.74674E + 133.91344E + 11k-GA-FULL-m2, μ=0.0013.72397E + 133.85824E + 133.76392E + 133.75036E + 133.95201E + 11k-GA-FULL-m2, μ=0.013.72859E + 133.75769E + 133.74216E + 133.74359E + 130.78992E + 11k-GA-FULL-m2, μ=0.13.72555E + 133.78012E + 133.74676E + 133.74355E + 131.56028E + 11k-GA-RND-m1, μ=0.0013.71491E + 133.73835E + 133.72213E + 133.72072E + 130.52620E + 11k-GA-RND-m1, μ=0.013.71967E + 133.72074E + 133.72039E + 133.72070E + 130.03821E + 11k-GA-RND-m1, μ=0.13.71466E + 133.72074E + 133.72007E + 133.72072E + 130.15455E + 11k-GA-RND-m2, μ=0.0013.71530E + 133.72072E + 133.71979E + 133.72011E + 130.14772E + 11k-GA-RND-m2, μ=0.013.71466E + 133.72083E + 133.72015E + 133.72072E + 130.15465E + 11k-GA-RND-m2, μ=0.13.71592E + 133.72072E + 133.71980E + 133.72072E + 130.16092E + 11k-GA-ONE-m1, μ=0.0013.72009E + 133.72102E + 133.72053E + 133.72072E + 130.03291E + 11k-GA-ONE-m1, μ=0.01↕⇕3.71472E + 133.72074E + 133.71938E + 133.72009E + 130.22370E + 11k-GA-ONE-m1, μ=0.13.71969E + 133.72869E + 133.72107E + 133.72072E + 130.21359E + 11k-GA-ONE-m2, μ=0.0013.71681E + 133.72430E + 133.72062E + 133.72072E + 130.14321E + 11k-GA-ONE-m2, μ=0.013.71968E + 133.73260E + 133.72133E + 133.72072E + 130.31388E + 11k-GA-ONE-m2, μ=0.13.71528E + 133.72077E + 133.71984E + 133.72072E + 130.18669E + 11(C)Genetic algorithms with a new mutation operatork-GA-FULL-GHM3.71908E + 133.73862E + 133.72381E + 133.72108E + 130.61387E + 11k-GA-FULL-SUBPOP3.71934E + 133.73928E + 133.72527E + 133.72162E + 130.62692E + 11k-GA-RND-GHM3.71977E + 133.72072E + 133.72045E + 133.72071E + 130.03486E + 11k-GA-RND-SUBPOP ↕⇕3.71529E + 133.72072E + 133.71938E + 133.72024E + 130.13139E + 11k-GA-ONE-GHM3.71976E + 133.72074E + 133.72052E + 133.72072E + 130.03436E + 11k-GA-ONE-SUBPOP3.72009E + 133.72083E + 133.72061E + 133.72072E + 130.02444E + 11Table 5
Comparative results for Europe dataset,k=30 clusters and time limitation 10 seconds.
AlgorithmObjective function valueSummarized after 30 attemptsMin (record)Max (worst)Avg.Median valueStd. dev(A)Known algorithmsk-Means (multistart)7.54173E + 127.57541E + 127.55414E + 127.54853E + 1211.2422E + 9j-Means7.55697E + 127.71002E + 127.64233E + 127.64924E + 1247.5626E + 9k-GH-VNS17.49695E + 127.50850E + 127.50287E + 127.50346E + 123.4668E + 9k-GH-VNS27.50035E + 127.51500E + 127.50727E + 127.50753E + 124.3317E + 9k-GH-VNS37.50346E + 127.51458E + 127.50803E + 127.50919E + 123.7463E + 9k-GA-FULL7.50359E + 127.51505E + 127.51020E + 127.50998E + 122.9113E + 9k-GA-RND7.50036E + 127.50752E + 127.50350E + 127.50360E + 121.5822E + 9k-GA-ONE7.49831E + 127.55141E + 127.50696E + 127.50372E + 1212.4626E + 9(B)Genetic algorithms with new combinations of known genetic operatorsk-GA-FULL-m1, μ=0.0017.50359E + 127.51488E + 127.51099E + 127.51182E + 122.8380E + 9k-GA-FULL-m1, μ=0.017.50359E + 127.51504E + 127.51057E + 127.51065E + 122.7895E + 9k-GA-FULL-m1, μ=0.17.50362E + 127.51504E + 127.51020E + 127.51065E + 123.1105E + 9k-GA-FULL-m2, μ=0.0017.50359E + 127.51505E + 127.51003E + 127.50919E + 123.4939E + 9k-GA-FULL-m2, μ=0.017.50077E + 127.51503E + 127.50926E + 127.51108E + 124.6759E + 9k-GA-FULL-m2, μ=0.17.49595E + 127.51417E + 127.50831E + 127.50919E + 124.5349E + 9k-GA-RND-m1, μ=0.0017.50102E + 127.50723E + 127.50468E + 127.50472E + 122.0215E + 9k-GA-RND-m1, μ=0.017.50066E + 127.50652E + 127.50321E + 127.50361E + 121.9696E + 9k-GA-RND-m1, μ=0.17.50091E + 127.50704E + 127.50382E + 127.50375E + 121.9825E + 9k-GA-RND-m2, μ=0.0017.49812E + 127.50851E + 127.50478E + 127.50528E + 122.7402E + 9k-GA-RND-m2, μ=0.017.49506E + 127.50520E + 127.50257E + 127.50353E + 122.5055E + 9k-GA-RND-m2, μ=0.1↕⇕7.49573E + 127.50677E + 127.50256E + 127.50251E + 123.4842E + 9k-GA-ONE-m1, μ=0.0017.49840E + 127.55417E + 127.50577E + 127.50353E + 1213.5436E + 9k-GA-ONE-m1, μ=0.017.49234E + 127.54085E + 127.50941E + 127.50363E + 1215.8707E + 9k-GA-ONE-m1, μ=0.17.50089E + 127.55332E + 127.51161E + 127.50372E + 1217.5433E + 9k-GA-ONE-m2, μ=0.0017.49731E + 127.55152E + 127.50997E + 127.50270E + 1216.7714E + 9k-GA-ONE-m2, μ=0.017.50075E + 127.55416E + 127.50721E + 127.50374E + 1213.1445E + 9k-GA-ONE-m2, μ=0.17.49523E + 127.55026E + 127.51145E + 127.50363E + 1218.1598E + 9(C)Genetic algorithms with a new mutation operatork-GA-FULL-GHM7.50034E + 127.50777E + 127.50361E + 127.50376E + 122.4491E + 9k-GA-FULL-SUBPOP ↑⇑7.49812E + 127.50376E + 127.50103E + 127.50074E + 121.4074E + 9k-GA-RND-GHM7.49859E + 127.50399E + 127.50211E + 127.50213E + 121.6438E + 9k-GA-RND-SUBPOP7.49957E + 127.50364E + 127.50124E + 127.50081E + 121.4788E + 9k-GA-ONE-GHM7.49966E + 127.50373E + 127.50222E + 127.50233E + 121.4000E + 9k-GA-ONE-SUBPOP7.50042E + 127.50730E + 127.50304E + 127.50346E + 121.9860E + 9Table 6
Comparative results for Mopsi-Joensuu dataset,k=300 clusters and time limitation 10 seconds.
AlgorithmObjective function valueSummarized after 30 attemptsMin (record)Max (worst)Avg.Median valueStd. dev(A)Known algorithmsk-Means (multistart)5.32297.57116.66166.80500.6727j-Means2.78676.06234.23773.83801.1752k-GH-VNS11.99603.40272.49892.39280.5308k-GH-VNS23.10709.14686.93447.49902.2980k-GH-VNS30.14320.29740.18360.15920.0582k-GA-FULL0.19121.06150.42900.35640.2299k-GA-RND0.70392.57331.43481.29300.6968k-GA-ONE2.12657.36224.40114.31841.3787(B)Genetic algorithms with new combinations of known genetic operatorsk-GA-FULL-m1, μ=0.0010.14991.01240.62560.58170.2681k-GA-FULL-m1, μ=0.010.14920.99510.37410.29490.2330k-GA-FULL-m1, μ=0.10.14400.43540.26320.26990.0807k-GA-FULL-m2, μ=0.0010.13020.38720.20170.15890.0811k-GA-FULL-m2, μ=0.010.12390.34410.19690.15520.0726GA-FULL-m2,μ=0.1↕⇕0.11230.28230.16220.13840.0535k-GA-RND-m1, μ=0.0010.415715.86797.13725.94565.6937k-GA-RND-m1, μ=0.010.406120.58748.72516.30257.1967k-GA-RND-m1, μ=0.10.267810.24163.45293.35822.7349k-GA-RND-m2, μ=0.0010.68257.29324.87893.93252.1523k-GA-RND-m2, μ=0.010.63736.75223.25383.34731.5760k-GA-RND-m2, μ=0.10.136615.27593.20851.59044.4927k-GA-ONE-m1, μ=0.0012.15278.24273.52673.20281.7428k-GA-ONE-m1, μ=0.012.13369.11643.91203.64031.9144k-GA-ONE-m1, μ=0.12.11995.90043.52093.48190.9954k-GA-ONE-m2, μ=0.0012.513714.87357.47193.84624.8952k-GA-ONE-m2, μ=0.012.301020.56858.34494.98966.2828k-GA-ONE-m2, μ=0.12.81338.40654.04723.53931.5569(C)Genetic algorithms with a new mutation operatork-GA-FULL-GHM0.14571.01080.35290.30770.2326k-GA-FULL-SUBPOP↕⇕0.13310.31860.16420.13840.0679k-GA-RND-GHM0.26473.81192.34512.69051.1910k-GA-RND-SUBPOP0.40143.84152.34302.89021.2284k-GA-ONE-GHM2.05438.27194.21524.09041.6552k-GA-ONE-SUBPOP2.26346.82754.05343.53531.6508For comparison, we used the genetic algorithms with greedy heuristic crossover (k-GA-FULL, k-GA-ONE, and k-GA-RND described in Section2) as well as the kMeans procedure in the multistart mode and j-Means algorithm (centers are replaced with the data vectors) [73]. In addition, we ran various Variable Neighborhood Search (VNS) algorithms with randomized neighborhoods formed by greedy heuristic procedure [32], see algorithms k-GH-VNS1 and k-GH-VNS2. For algorithms launched in the multistart mode (j-Means and kMeans), only the best results achieved in each attempt were recorded. The minimum, maximum, average, and median objective function values and its standard deviation are summarized after 30 runs. For all algorithms, we used the same realization of the kMeans procedure which consumes the absolute majority of the computation time. The initial population size for all genetic algorithms consisted of NPOP=10 chromosomes.All algorithms were classified into three groups. The first group of algorithms consists of known algorithms including the genetic algorithms with greedy heuristic crossover. Algorithms of the second group are the genetic algorithms with greedy heuristic crossover and known mutation operators (k-GA-xxx-m1 for uniform random mutation and k-GA-xxx-m2 for scramble mutation [86] where a gene (centroid) is replaced with a randomly chosen data point). We performed our experiments with various values of mutation probability μ. Algorithms of the third group are genetic algorithms with greedy agglomerative crossover and new instruments for maintaining the population diversity: k-GA-xxx-GHM are algorithms with the new GHM mutation operator, and k-GA-xxx-SUBPOP are algorithms with the new GHM mutation operator and two subpopulations.In each group of algorithms, the best average and median values of the objective function (1) are underlined. We compared the best algorithms in the second and third groups with the best algorithm in the first group (the best of known algorithms) with the use of t-test and Mann–Whitney U test.In the comparative analysis of algorithm efficiency, the choice of the unit of time plays an important role. The astronomical time spent by an algorithm strongly depends on the peculiarities of its implementation, the ability of the compiler to optimize the program code, and the fitness of the hardware to execute the code of a specific algorithm. Algorithms are often estimated by comparing the number of iterations performed (for example, the number of population generations for a GA) or the number of evaluations of the objective function. In our case, some of the algorithms are not evolutionary, and in genetic algorithms, the execution time of the crossover operator with the embeddedkMeans algorithm can differ hundreds of times. Therefore, comparing the number of generations is unacceptable. Comparison of the objective function calculations is also not quite correct. Firstly, the kMeans algorithm which consume almost all of the processor time, do not calculate (1) directly. Secondly, during the operation of the greedy agglomerative crossover operator, the number of centroids changes (decreases from 2k down to k or from k+1 down to k), and the time spent on computing the objective function also varies. Therefore, we nevertheless chose astronomical time as a scale for comparing algorithms. Moreover, all the algorithms use the same implementation of the kMeans algorithm launched under the same conditions.In our computational experiments, the time limitation was used as the stop condition for all algorithms. As can be seen from Figures1 and 2, the result of each algorithm depends on the elapsed time. Nevertheless, an advantage of the new algorithms remains regardless of the chosen time limit.Figure 1
Comparative results of various algorithms for SUSY dataset (N=5·106 data vectors in ℝ18 and k=25 clusters).Figure 2
Comparative results of various algorithms for Chess dataset (N=3196 in ℝ36 and k=50 clusters).The range of values in all tables is small; nevertheless, the differences are statistically significant in several cases. In all cases, new algorithms with the greedy heuristic mutation outperform known ones or demonstrate approximately the same efficiency (difference in the results is statistically insignificant). Moreover, new algorithms demonstrate the stability of results (narrow range of objective function values). In most cases, the best results were achieved by the genetic algorithms with nonempty mutation operators.


## 6. Conclusions

When solving some large-scale clustering problems, traditional local search algorithms often give a result very far from the optimal solution. In this research we aimed at developing not only fast but also the most accurate algorithm, based on genetic algorithms with greedy heuristic crossover operator, for solving related optimization problems. Methods for obtaining solutions in a fixed time, which would be difficult to improve by known methods without a significant increase in computational costs, include genetic algorithms with a greedy agglomerative crossover operator. As the computational results presented in this article show, further improvement in the achieved result of such algorithms is possible by increasing the diversity in their populations.Computational experiments show that the population diversity maintaining mechanisms such as mutation genetic operator and subpopulations improve the features of genetic algorithms with greedy heuristic crossover for the large-scalek-means problem. Moreover, the best results can be shown by algorithms with a mutation operator based on greedy heuristic crossover operator with a randomly generated chromosome (new greedy heuristic mutation).The similarity in mathematical formulations ofk-means, k-medoids, and p-median problems, as well as the problem of a mixture probability distribution separation, gives us a reasonable hope for the applicability of similar approaches to improving the results of solving those problems which determine possible directions for further research.



---

*Source: 8839763-2020-11-30.xml*