Jon’s PhD Journal

April 16, 2007

Monday: Reading into particle swarm optimisation…

Filed under: Notes — JDE @ 12:54 pm

Today I’m starting on the next report topic, which is particle swarm optimisation.  To begin with I’m going to have an initial glance around the Internet, just to try and whet my feet as to what the subject is about.

  1. From www.swarmintelligence.org:
    1. “Particle swarm optimization (PSO) is a population based stochastic optimization technique developed by Dr. Eberhart and Dr. Kennedy in 1995, inspired by social behavior of bird flocking or fish schooling.”.
    2. PSO is apparently quite similar to genetic algorithms and other evolutionary computation techniques.
    3. The system starts with a population of random solutions, and the optima is searched for by updating generations.
    4. In PSO the potential solutions are called particles, which fly through the problem space by following the current optimum particles.
    5. Each particle keep track of it is coordinates in the problem space which are associated with the best solution (fitness) it has achieved so far (the fitness value is also stored).  This value is called pbest.
    6. The best value obtained so far by any particle in the neighbours of the particle is called lbest
    7. If the particle takes the entire population as its topological neighbourhood, the best value is a global best and is called gbest
    8. At each time step, the particle swarm optimisation concept involve changing the velocity of (accelerating) each particle towards its pbest and lbest locations (local version of PSO).
    9.     Acceleration is weighted by a random term, with separate random numbers being generated for acceleration towards pbest and lbest locations.
    10. PSO is attractive because there are few parameters to adjust

There’s a tutorial page on this website as well: http://www.swarmintelligence.org/tutorials.php, which seems reasonable.

Some quick points:

  1. And from the Wikipedia entry on particle swarm optimisation, the following:
    1. PSO is a form of swarm intelligence
    2. if you imagine a swarm of insects, and one sees a desirable path to go in, such as food protection etc, the rest of the swarm will be able to follow quickly even if they are on the opposite side of the swarm.
    3. However you want each particle to have a certain amount randomness inherent to their character, so that the swarm has a certain exploration capability: the swarm shall be influenced by the rest of the swarm will also should independently explore to a certain extent (this is a manifestation of the basic exploration-exploitation trade off that occurs in any search problem)
    4. the search is modelled by particles in multi dimensional space that have a position on a velocity.  These particles are flying through hyperspace and have two essential reasoning capabilities: their memory of their own best position and knowledge of the swarm’s best — “best” in this sense simply means the position with the smallest objective value.
    5. Members of the swarm communicate good positions to each other and adjust their own position and velocity based on this good positions.  Communication is done in two ways:
    6.     a global best is known to all and immediately updated when a new best position is found by any particle in the swarm   
    7.     “neighbourhood” bests where each particle only immediately communicates with a subset of the swarm about best positions
    8. (FYI the Wikipedia entry contains a basic PSO algorithm for further inspection)
    9. from the discussion section of the article: “By studying this algorithm, we see that we are essentially carrying out something like a discrete-time simulation where each iteration of it represents a “tic” of time. The particles “communicate” information they find about each other by updating their velocities in terms of local and global bests; when a new best is found, the particles will change their positions accordingly so that the new information is “broadcast” to the swarm. The particles are always drawn back both to their own personal best positions and also to the best position of the entire swarm. They also have stochastic exploration capability via the use of the random multipliers r1,r2.”

