Effect of Inertia and Constriction Factors on PSO and Quantum Behaved PSO

Effect of Inertia and Constriction Factors on PSO and Quantum Behaved PSO

Gurwinder Singh Research Scholar, IKGPTU, Jalandhar

Amarinder Singh

Baba Banda Singh Bahadur Engineering College Fatehgarh Sahib

AbstractParticle Swarm Optimization (PSO) is characterized as a stochastic optimization algorithm that is based on the behaviour of swarm of birds searching for food. PSO is a very powerful tool for obtaining the optimal solution for complex problems. The algorithm may be modified by varying the various parameters involved and hence new variants of PSO may be obtained that improve the rate of convergence and the diversity of the solutions. In this paper, the basic PSO and the Quantum behaved PSO are compared with the variations of inertia factor and constriction factor applied on the Sphere function and Rosenbrock function.

KeywordsParticle Swarm Optimization (PSO), Quantum PSO (QPSO), PSO with Inertia Factor (PSO-In), PSO with Constriction Factor (PSO-Co)

1. INTRODUCTION

   Optimization techniques, the techniques to find the best solution for problems, are generally of two types deterministic and stochastic. Most of the real world problems are stochastic in nature and hence require respective techniques for solution. The stochastic techniques often result in huge computational efforts and hence may fail as the complexity of the problem increases. To deal with such complex problems, bio-inspired stochastic algorithms have been developed and have gained importance because of their computational efficiency. Population based techniques are the meta-heuristic iterative approaches that involve selecting appropriate initial population and operators to produce new set of solutions. PSO algorithm, introduced by Kennedy and Eberhart [1], is based on the simulation of the social behaviour of birds. The algorithm simulates the graceful and unpredictable choreography of swarm of birds. Each individual within the swarm is represented by a vector in the multidimensional search space. This position vector is assigned another vector, called the velocity vector, which determines the next movement of the particle. Each particle updates its velocity based on its current velocity, the individual best position and the global best position explored so far. It has been observed to have good convergence rate and has been applied to many real world optimization problems. PSO seems to have much in common with the Evolutionary Algorithms, however, it differs from these approaches because of the fact that there is no criterion for selecting the population and the population remains the same throughout the iterative procedure. Each particle in the population is attracted to it previous best position and to the global best position attained by the swarm.

   One problem with the PSO is that it may fall into the trap of local optima in many optimization problems, since the particles may come close to their previous best and the global

   best thereby decreasing their dissimilarities. This results in premature convergence, in which case the population needs to be re-initialized to obtain the diversified solutions and hence search for the global optimal solution.

   In this paper, basic PSO approach and the Quantum PSO are being compared with emphasis on the Inertia factor and the Constriction Factor. These variants are being applied on the benchmark problems, the Sphere function and the Rosenbrock function to study the convergence of these techniques.

2. BASIC PARTICLE SWARM OPTIMIZATION PSO remembers both the best position found by all the

   particles and those obtained by each particle in the search process. For a search problem in an n-dimensional space, a particle represents a potential solution. The velocity vij and the position xij of the jth dimension of the ith particle are updated according to equations

   vij(t+1)=w.vij(t)+c1.rand1ij.(pbestij(t)-xij(t))

   +c2.rand2ij.(gbestij(t)-xij(t)) (1)

   xij(t+1)=xij(t)+vij(t+1) (2)

   where i=1,2,… is the particle's index and Xi=(xi1,xi2,,xin) is the position of the ith particle, Vi=(vi1,vi2,…,vin) is the velocity of the ith particle. The pbesti=(pbesti1,pbesti2,…,pbestin) is the previous best yielding the best fitness value for the ith particle and gbest=(gbest1,gbest2,…,gbestn) is the global best particle found by all the particles so far. The inertia factor w has been proposed by Shi and Eberhart [2], rand1ij and rand2ij are two random numbers independently generated within the range of [0,1], c1 and c2 are two learning factors which control the influence of the social and cognitive components and t=1,2,… represents the iterations.

