# An Improved Particle Swarm Optimization Algorithm Based on Centroid and Exponential Inertia Weight

Authors: Shouwen Chen; Zhuoming Xu; Yan Tang; Shun Liu
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

Particle swarm optimization algorithm (PSO) is a global stochastic tool, which has ability to search the global optima. However, PSO algorithm is easily trapped into local optima with low accuracy in convergence. In this paper, in order to overcome the shortcoming of PSO algorithm, an improved particle swarm optimization algorithm (IPSO), based on two forms of exponential inertia weight and two types of centroids, is proposed. By means of comparing the optimization ability of IPSO algorithm with BPSO, EPSO, CPSO, and ACL-PSO algorithms, experimental results show that the proposed IPSO algorithm is more efficient; it also outperforms other four baseline PSO algorithms in accuracy.


---

## Body

## 1. Introduction

Particle swarm optimization (PSO) has been proposed originally by Kennedy and Eberhart in 1995, which is a population-based stochastic optimization techniques inspired by social behavior of bird flocking or fish schooling [1]. The PSO algorithm is easy to implement and has been empirically shown to perform well on many optimization problems [2–5]. The development of PSO can be classified into three categories in general. The first category emphasizes the variants of PSO mechanism itself, both in mathematics [6] and in topology [7]. The second one hybridizes other optimization techniques into PSO, such as ACO [8], GA [9, 10], Tabu [11], and simulated annealing [12]. The third one leverages the advantages of Chaos Maps, such as certainty, ergodicity, and stochastic property [13]. The hybridization of chaos with PSO has also become an active direction in recent research activities [14, 15].With the concept of the center of gravity in Physics, Song et al. designed a centroid particle swarm based on each particle’s best position and proposed a centroid PSO (CPSO) algorithm [16] to enhance individual and group collaboration and information sharing capabilities. Also, Gou et al. proposed an ACL-PSO algorithm [17] with a population centroid based on every particle’s current position. Their experimental results showed that ACL-PSO algorithm improved the global searching capability and effectively avoided the premature convergence. Inertia weight [18], in the form of linear decreasing one, was embedded into the original PSO firstly by Shi and Eberhart [18]. Based on their work, a conclusion can be drawn that a large inertia weight facilitates a global search while a small one facilitates a local search. After that, different kinds of inertia weights were introduced and expressed in exponential formalities [19] or other nonlinear formalities [20–22]. Recently, Ting et al. [23] proposed an exponential inertia weight frame. After their carefully analysis of the effect of local attractor and global attractor, they presented suggestions for adjusting these attractors in order to improve the performance of PSO algorithm.In this paper, in order to prevent PSO from falling in a local optimum, we propose an improved PSO algorithm (IPSO) based on two forms of exponential inertia weight proposed by Ting et al. and two kinds of centroids, population centroid and the best individual centroid, which are based on a new weighted linear combination of each particle’s current position and a linear combination of each particle’s best position, respectively. Therein, the proposed IPSO algorithm provides two velocity updating forms, which are selected by roulette wheel for every particle at each of evolution iterations. Besides one particle’s own extreme position and the global extreme position, one of velocity updating forms is based on population centroid, another is based on best individual centroid. By means of comparing its optimization ability with other four PSO algorithms, the experiment results show that the proposed IPSO algorithm can reach more excellent optima.The remainder of this paper is organized as follows. Basic PSO algorithm (BPSO) [18], exponential inertia weight PSO (EPSO) [23], center PSO (CPSO) [16], and self-adaptive comprehensive learning PSO (ACL-PSO) [17] are proposed in Section 2. We present our improved PSO algorithm (IPSO) model in Section 3. Section 4 shows our experimental results. Finally, we conclude our work in the last section.


## 2. Background

The basic PSO (BPSO) algorithm is a useful tool for optimization. Each particle’s position stands for a candidate solution to the problem which will be solved. The BPSO, EPSO, CPSO, and ACL-PSO are proposed below.


### 2.1. BPSO

Denotef
,
S and C
S as the fitness function, the scale of swarm, and the maximum iteration number, respectively. Let X
i
(
t
)
=
(
x
i
1
t
,
…
,
x
i
d
(
t
)
,
…
,
x
i
D
(
t
)
)
,
v
i
(
t
)
=
(
v
i
1
(
t
)
,
…
,
v
i
d
(
t
)
,
…
,
v
i
D
(
t
)
), and f
i
(
t
)
=
f
X
i
(
t
) be the position, velocity, and fitness of the i
th particle at the t
th iteration, respectively. In addition, let f
i
(
r
) be the i
th particle’s best fitness and let p
i be the corresponding position, St. r
=
arg
max
⁡
t
{
f
i
(
t
)
}. Also, let f
g
(
r
) be the swarm’s best fitness and let p
g be the corresponding position, St. g
=
arg
max
⁡
i
∈
{
1,2
,
…
,
S
}
{
f
i
(
r
)
}.In BPSO, tracking the two positionsp
g and p
i, each particle flows through the multidimensional searching space to update its inertia weight, velocity, and position according to (1)–(3), respectively. Consider
(1)
w
t
=
w
max
⁡
-
t
×
(
w
max
⁡
-
w
min
⁡
)
C
S
,
(2)
v
i
d
(
t
+
1
)
=
w
t
v
i
d
t
+
c
1
r
1
t
p
i
d
-
x
i
d
t
+
c
2
r
2
t
p
g
d
-
x
i
d
t
,
(3)
x
i
d
(
t
+
1
)
=
x
i
d
(
t
)
+
v
i
d
(
t
+
1
)
.In (1), w
(
t
) stands for inertia weight at the t
th iteration and w
max
⁡ and w
min
⁡ are the initial inertia weight and the final inertia weight, respectively. In (2), c
1 and c
2 are accommodation parameters and random numbers r
1
(
t
) and r
2
(
t
) belong to the interval of 0 and 1.


