# Convergence Time Analysis of Particle Swarm Optimization Based on Particle Interaction

Authors: Chao-Hong Chen; Ying-ping Chen
Journal: Advances in Artificial Intelligence
 (2011)

---

## Abstract

We analyze the convergence time of particle swarm optimization (PSO) on the facet of particle interaction. We firstly introduce a statistical interpretation of social-only PSO in order to capture the essence of particle interaction, which is one of the key mechanisms of PSO. We then use the statistical model to obtain theoretical results on the convergence time. Since the theoretical analysis is conducted on the social-only model of PSO, instead of on common models in practice, to verify the validity of our results, numerical experiments are executed on benchmark functions with a regular PSO program.


---

## Body

## 1. Introduction

Particle swarm optimizer (PSO), introduced by [1, 2], is a stochastic population-based algorithm for solving continuous optimization problems. As shown by [3] and by lots of real-world applications, PSO is an efficient and effective optimization framework. Although PSO has been widely applied in many fields [4–7], understanding of PSO from the theoretical point of view is still quite limited. Most of previous theoretical results [8–18] are derived under the system that assumes a fixed attractor or a swarm consisting of a single particle.Due to the lack of theoretical analysis on PSO particle interaction, in this paper, we will make an attempt to analyze the convergence time for PSO on the facet of particle interaction. In particular, we will firstly introduce a statistical interpretation of PSO, proposed by [19], to capture the essence of particle interaction. We will then analyze the convergence time based on the statistical model. Finally, numerical experiments will be conducted to confirm the validity of our theoretical results obtained on simplified PSO, the social-only model, in a normal PSO configuration.In the next section, we will briefly introduce the algorithm of PSO and the statistical interpretation of social-only PSO. In Section3, we will analyze the convergence time of PSO based on the statistical model. The experimental results are presented in Section 4, followed by Section 5 which concludes this work.


## 2. Particle Swarm Optimization and the Statistical Interpretation