3. QUANTUM PARTICLE SWARM OPTIMIZATION

   In QPSO, the Contraction-Expansion (CE) coefficient is the most important algorithmic parameter that requires to be adjusted to balance the local and global search of the algorithm during the search process. This work provides an analysis of the impact of the CE coefficient on the behaviour of the particle in both types of the QPSO algorithms and discusses how to select its value for practical usage. Sun, Lai and Wu [3] has discussed both the basic and quantum perspectives of PSO.

   A. Procedure of QPSO

   The procedure of QPSO is similar to that of the PSO algorithm, except that it has different evolution equations In the QPSO algorithm, there is no velocity vector for each particle, and the position of the particle updates directly according to the equations

   X j=p

   j±| X

   j – p

   j |ln(1/ u

   j )| (3)

   The Sphere function is strongly convex and unimodal

   i,n+1

   or

   i,n

   i,n

   i,n

   i,n+1

   function whereas the Rosenbrock function is a non-convex function and have been widely studied as benchmark problems

   i,n+1 i,n i,n i,n i,n+1

   X j = p j±| X j – g j |ln(1/ u j )| (4)

   where pi,nj is the jth component of the local focus pi,n of particle i at the nth iteration, ui,n+1j is a sequence of random number uniformly distributed on (0,1).

4. INERTIA FACTOR AND CONSTRICTION FACTOR

   1. PSO with Inertia Factor (PSO-In)

      Inertia weight maintains a balance between exploring the search space and exploiting the solutions. The Inertia weight determines the contribution of the particle's previous velocity to the current iteration. Shi and Eberhart [2] established that a large inertia weight would facilitate the global search while small inertia weight would facilitate the local search. However, later on, many researchers studied the dynamic inertia weight to improve the convergence of PSO. Eberhart and Shi [4] gave a random inertia weight strategy while Xin, Chen and Hai [5] proposed the linearly decreasing strategy to enhance the efficiency and performance of PSO. In this paper, the linearly decreasing inertia weight has been considered in which the weight is computed by the equation:

      w=wmax+((wmax-wmin)/maxiter)× iter (5) where wmax and wmin are the maximum and minimum values

      of the inertia weight that are pre-decided, iter represents the number of the current iteration and maxiter represents the maximum number of iterations.

   2. PSO with Constriction Factor (PSO-Co)

   Many researchers have indicated that the PSO often converges significantly faster to the global optimum but has difficulties in premature convergence, performance and diversity loss in the optimization process. In the absence of any restriction of the maximum velocity of the particles, researchers observed that they started oscillating around the optimal solution and the procedure would not reduce thevelocity so as to search minutely in the limited search space for the global optimal. Clerc [6] suggested the use of properly defined constriction factor to ensure early convergence of the PSO. The velocity using the PSO with the constriction factor K is given by:

   vij(t+1)=K[vij(t)+c1.rand1ij.(pbestij(t)-xij(t))

   +c2.rand2ij.(gbestij(t)-xij(t))] (6)

   K=2/(|2–( 2-4)|), where =c1+c2, >4 (7)

   The convergence characteristic of the system is controlled by that has to be greater than 4. Generally, when the constriction factor is used, c1 and c2 are both set as 2.05 and thus =4.1. Thus the constriction factor is evaluated to 0.729.