### 2.2. EPSO

Inertia weight, which had been introduced firstly by Shi and Eberhart is one of the important parameters in PSO algorithm [18]. Since that, linearly decreasing inertia weight and nonlinearly decreasing one have been used widely in literature. Chauhan et al. [22] summarized different inertia weight forms. However, there is no clear justification of how this parameter can be adjusted to improve the performance of PSO algorithm. In [23], Ting et al. have investigated the property for an exponential inertia weight inspired by adaptive crossover rate (ACR) used in differential evolution algorithm. The ACR is defined as
(4)
CR
=
CR
0
·
e
-
a
t
/
C
S
b
,
where CR
0 is the initial crossover rate, t is the current generation number, and C
S is the maximum number of generations. The adaptive function for the crossover rate is simply crafted based on the logic of high CR at the beginning of run to prevent premature convergence and low CR at the end of run to enhance the local search. This concept is exactly the same for the case of inertia weight w in BPSO. Thus, Ting et al. defined their exponential inertia weight as follows:
(5)
w
t
=
w
max
⁡
·
e
-
a
t
/
C
S
b
,
where w
max
⁡ is the initial inertia weight. Parameters a and b in (5) are named the local search attractor and the global search attractor, respectively. On the one hand, while parameter b is set to 1, parameter a has the ability to push down the value of w. On the other hand, when b is increased, it has the ability to pull up the value of the w. Note that when a is zero, the inertia weight becomes a static value w
max
⁡; when b is zero, it is in fact a static w with the value approximate to 0.32 on condition that a is set to 1.Substituting (5) for (1) in BPSO algorithm, Ting et al. proposed an exponential inertia weight PSO algorithm (EPSO). After testing on 23 benchmark problems, they draw a conclusion from simulation results that EPSO algorithm was capable of global search and local search when b
>
a and a
>
b, respectively. At the same time, their simulation results showed that the EPSO algorithm had better performance in comparison to the BPSO algorithm, which was used widely in many significant works.


### 2.3. CPSO

In order to enhance interparticle cooperation and information sharing capabilities, Song et al. proposed a centroid PSO (CPSO) [16] algorithm. In CPSO algorithm, the centroid of particle swarm is defined as (6), and (2) in BPSO algorithm is substituted for (7). Consider
(6)
C
=
1
S
∑
i
=
1
S
p
i
,
(7)
v
i
j
(
t
+
1
)
=
w
(
t
)
v
i
j
t
+
c
1
r
1
p
i
j
-
x
i
j
t
+
c
2
r
2
p
g
j
-
x
i
j
t
+
c
3
r
3
C
j
-
x
i
j
t
.In the abovementioned (7), c
3 is a positive constant similar to c
1 and c
2; r
3 is a random number between 0 and 1.In this way, the running track of each particle is not only interrelated with the individual best position and the best position of the swarm but also interrelated with the centroid of the whole particle swarm. Their experimental results show that the CPSO algorithm not only enhances the local searching efficiency and global searching performance but also has an ability to avoid the premature convergence problem effectively.


### 2.4. ACL-PSO

After introducing population centroid learning mechanism into the BPSO, Gou et al. proposed an ACL-PSO algorithm [17] based on self-adapted comprehensive learning. They defined the fitness proportion of the i
th particle as (8), and the population centroid corresponding to the t
th iteration as (9). Consider
(8)
Pecen
t
i
t
=
f
X
i
t
∑
k
=
1
S
f
X
k
t
,
(9)
p
c
t
=
∑
i
=
1
S
Pecen
t
i
t
*
X
i
t
.Considering not only individual particle’s own previous best position but also the evolution trend of populations, Gou et al. proposed two different evolution strategies at different evolution stage. Therein,p
c
(
t
) was used to guide the particle searching direction at the early stage of evolution, while p
g was used to guide its direction at the later stage. To realize these evolution strategies, they used (10) to compute R
t at the t
th iteration and used a random number P between 0 and 1 to compare with R
t. Consider
(10)
R
t
=
1
-
t
C
S
.IfP
≤
R
t, update the i
th particle’s velocity by (11) or (12), else by (2). Consider
(11)
v
i
j
(
t
+
1
)
=
w
t
v
i
j
t
+
c
1
r
1
p
i
j
-
x
i
j
t
+
c
2
r
2
a
i
j
*
p
c
j
-
x
i
j
t
,
(12)
v
i
j
(
t
+
1
)
=
w
(
t
)
v
i
j
t
+
c
1
r
1
p
i
j
-
x
i
j
t
+
c
2
r
2
p
g
j
-
x
i
j
t
+
c
3
r
3
a
i
j
*
p
c
j
-
x
i
j
t
.In the abovementioned formulas, inertia weight of ACL-PSO was computed by the following:(13)
w
t
=
w
max
⁡
·
e
-
t
2
/
2
,
where random number a
i
j was in 1
/
S
,
1. In addition, c
3 was the weight coefficient of population centroid and r
3 was a random number between 0 and 1. The item c
3
r
3
(
a
i
j
*
p
c
j
-
x
i
j
(
t
)
) was the entry of population centroid learning, which reflected an individual particle’s social cognition learning and thinking.Compared to other four improved PSO algorithms in terms of accuracy, convergence speed, and computational complexity, ACL-PSO converged faster, resulting in more robust and better optima [17].