(N. B. Firefox has died on me a couple of times today: as such here are the URLs I was looking at in case of emergencies:

  1. From Adaptive View’s an Introduction to Particle Swarm Optimisation article:
    1. the original developers of particle swarm optimisation, Kennedy and Eberhart, were interested in models developed by biologist Frank Heppner.
    2. Heppner’s bird models demonstrating most of the flocking behaviours that other models were producing, but with the addition that his birds were attracted to a roosting area.
    3. In simulations the birds would fly around in flocks with no particular destination until one of the birds flew over the roosting area.
    4. When the programmed ” desire to roost” parameter was higher than the “desire to stay in the flock”, a bird would pull away from the flock and land.
    5. The birds use simple rules to set their direction and velocity — basically each bird is trying to stay in the middle of the birds it is near to while trying not to run into any of them — and as such, a bird pulling away from the flock in order to land at the roosting site would result in nearby birds moving towards the roost.
    6. As these birds discovered the roost, they would land, in turn pulling more birds towards the roosting site, and so on until the entire flock had landed.
    7. Eberhart was an electrical engineer, and Kennedy was a social psychologist
    8. in particle swarm optimisation, finding a roost is analogous to finding a solution in a field of possible solutions, sometimes called a solution space, and the manner in which a bird who has found the roost “leads ” its neighbours toward it, increasing the odds are that they will also find it, is in keeping with the socio-cognitive of mind.
    9. Eberhart and Kennedy mortified Heppner’s simulation so that particles could fly over a simulation space and land on the best solution.
    10. An issue in this area is how to keep the particles from landing on any solution instead of just the best solution.  This is where the social aspect of mind and intelligence comes into play.  The essence of the “mindless social” viewpoint is that individuals learn primarily from the successes of their neighbours.
    11. PSO requires a good balance between exploration, hunting around for good solution, and exploitation, taking advantage of someone else’s success.  Too little exploration will lead the particles to converge on the first good solution encountered.  Too little exploitation and the particles will never converge.
    12. Another way of looking at this, is that instead of balancing the exploration and exploitation behaviours, is balancing individuality and sociality.  Ideally you want individuals to prefer being individualistic, akin to Heppner’s birds not wanting to run into each other, but you want them to know where good solutions have been found by others that they can “learn from what they did”.
    13. A subtle aspect of finding the best solution has to do with which particle is in a particular neighbourhood, and whose successes will influence surrounding particles.  A “global neighbourhood” with all the particles acting as one large neighbourhood increases the odds that a sub optimal solution will be converged on the certain types of problems.  Kennedy and Eberhart discovered that using smaller, overlapping neighbourhoods was often more effective.
    14. E.g. given seven particles A., B., C., D., E., F., and G.: instead of them all belonging to the neighbourhood ABCDEF more of the solution space may be searched by having neighbourhoods GAB, ABC, BCD, CDE, DEF, EFG, and FGA, with the particle the range in a circle, so G. and A. are next to each other, and each particle includes the particles on its left and right as its neighbourhood.  Using such a neighbourhood apology tend to delay convergence and therefore allow more exploration
    15. using the above example, particle A’s neighbours are G. and B. If either of these two neighbours find a better solution than A has, A will be influenced by this — it will, so to speak, arrive at a compromise between where it wants to go and where the neighbourhood best is located.  At the same time, G and B have their own neighbourhoods (FGA and ABC) and will be hence moving under the influence of their neighbourhood bests.
    16. This method serves to slowly propagate the global best solution to all of the neighbourhoods.  However significant here is the propagation taking time.  During this propagation time, members of the still unaffected neighbourhoods continue to hunt in their area the solution space following the scent of what they think is best.  This increases the odds that if there is a new global best solution near or between them, they’ll find it.

(Got down to where “important” is in bold, ~1/3 of the page down)

Monday: Reading into particle swarm optimisation…

Filed under: Notes — JDE @ 12:54 pm

Today I’m starting on the next report topic, which is particle swarm optimisation.  To begin with I’m going to have an initial glance around the Internet, just to try and whet my feet as to what the subject is about.

  1. From www.swarmintelligence.org:
    1. “Particle swarm optimization (PSO) is a population based stochastic optimization technique developed by Dr. Eberhart and Dr. Kennedy in 1995, inspired by social behavior of bird flocking or fish schooling.”.
    2. PSO is apparently quite similar to genetic algorithms and other evolutionary computation techniques.
    3. The system starts with a population of random solutions, and the optima is searched for by updating generations.
    4. In PSO the potential solutions are called particles, which fly through the problem space by following the current optimum particles.
    5. Each particle keep track of it is coordinates in the problem space which are associated with the best solution (fitness) it has achieved so far (the fitness value is also stored).  This value is called pbest.
    6. The best value obtained so far by any particle in the neighbours of the particle is called lbest
    7. If the particle takes the entire population as its topological neighbourhood, the best value is a global best and is called gbest
    8. At each time step, the particle swarm optimisation concept involve changing the velocity of (accelerating) each particle towards its pbest and lbest locations (local version of PSO).
    9.     Acceleration is weighted by a random term, with separate random numbers being generated for acceleration towards pbest and lbest locations.
    10. PSO is attractive because there are few parameters to adjust

There’s a tutorial page on this website as well: http://www.swarmintelligence.org/tutorials.php, which seems reasonable.

Some quick points:

  1. And from the Wikipedia entry on particle swarm optimisation, the following:
    1. PSO is a form of swarm intelligence
    2. if you imagine a swarm of insects, and one sees a desirable path to go in, such as food protection etc, the rest of the swarm will be able to follow quickly even if they are on the opposite side of the swarm.
    3. However you want each particle to have a certain amount randomness inherent to their character, so that the swarm has a certain exploration capability: the swarm shall be influenced by the rest of the swarm will also should independently explore to a certain extent (this is a manifestation of the basic exploration-exploitation trade off that occurs in any search problem)
    4. the search is modelled by particles in multi dimensional space that have a position on a velocity.  These particles are flying through hyperspace and have two essential reasoning capabilities: their memory of their own best position and knowledge of the swarm’s best — “best” in this sense simply means the position with the smallest objective value.
    5. Members of the swarm communicate good positions to each other and adjust their own position and velocity based on this good positions.  Communication is done in two ways:
    6.     a global best is known to all and immediately updated when a new best position is found by any particle in the swarm   
    7.     “neighbourhood” bests where each particle only immediately communicates with a subset of the swarm about best positions
    8. (FYI the Wikipedia entry contains a basic PSO algorithm for further inspection)
    9. from the discussion section of the article: “By studying this algorithm, we see that we are essentially carrying out something like a discrete-time simulation where each iteration of it represents a “tic” of time. The particles “communicate” information they find about each other by updating their velocities in terms of local and global bests; when a new best is found, the particles will change their positions accordingly so that the new information is “broadcast” to the swarm. The particles are always drawn back both to their own personal best positions and also to the best position of the entire swarm. They also have stochastic exploration capability via the use of the random multipliers r1,r2.”

(N. B. Firefox has died on me a couple of times today: as such here are the URLs I was looking at in case of emergencies:

  1. From Adaptive View’s an Introduction to Particle Swarm Optimisation article:
    1. the original developers of particle swarm optimisation, Kennedy and Eberhart, were interested in models developed by biologist Frank Heppner.
    2. Heppner’s bird models demonstrating most of the flocking behaviours that other models were producing, but with the addition that his birds were attracted to a roosting area.
    3. In simulations the birds would fly around in flocks with no particular destination until one of the birds flew over the roosting area.
    4. When the programmed ” desire to roost” parameter was higher than the “desire to stay in the flock”, a bird would pull away from the flock and land.
    5. The birds use simple rules to set their direction and velocity — basically each bird is trying to stay in the middle of the birds it is near to while trying not to run into any of them — and as such, a bird pulling away from the flock in order to land at the roosting site would result in nearby birds moving towards the roost.
    6. As these birds discovered the roost, they would land, in turn pulling more birds towards the roosting site, and so on until the entire flock had landed.
    7. Eberhart was an electrical engineer, and Kennedy was a social psychologist
    8. in particle swarm optimisation, finding a roost is analogous to finding a solution in a field of possible solutions, sometimes called a solution space, and the manner in which a bird who has found the roost “leads ” its neighbours toward it, increasing the odds are that they will also find it, is in keeping with the socio-cognitive of mind.
    9. Eberhart and Kennedy mortified Heppner’s simulation so that particles could fly over a simulation space and land on the best solution.
    10. An issue in this area is how to keep the particles from landing on any solution instead of just the best solution.  This is where the social aspect of mind and intelligence comes into play.  The essence of the “mindless social” viewpoint is that individuals learn primarily from the successes of their neighbours.
    11. PSO requires a good balance between exploration, hunting around for good solution, and exploitation, taking advantage of someone else’s success.  Too little exploration will lead the particles to converge on the first good solution encountered.  Too little exploitation and the particles will never converge.
    12. Another way of looking at this, is that instead of balancing the exploration and exploitation behaviours, is balancing individuality and sociality.  Ideally you want individuals to prefer being individualistic, akin to Heppner’s birds not wanting to run into each other, but you want them to know where good solutions have been found by others that they can “learn from what they did”.
    13. A subtle aspect of finding the best solution has to do with which particle is in a particular neighbourhood, and whose successes will influence surrounding particles.  A “global neighbourhood” with all the particles acting as one large neighbourhood increases the odds that a sub optimal solution will be converged on the certain types of problems.  Kennedy and Eberhart discovered that using smaller, overlapping neighbourhoods was often more effective.
    14. E.g. given seven particles A., B., C., D., E., F., and G.: instead of them all belonging to the neighbourhood ABCDEF more of the solution space may be searched by having neighbourhoods GAB, ABC, BCD, CDE, DEF, EFG, and FGA, with the particle the range in a circle, so G. and A. are next to each other, and each particle includes the particles on its left and right as its neighbourhood.  Using such a neighbourhood apology tend to delay convergence and therefore allow more exploration
    15. using the above example, particle A’s neighbours are G. and B. If either of these two neighbours find a better solution than A has, A will be influenced by this — it will, so to speak, arrive at a compromise between where it wants to go and where the neighbourhood best is located.  At the same time, G and B have their own neighbourhoods (FGA and ABC) and will be hence moving under the influence of their neighbourhood bests.
    16. This method serves to slowly propagate the global best solution to all of the neighbourhoods.  However significant here is the propagation taking time.  During this propagation time, members of the still unaffected neighbourhoods continue to hunt in their area the solution space following the scent of what they think is best.  This increases the odds that if there is a new global best solution near or between them, they’ll find it.

(Got down to where “important” is in bold, ~1/3 of the page down)

Monday: more work on the vector coordinate figures…

Filed under: Coding — JDE @ 11:01 am

Following Friday’s lesson on what vector coordinates really mean, today I’m having a little more of a look through the literature to see what people who have explained the model in the past reckoned the vector figures represent.  (Dictating with a cold today, so it’s going to be interesting to see how Dragon performs)

I suppose understand a little more about the vector quantity is using the simulation.  All they free vectors, with all vectors measured from the origin?  Are they normalised vectors, or with a length equal to one?  Or are they an additional type of vector?

From Conrad Parker’s boid page (http://www.vergenet.net/%7Econrad/boids/pseudocode.html), he interprets “the velocity as how far the boid moves per time step”.

(N.b. Parker also has a section on the bounding the position of the flock, to keep the flock within a certain area)

From Computer Graphics, 21(4), July 1987, pp. 25-34., Craig W. Reynolds,  “velocity is a vector quantity, referring to the combination of heading and speed.”  — which is something I already knew.

From looking at the data, examples of which are below, the figures involved are very small (I have no idea how the formatting is going to come out below, btw …):

   Obs   Bird_ID   Radius   Timestep    B_Vel_x    B_Vel_y    B_Vel_z   F_Vel_x   F_Vel_y   F_Vel_z
    1094     0       0.3      910     0.47887   0.02008  -0.02601   0.095783   0.003826  -0.005201
    1095     1       0.3      911    -0.01961  -0.09468  -0.47016  -0.004031  -0.018935  -0.094028
    1096     2       0.3      912    -0.09798   0.10306  -0.01509   0.000000   0.000000   0.000000
    1097     3       0.3      913     0.47946  -0.01399  -0.01719   0.095913  -0.001879  -0.003627
    1098     4       0.3      914    -0.02006  -0.09467  -0.47014  -0.003922  -0.018935  -0.094032
    1099     5       0.3      915    -0.05677  -0.16655  -0.18719   0.000000   0.000000   0.000000
    1100     6       0.3      916     0.47891   0.01929  -0.02601   0.095775   0.004017  -0.005201
    1101     7       0.3      917    -0.12513  -0.01598   0.10526   0.000000   0.000000   0.000000
    1102     8       0.3      918     0.47955  -0.01016  -0.01798   0.095892  -0.002797  -0.003438
    1103     9       0.3      919     0.18955   0.05836   0.09798   0.000000   0.000000   0.000000
    1104     .        .         .      .         .         .         .          .          .
    1105     .        .         .      .         .         .         .          .          .
    1106     0       0.3      920     0.47888   0.01995  -0.02601   0.095781   0.003858  -0.005201
    1107     1       0.3      921    -0.01969  -0.09468  -0.47016  -0.004013  -0.018935  -0.094029
    1108     2       0.3      922    -0.09798   0.10306  -0.01509   0.000000   0.000000   0.000000
    1109     3       0.3      923     0.47950  -0.01335  -0.01732   0.095910  -0.002032  -0.003595
    1110     4       0.3      924    -0.02000  -0.09467  -0.47015  -0.003937  -0.018935  -0.094032
    1111     5       0.3      925    -0.05677  -0.16655  -0.18719   0.000000   0.000000   0.000000
    1112     6       0.3      926     0.47890   0.01940  -0.02601   0.095776   0.003990  -0.005201
    1113     7       0.3      927    -0.12513  -0.01598   0.10526   0.000000   0.000000   0.000000
    1114     8       0.3      928     0.47955  -0.01069  -0.01787   0.095901  -0.002670  -0.003465
    1115     9       0.3      929     0.18955   0.05836   0.09798   0.000000   0.000000   0.000000

…  Where the figures that begin with ” B” are velocities of individual birds, and those that begin with a “F.” are relevant to the flock as a separate entity.  From looking at the data, the differences between velocity values are very small for each bird.

Now incredibly, open office does not have a text columns function built in.  As such I attempted to download one from the Internet and install it, but it doesn’t appear to have turned up yet.  However the plan of attack was to basically average all of the velocities of individual birds in one particular dimension — e.g. b_vel_x — for 10 time steps.  After that compare each bird velocity against the calculated average, and see if this would reveal anything.  However I think this is one  to try tomorrow, as today’s time is up and I’m going to start researching into particle swarm optimisation.

Blog at WordPress.com.