## 2 Diversity Measures Utilised in Population Based Algorithms
### Swarm Diversity
#### 2.1.2 Sum of Distances to Nearest Neighbour  
As the name suggests, the sum of distances to the nearest neighbour (SDNN) [8] calculates diversity of candidate solutions by summing up the pairwise distances of each candidate solution to its closest neighbour [9]. The SDNN is calculated as  
\[D_{\text{SDNN}}=\sum_{\mathbf{x}_{i}\in S}\min_{\begin{subarray}{c}\mathbf{x} _{j}\\ j\
eq i\end{subarray}}\left\|\mathbf{x}_{i}-\mathbf{x}_{j}\right\|_{2} \tag{3}\]  
While it is reasonable to assume that a pair of nearest neighbours (NN) are particles in the same niche, it is still possible that a candidate solutions' nearest neighbour is a particle in a niche that has already converged. This may lead to the calculated \(D_{\text{SDNN}}\) values being high even if niches are converged. As a result, the diversity computed using the SDNN measure may not be as expected during convergence.  
For the SDNN measure to be applicable for niching algorithms, the diversity should be calculated for each candidate niche, i.e., the NN of each particle is selected from that particle's niche. The obtained values should then be summed and averaged to give one SDNN score for the swarm. The adapted SDNN measure is computed as  
\[D_{\text{mSDNN}}=\frac{1}{\mu}\sum_{k=1}^{\mu}\left(\sum_{\mathbf{x}_{i}\in N _{k}}\min_{\begin{subarray}{c}\mathbf{x}_{j}\\ j\
eq i\end{subarray}}\left\|\mathbf{x}_{i}-\mathbf{x}_{j}\right\|_{2}\right) \tag{4}\]  
Figure 2: Illustration of the expected diversity values when quantified using the SD measure.  
The adapted measure ensures that the computed \(D_{m\text{SDNN}}\) value is a measure of the sum of intra-niche nearest neighbours distances.  
Niching algorithms define niche formation differently. For instance, the ESPSO algorithm [5] utilises the concept of different species in a population to form niches. Broadly, the algorithm starts by firstly identifying species seed which form the candidate niches(\(N\)). For the ESPSO, each identified species seed is the best fit particle in a neighbourhood, i.e., the nbest. Species seed is determined by initially sorting all particles, \(x_{i}\) in the main swarm, in decreasing order of fitness. In addition, a parameter \(r_{s}\) is defined which is the Euclidean distance between the species seed and the boundary of the species (i.e., the candidate niche(\(N\))). Particles that fall within \(r_{s}\) distance from the species seed are part of the species. If a particle is found that falls outside the radius of that seed, then it is also added to the set \(N\) as a new species seed. As N continues to be filled, subsequent particles are checked against all seeds \(N\) adding only those particles that do not fall within any radii of any of the seeds in \(N\). The set of species seed is complete once all particles have been checked. This means that in ESPSO each particle is part of a distinct specie (candidate niche).  
Unlike the ESPSO, in other PSO niching algorithms, particles could still belong to a particular niche even if their Euclidean distance from their neighbourhood best is somewhat large. As a result, while a high SDNN value means that particles in a niche are far from each other, a low SDNN value may not indicate niche convergence because the calculated distance is only with respect to NNs and not entire members of a candidate niche. Thus, the modified SDNN measure is affected by how a niching algorithm defines niche membership. A potential solution to this problem is to calculate the average SDNN for each niche and then to average over all niches. In essence, this will yield an average intra-niche NNs distance. However, for the purpose of this work, the \(D_{m\text{SDNN}}\) measure was calculated as per Equation (4).