A Study of Normalized Population Diversity in Particle Swarm Optimization

A Study of Normalized Population Diversity in Particle Swarm Optimization

Shi Cheng (Department of Electrical Engineering and Electronic, University of Liverpool, Liverpool, UK), Yuhui Shi (Department of Electrical and Electronic Engineering, Xi’an Jiaotong-Liverpool University, Suzhou, China) and Quande Qin (College of Management, Shenzhen University, Shenzhen, China)
Copyright: © 2013 |Pages: 34
DOI: 10.4018/jsir.2013010101
OnDemand PDF Download:
$30.00
List Price: $37.50

Abstract

The values and velocities of a Particle swarm optimization (PSO) algorithm can be recorded as series of matrix and its population diversity can be considered as an observation of the distribution of matrix elements. Each dimension is measured separately in the dimension-wise diversity, on the contrary, the element-wise diversity measures all dimension together. In this paper, PSO algorithm is first represented in the matrix format, then based on the analysis of the relationship between pairs of vectors in PSO solution matrix, different normalization strategies are utilized for dimension-wise and element-wise population diversity, respectively. Experiments on benchmark functions are conducted. Based on the simulation results of ten benchmark functions (include unimodal/multimodal function, separable/non-separable function), the properties of normalized population diversities are analyzed and discussed.
Article Preview

1. 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).

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 9: 4 Issues (2018): 1 Released, 3 Forthcoming
Volume 8: 4 Issues (2017)
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing