## 2 Related Work
### Evolutionary Algorithm Concepts
#### 2.4.1 GA-K-Means  
The genetic algorithm developed by [PERSON] in [10], referred to as GA-K-Means, represents a fundamental influencing work. GA-K-Means starts by defining an initial population, \(\wp\), with \(J\) solutions, each one achieved by choosing \(K\) data points (centroids) from the dataset \(X\) by uniform random, and by executing the partitioning step 2 (see Algorithm 1) of Lloyd's K-Means.  
GA-K-Means depends on an _elitist_ approach. Only an \(S_{B}\) subset of the best solutions (according to the \(SSE\) or _distortion_ index) in \(\wp\) is considered for the crossover operations, which will transform \(\wp\) into the next generation \(\wp^{\prime}\). In a case, it can happen that \(S_{B}\equiv\wp\); that is, all the solutions in the population are the best solutions.  
In particular, starting from \(\wp^{\prime}~{}=~{}\varnothing\), for \(J\) times, first a pair of solutions \(<C^{1}\), \(P^{1}>\) and \(<C^{2},P^{2}>\) (_parents_) in \(S_{B}\) are chosen, then the two solutions are crossed with each other to define an _offspring_ solution which is added to \(\wp^{\prime}\): \(\wp^{\prime}~{}=~{}\wp^{\prime}\cup\{offspring\}\). The number of possible solution pairs is \(\frac{S_{B}*(S_{B}-1)}{2}\).  
The crossing operation is realized by first establishing a solution of \(2*K\) clusters/ centroids \(<\)\(C^{new},P^{new}>\) where \(C^{new}\) is \(C^{1}\cup C^{2}\), and \(P^{new}\) is the corresponding optimal partitioning. Then, the new solution is reduced to \(K\) elements by deterministic iterations of the _Pairwise Nearest Neighbor_ (\(PNN\)) technique, that is, by subsequent _merging_ operations. At each iteration of the \(PNN\), the two clusters in \(C^{new}\) are identified whose merging would increase the distortion least. The centroid is then defined for the resultant merged cluster. Finally, the partitions of the remaining clusters in \(C^{new}\) are updated accordingly to the merged cluster, and their centroids are redefined by executing step 3 of Lloyd's K-Means (see Algorithm 1). Only a part of the remaining clusters needs to be updated: those containing points which now have as nearest the centroid of the merged cluster. The centroids and the partitions must be redefined only for these clusters.  
The offspring solution can be affected by a _mutation_ operation to improve the population's genetic variation. As in the Random Swap (see Section 2.2), with a given probability, a randomly selected centroid in the solution is possibly replaced by a randomly chosen dataset point.  
Finally, Lloyd's K-Means is executed to refine the offspring solution.  
GA-K-Means is characterized by the efficient support of the \(PNN\) technique. For example, the pair of clusters \(a\) and \(b\) to merge can be found by anticipating the distortion increase \(\Delta_{a,b}\), which would follow the merging operation by using only the centroids \(\mu_{a},~{}\mu_{b}\) of the two originating clusters and the cluster sizes \(n_{a},n_{b}\):  
\[\Delta_{a,b}~{}=~{}\frac{n_{a}*n_{b}}{n_{a}+n_{b}}*d(\mu_{a},\mu_{b})^{2}\]  
In addition, the centroid of the new merged cluster can also be computed by using only the centroids and the cluster sizes:  
\[\mu_{merged}~{}=~{}\frac{n_{a}*\mu_{a}+n_{b}*\mu_{b}}{n_{a}+n_{b}}\]