## 2.1. BPSO

Denotef
,
S and C
S as the fitness function, the scale of swarm, and the maximum iteration number, respectively. Let X
i
(
t
)
=
(
x
i
1
t
,
…
,
x
i
d
(
t
)
,
…
,
x
i
D
(
t
)
)
,
v
i
(
t
)
=
(
v
i
1
(
t
)
,
…
,
v
i
d
(
t
)
,
…
,
v
i
D
(
t
)
), and f
i
(
t
)
=
f
X
i
(
t
) be the position, velocity, and fitness of the i
th particle at the t
th iteration, respectively. In addition, let f
i
(
r
) be the i
th particle’s best fitness and let p
i be the corresponding position, St. r
=
arg
max
⁡
t
{
f
i
(
t
)
}. Also, let f
g
(
r
) be the swarm’s best fitness and let p
g be the corresponding position, St. g
=
arg
max
⁡
i
∈
{
1,2
,
…
,
S
}
{
f
i
(
r
)
}.In BPSO, tracking the two positionsp
g and p
i, each particle flows through the multidimensional searching space to update its inertia weight, velocity, and position according to (1)–(3), respectively. Consider
(1)
w
t
=
w
max
⁡
-
t
×
(
w
max
⁡
-
w
min
⁡
)
C
S
,
(2)
v
i
d
(
t
+
1
)
=
w
t
v
i
d
t
+
c
1
r
1
t
p
i
d
-
x
i
d
t
+
c
2
r
2
t
p
g
d
-
x
i
d
t
,
(3)
x
i
d
(
t
+
1
)
=
x
i
d
(
t
)
+
v
i
d
(
t
+
1
)
.In (1), w
(
t
) stands for inertia weight at the t
th iteration and w
max
⁡ and w
min
⁡ are the initial inertia weight and the final inertia weight, respectively. In (2), c
1 and c
2 are accommodation parameters and random numbers r
1
(
t
) and r
2
(
t
) belong to the interval of 0 and 1.


## 2.2. EPSO

Inertia weight, which had been introduced firstly by Shi and Eberhart is one of the important parameters in PSO algorithm [18]. Since that, linearly decreasing inertia weight and nonlinearly decreasing one have been used widely in literature. Chauhan et al. [22] summarized different inertia weight forms. However, there is no clear justification of how this parameter can be adjusted to improve the performance of PSO algorithm. In [23], Ting et al. have investigated the property for an exponential inertia weight inspired by adaptive crossover rate (ACR) used in differential evolution algorithm. The ACR is defined as
(4)
CR
=
CR
0
·
e
-
a
t
/
C
S
b
,
where CR
0 is the initial crossover rate, t is the current generation number, and C
S is the maximum number of generations. The adaptive function for the crossover rate is simply crafted based on the logic of high CR at the beginning of run to prevent premature convergence and low CR at the end of run to enhance the local search. This concept is exactly the same for the case of inertia weight w in BPSO. Thus, Ting et al. defined their exponential inertia weight as follows:
(5)
w
t
=
w
max
⁡
·
e
-
a
t
/
C
S
b
,
where w
max
⁡ is the initial inertia weight. Parameters a and b in (5) are named the local search attractor and the global search attractor, respectively. On the one hand, while parameter b is set to 1, parameter a has the ability to push down the value of w. On the other hand, when b is increased, it has the ability to pull up the value of the w. Note that when a is zero, the inertia weight becomes a static value w
max
⁡; when b is zero, it is in fact a static w with the value approximate to 0.32 on condition that a is set to 1.Substituting (5) for (1) in BPSO algorithm, Ting et al. proposed an exponential inertia weight PSO algorithm (EPSO). After testing on 23 benchmark problems, they draw a conclusion from simulation results that EPSO algorithm was capable of global search and local search when b
>
a and a
>
b, respectively. At the same time, their simulation results showed that the EPSO algorithm had better performance in comparison to the BPSO algorithm, which was used widely in many significant works.


## 2.3. CPSO

In order to enhance interparticle cooperation and information sharing capabilities, Song et al. proposed a centroid PSO (CPSO) [16] algorithm. In CPSO algorithm, the centroid of particle swarm is defined as (6), and (2) in BPSO algorithm is substituted for (7). Consider
(6)
C
=
1
S
∑
i
=
1
S
p
i
,
(7)
v
i
j
(
t
+
1
)
=
w
(
t
)
v
i
j
t
+
c
1
r
1
p
i
j
-
x
i
j
t
+
c
2
r
2
p
g
j
-
x
i
j
t
+
c
3
r
3
C
j
-
x
i
j
t
.In the abovementioned (7), c
3 is a positive constant similar to c
1 and c
2; r
3 is a random number between 0 and 1.In this way, the running track of each particle is not only interrelated with the individual best position and the best position of the swarm but also interrelated with the centroid of the whole particle swarm. Their experimental results show that the CPSO algorithm not only enhances the local searching efficiency and global searching performance but also has an ability to avoid the premature convergence problem effectively.