The social-only model of PSO can be described as pseudocode shown in Algorithm1. In this paper, we will use boldface for vectors, for example, Xi, Vi. Without loss of generality, we assume that the goal is to minimize the objective function.Algorithm 1:Social-only model of PSO.
procedureSocial-only PSO (Objective function ℱ:ℝn→ℝ)Initializem particleswhile the stopping criterion is not satisfied dofori=1,2,…,m  doif  ℱ(Xi)<ℱ(Pbi)  thenPbi←Xiif  ℱ(Pbi)<ℱ(Nb)  thenNb←Pbiend ifend ifend forfor  i=1,2,…,m  dofor  j=1,2,…,n  doVij←wVij+Cn(Nbj-Xij)Xij←Xij+Vijend forend forend whileend procedureAccording to Algorithm1, in the beginning, m particles are initialized, where m is the swarm size, an algorithmic parameter of PSO. Each particle contains three types of information: its location (Xi), velocity (Vi), and personal best position (Pbi). At each generation, each particle updates its personal best position (Pbi) and neighborhood best position (Nb) according to its objective value. After updating the personal and neighborhood best positions, each particle updates the velocity according to Pbi and Nb. In the velocity update formula, w is the weight of inertia which is usually a constant. Cp and Cn are random values sampled from uniform distributions U(0,cp) and U(0,cn), where cp and cn are called acceleration coefficients. Finally, each particle updates its position according to the velocity and then goes to next generation.From the aforementioned brief description, we can already see that particle interaction is a crucial mechanism in the design of PSO. Although there have been previous studies on particle interaction and the PSO behavior, most of these studies were totally based on the assumption of fixed attractors, a false condition for PSO in action. In order to take particle interaction into consideration, we use an alternative view of PSO that regards the whole swarm as a unity. Instead of tracking the movement of each particle, we consider the overall swarm behavior by transforming the state of entire swarm into a statistical abstraction. Furthermore, in order to concentrate on particle interaction, we adopt the social-only model of PSO [20], which does not consider personal best positions.The statistical interpretation of PSO we use in this paper is modified from [19], summarized in Algorithm 2. In the statistical model, the exact particle locations are not traced but modeled as a distribution θ over ℝn. Velocities are viewed as random vectors 𝒱∈ℝn. The swarm size m is considered as the number of samples from distribution θ, since the geographic knowledge is embodied in the distribution, the neighborhood attractor can be viewed as the best of the m samples.Algorithm 2:Statistical model of social-only PSO. Distribution θ is represented by μ=(μ1,μ2,…,μn) and σ=(σ1,σ2,…,σn). Acceleration coefficient C~U(0,c).
procedureStatistical interpretation of social-onlyPSO (ObjectiveFunctionℱ:ℝn→ℝ)Initialize:σ←σ0,μ←μ0while the stopping criterion is not satisfied dofor  i=1,2,…,m  dofor  j=1,2,…,n  doPij~N(μj,σj2)end forend forPa=minPi{ℱ(Pi)}for  i=1,2,…,m  dofor  j=1,2,…,m  doPij′←Pij+C(Paj-Pij)end forend forμ←(∑i=1mPi′)/mσ2←MLE(P1′,P2′,…,Pm′)end whileend procedureEach particlePi is considered as a random vector sampled from θ, and the velocity Vi is sampled from 𝒱. The neighborhood attractor can then be defined as Pa:=minPi{ℱ(P1),ℱ(P2),…,ℱ(Pm)}. At each generation, Pij is updated as Pij+wVij+C(Paj-Pij). The next distribution is thus the statistical characterization denoted by functions of the observed values:(1)θ⟵Tp(P1,…,Pm),V⟵Tv(P1,…,Pm,V1,…,Vm).
Since w is a constant, distribution 𝒱 can be removed because given two random vectors X~θ and V~𝒱, we can simply let θ′ be the distribution of  X′∶=X+wV.For simplicity, in this paper, we consider the positions of each dimension of a particle is independently sampled from distributionθi. Consider the random variable X~θi and let E[X]=μ. If we divide the support of θi into s disjoint regions R1,…,Rs, such that Prob[X∈Ri]=1/s for i=1,2,…,s, and each region is associated with a random variable of velocity Vi~𝒱i. By picking xi∈Ri for each region, when s is sufficiently large, the swarm can be characterized as(2)∑i=1s1s(xi+Vi)=∑i=1sxis+∑i=1sVis≈μ+∑i=1sVis.
Each component of ∑i=1sVi/s can be approximated with a normal distribution by the central limit theorem. As a consequence, normal distributions are a reasonable choice for describing the behavior of the entire swarm. We let the distribution of ith dimension, θi, be N(μi,σi2), where N(μi,σi2) is the normal distribution with mean μi and variance σi2. The update of distribution becomes simply by calculating the mean and the variance.The mean can be calculated by taking the average of updated positions, and the variance is calculated by using the maximum likelihood estimation (MLE). Letσti2 and μti2 be the variance and mean of the ith dimension at the tth generation. Let yj=Pji and yj′=Pji′ for j=1,2,…,m and let ya=Pai, y¯=(1/m)∑j=1myj′. To estimate the variance of the ith dimension at the (t+1)th generation, we use the maximum likelihood estimation (MLE). The likelihood function L(σti2) is defined as the joint probability:(3)L(σti2)∶=∏j=1m(12πσt+1i2)exp⁡(-(yj′-y¯)22σt+1i2)=(12πσt+1i2)mexp⁡(-∑j=1m(yj′-y¯)22σt+1i2).
To find σt+1i2 that maximizes L(σti2), we differentiate L(σti2) with respect to σt+1i2:(4)L′(σti2)=-(m2)(12π)mσt+1i-m-2×exp⁡(-∑j=1m(yj′-y¯)22σt+1i2)+(12π)m∑j=1m(yj′-y¯)22σt+1i-m-4×exp⁡(-∑j=1m(yj′-y¯)22σt+1i2),
the value of σt+1i2 that maximizes L(σti2) is ∑j=1m(yj′-y¯)2/m. As a result, in our model of PSO, the results of MLE is σt+1i2=∑j=1m(yj′-y¯)2/m for i=1,2,…,n.


## 3. Convergence Time Analysis

