# A Selection Process for Genetic Algorithm Using Clustering Analysis
## 3 Problem Definition
Consequently, clusters with more individuals will be attributed a larger probability sum. * An individual with a lower fitness value \(f(x_{i})\) inside a cluster of size \(m_{j}\) is awarded a higher \(MP\) score. This is translated in the \(\frac{S_{j}-f(x_{i})}{S_{j}}\) term, thus allocating fitter solutions a higher probability of selection. * In order to reduce the probability of recombination between individuals from the same cluster, thus avoiding local optimal traps, fitter individuals in smaller clusters are awarded a higher \(MP\) score. This is the direct effect of \(\frac{m_{j}}{m_{j}-1}\) term. * The sum of all membership probability scores is equal to one. Fitness scaling converts the membership scores in a range suitable for the selection function which selects the parents of the next generation. The selection function allocates a higher probability of selection to individuals with higher scaled values. The range of the scaled values can affect the performance of the genetic algorithm. If the scaled values vary too extensively, higher scaled value individuals will reproduce too rapidly and prevent the GA from searching other regions in the search space. In contrast, for lower scaled value variations,all individuals will have an equal chance of reproduction and therefore will result in very slow search progress. The general framework of the proposed KGA\({}_{f}\) algorithm is shown in Figure 1 below. ### Kga\({}_{o}\)

It is obvious that a problem we face in the KGA\({}_{f}\) algorithm is to decide the optimal number of clusters. Visual verification of a large multidimensional data set (e.g., more than three) is difficult [55]. In order to find the optimal clustering scheme that best fits the inherent partitions of the data set, the concept of clustering validation has been subject to numerous research efforts. The fundamental concepts, drawbacks and applications of clustering validation techniques were discussed in [55; 56; 57; 58]. In essence, there are three main approaches to examine cluster validity:

* External criteria: evaluation of the clustering algorithm results is based on previous knowledge about data. * Internal criteria: clustering results are evaluated using a mechanism that takes into account the vectors of the data set themselves and prior information from the data set is not required. * Relative criteria: aim to evaluate a clustering structure by comparing it to other clustering schemes. The KGA\({}_{o}\) attempts to answer the following questions:

* In how many clusters can the population be partitioned to? * Is there a better \"optimal\" partitioning for our evolving population of chromosomes? Figure 1: Flowchart of the proposed KGA\({}_{f}\) technique. Two main approaches to determining the suitable number of clusters for a given data set can be distinguished:

* Compatible Cluster Merging (CCM): starting with a large number of clusters, and successively reducing the number by merging clusters which are similar (compatible) with respect to a similarity criterion. * Validity Indices (VI's): clustering the data for different values of \(K\), and using validity measures to assess the obtained partitions. The CCM approach requires more computational operations than the use of a validity index to determine the optimal number of clusters. Moreover, the size of the evolving population is small (less than or equal to 100 chromosomes), therefore there is no need to apply a CCM approach. On the other hand, the validity index is not a clustering algorithm itself, but rather a measurement of the results and thus suggests a scheme that best fits the data set. At each generation in the proposed KGA\({}_{o}\) technique, the optimal number of clusters is calculated using a validity assessment index. Different validity indices suitable for \(k\)-means clustering have been proposed in the literature. In this paper, two different internal validity indices are applied in the KGA\({}_{o}\) technique: Silhouette [59] and the Davies-Bouldin index [60] as explained in Figure 2 below.