# A Selection Process for Genetic Algorithm Using Clustering Analysis
## 3 Problem Definition
Strong exploitation encourages premature convergence of the genetic search. Recombining individuals inside the same cluster reduces population diversity, and thus clustering the population can allow an enhanced balance between exploitation and exploration. The aim of clustering is to find a given structure among the series of data and is therefore exploratory in nature [49]. The task of organizing a set of data using cluster analysis requires some dissimilarity measurement among the set of patterns. The dissimilarity metric is defined according to the nature of the data and the purpose of the analysis. Many types of clustering algorithms have been proposed; the reader is referred to [49; 50; 51; 52] for a taxonomy of clustering techniques, discussions on major challenges and key issues and useful surveys of recent advances. The simplest and most popular clustering algorithm is the \(k\)-means algorithms (KMA), and was originally published by [PERSON] [53] in 1956. Even though it was first proposed 60 years ago, it is still the most widely used algorithm for clustering. A general definition of clustering can be stated as follows: given a set of data composed on n objects, find \(K\) groups in such a way that the measure of similarities between objects in the same group is low while the similarities between objects in different groups are high. The \(k\)-means algorithm attempts to find a partition such that the squared error between the empirical mean of a cluster and the objects in the cluster is minimized. The goal is to minimize the sum of the squared error \(J\) over all \(K\) clusters, as follows:

\[J(X,C)=\sum_{k=1}^{K}\sum_{x_{i}\in c_{k}}\|x_{i}-\mu_{k}\|^{2} \tag{1}\]

where \(X=\{x_{i}\},\ i=1,\ \dots,\ N\) is the set of \(N\)\(d\)-dimensional points to be clustered into \(K\) clusters, \(C=\{c_{k}\},\ k=1,\ \dots,\ K\) and \(\mu_{k}\) the mean of cluster \(c_{k}\). Minimizing the \(k\)-means objective function is an NP-hard problem (even for \(K=2\)) [54], and therefore the algorithm can only converge to local minima. The main steps of the \(k\)-means algorithm can be summarized as follows:Choose an initial partition with \(K\) clusters. * Generate a new partition by assigning each pattern to its nearest cluster centroid. * Compute new cluster centroids. * If a convergence criterion is not met, repeat steps 2 and 3. In the KGA\({}_{f}\) algorithm, the number of clusters is kept the same throughout the evolution process. The four main stages of KGA\({}_{f}\) are as follows:

* Clustering the population by the \(k\)-means algorithm
* Computing the membership probability (MP) vector (Equations (2)-(4))
* Fitness scaling of MP
* Selection of the parents for recombination. In general, we want to maintain an even selection pressure during the evolution of the genetic search. At the beginning, the search may be bias towards high fitness individuals. Near the end of the search, as the population is converging towards an optimal solution, there may not be much separation among individuals in the population. Neither situation is desirable, thus there is a necessity to scale the fitness in such a manner to keep the selection pressure the same throughout in the population. The membership probability score of an individual is a measurement of its affiliation with respect to both designated and external clusters (Equation (2)). For a given solution \(i\) inside a cluster \(j\) of size \(m_{j}\), the membership probability index is calculated as follows:

\[MP(i,j)=\frac{m_{j}}{m_{j}-1}\times\frac{1}{P}\times\frac{S_{j}-f(x_{i})}{S_{ j}} \tag{2}\]

and

\[S_{j}=\sum_{i=1}^{m_{j}}f(x_{i}) \tag{3}\]

\[P=\sum_{j=1}^{K}m_{j} \tag{4}\]

where \(P\) is the population size and \(S_{j}\) is the sum of the fitness values \(f(x_{i})\) inside cluster \(j\). The key characteristics that are associated with the use of the membership probability function are the following:

* The sum of the membership probability scores of a given cluster \(j\) of size \(m_{j}\) is equal to \(\frac{m_{j}}{P}\).