In this section, we will analyze the PSO convergence time based on the aforementioned statistical interpretation of the social-only model. As the first step, we must define the state of convergence. Since, in this work, we regard the entire swarm as a distribution, the state of convergence is then referred to as the variance of the distribution. We define the state of convergence as the variance for every dimension is less than a given valueϵ>0. By using this definition, we can now start our analysis of PSO convergence time. To estimate the variance after distribution update, we need the following lemma from [21].Lemma 1.
LetX1,X2,…,Xm~N(μ,σ2). Define  S=∑i=1m(Xi-X¯)2/(m-1), where  X¯=∑i=1mXi/m. One has  (m-1)S~σ2χm-12, where  χm-12 is the chi-square distribution with  m-1 degrees of freedom.With this lemma, we can obtain the following.Lemma 2.
Given the swarm sizem, acceleration coefficient  c, and variance of the  ith dimension at the  tth generation  σti2, one has  E[σt+1i2]=[(1/3)c2-c+1][(m-1)/m]σti2.Proof.
We knowσt+1i2=∑j=1m(yj′-y¯)2/m. The expected value is
(5)E[1m∑j=1m(yj′-∑k=1myk′m)2]=1mE[∑j=1m(yj+C(ya-yj)-∑k=1myk+C(ya-yk)m)2]=1mE[∑j=1m(m(1-C)yj-(1-C)∑k=1mykm)2]=1m3E[(1-C)2∑j=1m(myj-∑k=1myk)2]=1mE[(1-C)2]E[∑j=1m(yj-1m∑k=1myk)2].
Let S=∑j=1m(yj-(1/m)∑k=1myk)2. Since yj~N(μt+1i,σt+1i2) for j=1,2,…,m and y1,y2,…,ym are i.i.d., by Lemma 1, S~σti2χm-12, and E[S]=(m-1)σti2. Then, we can obtain
(6)E[σt+1i2]=1mE[(1-C)2]E[∑j=1m(yj-1m∑k=1myk)2]=1mE[1-2C+C2]E[S]=1m(13c2-c+1)(m-1)σti2=(13c2-c+1)m-1mσti2.Lemma2 is derived under the condition that σti2 is given. The following lemma will derive the relationship between E[σti2] and E[σt+1i2].Lemma 3.
E[σt+1i2]=((1/3)c2-c+1)((m-1)/m)E[σti2].Proof.
(7)E[σti2]=∫σ2∈R+E[σt+1i2∣σti2=σ2]Prob{σti2=σ2}dσ2=∫σ2∈R+(13c2-c+1)m-1mσ2Prob{σti2=σ2}dσ2(byLemma2)=(13c2-c+1)m-1m∫σ2∈R+σ2Prob{σti2=σ2}dσ2=(13c2-c+1)m-1mE[σti2].Now, we can obtain the relationship of convergence time and algorithmic parameters of PSO.Theorem 4.
Given swarm sizem, acceleration coefficient  c,  ϵ, and  σ0. Let  h=maxi{σ0i2}. One has  E[σti2]<ϵ for  i=1,2,…,n when  [(1/3)c2-c+1][(m-1)/m]<1 and  t>log(ϵ/σ0h2)/log([(1/3)c2-c+1][(m-1)/m]).Proof.
From Lemma3, we know
(8)E[σti2]=(13c2-c+1)t(m-1m)tE[σ0i2]=(13c2-c+1)t(m-1m)tσ0i2.
Since [(1/3)c2-c+1][(m-1)/m]<1, we have
(9)E[σti2]=(13c2-c+1)t(m-1m)tσ0i2<(13c2-c+1)t(m-1m)tσ0h2<ϵ.
The last inequality holds because
(10)log⁡((13c2-c+1)t(m-1m)tσ0h2)=tlog⁡((13c2-c+1)(m-1m))+log⁡σ0h2<log(ϵσ0h2)+log⁡σ0h2=log⁡ϵ.We have two corollaries immediately from Theorem4.Corollary 5.
Given swarm sizem, acceleration coefficient  c, and level of convergence  ϵ such that  [(1/3)c2-c+1][(m-1)/m]<1 and  ϵ<1, one has  E[σti2]<ϵ for  i=1,2,…,n for  t=O(-logϵ).Corollary 6.
Given swarm size,m,  c, and  ϵ such that  [(1/3)c2-c+1][(m-1)/m]<1 and  ϵ<1, there exists a constant  c′<1 such that for  t=O(-1/logc′(1-1/m)), one has  E[σti2]<ϵ for  i=1,2,…,n.Corollary5 reveals the linear relationship between the level of convergence and the convergence time, and the interpretation of Corollary 6 is that when the swarm size is sufficiently large, the effect of enlarging swarm size on the convergence time is not important. In the next section, we will empirically examine the two corollaries with a common practical PSO configuration.


## 4. Experiments

