A Modified Particle Swarm Optimizer
Yuhui Shi and Russell Eberhart
Department of Electrical Engineering
Indiana University Purdue University Indianapolis
hdianqolis, IN 46202-5160
Shi. eberhart@,tech.iuEnti. edu
ABSTRACT
In this paper, we introduce a new parameter, called
inertia weight, into the original particle swarm
optimizer. Simulations have been done to illustrate the
signilicant and effective impact of this new parameter on
the particle swarm optimizer.
1. INTRODUCTION
Evolutionary computation techniques (evolutionary
programming [4], genetic algorithms [5], evolutionary
strategies [9] and genetic programming [SI) are
motivated by the evolution of nature. A population of
individuals. which encode the problem solutions. are
manipulated according to the rule of survival of the
fittest through “genetic” operations, such as mutation,
crossover and reproduction. A best solution is evolved
through the generations. These kjnds of techniques have
been successfully applied in many areas and a lot of new
applications are expected to appear. In contrast to
evolutionary computation techniques, Eberhart and
Kennedy developed a different algorithm through
simulating social behavior [2,3,6,7J As in other
algorithms, a population of individuals exists. This
algorithm is called particle swarm optimization (PSO)
since it resembles a school of flying birds. In a particle
swarm optimizer, instead of using genetic operators,
these individuals are “evolved” by cooperation and
competition among the individuals themselves through
generations. Each particle adjusts its flying according to
its own flying experience and its companions’ flying
experience. Each individual is named as a “particle”
which, in fact, represents a potential solution to a
problem. Each particle is treated as a point in a D-
dimensional space. The ith particle is represented as
X ~ ( x , ~ , x ~ , .__ , x~). The best previous position (the
position giving the best fitness value) of any particle is
recorded and represented as PF(pll,po, . . . , pa). The
0-7803-4869-9198 $10.0001998 EEE 69
index of the best parhcle among all the particles in the
population is represented by the symbol g . The rate of
the position change (velocity) for particle i is represented
as Vf(vil,viz, . .. , VD). The particles are manipulated
according to the following equation:
where c1 and c2 are two positive constants, rand() and
Rand() are two random functions in the m g e [0,1]. The
second part of the equation (la) is the “~~gnition” part,
which represents the private thinking of the particle
itself. The third part is the “social” part, which
represents the collaboration among the particles [7]. The
equation (1 a) is used to calculate the particle‘s new
velocity according to its previous velocity and the
distances of its current position from its own best
experience (position) and the group’s best experience.
Then the particle flies toward a new position according
to equation (lb). The performance of each particle is
measured according to a predefined fitness fundion,
which is related to the problem to be solved.
The particle swarm optimizer has been found to be
robust and fast in solving nonlinear, non+iiEerentiable.
multi-modal problems. but it is still in its infmcy. A lot
of work and research are needed In this ]paper, a new
parameter is introduced into the equation, which can
improve the performance of the particle swarm
optimizer.
2. A MODIFIED PARTICLE SWARM
OPTIMIZER
Refer to equation (la). the right side of which consists of
three parts: the first part is the previous velocity of the
F c l e : the second and third parts are the ones
contributing to the change of the velocity of a particle.
Without these two parts, the particles will keep on
“flying” at the current speed in the same direction mtd
they hit the bounw. PSO will not find a acceptable
solution unless there are acceptable solutions on their
“flying” trajectories. But that is a rare case. On the
other han4 refer to equation (la) without the first part.
Then the “flying” particles’ velocities are only
determined by their current positions and their best
positions in history. The velocity itself is memoryless.
Assume at the beginning, the particle i has the best
global position, then the particle z will be “Ylying” at the
velocity 0, that is, it will keep still until another particle
takes over the global best position. At the same time,
each other particle will be “flying” toward its weighted
centroid of its own best position and the global best
position of the population. As mentioned in [6], a
recommended choice for constant c1 and c2 is integer 2
since it on average makes the weights for “social” and
“c0gniti0n’’ parts to be 1. Under t h s condition, the
particles statistically contract swarm to the current global
best position until another parhcle takes over from which
time all the particles statistically contract to the new
global best position. Therefore, it can be imagmed that
the search process for PSO without the first part is a
process where the search space statistically shrinks
through the generations. It resembles a local search
algorithm. This can be illuminated more clearly by
displaying the “flying” process on a screen. From the
screen, it can be easily seen that without the first part of
equation (la), all the particles wil l tend to move toward
the same position, that is, the search area is contracting
through the generations. Only when the global optimum
is within the initial search space, then there is a chance
for PSO to find the solution. The final solution is
heavily dependent on the initial seeds (population). So it
is more likely to exhibit a local search ability without the
first part. On the other hand, by adding the first part, the
parttcles have a tendency to expand the search space, that
is, they have the ability to explore the new area. So t h q
more likely have a global search ability by adding the
first part. Both the local search and global search will
benefit solving some kinds of problems. There is a
tradeoff between the global and local search For
different problems, there should be different balances
between the local search ability and global search ability.
Considering of this, a inertia weight w is brought into the
equation (1) as shown in equation (2). This w plays the
role of balancing the global search and local search It
can be a positive constant or even a positive linear or
nonlinear function of time.
3. EXPERIMENTS AND DISCUSSION
In order to see the influence which the inertia weight has
on the PSO performance, the benchmark problem of
Schaffer’ s f6 function [ 11 was adopted as a testing
problem since it is a well known problem and its global
optimum is known. The implementation of the PSO was
written in C and compiled using the Borland C++ 4.5
compilex. For the purpose of comparison, all the
simulations deploy the same parameter settings for the
PSO except the inertia weight w. The population size
(number of particles) is 20; the maxi” velocity is set
as 2; the dynamic range for all elements of a particle is
defined as (-100, loo), that is. the particle cannot move
out of this range in each dimension. For the SchafEer ’ s
f6 function ~ the dimension is 2. So we display particles’
<‘flying” process on the computer screen to get a visual
understanding of the PSO performance; the maximum
number of iterations allowed is 4000. If PSO cannot
find a acceptable solution within 4000 iterations. it is
claimed that the PSO fails to find the global optimum in
this run.
Different inertia weights w have been chosen for
simulation For each selected w, thirty runs are
performed and the iterations required for finding the
global optimum are recorded The results are listed in
Table 1. In Table 1, the empty cells indicate that the
PSO failed to ftnd the global optimum within 4000
iterations in that running. For each w, the average
number of iterations required to &id the global optimum
is calculated and only the runs which find the global
optimum are used for calculating the average. For
example. when w=O.95, one run out of 30 failed to find
the global optimum, so only 29 run results are used to
calculate the average. The average number of iterations
for each w is listed at the bottom of the table 1. From
Table 1, it’s easy to see that when w is small (< OX), if
the PSO finds the global optimum. then it fitids it fast.
Also from the display on the screen, we can see that all
the particles tend to move together quickly. This
confirms our discussion in the previous section that when
w is small. the PSO is more like a local search algorithm
If there is acceptable solution within the initial search
space, then the PSO will find the global optimum
quickly, otherwise it will not find the global optimum.
When w is large (>1.2), the PSO is more like a global
search method and even more it always tries to exploit
the new areas. This is also illustrated by the “flying-’
display on the screen It is natural that the PSO will take
more iterations to find the global optimum and have
more chances of failing to find the global optimum.
When w is medium (0.8
本文档为【改进的粒子群算法】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑,
图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
该文档来自用户分享,如有侵权行为请发邮件ishare@vip.sina.com联系网站客服,我们会及时删除。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。