Article Preview
Top1. Introduction
Swarm intelligence is a collection of nature-inspired searching techniques. Particle Swarm Optimization (PSO), which is one of the swarm intelligence algorithms, was introduced by Eberhart and Kennedy in 1995 (Eberhart & Kennedy, 1995; Kennedy & Eberhart, 1995). It is a population-based stochastic algorithm modeled on the social behaviors observed in flocking birds. Each particle, which represents a solution, flies through the search space with a velocity that is dynamically adjusted according to its own and its companion's historical behaviors. The particles tend to fly toward better search areas over the course of the search process (Eberhart & Shi, 2001; Eberhart & Shi, 2007).
Optimization, in general, is concerned with finding the “best available” solution(s) for a given problem, and the problem may has several or numerous optimum solutions, of which many are local optima. Evolutionary optimization algorithms are generally difficult to find the global optimum solutions for multimodal problems due to the possible occurrence of the premature convergence.
Particles fly in the search space. If particles can easily get clustered together in a short time, these particles will lose their “search potential.” Population premature convergence around a local optimum is a common problem for population-based algorithms. It is a result of individuals congregating within a small region of the search space. An algorithm's search ability of exploration is decreased when premature convergence occurs, and particles will have a low possibility to explore new search areas. Normally, diversity, which is lost due to particles getting clustered together, is not easy to be recovered. An algorithm may lose its search efficacy due to premature convergence. As a population becomes converged, the algorithm will spend most of the iterations to search in a small region.
Diversity has been defined to measure the search process of an evolutionary algorithm. Generally, it is not to measure whether the algorithm find a “good enough” solution or not, but to measure the distribution of individuals in the population (current solutions). Leung et al. used Markov chain analysis to measure the degree of population diversity in the premature convergent process of genetic algorithms (Leung, Gao,, & Xu, 1997). Olorunda and Engelbrecht utilized swarm diversity to measure the state of exploration or exploitation during particles searching (Olorunda & Engelbrecht, 2008). Shi and Eberhart introduced three different definitions on population diversity to measure the PSO search process (Shi & Eberhart, 2008; Shi & Eberhart, 2009). Cheng and Shi utilized these three kinds of population diversities on different subjects, which includes the population diversity control (Cheng & Shi, 2011a), search space boundary constraints handle (Cheng, Shi,, & Qin, 2011a), promoting diversity to solve multimodal problems (Cheng, Shi,, & Qin, 2011b), search information propagation analysis (Cheng, Shi,, & Qin, 2012b), and dynamical exploitation space reduction for solving large scale problems (Cheng, Shi,, & Qin, 2012a).
Compared with other evolutionary algorithms, e.g., genetic algorithm, PSO has more search information, that includes not only the solution (position), but also the velocity and the previous best solution (cognitive). Population diversities, which include position diversity, velocity diversity, and cognitive diversity, are utilized to measure the information, respectively. There are several definitions on the measurement of population diversities (Shi & Eberhart, 2008; Shi & Eberhart, 2009; Cheng & Shi, 2011b).