改进的粒子群算法

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