Particle Swarm Algorithm

    Introduction


    A flock of birds is a great example of collective animal behavior. Flying in large groups, they almost never collide in the air. A flock moves smoothly and in a coordinated manner, as if someone is controlling it. And anyone who hung a feeder in his yard knows that after a few hours all the birds in the area will find him.



    The point here is not at all the leader giving orders - in flocks of many species of birds he simply does not exist. Like a colony of ants or bees, the flock is a swarm intelligence. The birds in it act according to certain — rather simple — rules. Circling in the sky, each of the birds watches its relatives and coordinates its movement according to their position. And finding a source of food, she will notify them of this.

    The last fact should be considered in more detail, since it plays one of the key roles in the optimization method under consideration. The reasons for this "altruism" of birds (and other animals acting in a similar way) were the subject of research by many sociobiologists. One of the most popular explanations for this phenomenon is that the benefits of such behavior of each individual of the pack are greater than such obvious disadvantages as the need to fight for food found with other individuals.

    Food sources are usually located randomly, so in solitude the bird may well die without finding a single one for a long time. However, if all the birds "play by the rules", sharing information about the finds with their relatives, then the chances of each of them to survive increase sharply. Thus, being ineffective for an individual individual, such a strategy is the key to the effectiveness of the pack and the species as a whole.

     

    Boids


    Bird watching inspired Craig Reynolds to create a computer model in 1986, which he called Boids. To simulate the behavior of a flock of birds, Reynolds programmed the behavior of each of them individually, as well as their interaction. He used three simple principles. Firstly, each bird in his model sought to avoid collisions with other birds. Secondly, each bird moved in the same direction as the birds nearby. Thirdly, the birds sought to move at the same distance from each other.

    The results of the first simulations surprised the creator himself: despite the simplicity of the algorithms underlying the program, the flock on the screen looked extremely believable. Birds huddled in groups, avoided collisions, and even randomly rushed exactly like real ones.
    As a specialist in computer graphics, Craig Reynolds was primarily interested in the visual side of the results of the simulation he created. However, in an article on Boids, he also noted that the behavior model he developed could be expanded by the introduction of additional factors, such as food searches or fear of predators [1].

     

    Classic particle swarm algorithm


    In 1995, James Kennedy and Russell Eberhart proposed a method for optimizing continuous nonlinear functions, which they called the particle swarm algorithm [2]. The inspiration for them was a simulation model of Reynolds, as well as the work of Heppner (Heppner) and Grenadier (Grenader) on a similar topic [4]. Kennedy and Eberhart noted that both models are based on controlling the distance between the birds - and, therefore, the synchronism of the flock is a function of the efforts that the birds make to maintain the optimal distance.

    The algorithm they developed is quite simple and can be implemented in just a few dozen lines of code in any high-level programming language. He models a multi-agent system where particle agents move toward optimal solutions while exchanging information with neighbors.

    The current state of the particle is characterized by the coordinates in the space of solutions (that is, in fact, the solution associated with them), as well as the displacement velocity vector. Both of these parameters are randomly selected at the initialization stage. In addition, each particle stores the coordinates of the best solution found by it, as well as the best of the solutions passed by all particles - this simulates the instant exchange of information between birds.

    At each iteration of the algorithm the direction and length of the velocity vector of each of the particles is changed in accordance with information about the found optima:

    ,

    wherein - the particle velocity vector ( - its i-th component) , - constant acceleration, - the best found by particle point - the best point of those traversed by all particles of the system, is the current position of the particle, and the function returns a random number from 0 to 1 inclusive.

    After calculating the direction of the vector , the particle moves to a point . If necessary, the values ​​of the best points for each particle and for all particles as a whole are updated. After that, the cycle repeats.

     

    Modifications to the Classic Algorithm


    The particle swarm algorithm appeared relatively recently, however, a number of modifications have already been proposed by various researchers, and new works on this subject have not ceased to be published. There are several ways to improve the classical algorithm, implemented in most of them. This is a combination of the algorithm with other optimization algorithms, a decrease in the probability of premature convergence by changing the characteristics of particle motion, and also a dynamic change in the algorithm parameters during optimization. Below are the most noteworthy of the modifications.

    Lbest


    Later that same 1995, an article by Kennedy and Eberhart was published in which they called the original “GBEST” algorithm, because it uses the global best solution to form velocity vectors, and also proposed a modification called “LBEST”. When updating the direction and velocity of the particle movement in LBEST use information about the decisions the neighboring particles of them:

    ,

    where - the best result among the particles and its neighbors. Neighboring particles are either particles that differ from the given index by no more than a certain given value, or particles whose distance does not exceed a given threshold.

    This algorithm more thoroughly explores the search space, but is slower than the original. Moreover, the smaller the number of neighbors taken into account when forming the velocity vector, the lower the convergence rate of the algorithm, but the more efficient it avoids suboptimal solutions.

    Inertia Weighted PSO


    In 1998, Yuhui Shi and Russell Eberhart proposed a modification that, at first glance, differs only slightly from the classical algorithm [5]. In their article, Shea and Eberhart noted that one of the main problems in solving optimization problems is the balance between thorough research of the search space and the rate of convergence of the algorithm. Depending on the task and the characteristics of the search space in it, this balance should be different.
    In view of this, Shi and Eberhart proposed to change the update rule particle velocity vectors:

    ,

    factor , named their inertia coefficient, determines said balance between latitude and attention to the study found suboptimal solutions. In the case when, the particle speeds increase, they fly apart and explore the space more carefully. Otherwise, the particle velocities decrease with time, and the convergence rate in this case depends on the choice of parameters and .

    Time-Varying Inertia Weighted PSO


    In their 1998 work, Shea and Eberhart noted that inertia does not have to be a positive constant: it can change during the operation of the algorithm according to a linear and even nonlinear law [5]. In a 1999 article and later works, they most often used the linear law of decrease, as quite effective and at the same time simple [6]. Nevertheless, other laws of inertia change were developed and successfully applied.

    The value of the inertia coefficient can either decrease or grow. As it decreases, the particles first explore the search area extensively, finding many suboptimal solutions, and eventually concentrate more on exploring their surroundings. The increase in inertia contributes to the convergence of the algorithm in the later stages of work.

    Canonical PSO


    In 2002, Maurice Clerc and James Kennedy proposed their modification of the particle swarm algorithm, which has become so popular that it is now called the canonical particle swarm algorithm [7]. It eliminates the need to "guess" the appropriate values ​​of the adjustable parameters of the algorithm, controlling the convergence of the particles.

    Clair and Kennedy modified method of calculating the velocity vectors of the particles by introducing into it an additional factor:

    ,

    where , as the compression ratio is:

    .

    This approach guarantees the convergence of the algorithm without the need to explicitly control the particle velocity.

    Fully Informed Particle Swarm


    In their 2004 work, Rui Mendes, James Kennedy, and José Neves noted that the assumption that each particle is affected by only the most successful particle in the canonical particle swarm algorithm does not correspond to its underlying natural mechanisms and, possibly, leads to a decrease in the efficiency of the algorithm [8]. They suggested that because of the excessive attention of the algorithm to a single solution, important information about the structure of the search space could be lost.

    Based on this, they decided to make all the particles "fully informed", that is, receiving information from all neighboring particles. To do this, they have changed in the canonical law of the rate of change algorithm:

    ,

    where - the set of particles neighbors- the best of the points passed by the k-th neighbor. - a weight function that can reflect any characteristic of the kth particle that is considered important: the value of the objective function at the point at which it is located, the distance from it to the given particle, and so on.

     

    Conclusion


    In the first article describing the particle swarm algorithm, James Kennedy and Russell Eberhart expressed the idea of ​​using the algorithm to simulate social behavior - Kennedy, as a social psychologist, was extremely attracted to this idea [1]. However, the algorithm is most widely used in optimization problems for complex multidimensional nonlinear functions.

    The particle swarm algorithm is widely used, among others, in machine learning tasks (in particular, for training neural networks and image recognition), parametric and structural optimization (shapes, sizes and topologies) in the field of design, in the fields of biochemistry and biomechanics. In terms of efficiency, it can compete with other methods of global optimization, and low algorithmic complexity contributes to the simplicity of its implementation.

    The most promising areas for further research in this direction should be considered theoretical studies of the reasons for the convergence of the particle swarm algorithm and related issues from the areas of swarm intelligence and chaos theory, combining various modifications of the algorithm to solve complex problems, considering the particle swarm algorithm as a multi-agent computing system, and study of the possibilities of including analogues of more complex natural mechanisms in it.

     

    Literature


    [1] Craig Reynolds, “Flocks, Herds, and Schools: A Distributed Behavioral Model” // Computer Graphics, 21 (4), pp. 25–34, 1987.
    [2] J. Kennedy, RC Eberhart, “Particle swarm optimization ”// In Proceedings of IEEE International Conference on Neural Networks, pp. 1942–1948, 1995.
    [3] RC Eberhart, J. Kennedy,“ A new optimizer using particle swarm theory ”// Proceedings of the Sixth International Symposium on Micro Machine and Human Science MHS'95, pp. 39–43, 1995.
    [4] F. Heppner, U. Grenander, “A stochastic nonlinear model for coordinated bird flocks” // The Ubiquity of Chaos, p. 233–238, 1990.
    [5] Y. Shi, R. Eberhart, “A modified particle swarm optimizer” // The 1998 IEEE International Conference on Evolutionary Computation Proceedings, pp. 69–73, 1998.
    [6] Y. Shi, R. Eberhart, “Empirical study of particle swarm optimization” // Proceedings of the 1999 IEEE Congress on Evolutionary Computation, pp. 1945–1950, 1999.
    [7] M. Clerc, J. Kennedy , “The particle swarm - explosion, stability, and convergence in a multidimensional complex space” // IEEE Transactions on Evolutionary Computation, No. 6 (1), pp. 58–73, 2002.
    [8] R. Mendes, J. Kennedy, J. Neves, “The fully informed particle swarm: Simpler, maybe better” // IEEE Transactions on Evolutionary Computation, No. 8 (3), pp. 204–210, 2004.

    Also popular now: