# Particle Swarm Optimization Based on a Novel Evaluation of Diversity
## 3 Pso-Ed
### Evaluation of the Exploration Degree  
#### 3.2.1 A Novel Diversity Evaluation Scheme  
As mentioned above, the distance-based diversity is evaluated by computing the distances between particles. The essence of this scheme is space compression, which compresses the \(D\)-dimensional space features into one-dimensional space. For example, assume that there are three particles in the three-dimensional space, their positions are \(p_{1}\) = {1,0,0}, \(p_{2}\) = {0,1,0} and \(p_{3}\) = {0,0,1}, then the mutual distance between any two particles is {(\(p_{1},p_{2}\)) = 20.5, (\(p_{1},p_{3}\)) = 20.5, (\(p_{2},p_{3}\)) = 20.5}, which has only one dimension. Observe that \begin{table}
\begin{tabular}{l l} \hline \hline
**Symbol** & **Quantity** \\ \hline \(c_{i}\) & The ID of subspace where the \(i\)-th particle is located and will be discussed in Section 3.2.1 \\ \(E\) & The information entropy of swarm position \\ \(E_{d}\) & The exploration degree of the swarm, and \(E_{d}\in[Ed_{lb},Ed_{ab}]\) where \(Ed_{lb}\) and \(Ed_{ab}\) are the lower and upper bounds of the \(E_{d}\) \\ \(N_{w}\) & the number of weak particles that require the disturbance update mode \\ \(m_{i}\) & The update mode of particle \(i\), and \(m_{i}\in\{m_{nor},m_{dis}\}\) where \(m_{nor}\) and \(m_{dis}\) are the Normal and Disturbance update modes \\ \hline \hline \end{tabular}
\end{table} 
Table 1: \(Cont.\)  
Figure 1: Flowchart of the particle swarm optimization variant based on a novel evaluation of diversity (PSO-ED). the three points are separated by a distance of \(2^{0.5}\), but they are regarded as being aggregated together since the information entropy of the distance information is 0 (Equations (3) and (4)). Therefore, the information entropy based on distance cannot reflect the swarm diversity very well. On the other hand, if space is divided into multiple small subspaces, the complexity of traversing all subspaces is fairly high. For example, in the \(D\)-dimensional space, if each dimension is divided into \(K\) equal parts, then the complexity of traveling all subspaces is \((O(K^{D}))\), which is formidable when \(D\) is larger than 10. To calculate the information entropy of the swarm efficiently and evaluate the degree of dispersion of the swarm as accurately as possible, we propose a novel diversity Evaluation scheme. The crucial steps of our approach are as follows:  
For each particle in the swarm, compute the index (ID) of the subspace where the particle is located. First of all, each dimension of the search space is divided into K equal parts. Then the ID of a subspace is a string of \(D\) numbers, each of which represents the index of the part of the dimension occupied by the subspace. For example, in the 3-dimensional space in Figure 2, the ID of the blue subspace is {2, 3, 1}. Denote \(c_{i}=\left\{c_{i}^{1},c_{i}^{2},\ldots,c_{i}^{D}\right\}\) as the ID of subspace where the \(i\)-th particle is located, where \(c_{i}^{d}\) is obtained from Equation (5):  
\[C_{i}^{d}=\left\lceil\frac{x_{i}^{d}-x_{lb}}{(x_{ub}-x_{lb})/K}\right\rceil \tag{5}\]  
Build a hash table \(h\) by traversing the IDs obtained in the Step (1). \(h\) is composed of key-value pairs {_key_, _value_}, where _key_ is the ID of the subspace, and _value_ is the number of particles in the subspace. We traverse the IDs of the subspaces obtained by the above steps, if a key \(c\) exists in h its value \(h(c)\) is increased by 1, else a new key-value pair {_c,1_} is inserted into \(h\). Determine the information entropy \(E\) of the swarm based on \(h\). Note that the empty subspace without any particle contributes 0 to the calculation of information entropy since the probability \(p\) of particles falling into this subspace is 0 by Equations (3) and (4). Therefore, only the subspace corresponding to a key of \(h\) can contribute to the information entropy. \(p_{q}\) in Equation (3) represents the probability of falling into the subspace \(q\), and \(p_{i}=h(c)/N_{s}\).