In this section, we verify the validity of Corollaries5 and 6 by running standard PSO 2006 downloaded from Particle Swarm Central. We use two objective functions in our experiments:(i)
sphere function [22]:(11)f1(x)=∑i=1Dxi2,x∈[-100,100]D,(ii)
schwefel’s problem 1.2 [22]:(12)f2(x)=∑i=1D(∑j=1ixj2),x∈[-100,100]D.
We have D=10 for both f1(x) and f2(x) in the following experiments.We firstly examine Corollary5. The PSO algorithmic parameters are given as cp=1, cn=1, w=1/(2ln2), and swarm size = 50. The value of ϵ is varied from 10-1 to 10-10. For each value of ϵ, we perform 100 independent runs. For each run, we count the number of generations from initialization to the state in which variances for all dimensions are smaller than ϵ, and we calculate the mean number of generations for the 100 runs.The comparison of these experimental results and our theoretical results is shown in Figures1 and 2. From Figure 1, we can see that the experimental results of f1(x) are very close to -4.6logϵ+43=O(-logϵ), and from Figure 2, the experimental results of f2(x) are very close to -4.7logϵ+43.5=O(-logϵ). The experimental results agree with our estimation in Corollary 5, in which the value of -lnϵ and the PSO convergence time are linearly related.Figure 1
Comparison of experimental results and theoretical results from Corollary5 of f1(x). The x-axis represents the value of ϵ, and y-axis represents the mean number of generation. The experimental results are very close to 𝒪(-logϵ).Figure 2
Comparison of experimental results and theoretical results from Corollary5 of f2(x). The x-axis represents the value of ϵ, and y-axis represents the mean number of generation. The experimental results are very close to 𝒪(-logϵ).After Corollary5 is empirically verified with the standard PSO, we now examine Corollary 6. The parameters we used in PSO are given as cp=1, cn=1, w=1/(2ln2), and ϵ=10-6. The swarm size ranges from 50 to 1000 with step 5. For each swarm size, we perform 100 independent runs and record the mean as we did in last experiment.The comparison of experimental and theoretical results is shown in Figures3, 4, 5, and 6. From Figures 3 and 4, we can see that the convergence time is close to -64.9/log0.555(1-1/m)=𝒪(-1/logc′(1-1/m)), where c′=0.555, and in Figures 5 and 6, the convergence time is close to -99.75/log0.405(1-1/m)=𝒪(-1/logc′(1-1/m)), where c′=0.405. As we can observe from these figures, when the swarm size becomes large, the increase of convergence time is insignificant, confirming our estimation in Corollary 6.Figure 3
Comparison of experimental results and theoretical results from Corollary6 of f1(x). x-axis represents the swarm size ranging from 50 to 200, and y-axis represents the mean number of generation. The experimental results are very close to 𝒪(-1/logc′(1-1/m)) with c′<1.Figure 4
Comparison of experimental results and theoretical results from Corollary6 of f1(x). x-axis represents the swarm size ranging from 50 to 1000, and y-axis represents the mean number of generation. The experimental results are very close to 𝒪(-1/logc′(1-1/m)) with c′<1.Figure 5
Comparison of experimental results and theoretical results from Corollary6 of f2(x). x-axis represents the swarm size ranging from 50 to 200, and y-axis represents the mean number of generation. The experimental results are very close to 𝒪(-1/logc′(1-1/m)) with c′<1.Figure 6
Comparison of experimental results and theoretical results from Corollary6 of f2(x). x-axis represents the swarm size ranging from 50 to 1000, and y-axis represents the mean number of generation. The experimental results are very close to 𝒪(-1/logc′(1-1/m)) with c′<1.


## 5. Conclusions

In this paper, a statistical interpretation of a simplified model of PSO was adopted to analyze the PSO convergence time. In order to capture the essence of particle interaction, the statistical model adopted in this paper assumed no fixed attractors. The effect of particle interaction was included in our analysis. Our theoretical results revealed the relationship between the convergence time and the level of convergence as well as the relationship between the convergence time and the swarm size. Numerical results, in the standard settings of PSO, were obtained to empirically verify our theoretical results derived with a simplified PSO configuration. The agreement between the experimental and theoretical results indicated the importance of particle interaction in PSO. Consequently, more research effort should be invested into analyzing the working of particle interaction in order to better understand particle swarm optimization.Some future extensions of this study are now ready to be explored. First of all, the relationship between PSO and the number of dimensions, that is, in the adopted model, the relationship betweent and E[σt(n)2], where σt(n)2=max{σt12,σt22,…,σtn2}. Second, the theoretical analysis conducted in this study is independent of objective functions. In Section 4, we verify the analysis with only two objective functions. More functions of various features and properties, which do not violate the settings of the adopted statistical model, should be used to examine the estimation. Third, the distribution which we used in this paper is the normal distribution. However, there should exist some objective functions that enforce the swarm to distribute according to different distributions. The analysis presented in this paper will fail on those objective functions. As a result, more sophisticated models should be adopted to provide good descriptions of the PSO macrobehavior and to enable researchers to derive more accurate PSO estimations. Finally, the social-only PSO model we adopted in this paper does not take the personal experience into consideration. We also need more sophisticated models to analyze the PSO macrobehavior influenced by the personal experience.



---

*Source: 204750-2012-01-19.xml*