# A Selection Process for Genetic Algorithm Using Clustering Analysis
## 3 Problem Definition
* Silhouette (S) [59]

The silhouette technique assigns to the \(i\)th vector of cluster \(c_{j}\) (\(j=1,\ldots,K\)), a quality measure \(s(i)\) known as the silhouette width defined as \(S\):

\[s_{j}=\frac{1}{m_{j}}\sum_{i=1}^{m_{j}}\frac{\left(b(i)-a(i)\right)}{\max\left[ a(i),b(i)\right]} \tag{5}\]

and

\[S=\frac{1}{K}\sum_{j=1}^{K}s_{j} \tag{6}\]

where \(a(i)\) is the average distance between the \(i\)th vector and the remaining elements inside the same cluster \(j\) of size \(m_{j}\), \(b(i)\) is the minimum average distance between vector \(i\) and all elements inside clusters \(c_{k}\) (\(k=1,\ldots\)\(K;k\
eq j\)). The optimal partition is expected to minimize the intra-group distance \(a\) while maximizing the inter-group distance \(b\), thus maximizing the silhouette width criterion \(S\). * Davies-Bouldin (DB) [60]

The DB index aims to evaluate intra-cluster similarity and inter-cluster differences by computing the following:

\[BD=\frac{1}{K}\sum_{i=1}^{K}\max_{i\
eq j}\left[\frac{d(x_{i})+d(x_{j})}{d \left(c_{i},c_{j}\right)}\right] \tag{7}\]

where \(d(x_{i})\) and \(d(x_{i})\) are each the sum of all the distances between the centroid of the cluster and the elements of clusters \(i\) and \(j\) respectively, \(d(c_{i},c_{j})\) is the distance between centroids of cluster \(c_{i}\) and \(c_{j}\). A good partition composed of compact and separated clusters is represented by a small DB value. The Davies-Bouldin index presents decent results for dissimilar groups. However, it is not intended to handle overlapping clusters [27]. Throughout the KGA\({}_{o}\) technique, the evaluation of the validity index function is performed within a range of cluster numbers and then an optimal number is chosen. For instance, if the Silhouette index is applied, the number of clusters which maximizes S corresponds to the optimal partition, whereas the minimum DB value determines the optimal number of clusters for the clustering of the population. Since the size of the population is small, the maximum number of partitions is set to ten. Consequently, the search for the optimal partition varies between \(i=2\) (the minimum number of clusters) and \(i=10\), as per Figure 2.

## 5 Numerical Simulations

In this section, the performance of KGA techniques on seven well-known test functions is investigated. In recent years, various kinds of novel computational intelligence methods have been proposed and the field is attracting more and more attention. To promote research on expensive optimization, the CEC 2014 special session competition developed a set of benchmark optimization problems. All test functions are minimization problems defined as follows:

\[\text{min}f(\text{x});\ \text{x}=[x_{1},x_{2},\ldots,x_{D}] \tag{8}\]

\(D\) dimension of the search space. Most functions are shifted by \(o_{i}=[o_{1},\)\(o_{i2},\)\(\ldots,\)\(o_{iD}]\), randomly distributed in \([-10,10]^{D}\). Some problems are rotated by a predefined rotation matrix \(M\) (Table 1). Each rotation matrix is generated from standard normally distributed entries by Gram-Schmidt ortho-normalization with condition number equal to one or two. \begin{table}
\begin{tabular}{c c c c} \hline \hline
**No.** & **Functions** & **Search Ranges** & \(f_{i}^{*}=f_{i}(x^{*})\) \\ \hline
1 & shifted sphere & \([-20,20]\) & 0 \\
2 & shifted ellipsoid & \([-20,20]\) & 0 \\  & shifted and rotated & & \\
3 & ellipsoid & \([-20,20]\) & 0 \\
4 & shifted step & \([-20,20]\) & 0 \\
5 & shifted Ackley & \([-32,32]\) & 0 \\
6 & shifted Griewank & \([-600,600]\) & 0 \\
7 & shifted rotated & & \\  & Rosenbrock & & \\ \hline \hline \end{tabular}

* \(f_{1}(x)=\sum_{i=1}^{D}x_{i}^{2}\ F_{1}(x)=f_{1}(x-o_{1})\)
* \(f_{2}(x)=\sum_{i=1}^{D}ix_{i}^{2}\ F_{2}(x)=f_{2}(x-o_{2})\)

\end{table} 
Table 1: Summary of the test functions. Figure 2: Search for the optimal number of clusters. \(F_{3}(x)=f_{2}(M_{3}[x-o_{3}])\)
4. \(f_{3}(x)=\sum_{i=1}^{D}|x_{i}+0.5|^{2}\); \(F_{3}(x)=f_{3}(x-o_{4})\)
5.