Abstract
This paper presented an improved self-adaptive particle swarm optimization (IDPSO) algorithm with detection function to solve multimodal function optimization problems. To overcome the premature convergence of PSO in a short time, the evolution direction of each particle is redirected dynamically by tuning the three parameters of IDPSO in the evolution process. Numerical results on several benchmark functions indicate that the IDPSO strategy outperformed other variants of PSO.
1. Introduction
Particle swarm optimization (PSO), introduced by Kennedy and Eberhart [1, 2] in 1995, originates from the simulation of birds behavior and fish behavior. Essentially, PSO algorithm is a stochastic global optimization method to find the optimal or global optimum in the landscape of objective function, similar to other intelligent optimization algorithms, such as the mechanism of genetic algorithm (GA) and simulated annealing algorithm (SA). Compared with other evolutionary methods, PSO has an advantage of its implementation and the good tradeoff between exploration and exploitation ability [3–8]. The fundamental idea of PSO is inspired by research done on the behavior of bird flocking and is conducted by means of biological population model put forward by the biologist Heppner [9–11].
PSO is inspired from this organism’s behavior characteristic and used to solve the optimization problem. In PSO, each potential solution to the optimization problem can be conceived as a point in -dimensional search space; we call it “particles" [12, 13]. And all particles have an adaptive value determined by an objective function, and each particle has speed that determines the direction and distance for flying; then the particles search in the solution space following the optimal particles. Through the study of birds flying, scholars found that the birds only trail a limited number of their neighbours, but it seemed that the birds are in control of a certain range; that is to say, the complex global action is caused by the interaction of simple rules.
PSO is an algorithm with simple structure, simple parameter setting, and fast convergence speed, which has been widely applied in function optimization, mathematical modeling, system control, and some other areas [14–18]. The research, which has been done since particle swarm optimization was proposed, mainly includes the following aspects:(i)improvement of PSO,(ii)theoretical analysis of PSO,(iii)biological basis of PSO,(iv)comparative analysis between PSO and other evolutionary algorithms,(v)application of PSO.
How to improve the convergence speed and how to guarantee the convergence of PSO are the main problems of PSO improvement [19] and are gradually turning into a hot topic in this field. In order to weigh the relationship between local search and global search, Shi et al. [20–22] proposed improved particle swarm optimization with inertial weight to control the exploitation and exploration of PSO better, and he also formed a topical improved particle swarm algorithm with inertia factor, which is called topical particle swarm optimization [23].
The remainder of this paper is organized as follows. Section 2 describes the basic PSO and presents the details of the proposed algorithm. Section 3 introduces the stability and convergence analysis of IDPSO and indicates stability and convergence regions. The parametric analysis for IDPSO is discussed in Section 4. Section 5 presents the test functions, the experimental setting for each algorithm, the results, and discussion. Finally, conclusions are given in Section 6.
2. Method
2.1. Basic Particle Swarm Optimization
The basic principle of particle swarm optimization [1, 2] is that each individual in the -dimensional search space is considered as a particle with no weight and volume and that every particle flies at a certain speed; the quality of particle is measured by the fitness function,and particles can modify the speed dynamically according to the flying experience of themselves and other particles, in order to fly to the best position in the group. If is the current position of particle , is the current speed, is the best position that particle has visited, and is the best positions that all particles have visited, then the speed and position of each particle for each generation are shown as follows: where is inertia weight, and are positive acceleration factors, and and are random functions changing in the range of . In (1), the first part is the previous speed of particles, the second part is cognition, which stands for particle’s own thinking, and the third part is social component, which represents the information sharing and cooperation of particles. The flight speed of particles is limited by the maximum and minimum speed of all particles. The PSO with larger inertia weight has a faster convergence speed and works well in global search, while the PSO with smaller inertia weight can reach a more accurate optimum value but only works well in local search [24].
2.2. Improved Particle Swarm Optimization
Researchers have shown that the three parameters , , and have a significant impact on performance of the algorithm, especially the impact of inertia weight. The impact is different on different conditions and is also different at different times under the same condition. Now dynamic inertia weight modification is used to train the appropriate value of , in order to coordinate between search accuracy and search speed. Usually, is modified gradually in descending within the limit of [20], so that search space can be changed steadily from the global to the local. Decreasing inertia weight particle swarm optimization is a topical algorithm, of which inertia weight decreases linearly from 0.9 to 0.4 [20–22]. Some scholars propose the increasing inertia weight particle swarm optimization of which inertia weight increases linearly from 0.4 to 0.9 [25]. The further development of these algorithms is fuzzy adaptive PSO, which optimizes the value of dynamically using adaptive fuzzy inertia weight controller and can solve many problems satisfactorily.
However, the search process of PSO is a nonlinear complex process, where mechanical linear transformation of cannot achieve the accurate balance between local search and global search. Some researchers show that performance, when the inertia weight decreases gradually as the iteration proceeds, is not always better than when the inertia weight is at an appropriate fixed value.
In this paper, a self-adapting particle swarm optimization is proposed, which introduces a detection function ; is the Euclidean distance from the position of particle to the best position that all particles have passed at time , and is the Euclidean distance from the position of particle to the best position that the particle has passed at time . The algorithm may adjust , , and dynamically via the value of function , so that it can optimize dynamically by taking both global search and local search into account. The modification of inertia weight in the new algorithm is based on the variable sigmoid function. According to the different values of detection function, the inertia weight is decreasing irregularly in real time to find the optimum solution in a relatively short time and to reduce the time cost. The values of these two acceleration factors , are modified dynamically in real time according to detection function .
Improved PSO is shown as follows (it is called IDPSO): where and represent the initial value and the final value of , respectively (in (4), we can obtain that .), is the maximum number of evolutionary generation, is the current number of evolutionary generation, is the detection function, and is an adjustment factor to ensure that , , and keep the reverse change.
3. Stability and Convergence Analysis for IDPSO
Convergence analysis plays a great role in understanding the essence and convergence condition of PSO algorithm [26–30]. In this paper we reduce a multidimensional system to one-dimensional for discussion when we analyze the stability and convergence of IDPSO. This is decided by the independence of the multidimensional variables in IDPSO. In (3), (4), (5), and (6), is inertia weight, and are positive acceleration factors, and and are random functions fluctuating in the range of . Suppose that , and ; then we have
By formula transformation, we have
Taking (8) and (2) together, one obtains
Equation (9) can also be rewritten as the matrix form as follows:
Here, the parameters and are assumed to be constants. Then the IDPSO system is a linear time-invariant discrete system. When and and approach fixed values, the necessary and sufficient condition for the IDPSO system reaching stability is that , amplitudes should be less than one, where , are the eigenvalues of the vector matrix and we obtain
From (11), we will discuss the following three cases.(1)When , , are both real roots. For the IDPSO system to be stable, the amplitudes of the two real roots must be less than one; then we have Combining (12) and (13), we obtain It is obvious that the contradiction between (14) the assumption that , which leads to the system (10) being unstable.(2)When , , are both complex roots; their amplitude is It is clear that if , the system (10) is stable. Transforming the formula, we obtain Combining (16) and , we discuss the parameter section by section as follows:(i)when , we have (ii)when , we obtain Then when and if , satisfy the condition, as the shaded part shown in Figure 1, it will make the system (10) stable.(3)When and , the system (10) is stable.
From the above, we analyze the stability of IDPSO for the case of one-dimensional particles, which is also suitable for its convergence problem. In this case, we ignore the subscript of and denote the local best position and global best position as and . By (2) and (7), we obtain
Combining (19) and (20), we obtain
According to , we have
Obviously, (22) is a two-order constant coefficient homogeneous difference equation and its characteristic equation is And the solution of (23) is
Then we have the following.(1)When , and are both real roots: Solving (22), we obtain where is a nonzero constant.(2)When , and are both complex roots: Solving (22), we obtain where is a nonzero constant.(3)When , and are two equal roots: Solving (22), we obtain In (30), is a nonzero constant.
For the above, three cases can be identified; if and has its limit, then IDPSO converges algorithm. Generally, if we want to prove that algorithms converge with probability 1, we just need and . Then we obtain the following:(1)when , if and , then we wish to show that IDPSO is convergent;(2)when , if , then we wish to show that IDPSO is convergent;(3)when , if , then we wish to show that IDPSO is convergent.
4. Parametric Analysis for IDPSO
4.1. Analysis of the Value of in IDPSO
Usually, the variants of PSO set . When is 6000, is 0.9, and is 0.4 [25], the changes of are shown in Figure 2.
The improved in (3) modifies the momentum factor dynamically in real time, while the iteration goes on and chooses the step length corresponding with the current condition according to the detection function and then achieves the self-adaptive changes according to the numerical feedback. When , the values of , , , , and have great influence on inertia weight , which is shown in Figure 3.
We can draw a conclusion from Figures 2 and 3 that when , , and , of topical PSO decreases linearly, while of improved IDPSO reflects a decrease that resembles a reversed “." The algorithm should be searched in a larger step size at the early iteration stage and should ensure the ability of global search and strengthen the capability of “exploration." While the iteration goes on, the algorithm should search with a smaller step size at the later iteration stage and should ensure the ability of local search and strengthen the capability of “exploitation." The adjusting strategies of inertia weight take full advantage of the flexible coordination of detection function and sigmoid function. The inertia weight adjusts the proportion of “exploration" and “exploitation" based on the value of the detection function. If detection function , that is to say, , then the algorithm prefers “exploration," chooses the larger step size, and favors global search. If detection function ; that is to say, , and the algorithm prefers “exploitation," chooses the smaller step size with improved local search, so that it can achieve the smooth transition from “exploration" to “exploitation" adaptively based on sigmoidal function.
4.2. Analysis of the Value of and in IDPSO
The values of and are modified dynamically according to the detection function in IDPSO. If , the weight of social component in (3) should be increased to improve the information sharing and cooperation of particles, so the value of is decreased and the value of is increased. If , weight of “cognition" in (3) should be increased to strengthen the particle’s own influence, so the value of is increased and the value of is decreased.
In IDPSO, particles can “rationally” control the “exploration” and “exploitation” of PSO based on the dynamic modification of parameters , , and , play a critical role in the performance of the algorithm, and effectively avoid falling into the local minimum quickly.
5. Experiments
5.1. Benchmark Functions
In this section, three variants of PSO are compared with the IDPSO. In the first variant of PSO(PSO+SIW), the inertia weight was set to 0.6 [6]. In the second variant of PSO(PSO+LIW), the inertia weight was set to 0.9 at the beginning of the run and was made to decrease linearly to 0.4 at the maximum number of iterations [2]. In the second variant of PSO(PSO+NLIW), the inertia weight was set to 0.9 at the beginning of the run and made to decrease nonlinearly to 0.4 at the maximum number of iterations [14]. For comparison, four benchmark functions were used to compare the performance of the IDPSO algorithm with the three variants of PSO above:
Multimodal function
Schaffer function
Griewank function
Shubert function
The basic characters of the four benchmark functions are summarized in Table 1. In all cases, the population size was set to 20, and the maximum number of iterations was set to 1000. The acceleration constants . In all cases for which IDPSO was used, , , and .
5.2. Results and Discussion
The numerical results using the four different methods for the four benchmark test functions are shown in Figures 4–7. In all cases, the numerical results show that PSO+SIW can reach a local optimum and suffer from premature convergence in a short time. According to Figures 4 and 7, IDPSO significantly outperforms other algorithms for the benchmark functions. In Figure 4, only IDPSO can reach the global optimum and effectively avoid premature convergence. In Figure 7, both PSO+NLIW and IDPSO can reach the global optimum and converge to the criteria for the Shubert function. But IDPSO performs better than PSO+NLIW and IDPSO reaches the global optimum and converges to the criteria faster than PSO+NLIW. From Figures 5(b)–5(d) and 6(b)–6(d), IDPSO performs better than other algorithms in reaching the global optimum. And the average values of fitness present a vibration state, especially in Figure 5(d). From the above, it can be easily observed that the proposed variant IDPSO outperforms other variants of PSO significantly by providing a more accurate optimal solution and converges to the criteria with a greater probability.
(a)
(b)
(c)
(d)
(a)
(b)
(c)
(d)
(a)
(b)
(c)
(d)
(a)
(b)
(c)
(d)
6. Conclusions
A self-adapting particle swarm optimization with detection functions, referred to IDPSO algorithm, is presented in this paper, which may adjust the values of , , and dynamically in different circumstances based on the analysis of the detection function, . This approach ensures that the PSO explores the search space effectively. Experimental results show that IDPSO achieves better performance than other variants of PSO investigated in this paper.
Acknowledgments
This work was supported by Grants from a project funded by the Priority Academic Program Development of Jiangsu Higher Education Institutions, PAPD, Department of Education of Jiangsu Province and “Public Sector (meteorological) Special Research Projects” (GYHY201106040 to Yingchao Zhang), China Meteorological Administration, and “2013 Colleges and Universities in Jiangsu Province plans to graduate research and innovation (CXZZ13_0520 to Xiong Xiong).” The paper reflects the opinions of the authors who bear full responsibility for errors and omissions.