5. BENCHMARK PROBLEMS

   The benchmark problems considered in this paper are given by equations (8) and (9).

   1 2 n

   f(x1,x2,…,xn) = x 2+x 2+…+x 2 (8)

   i

   f(x1,x2,…,xn) = (100.(xi+1-x 2)2+(xi-1)2) (9)

   in the theory of evolutionary algorithms.

   1. Parameters used

      Population Size (M) 20

      Maximum Number of Iterations 1000

      Search Space [-100,100]

      Acceleration Coefficients (c1 and c2) 2.0 (For PSO and

      PSO-In)

      Acceleration Coefficients (c1 and c2) 2.05 (For PSO-

      Co)

      During initialization, the current position vector for all the particles are uniformly distributed within the search domain and the initial best position of the particle is set to its initial current position. The fitness value corresponding to each particle is computed followed by the identification of the global best positions. In case of PSO-In, the inertia weight 'w' should be computed as according to decreasing linearly from

      0.9 and 0.4 during the iterative procedure.

   2. Iterative Procedure

   The procedure of basic PSO, PSO-In and PSO-Co was executed and 50 cases of the final fitness values for each version of the PSO were obtained. The final fitness value for each run of a PSO algorithm was obtained after 1000 iterations of the search process. The average of the 50 best fitness values is known as the mean best fitness value. The standard deviation of the 50 best fitness values is computed for further comparative analysis. The quality of the solution or the fitness value obtained is only one of the aspects that reflect the performance of the algorithms. There are other important factors that may be employed evaluate the algorithms, including the convergence speed of the fitness values. To trace the convergence history of the algorithms, the fitness values at each iteration over 50 runs are averaged and plotted. It is observed that the basic PSO generated poor results even though the Sphere function is a unimodal function whereas PSO-In and PSO-Co generated better results. In particular, the mean best fitness value obtained through PSO-Co is 4.6526×10-8 that is extremely close to the optimal solution. Similarly, the solution obtained through the PSO-Co for the Rosenbrock function is extremely close to the optimal solution.

   In the similar manner, with the same parameter values and =0.75, the procedure of QPSO, QPSO-In and QPSO-Co was executed and 50 values of the fitness values were obtained. The graphs of the mean values of the 20 particles of the Sphere function using basic PSO are plotted in Fig. 1-Fig. 3 and those using QPSO are plotted in Fig. 4-Fig. 6. It was observed that the mean best fitness value obtained for Sphere function is 4.9667×10-37.The similar graphs of Rosenbrock function are plotted in Fig. 7-Fig. 9 and Fig. 10-Fig. 12 respectively. The final comparison of the mean values, the standard deviation and the global best of all the three variants for both the Sphere function and Rosenbrock function are given in Table I and Table II.

6. CONCLUSION

From Table I and Table II, it is easily concluded that the performance of Quantum behaved PSO is much better than the basic PSO because of its characteristic of enhancing the global search ability of the particles. Furthermore, while considering the Constriction Factor, the convergence and the rate of convergence are further improved by a great extent, establishing the significance of both the Quantum behaved PSO and the Constriction Factor while solving the optimization problem for the real world problems. PSO is a potential research topic and has room for considerable amount of modifications and hybridizations.

REFERENCES

1. J. Kennedy and R.C. Eberhart, Particle swarm optimization, Proceedings of IEEE International Conference on Neural Networks, pp. 1942-1948, 1995.

2. Y. Shi and R.C. Eberhart, A modified particle swarm optimization, Proceedings of IEEE Congress Evolutionary Computation, pp. 69-73, 1998.

3. J. Sun, C-H. Lai and X-J. Wu, Particle Swarm Optimization: Classical and Quantum Perspectives, CRC Press, 2012.

4. R.C. Eberhart and Y. Shi, Tracking and optimizing dynamic systems with particle swarms, Proceedings of the IEEE Congress on Evolutionary Computation, pp. 94-100, 2002.

5. J. Xin, G. Chen and Y. Hai, A particle swarm optimizer with multistage linearly-decreasing inertia weight, IEEE Interational Joint Conference on Computational Sciences and Optimization, pp. 505-508, 2009.

6. M. Clerc and J. Kennedy, The particle swarm explosion, stability and convergence in a multidimensional complex space, IEEE Trans. Evolutionary Computation, vol. 6, pp. 58-73, 2002.

FIG. 1 Plot of pbest for Sphere function using basic PSO

FIG. 2 Plot of pbest for Sphere function using PSO-In

FIG. 3 Plot of pbest for Sphere function using PSO-Co

FIG. 4 Plot of pbest for Sphere function using QPSO

FIG. 5 Plot of pbest for Sphere function using QPSO-In

FIG. 6 Plot of pbest for Sphere function using QPSO-Co

FIG. 7 Plot of pbest for Rosenbrock function using basic PSO

FIG. 8 Plot of pbest for Rosenbrock function using basic PSO-In

FIG. 9 Plot of pbest for Rosenbrock function using basic PSO-Co

FIG. 10 Plot of pbest for Rosenbrock function using QPSO

FIG. 11 Plot of pbest for Rosenbrock function using QPSO-In

FIG. 11 Plot of pbest for Rosenbrock function using QPSO-Co

TABLE 3: Mean and Standard Deviation of the Best Fitness Values using basic PSO and QPSO for Sphere Function

TABLE 4: Mean and Standard Deviation of the Best Fitness Values Obtained using basic PSO and QPSO for Rosenbrock Functions