## 2.4. ACL-PSO

After introducing population centroid learning mechanism into the BPSO, Gou et al. proposed an ACL-PSO algorithm [17] based on self-adapted comprehensive learning. They defined the fitness proportion of the i
th particle as (8), and the population centroid corresponding to the t
th iteration as (9). Consider
(8)
Pecen
t
i
t
=
f
X
i
t
∑
k
=
1
S
f
X
k
t
,
(9)
p
c
t
=
∑
i
=
1
S
Pecen
t
i
t
*
X
i
t
.Considering not only individual particle’s own previous best position but also the evolution trend of populations, Gou et al. proposed two different evolution strategies at different evolution stage. Therein,p
c
(
t
) was used to guide the particle searching direction at the early stage of evolution, while p
g was used to guide its direction at the later stage. To realize these evolution strategies, they used (10) to compute R
t at the t
th iteration and used a random number P between 0 and 1 to compare with R
t. Consider
(10)
R
t
=
1
-
t
C
S
.IfP
≤
R
t, update the i
th particle’s velocity by (11) or (12), else by (2). Consider
(11)
v
i
j
(
t
+
1
)
=
w
t
v
i
j
t
+
c
1
r
1
p
i
j
-
x
i
j
t
+
c
2
r
2
a
i
j
*
p
c
j
-
x
i
j
t
,
(12)
v
i
j
(
t
+
1
)
=
w
(
t
)
v
i
j
t
+
c
1
r
1
p
i
j
-
x
i
j
t
+
c
2
r
2
p
g
j
-
x
i
j
t
+
c
3
r
3
a
i
j
*
p
c
j
-
x
i
j
t
.In the abovementioned formulas, inertia weight of ACL-PSO was computed by the following:(13)
w
t
=
w
max
⁡
·
e
-
t
2
/
2
,
where random number a
i
j was in 1
/
S
,
1. In addition, c
3 was the weight coefficient of population centroid and r
3 was a random number between 0 and 1. The item c
3
r
3
(
a
i
j
*
p
c
j
-
x
i
j
(
t
)
) was the entry of population centroid learning, which reflected an individual particle’s social cognition learning and thinking.Compared to other four improved PSO algorithms in terms of accuracy, convergence speed, and computational complexity, ACL-PSO converged faster, resulting in more robust and better optima [17].


## 3. Our Proposed Method IPSO

