Population Diversity of Particle Swarm Optimization Algorithm on Solving Single and Multi-Objective Problems

1. Introduction

Optimization, in general, is concerned with finding “best available” solution(s) for a given problem within the allowable time. In mathematical terms, an optimization problem in , or simply an optimization problem, is a mapping , where is termed as decision space (Adra, Dodd, & Griffin, et al., 2009),parameter space (Jin & Sendhoff, 2009), or problem space (Weise, Zapf, & Chiong, et al., 2009)), and is termed as objective space (Sundaram, 1996). Optimization problems can be divided into two categories depending on the value of k. When k=1, this kind of problem is called Single Objective Optimization (SOO), and when k>1, this is called Multi-Objective Optimization (or Many Objective Optimization, MOO).

Particle Swarm Optimizer/Optimization (PSO), which is one of the evolutionary computation techniques, was invented 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; Hu, Shi, & Eberhart, 2004, Cheng et al. 2018).

Premature convergence occurs when all individuals in population-based algorithms are trapped in local optima. In this situation, the exploration of an algorithm is greatly reduced, i.e., the algorithm is searching in a narrow space. For continuous optimization problems, there are infinite numbers of potential solutions. Even with consideration of computational precision, there still have a great number of feasible solutions. The computational resources allocation should be optimized, i.e., maintaining an appropriate balance between exploration and exploitation is a primary factor.

Different problems have different properties. The single objective problem could be divided into the unimodal problem and multi-modal problem. As the name indicated, a unimodal problem has only one optimum solution, on the contrary, a multi-modal problem has several or number of optimum solutions, of which many are local optimal solutions. Optimization algorithms are difficult to find the global optimum solutions because generally it is hard to balance between fast converge speed and the ability of “jumping out” of local optimum. In other words, we need to avoid premature in the search process.

Different computational resource allocation methods should be taken when dealing with different problems. A good algorithm should balance its exploration and exploitation ability during its search process. The concept of exploration and exploitation was firstly introduced in organization science (March, 1991; Gupta, Smith, & Shalley, 2006). The exploration ability means an algorithm can explore more search place, to increase the possibility that the algorithm can find a “good enough” solution(s). In contrast, the exploitation ability means that an algorithm focuses on the refinement of found promising areas.

The population diversity (De Jong, 1975; Mauldin, 1984; Olorunda & Engelbrecht, 2008; Corriveau, Guilbault, & Tahan, et al., 2012) is a measure of individuals' search information. From the distribution of individuals and change of this distribution information, we can obtain the algorithm's status of exploration or exploitation. An important issue in multiobjective is the fitness metric in solutions. The Pareto domination is frequently used in current research to compare between two solutions. The Pareto domination has many strengths, such as easy to understand, computational efficiency, however, it has some drawbacks: