What is particle swarm optimization 1

Particle Swarm Optimization

  • 20 minutes to read

This article has been machine translated.

Artificial intelligence

James McCaffrey

Download the code sample

Particle Swarm Optimization (PSO) is an Artificial Intelligence (AI) technique that can be used to find approximate solutions to extremely difficult or impossible numerical maximization and minimization problems. The version of the PSO described in this article was first found in a 1995 research paper by j. presents. Kennedy and R. Eberhart. PSO is loosely based on group behavior, such as B. Birds flock and fish schooling modeled. The best way for you to get a feel for what PSO is and to see where I'm heading here is to check out illustration 1.

The first part of the figure describes a dummy problem that is solved by using a demonstration PSO program. The target X is looking for 0 and 1 X values, so the value of the function f = 3 + 0 X ^ 2 + 1 X ^ 2 is minimized. Here use the notation ^ 2 to indicate the squaring process. Note that I have chosen an unrealistically simple problem keeping the PSO's ideas clear. It is obvious that the solution to this problem is x 0 = 0.0 and x 1 = 0.0, yields the function value minimal 3.0, with PSO is really necessary. Discusses more realistic issues that can be resolved by PSO later in this article. In this example the dimension of the function is minimized 2 because we have to solve 2 for numeric values. PSO is generally well suited for numerical problems with dimensions 2 or larger. In most cases PSO have some restrictions on the range of possible X values. Here, X 0 and 1 X are arbitrarily limited to the range 100.0 to 100.0.

illustration 1 Run Particle Swarm Optimization Demo

The next part of the illustration 1 states that the PSO program is run through 10 particles and the program runs 1,000 times. As you will see shortly, each particle represents a possible solution to the PSO problem being solved. PSO is an iteration process and in most cases it is not possible to know when an optimal solution has been found. PSO algorithms therefore usually have to implement some limit on the number of iterations.

The next lines illustration 1 indicate that each of the 10 particles in the swarm is initialized to a random position. A particle represents a possible solution to the optimization problem to be solved. The best randomly generated starting position is x 0 = 26.53 and x 1 = -6.09, which corresponds to a suitability (the measure of the quality of the solution) of 3 + 26.53 ^ 2 + (-6.09) ^ 2 = 744.12. The PSO algorithm then enters a main processing loop where each particle updates position with each iteration of the loop. The update procedure is at the heart of the PSO and is explained later in this article. After 1,000 iterations the PSO algorithm will indeed find the optimal solution x 0 = 0.0 and x 1 = 0.0, but let me emphasize that in most situations, I do not know whether a PSO program has found an optimal solution.

In this article I explain PSO algorithm in detail and walk through the program in line by line illustration 1. I coded the demo program in C #, but you should transfer the code that is presented here to another language, such as B. Easily customize Visual Basic .NET or Python. The full source code for the program featured in this article is available at code.msdn.microsoft.com/mag201108PSO. This article assumes you have intermediate programming knowledge with modern procedural language but does not assume that you know anything about PSO or related AI techniques.

Particles

When using PSO, one possible solution to the numerical optimization problem under investigation is presented by the position of a particle. In addition, each particle has a current velocity that represents an amount and direction in a new direction, presumably a better solution position. A particle also has a measure of the quality of its current position, the particle known position (that is, a previous position with the known quality), and the quality of the most known position. I coded a particle class as shown in Figure 2.

Figure 2 Particle (definition)

The Particle class has five public data members: Position, Fitness, Speed, BestPosition, and BestFitness. When using PSO, for simplicity, prefer public field fields, but want to use private fields along with properties to get and set instead. The field with the position is an array of the type double and represents a possible solution to the problem of optimization under investigation. Although PSO can be used to solve numerical problems, in general it is best for solving numerical problems. Field fitness is a measure of how well the solution is represented by position. Minimization Problems The most common problems solved by PSO are that smaller values ​​of the Fitness field are better than larger values; Maximizing problems, greater aptitude values ​​are better.

Field Velocity is an array of type double and represents information necessary to update a particle's current position / solution. I will briefly describe Particle Velocity in detail. The fourth and fifth fields in the particle type are BestPosition and BestFitness. These fields contain the best position / solution found by the particle object and the associated suitability of the best position.