Define particle fitnessf as object function directly, and adjust the IPSO algorithm search mechanism as follows:
(14)
g
=
arg
min
⁡
i
∈
{
1,2
,
…
,
S
}
f
i
r
,
r
=
arg
min
⁡
t
f
i
t
.Combining the above EPSO algorithm’s inertia weight, CPSO and ACL-PSO algorithms’ population centroids, taking advantage of ACL-PSO algorithm’s evolution strategies, we propose a new improved PSO algorithm (IPSO) as follows.(1) Population Centroid and Best Individual Centroid. So as to CPSO and ACL-PSO algorithms, their centroids are different from each other. The centroid of CPSO algorithm is a linear combination of each particle’s best position, while the other is a weighted linear combination of each particle’s current position. Taking advantage of the two centroids, we embed them into BPSO to balance PSO algorithm’s performance of local and global searching, and denote them as best individual centroid and population centroid, respectively.Iff
(
X
i
(
t
)
) is smaller, that is to say, the object value is smaller at the t
th iteration, then the particle’s current position makes more contribution to the construction of the population centroid corresponding to the same iteration. Thus, in order to show the degree of importance of the particle’s current position, X
i
(
t
), in the population centroid, we define the i
th particle proportion as (15) and compute the population centroid p
c
(
t
) by (9). At the same time, (16) can be obtained naturally. Consider
(15)
Pecen
t
i
t
=
1
S
-
1
1
-
f
X
i
t
∑
k
=
1
S
f
X
k
t
,
(16)
∑
i
=
1
S
Pecen
t
i
(
t
)
=
1
.Gou et al. [17] have proved that their proposed population centroid will be the convergence position on condition that ACL-PSO algorithm converges to local minimum or global convergence. Similarly, Let P
* satisfy (17), (18) indicates that p
c
(
t
) is the convergence position of IPSO algorithm on condition that the algorithm converges to local minimum or global convergence. Consider
(17)
P
*
=
lim
⁡
t
→
∞
X
i
t
,
(18)
lim
⁡
t
→
∞
p
c
t
=
lim
⁡
t
→
∞
∑
i
=
1
S
1
S
-
1
1
-
f
(
X
i
(
t
)
)
∑
k
=
1
S
f
(
X
k
(
t
)
)
*
X
i
(
t
)
=
1
S
-
1
∑
i
=
1
S
1
-
lim
⁡
t
→
∞
f
(
X
i
(
t
)
)
∑
k
=
1
S
lim
⁡
t
→
∞
f
(
X
k
(
t
)
)
*
lim
⁡
t
→
∞
X
i
(
t
)
=
1
S
-
1
∑
i
=
1
S
1
-
f
(
P
*
)
∑
k
=
1
S
f
(
P
*
)
*
P
*
=
P
*
.(2) Inertia Weight. Based on the exponential inertia weight proposed by Ting et al. [23], we select two pairs of a and b. One pair is that a is 1 and b is 2. Another one is contrary. Denote them as (19) at the t
th iteration. These inertia weights work in with different evolution strategies, the same as ACL-PSO algorithm. Consider
(19)
w
1
t
=
w
max
⁡
·
e
-
t
/
C
S
2
,
w
2
t
=
w
max
⁡
·
e
-
2
t
/
C
S
.(3) Update Velocity. It can be drawn from (18) that population centroid will coincide with the population globally optimal location. So, we use Gou et al.’s method [17] to help the i
th particle to select velocity updating formula. If P
≤
R
t, update the i
th particle’s velocity by (12) with w
2
(
t
), else by (7) with w
1
(
t
). The execution process of IPSO algorithm is shown in Algorithm 1.Algorithm 1:The execution process of IPSO algorithm.
Algorithm. IPSO (x
min
⁡
,
x
max
⁡
,
v
min
⁡
,
v
max
⁡
,
w
max
⁡
,
c
1
,
c
2
,
c
3
,
D
,
S
,
C
S)
Input:     x
min
⁡
,
x
max
⁡
,
v
min
⁡
,
v
max
⁡
,
w
max
⁡
,
c
1
,
c
2
,
c
3
,
D
,
S
,
C
S
Output:   p
g, f
(
p
g
)
Begin
(1) Initialize the parameters including population sizeS
,
x
min
⁡
,
x
max
⁡
,
v
min
⁡
,
v
max
⁡
,
w
max
⁡
,
c
1
,
c
2
,
c
3, the dimension size D,
the maximum iteration numberC
S, and the current iterative count t
=
0
(2) Generate the initial population and initial velocity. The initial population and initial velocity for each
particle are randomly generated as follows:
Population =[
X
1
(
t
)
X
2
(
t
)
⋮
X
S
(
t
)
]  X
i
(
t
)
=
(
x
i
1
(
t
)
,
…
,
x
i
d
(
t
)
,
…
,
x
i
D
(
t
)
)
x
i
d
(
t
)
∈
[
x
min
⁡
,
x
max
⁡
]
i
=
1,2
,
…
,
S
d
=
1,2
,
…
,
D
Velocity =[
v
1
(
t
)
v
2
(
t
)
⋮
v
S
(
t
)
]  v
i
(
t
)
=
(
v
i
1
(
t
)
,
…
,
v
i
d
(
t
)
,
…
,
v
i
D
(
t
)
)
v
i
d
(
t
)
∈
[
v
min
⁡
,
v
max
⁡
]
i
=
1,2
,
…
,
S
d
=
1,2
,
…
,
D
whereX
i
(
t
) and v
i
(
t
) are the position and velocity at the tth iteration for the ith particle,
respectively.D is the dimension of each particle. x
min
⁡, x
max
⁡ are the minimum and maximum value of
each point belonging to thedth dimension, respectively. v
min
⁡, v
max
⁡ are the minimum and maximum
value of each point belonging to thedth dimension, respectively.
(3) Calculate the fitness value of each particle and record it as:f
i
(
t
)
←
f
(
X
i
(
t
)
), record the ith particle's
best fitness and its corresponding positionp
i as: f
i
(
r
)
←
f
i
(
t
), p
i
←
X
i
(
t
), St. r
=
arg
min
⁡
t
{
f
i
(
t
)
}, i
=
1
,
…
,
S
(4) Calculate the population’s best fitnessf
g
(
r
) and its corresponding position p
g, St. g
=
arg
min
⁡
i
∈
{
1,2
,
…
,
S
}
{
f
i
(
r
)
}
(5) Compute population centroid by (9) with the weighted coefficient Pecen
t
i
(
t
) computed by (15),
compute best individual centroid by (6).
(6)For  t
=
1 to C
S do
(6.1) ComputeR
t by (10), and generate a random number P
∈
[
0,1
];
(6.2)If  P
≤
R
t
(6.2.1) Updatew
2
(
t
) by (19)
(6.2.2)For  i
=
1 to S do
Updatev
i
(
t
) and X
i
(
t
) by (12) and (3) respectively, compute f
i
(
t
)
←
f
(
X
i
(
t
)
)
If  f
i
(
t
)
<
f
i
(
r
) then f
i
(
r
)
←
f
i
(
t
), p
i
←
X
i
(
t
), r
=
arg
min
⁡
t
{
f
i
(
t
)
},
End If
End
Else
(6.2.3) Updatew
1
(
t
) by (19)
(6.2.4)For  i
=
1 to S do
Updatev
i
(
t
) and X
i
(
t
) by (7) and (3) respectively, compute f
i
(
t
)
←
f
(
X
i
(
t
)
)
If  f
i
(
t
)
<
f
i
(
r
) then f
i
(
r
)
←
f
i
(
t
), p
i
←
X
i
(
t
), r
=
arg
min
⁡
t
{
f
i
(
t
)
},
End If
End
End If
(6.3) Computef
g
(
r
) and set p
g
←
X
g
(
r
), where g
=
arg
min
⁡
i
∈
{
1,2
,
…
,
S
}
{
f
i
(
r
)
}
(6.4) Compute population centroid by (9) with the weighted coefficient Pecen
t
i
(
t
) computed by (15),
compute best individual centroid by (6).
(6.5) lett
=
t
+
1
End
(7) outputp
g, f
(
p
g
)
End


## 4. Experiments and Results

In this section, BPSO, EPSO, CPSO, and ACL-PSO algorithm are compared as four benchmark functions to verify the feasibility of IPSO algorithm. The descriptions of those test functions, which can be divided into unimodal and multimodal function, are shown in Table1. Using the object function in Table 1 to evaluate each particle’s fitness, the smaller the function value the higher the fitness.Table 1
Descriptions of four benchmark functions.
Function
Mathematical formula
Range and dim.
Minima
Characteristics
Griewank(
f
1
)
f
(
x
)
=
∑
i
=
1
n
x
i
2
4000
-
∏
i
=
1
n
cos
⁡
(
x
i
i
)
+
1
[
-
600,600
]
20
0
Highly multimodal
Rastrigin(
f
2
)
f
(
x
)
=
∑
i
=
1
n
(
x
i
2
-
10
cos
⁡
(
2
π
x
i
)
)
+
10
[
-
5.12,5.12
]
20
0
Highly multimodal
Rosenbrock(
f
3
)
f
(
x
)
=
∑
i
=
1
n
-
1
(
100
(
x
i
+
1
-
x
i
2
)
2
+
(
x
i
-
1
)
2
)
[
-
30,30
]
20
0
Multiple local optima
Sphere(
f
4
)
f
(
x
)
=
∑
i
=
1
n
x
i
2
[
-
5.12,5.12
]
20
0
Unimodal convexExperiments use the following methods. Firstly, determine the parameter pairs of IPSO algorithm, such asS and c
3. Secondly, fixing the number of iterations, with different number of particles, evaluate performances of those five algorithms by average object value corresponding to the t
th iteration. At last, setting the maximum iteration number and different target accuracies of these functions, success rate and average convergence iteration number are compared.The average object value according to thet
th iteration of all the r turns is as (20) for each algorithm. Therein, f
j
(
i
)
(
t
) stands for the global best fitness for the j
th algorithm, corresponding to the t
th iteration at the i
th turn. Consider
(20)
y
t
=
1
r
∑
i
=
1
r
f
j
i
t
,
t
=
1
,
…
,
C
S
,
j
=
1
,
…
,
5
.(1) Determine the Parameter Pairs of
S
and
c
3
in IPSO Algorithm. With v
min
⁡
=
x
min
⁡
,
v
max
⁡
=
x
max
⁡
,
c
1
=
c
2
=
1.4
,
C
S
=
1000, let S be 10, 20, and 30 each time and let c
3 be updated by (21) for each S. Run the IPSO algorithm r
=
50 turns per time. Its (
t
-
log
⁡
(
y
)
) curves of above four benchmark functions are shown in Figures 1, 2, 3, and 4. Consider
(21)
c
3
k
=
0.5
×
k
-
1
k
=
1
,
…
,
5
.(
t
-
log
⁡
(
y
)
) curves of f
1 according to different S.
(a)
S
=
10
(b)
S
=
20
(c)
S
=
30(
t
-
log
⁡
(
y
)
) curves of f
2 according to different S.
(a)
S
=
10
(b)
S
=
20
(c)
S
=
30Figure 3
(
t
-
log
⁡
(
y
)
) curves of f
3 according to different S; (a2) is a partial graph of (a1) corresponding to log
⁡
(
y
)
∈
[
2.9407,2.946
]; (b2) is a partial graph of (b1) corresponding to log
⁡
(
y
)
∈
[
2.9385,2.9405
]; (c2) is a partial graph of (c1) corresponding to log
⁡
(
y
)
∈
[
2.937,2.9401
].(
t
-
log
⁡
(
y
)
) curves of f
4 according to different S.
(a)
S
=
10
(b)
S
=
20
(c)
S
=
30From Figures1–4, we can get that each of the number of iteration, the value of parameter c
3, and swarm size S produces an effect on performance of IPSO algorithm. Let c
3 be 0.5 and let S be 30; y
(
t
) will arrive to minimum at later iteration stage for the four benchmark functions. If y
(
t
) is zero, log
⁡
(
y
(
t
)
) will tend to be infinite, and the corresponding curves about (
t
-
log
⁡
(
y
)
) will not appear. The phenomenon happened in curves of functions f
1 and f
2, that is to say, IPSO algorithm can find target optima value for f
1 and f
2 at litter iteration number, this can be seen in Figures 1 and 2. While y
(
t
) is smaller, log
⁡
(
y
(
t
)
) will become smaller too. From Figure 3, we can get that setting c
3
=
2 is more effective for using IPSO algorithm to search optimal solution of f
3 at later iteration stage. So as to f
4, setting c
3
=
0.5 is reasonable.With different pairs of swarm size andc
3, y
(
t
) comes to the minimum at the later iteration. Table 2 lists the disjoint distribution of (
S
,
c
3
) pairs according to C
S
=
1000. Larger population sizes require more function evaluations and increase the computing efforts for convergence, but increase the reliability of the algorithm. The problem is to find a compromise between cost and reliability. In order to make IPSO algorithm have better optimization capability, we will set swarm size S
=
30, and let parameter c
3 take the corresponding values in the third row of Table 2 for the different benchmark functions in the following tests with the algorithm.Table 2
Disjoint distribution of(
S
,
c
3
) for each function.
Function
f
1
f
2
f
3
f
4
S
10
0.5
1
2
0.5
20
0.5
0.5
2
0.5
30
0.5
0.5
2
0.5(2) Compare IPSO Algorithm with Other Four Algorithms. Using BPSO, EPSO, CPSO, and ACL-PSO algorithm to compare with IPSO algorithm on above four benchmark functions, we set v
min
⁡
=
x
min
⁡
,
v
max
⁡
=
x
max
⁡
,
S
=
30
,
C
S
=
1000, and other parameters related to those compared with algorithms are listed in Table 3.Table 3
Parameter settings of different algorithms.
Algorithms
Parameters
BPSO [18]
w
min
⁡
=
0.4
,
w
max
⁡
=
0.9
,
c
1
=
c
2
=
2
,
w
(
t
)
=
w
max
⁡
-
(
w
max
⁡
-
w
min
⁡
)
*
t
/
C
S
EPSO [23]
w
max
⁡
=
0.9
,
c
1
=
c
2
=
2
,
a
=
1
,
b
=
1
CPSO [16]
w
min
⁡
=
0.4
,
w
max
⁡
=
0.9
,
c
1
=
c
2
=
c
3
=
1.4
,
w
(
t
)
=
w
max
⁡
-
(
w
max
⁡
-
w
min
⁡
)
*
(
t
/
C
S
)
ACL-PSO [17]
w
max
⁡
=
1.2
,
c
1
=
c
2
=
c
3
=
2
,
w
(
t
)
=
w
max
⁡
*
exp
⁡
(
-
0.5
*
t
*
t
)
IPSO
w
max
⁡
=
0.9
,
c
1
=
c
2
=
1.4
,
w
1
(
t
)
=
w
max
⁡
*
exp
⁡
(
-
(
t
/
C
S
)
2
)
,
w
2
(
t
)
=
w
max
⁡
*
exp
⁡
(
-
2
*
t
/
C
S
)Run each of above five algorithms 50 times independently. Record five indicators, which are the minimum object value (Min), the maximum object value (Max), the mean object value (Mean), the deviation of object value (Dev), and the average convergence iteration number (ACIN), for every run. Ours experimental results are shown in Table4 and Figures 5, 6, 7, and 8.Table 4
Comparison of the results of different PSO algorithms (D = 20).
Functions
Algorithms
Indicators
Min
Mean
Max
Deviation
ACIN
f
1
BPSO
1.0397
E
+
00
5.3844
E
+
00
2.6224
E
+
01
4.9320
E
+
00
9.9424
E
+
02
EPSO
5.8010
E
-
01
1.0862
E
+
00
1.6439
E
+
00
2.1640
E
-
01
9.5420
E
+
02
CPSO
9.8400
E
-
01
3.3640
E
+
00
9.2279
E
+
00
2.0551
E
+
00
9.7812
E
+
02
ACL-PSO
2.0906
E
-
06
6.0700
E
-
02
5.8570
E
-
01
1.4610
E
-
01
9.9998
E
+
02
IPSO
0
0
0
0
5.5164
E
+
02
f
2
BPSO
3.2302
E
+
01
8.0862
e
+
01
1.2456
e
+
02
2.0199
E
+
01
9.8684
E
+
02
EPSO
1.8100
E
+
01
5.7588
E
+
01
1.2552
E
+
02
2.3422
E
+
01
9.9958
e
+
02
CPSO
3.0708
E
+
01
6.3367
E
+
01
1.1899
E
+
02
2.0263
E
+
01
9.6404
E
+
02
ACL-PSO
1.3242
E
-
08
5.0000
E
-
03
4.5100
E
-
02
1.0100
E
-
02
1.0000
E
+
03
IPSO
0
0
0
0
5.4176
E
+
02
f
3
BPSO
4.1348
E
+
01
3.7374
E
+
04
3.0661
E
+
05
6.1177
E
+
04
9.9250
E
+
02
EPSO
2.7485
E
+
01
5.6346
E
+
02
3.5538
E
+
03
8.1005
E
+
02
9.9520
E
+
02
CPSO
2.4717
e
+
01
1.7367
E
+
04
9.5022
E
+
04
2.5152
E
+
04
9.8090
E
+
02
ACL-PSO
1.8851
E
+
01
1.8965
E
+
01
1.9363
E
+
01
8.4700
E
-
02
1.0000
E
+
03
IPSO
1.8605
E
+
01
1.8878
E
+
01
1.8942
E
+
01
5.5500
E
-
02
9.9974
E
+
02
f
4
BPSO
4.1700
E
-
02
2.0394
E
+
00
1.1227
E
+
01
2.9060
E
+
00
9.8864
E
+
02
EPSO
3.2000
E
-
02
6.0300
E
-
02
1.0026
E
+
00
1.3970
E
-
01
9.9978
E
+
02
CPSO
9.2000
E
-
03
5.5700
E
-
01
5.8396
E
+
00
9.1550
E
-
01
9.7898
E
+
02
ACL-PSO
2.1674
E
-
17
2.7549
E
-
05
2.1864
E
-
04
4.9741
E
-
05
1.000
E
+
03
IPSO
9.6962
E
-
84
6.2702
E
-
61
1.6301
E
-
59
2.7260
E
-
60
9.9994
E
+
02(
t
-
y
(
t
)
) curves of f
1 according to results of five algorithms. (b) is a partial graph of (a) corresponding to y
(
t
)
∈
[
0,1.2
].
(a)
(b)(
t
-
y
(
t
)
) curves of f
2 according to results of five algorithms. (b) is a partial graph of (a) corresponding to y
(
t
)
∈
[
0,0.1
].
(a)
(b)(
t
-
y
(
t
)
) curves of f
3 according to results of five algorithms. (b) is a partial graph of (a) corresponding to y
t
∈
18.6,22.
(a)
(b)(
t
-
y
(
t
)
) curves of f
4 according to results of five algorithms. (b) is a partial graph of (a) corresponding to y
(
t
)
∈
[
0,1
0
-
3
].
(a)
(b)From Table4, it can be seen that there are higher accuracy for the IPSO than that for the BPSO, EPSO, CPSO, and ACL-PSO. From the mean and deviation in Table 4, the IPSO is better than the BPSO, EPSO, CPSO, and ACL-PSO, with a steady convergence. In addition, IPSO algorithm needs less number of iteration for coming to convergence than ACL-PSO algorithm does.Let iteration numbert be as x-coordinate and average best object value according to the t
th iteration y
(
t
) as y-coordinate; we plot (
t
-
y
(
t
)
) curves of these four benchmark functions in Figures 5–8.From Figures5–8, it can be seen that IPSO algorithm, compared to other four algorithms, searches more excellent object value at later iteration. EPSO, CPSO, ACL-PSO, and IPSO algorithm all can find more optimal solution than BPSO algorithm does after litter iteration number, and the performance of IPSO algorithm is the best among these five algorithms. In addition, IPSO algorithm needs less iteration number to come to convergence than ACL-PSO algorithm does. This phenomenon is considered to be due to the combination of inertia weight w
2
(
t
) working with population centroid and w
1
(
t
) working with best individual centroid.(3) Compare Success Rate and Average Number of Iteration Corresponding to Target Precision Arriving. In order to validate the effectiveness of IPSO algorithm further, we set target precisions of above four benchmark functions, which are listed in Table 5 and run every algorithm 100 turns for each of test functions, respectively. Setting the maximum iteration number as 1000, while object value is less than or equal to its target precision, we plus success convergence number with one and record the current iteration number at one turn. Then, success rate (SR) is equal to the success convergence number divided by total number of turns. Average convergence iteration (ACI) is the mean iteration numbers at all. Four group target accuracies, which are listed in Table 5, are used to evaluate the stability of those algorithms. Our experimental results are shown in Table 5.Table 5
Comparison of experimental results of success rate and average convergence iteration.
Functions
Target precision
Indicators
BPSO
EPSO
CPSO
ACL-PSO
IPSO
f
1
0.1
SR
0
0
0
86
100
ACI
1000
1000
1000
901.28
676.66
0.6
SR
0
4
0
98
100
ACI
1000
974.80
1000
747.80
607.82
1
SR
0
26
4
100
100
ACI
1000
818.98
989.02
439.76
472.48
1.5
SR
16
100
64
100
100
ACI
991.82
327
840.20
23.10
269.64
f
2
10−7
SR
0
0
0
48
100
ACI
1000
1000
1000
967.60
369.50
20
SR
0
4
0
100
100
ACI
1000
971.98
1000
40.92
262.20
30
SR
0
8
2
100
100
ACI
1000
945.64
998.82
42.42
267.02
40
SR
2
30
12
100
100
ACI
982.44
775.36
944.36
28.62
254.82
f
3
19
SR
0
0
0
70
100
ACI
1000
1000
1000
932.98
336.88
30
SR
0
8
0
100
100
ACI
1000
947.38
1000
444.52
275.40
40
SR
0
14
2
100
100
ACI
1000
903.22
983
333.14
608.60
500
SR
6
62
30
100
100
ACI
998.72
530.34
943.50
36.18
28.40
f
4
10−10
SR
0
0
0
78
100
ACI
1000
1000
1000
920.22
330.84
0.01
SR
0
10
8
100
100
ACI
1000
932.46
980.92
229.54
255.48
0.05
SR
4
68
18
100
100
ACI
998.68
504.24
959.46
53.96
225.48
0.1
SR
14
90
52
100
100
ACI
994
294.80
899.40
34.64
209.18From Table5, it can be seen that success rates of those five algorithms are affected by the target accuracies. Success rate of IPSO algorithm for each test function reaches 100% and is obviously better than those of BPSO, EPSO, CPSO, and ACL-PSO. Average convergence iteration of EPSO is smaller than CPSO algorithm, and ACI of IPSO is smaller than EPSO algorithm. So as to the ability of finding optimal solutions, ACL-PSO algorithm is better than BPSO, EPSO, and CPSO algorithms, and IPSO algorithm is better than ACL-PSO algorithm.


## 5. Conclusions

The particle swarm optimization algorithm is a global stochastic tool, which has ability to search the global optima. PSO algorithm is easily trapped into local optima. In this paper, in order to overcome the shortcoming of PSO algorithm, we propose an improved particle swarm optimization algorithm (IPSO) based on two forms of exponential inertia weight and two kinds of centroids. By means of comparing optimization ability of IPSO algorithm with BPSO, EPSO, CPSO, and ACL-PSO algorithms, experimental results of these four benchmark functions show that the proposed IPSO algorithm is more efficient and outperforms other PSO algorithms in accuracy investigated in this paper. Inertia weight is one of the important parameters in PSO algorithm. How can (5) respect the constraint on w
min
⁡? Moreover can a
and
b be chosen to be adaptive throughout a single evolution to guarantee a suitable trade-off between exploration and exploitation phase? These are good future research directions for us.



---

*Source: 976486-2014-12-30.xml*