The particle class has a single constructor that accepts five parameters, each corresponding to five data fields of the particle. The constructor simply copies each parameter value into the corresponding data field of the. Since all five fields of the particle are public area, I could have specified the constructor and only used field assignment statements in the PSO code, but I think the constructor performs cleaner code.

The particle class definition contains a ToString method that echoes the values ​​of the data fields into five. As with the constructor, since I declared the Position, Fitness, Velocity, BestPosition, and BestFitness fields with the public area, I really need a ToString method for a Particle object, but including it simplifies the display of the fields and it is useful for the WriteLine style to debug while developing. In the ToString method, I use string concatenation instead of the more efficient StringBuilder class to make it easier to refactor code in a Microsoft .NET Framework-based language if you wish.

PSO algorithm

Although the heart of the ThePSO Algorithm is pretty simple, you must understand it thoroughly in order to modify the code in this article to suit your own needs. PSO is an iterative process. At each iteration in the main PSO processing loop, each particle's current velocity is first updated based on the particle's current velocity, the particle local information and global swarm information. Then each particle position is updated using the particle new velocity. In math are terms that update the two equations:

v(t + 1) = (w * v(t)) + (c1 * r1 * (p(t) - x(t)) + (c2 * r2 * (G(t) - x(t))

x(t + 1) = x(t) + v(t + 1)

Bear here with me; actually updating the position is much simpler than these equations suggest. The first equation updates a particle velocity. The term v(t + 1) means the velocity at time t + 1. Note that v is formatted in bold, is a vector value that indicates velocity and has several components such as: B. {1.55, -0.33} instead of a single scalar value . The new speed depends on three terms. The first term is w * v(t). W factor is called the weight of inertia and is simply a constant like 0.73 (more on this shortly); v (t) is the current speed at time t. The second expression is c1 * r1 * (p(t) - x(t)). The c1 factor is a constant called cognitive (or personal or local) weight. The r1 factor is a random variable in the range [0, 1) that is greater than or equal to 0 and less than 1. The p(t) vector value is the particle's optimal position found so far. The x(t) -vector value is the current position of the particle. The third term velocity update equation is (c2 * r2 * (G(t) - x(t)). The c2 factor is a constant called social - or global - weight. The r2 factor is a random variable in the [0, 1). The ** g (** t) vector value is the best known position to be found by any particle in the swarm so far. Once the new velocity, v (t + 1), has been determined, it will be used to calculate the new particle position x(t + 1).

Make a specific example of deactivating the update. For example, suppose you are trying to minimize 3 + 0 X ^ 2 + 1 X ^ 2, as described in the introductory section of this article. The function is shown in Figure 3. The base of the containing cube in Figure 3 represents X 0 and 1 X values ​​and the vertical axis represents the function value. Note that the plot surface is minimized with f = 3 when x 0 = 0 and x 1 = 0.

Figure 3 Plot f = 3 + 0 X ^ 2 + 1 X ^ 2

Assuming that a particle has its current position, x(t), is {x 1 X 0} = {3.0, 4.0}, and that the particle's current velocity, v(t), is {1.0, -1.5}. Let us further assume that constant w = 0.7, constant c1 = 1.4, constant c2 = 1.4, and random numbers r1 and r2 are 0.5 and 0.6, respectively. Finally suppose the particle is known 's location p(t) = {2.5, 3.6} and is the globally known position through any particle in the swarm G(t) = {2.3, 3.4}. Then the new values ​​for speed and position will be:

V(t + 1) = (0.7 * {1.0, -1.5}) +

         (1.4 * 0.5 * {2.5, 3.6} - {3.0, 4.0}) +

         (1.4 * 0.6 * {2.3, 3.4} – {3.0, 4.0})

       = {-0.70, -1.05} + {-0.35, -0.28} + {-0.59, -0.50}

       = {-1.64, -1.83}

X(t + 1) = {3.0, 4.0} + {-1.64, -1.83}

       = {1.36, 2.17}

Remember that the optimal solution is {x 1 X 0} = (0.0, 0.0}. Note that the update process improved the old position / solution from (3.0, 4.0} to {1.36, 2.17} If you mulled a little about the update process, you'll see that the new velocity is the old velocity (times a weight) plus a factor that depends on a particle's known position plus another factor that depends on the most known position from all of the particles in The swarm depends. A Particle's new position therefore tends to move towards a better position based on the known particle and the most known position of all the particles. The diagram in the Figure 4 shows the movement of one of the particles during the first eight iterations of the PSO run demo. The particle starts at 0 X = 100.0 x 1 = 80.4 and tends to move towards x 0 = 0 x 1 = 0 the optimal solution. The spiral movement is typical of PSO.

Figure 4 Particle movement towards optimal solution

Implement the PSO algorithm

Figure 5 represents the general structure of the program PSO the program executed, see generated illustration 1. I have Visual Studio creating a C # console application project called ParticleSwarmOptimization. PSO code is pretty simple, so any version of the .NET Framework (1.1 through 4) will work fine. All Visual Studio generated using statements except for the reference to the core system namespace has been removed. I explained a scope of the class Object of type Random for generating the cognitive and social random numbers described in the previous section. I also have the random object to generate random initial velocities and positions for each particle object. Inside the main method I wrap all of my code in a single general try statement to catch exceptions.

Figure 5 PSO program structure

After instantiating the random object with any starting value 0, some important PSO variables are initialized:

I am using 10 particle objects. As a rule of thumb, more particle objects are better than fewer, but more can significantly affect program performance. Can I set the number of main processing loop iterations to 1,000. The number of iterations you want to use depends on the complexity of the problem you want to optimize and the processing power of the host machine. PSO programs typically use a value between 1,000 and 100,000. The variable called iteration is a counter to keep track of the number of main loop iterations. The Dim variable contains the number of x values ​​in a solution / position. Since my problem example needs to find the values ​​of 0x and the minimization of 3 X 1 + 0 X ^ 2 + 1 X ^ 2, I set Dim to 2. As already mentioned, in most situations the PSO should restrict the X -values ​​that form the vector position-solution to some problem-dependent area. Without some restrictions they are effectively sought from double.MinValue to double.MaxValue. Here I arbitrarily constrain X 0 and X 1, [100.0, +100.0].

Next, I prepare to instantiate the particle swarm:

I create an array of particle objects named swarm. I also set up an array, holding the globally known position determined by any particle - denoted by G(t) in the algorithm - and the corresponding suitability of the array position. Limitations set for the maximum and minimum values ​​for a new velocity. The idea behind this is that since a new velocity determines a particle's new position, the magnitude of the velocity components should not be enormous.

The code to initialize the swarm of points is as follows:

Iterate through each particle object in the array named swarms of points. I explain it to be an array of size Dim to hold a random position for the current particle. For each X value of the position I generated a random value between MinX (100.0) and MaxX (+100.0). In many realistic PSO problems, the range will be different for each X-value so you will need to add code to deal with each X-value in the position array separately.

Now that continued the initialization process:

First computes the quality of the current random position array of arrays passed to the Objective Function method. When you get back in Figure 5, you can see that the ObjectiveFunction method simply calculates the value of the function I am trying to minimize, which is 3 + x 0 ^ 2 + 1 X ^ 2. Next, you calculate a random velocity for the current Particle object. After I have a random position, the suitability of the random position, and a random one, pass these values ​​to the particle constructor. Remember that the fourth and fifth parameters are known to the particle's position and its associated fitness, so when you initialize a particle, its initial random position and fitness are the known values.

The initialization code swarm ends with:

I check whether the suitability of the current particle is the best (in case of a minimization problem, smallest) fitness found so far. If so, the array updates BestGlobalPosition and the corresponding variable BestGlobalFitness.

Next I prepare the main loop for processing the PSO to enter:

I set the value for w, the weight inertia to 0.729. This value was recommended by research examining the effects of the various PSO parameter values ​​on a range of benchmark minimization problems. Instead of a single, constant value for w, an alternative approach is to vary the value of w. For example, if the PSO algorithm is set 10,000 times it could first iterate w as 0.90 and gradually decrease it to 0.40 by reducing ww 0.10 after every 2,000 iterations. The idea of ​​a dynamic w is that early in the algorithm you want to investigate larger changes in position, but later you want smaller particle movements. I set the values ​​for c1 and c2, the cognitive and social weights at 1.49445. Again, this value was recommended by a study. If the value is set greater than the value of c2 c1, you are placing more weight on a particle known position as the world's most known position of the point swarm and vice versa. Random variables r1 and r2 add a random component to the PSO algorithm, and prevent the algorithm from being stuck with a non-optimal local minimum or maximum solution.

Next, start the main loop for processing the PSO:

Each particle object using i swarm will be traversed as an index variable. I create a reference to the current Particle Object named CurrP to simplify my code, but I could have used Swarm [i] already directly. As explained in the previous section, the first step is to update each particle velocity vector. For the current Particle Object, I loop through each of the values ​​in the Object-Velocity-Array to generate random variables r1 and r2 and update each Velocity component as explained in the previous section.

After I calculate a new velocity component for the current particle object, I check whether this component is between the minimum and maximum values ​​for a velocity component:

If the component is out of range I will bring it back in range. The idea behind this is that extreme values ​​for the velocity component shouldn't spin because extreme values ​​could spin my new position out of bounds. After all Velocity components have been calculated, update the current Particle Object Velocity Array using the handy.NET CopyTo method.

Once the velocity of the current particle has been determined, the new velocity can be used to calculate and update the current particle position:

Do a range check again, this time on the current particle's new position components. In some ways this is a redundant check box because I've already constrained the value of each Velocity component, but in my opinion adding additional check boxes here is warranted.

Now, I re-position the current particle object, I calculate new fitness value and update the object’s fitness field:

After updating the current particle, I check that the new position is the best known position of the particle; I also check that the new position is an optimal position for the global swarm. Note that logically, there can be a new global best position only if it is local best position so I could have nested the global best check inside the check box for a local optimal position.

At this point my main PSO algorithm loop is complete and I can see my results:

Expand and change

Now that you've seen writing a basic PSO, consider expanding and changing the code presented. The example problem that I solved is artificial in the sense that there is no need to use PSO to find an approximate solution as the exact problem can be solved. Whereby PSO is really useful when the numerical problem being studied is extremely difficult or impossible to solve using standard techniques. Consider the following problem. The evaluation of an (American) soccer game between teams A and B should be predicted Historical data consisting of the previous results of a and b against other teams. Mathematically, model the historical rating for a team X so that the team wins a game, the team rating goes by some fixed value (e.g.16 points) plus another value, the difference between ratings of the teams depends on (0.04 times tell the difference when the team X rating is less than the opposing team). In addition, model a team's predicted edge victory as a function of the difference in team ratings; For example, if Team X is rated 1720 and Team Y is rated as 1,620, your model predicts a profit margin of win for x 3.5 points. In short, have a large amount of data and need several numeric values ​​(such as the 16 and the 0.04) to determine which will minimize your prediction errors. This data-driven parameter estimation is the kind of problem that is right up the top of PSO Alley.

PSO is just one of several AI techniques that affect the behavior of natural systems. Perhaps the technology closest to PSO algorithms is genetic algorithms (GAs). Both methods are well suited to difficult numerical problems. GAs have been studied extensively for decades. One advantage of PSO over GAs is that PSO algorithms are much easier to implement than GAs. It is not clear at this point whether PSOs are more or less effective than GAs or about the same.

The version of the PSO presented here can be changed in many ways. One change particularly interesting is to use multiple sub-swarms of particles instead of a global swarm. With such a design, each particle belongs to a sub-swarm and the new velocity of a particle could depend on four terms rather than three: the old velocity, the particle's best known position, the best known position of any particle in the sub- swarm, and the best known position of any particle. The idea of ​​this sub-swarm design is to reduce the risk of the PSO algorithm being stuck in a non-optimal solution. To the best of my knowledge, such a design has not yet been thoroughly studied.

Dr. James McCaffreyworks for Volt Information Sciences Inc. and where he provides technical training for software developers at the Microsoft in Redmond, Washington campus. He has worked on various Microsoft products, including Internet Explorer and MSN Search. Dr. McCaffrey is the author of .NET Test Automation Recipes (Apress, 2006) and can be reached at [email protected]

Thanks to the following Microsoft technical experts for reviewing this article: Paul Koch, Dan Liebling, Anne Loomis Thompson other Shane Williams