Tuesday: more reading on PSO …

1. Continuing from yesterday’s notes on particle swarm optimisation, more notes from the Adaptive View’s webpage on PSO (http://www.adaptiveview.com/articles/ipsoprnt.html):
   1. N. B. unlike the model Heppner use, the concept of “neighbour” in PSO has nothing to do with the individual’s proximity in solution space. Memberships are defined before the particles begin the search. The analogy is given that when people visit a foreign country, those people who live near them at home are, and remain, their neighbours. This means that searches ” within a neighbourhood” can take place in distant areas of the solution space.
   2. Instead of believing the individual particles are intelligent, it’s more accurate to think of them as brainless specks that fly through the court notes of an n.-dimensional space.
   3. As particles move, they send their coordinates to a function that applies them to the problem and measure their fitness — how close to a better solution for the problem is the result produced by the coordinates.
   4. A particle remembers its current coordinates, its velocity — and how fast it is moving along dimensions of the solution space — the best fitness value it received so far, and the coordinates that value was computed from. It is this personal best combined with its neighbourhood’s best that influences where the particle moves to through the solution space. (So how its velocity and direction along each dimension of the solution space will be altered each time it moves)
   5. The solution space has one or more dimensions matching the number of variables, or unknown is, in the problem.
   6. The solution space for the function 5x^2 + 2y^3-(z/w)^2 + 4 will be four dimensional, as there are four unknowns, XYZ and W. therefore a particles location in the problem solution space is defined by four coordinates.
   7. The PSO algorithm has no difficulty working in multiple dimensions: if you have 50 variables, PSO has no problems dealing with a 50 dimensional solution space, and doesn’t need any modification to do so.
   8. (JE — this paragraph is a little confused but I will give it a go anyway…) The evaluation of a function representing the problem is of no consequence to the PSO algorithm, or the particles. So if you are looking for a solution to the above formula equal to 0 — i.e. what are the values of XYZ and W when 5x^2 + 2y^3-(z/w)^2 + 4 = 0. A particle calling the fitness function from the coordinates x=3, y=3, z=8 and w=1 does not need to know that the function’s result is 39.
   9. What’s needed is an indication of how good (fitness) the answer is relative to the optimum (a value you define).
   10. The fitness function calculates the fitness value, and this is of significance, but only to the extent that the PSO algorithm can use it to accurately and consistently compare the relative fitness of any to coordinates sets, in order to determine neighbourhood and particle bests.
   11. Using the above example, and assuming that your optimum is zero and the PSO algorithm is set up to rank higher fitness values as better, the fitness function could return zero minus the absolute value of the answer (0 – abs(39) = -39).
   12. (JE — I’ve missed out the pseudocode for a PSO algorithm…)
   13. The PSO algorithm is not very complex. However, the algorithm is really a recipe for complexity. There are two essential ingredients for complexity, effective connections between things, and some chaos. The PSO algorithm has both. The algorithm connects particles and the behaviour of particles through the implementation of neighbourhoods and the inclusion of the neighbourhood-best fitness in the factors that determine how a particle will move. As for chaos, it uses randomly altered weights to keep the particles individuality and sociality traits from getting stuck in a rut. Coding of the PSO algorithm keeps the effects of the randomised weight within a certain range.
   14. (JE — the remainder of the article has comments on the emergence of intelligence, has a balance between sociality and individuality. I’ll leave it for the time being…)

From this page http://upetd.up.ac.za/thesis/available/etd-01312006-125743/, I’m not sure that there is anything of particular value at this point in time — it’s somebody’s MSc dissertation on comparing particle swarm optimisations. However it may be worthwhile coming and having a look at this at a later point when I know a bit more about the subject.

N.b. when you go to Reading campus next, remember to look at this book: Swarm Intelligence, by James Kennedy and Eberhart, http://www.amazon.co.uk/Swarm-Intelligence-Morgan-Kaufmann-Artificial/dp/1558605959/ref=pd_bbs_sr_2/202-1990616-4089405?ie=UTF8&s=books&qid=1176824192&sr=8-2

1. Notes from swarmintelligence.org’s tutorial page (http://www.swarmintelligence.org/tutorials.php):
   1. PSO has many similarities with other evolutionary computation techniques such as genetic algorithms.
   2. In PSO the potential solutions, call particles, fly through the problem space by following the current optimum particles.
   3. Compare to genetic algorithms, PSO is easy to implement and few parameters to adjust.
   4. PSO has been successfully applied in many areas: function optimisation, artificial neural networks training, fuzzy system control, and other areas where genetic algorithms can be applied.
   5. From the article, artificial life either studies how computational techniques can help when studying biological phenomena, or artificial life studies how biological techniques can help out with computational problems. PSO deals with the second of these two options.
   6. With PSO, we are discussing social biological systems, specifically the collective behaviours of simple individuals interacting with their environment and each other.
   7. Simulations in this area utilise local processes, such as those modelled by cellular automata, and might underlie the unpredictable group dynamics of social behaviour.
   8. The article does mention boids, but also mentions something I haven’t come across before, something called floys. These seem to be boids but ones which are territorial, and aggressive to strangers who wander into their territorials. See http://www.aridolan.com/ for more information
   9. Ant colony optimisation (ACO) is related to PSO, inspired by the behaviour of ants, and as many successful applications in discrete optimisation problems (http://iridia.ulb.ac.be/~mdorigo/ACO/ACO.html)
   10. The particle swarm concept originated as a simulation of simplified social system. The original intent was to graphically simulate the choreography of a bird flock to fish school — however it was found a particle swarm model can be used as an optimiser. (See the original Kennedy and Eberhart paper for more details)

That’s where I’ve got to with today’s reading. Tomorrow I want to have a look at the section of this page, the third section entitled “The algorithm”.

Saturday night: conversations with a biologist…

As a quick reminder to myself, on Saturday I went for a drink with a friend of mine who is now studying for a PhD at the University of Cambridge.  He is a biologist, interested in DNA repair.  Interestingly it seemed that he is interested in emergent behaviour — the situation as I understand it is described below:

DNA is under permanent attack/degradation, and needs to be permanently and actively repaired.  Now what seems to happen, is that proteins in the cell notice that particular portion of DNA requires repairing.  These proteins (I’m assuming) spot an issue with DNA, and then move to begin repairing process.  This appears to trigger a cascading process, in which as one protein moves to carry out repair, other proteins follow: before long, a congregation of proteins appears at the site of DNA damage, and repair processes take place.

Now my friend was interested in how this emergent behaviour occurs.  Although I appreciate I’m only on day two of learning about particle swarm optimisation, and on Saturday I was on day -2, this seems to be a similar situation to how birds look for a roosting spot.  A.k.a. the work done by Frank Heppner.

Needless to say, I’ll keep my eyes open, in case anything I come across can also assist my friend, and the area of DNA repair.

Monday: Reading into particle swarm optimisation…

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:

• there is a Perl PSO module: http://search.cpan.org/~kylesch/AI-PSO-0.86/lib/AI/PSO.pm
• there appears to be a good online visual demonstration here: http://gecco.org.chemie.uni-frankfurt.de/PsoVis/applet.html
• …  And another, probably slightly easier to grok, online applet here: http://www.projectcomputing.com/resources/psovis/.

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:

• http://www.adaptiveview.com/articles/ipsoprnt.html
• http://upetd.up.ac.za/thesis/available/etd-01312006-125743/
• http://isbn.nu/1558605959 – book
• http://www.swarmintelligence.org/tutorials.php
• http://www.engr.iupui.edu/~shi/Coference/psopap4.html — this is the paper by Kennedy and Eberhart behind particle swarm optimisation

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…

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:

• there is a Perl PSO module: http://search.cpan.org/~kylesch/AI-PSO-0.86/lib/AI/PSO.pm
• there appears to be a good online visual demonstration here: http://gecco.org.chemie.uni-frankfurt.de/PsoVis/applet.html
• …  And another, probably slightly easier to grok, online applet here: http://www.projectcomputing.com/resources/psovis/.

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:

• http://www.adaptiveview.com/articles/ipsoprnt.html
• http://upetd.up.ac.za/thesis/available/etd-01312006-125743/
• http://isbn.nu/1558605959 – book
• http://www.swarmintelligence.org/tutorials.php
• http://www.engr.iupui.edu/~shi/Coference/psopap4.html — this is the paper by Kennedy and Eberhart behind particle swarm optimisation

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…

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.

Friday: so what is this velocity coordinate then?…

After examining yesterday’s results in SAS, the data outputted by the simulation produced tuples of coordinates that represented a particular velocity, eg [20 30 40].  However, I must admit I was a bit confused what this number represented.  As such today I’ve been at the University of Hertfordshire’s library, looking through a number of programming games in 3-D books.  As such the notes from which are below:

• From Beginning Math and Physics for Game Programmers, by Wendy Stahler:
• In one dimensions, velocity is a positive or negative number where a sign indicates the direction required.
• In two dimensions: displacement equals the final minus initial positions
• n.b. vectors need to be in component form before they can be subtracted: distance in the x direction and distance in the y direction
• for a diagram of this, see your notes on the 13th of April 2007
• *velocity is displacement divided by time
• n.b. polar coordinates like 10 m per second at 53°, whereas Cartesian coordinates like [ 6 8 ] represent a vector, where 6 and 8 represent the x and y coordinates of the vector respectively
• The x component is equal to the magnitude multiplied by the angle’s cosine
• The y component is equal to the magnitude multiplied by the angle’s sine
• from Beginning 3-D Game Programming by Tom Miller:
• again, see your notes the 13th of April 2007 for a figure indicating the difference between two different vectors
• vectors measure both direction and velocity
• most times a vector is defined as a free vector, which is when the root of the vecto is at the  origin
• and therefore the arrowhead in the figure in your notebook indicates the [x,y,z]  vector value
• drawing a line between this point in the origin therefore leads to the direction and the velocity of the two points
• nb vectors do not need to be rooted at the origin, but it makes calculations easier
• to calculate the velocity of a vector when you know the arrowhead coordinates, the length of the vector is equal to the square root of (x coordinate squared, + y coordinate squared, + z coordinate squared) — again see your notes for the written equation
•  a normalised vector, otherwise known as unit vector, is a vector with a length equal to one: this means you can store direction without regard to the velocity
• to calculate the normalised version of a vector, take each vector component and divide by the vector length
• e.g. with a free vector of (23, 18, 7) the length this vector is approx 30 .0333
• dividing each component by this number leads to a new vector with coordinates: (0.77, 0.60, 0.23): the length of this vector was approximately one, which is expected
• from 3-D Game Programming with C++by John De Goes
• you can describe the position of a three-dimensional object that is moving in a straight line by using its initial velocity, its initial position and its acceleration. Equation:
• P(t) = P(0) – V(0)t + 1/2at^2, where:
• P(t) point of the object
• P(0) initial position
• V(O) initial velocity
• a acceleration
• t time
• this can be expressed equivalently for the x, y, z coordinates:
• Px = P(x0) – V(x0)t + 1/2axt^2
• Py = P(y0) – V(y0)t + 1/2ayt^2
• Pz = P(z0) – V(z0)t + 1/2azt^2
• this equation can also be useful:
• V = V0 + at
• Game Physics by David H Eberly
• looked interesting but probably a little bit too much at this point
• websites of interest:
• gamedev.net
• gamasutra.com

No doubt more will follow, and hopefully tomorrow will have the opportunity to do a bit more investigation in this area. 

Thursday: more SAS action, calculating distances between flock members…

After yesterday’s introduction to SAS,today has been spent trying to work out how to calculate the distances between flock members.  Fundamentally flocks are supposed to, well, flock together.  As such, those flocks which have a small distance between their members should indicate that the flock is actually quite cohesive and is well joined from one another.

So far today I’ve worked out how to calculate the distance between a flock member and each other flock member, per timestep.  The following code below is the SAS syntax required to produce the correct output:

proc sql;
    /*input BOID RADIUS TIMESTEP X_POS Y_POS Z_POS VEL_X VEL_Y VEL_Z;*/
    create table Result as
    select     a.BOID         as FirstAgent,
            b.BOID        as SecondAgent,
            a.TIMESTEP    as FirstTimeStep,
            b.TIMESTEP    as SecondTimeStep,
            a.X_POS – b.X_POS    as X_Diff,
            a.Y_POS – b.Y_POS    as Y_Diff,
            a.Z_POS – b.Z_POS    as Z_Diff
    from     boids a, boids b
    /*where    a.BOID lt b.BOID and a.TIMESTEP lt b.TIMESTEP*/
    where    a.BOID lt b.BOID
    and     b.TIMESTEP = a.TIMESTEP + 1
    /*order by a.BOID, b.BOID, a.TIMESTEP, b.TIMESTEP*/
    /*order by a.BOID, a.TIMESTEP*/
    order by a.BOID, a.TIMESTEP
    ;
    quit;

proc print data=Result;
run;

To calculate the hypotenuse between each of the agents, now to be fairly basic to complete, working on the progress made yesterday. From looking at the results I generated on Tuesday from the simulation, I’ve got the following initial results:

Boid Radius Setting               Mean Distance btw Boids
          5.0                                       0.42
          1.0                                       0.44
          0.1                                       0.48

So this does match the hypothesis: as the boid radius parameter, which effectively dictates how far a bird can see,is increased, this means that particular birds can see farther, and hence join up with more distant flocks, the mean distance between flock members reduces.

This seems to be a way to work out the cohesiveness of the flock: I’m aiming to do a report on particle swarm optimisation starting next week, so I’ll look to see if there is anything in the literature on the measurement of cohesiveness in groups.  The next problem I need to solve, is how to measurethe degree of polarisation within the flock.  From the simulation I’m running, I have managed to extract velocity data — I now just need to turn this into useful information, in a bid to trying to do something about the state of the flock.

This is a testof Dragon NaturallySpeaking…

Well, I must admit I finally splashed out, and treated myself to a copy of Dragon NaturallySpeaking.  This is its maiden voyage in my blogging application Flock, just to see how well it will perform under the daily stresses of having to listen to my dulcet tones. So far, it appears to be performing pretty well, but I think the real test will be in the future.

it does seem to be a little bit jumpy, and I can see my CPU going all over the place, I suppose this is very processor intensive programme. it seems the programme caches what you’ve just said, and picks a quiet moment when it can compute what you said, and then turn what you dictated into text.

Now it seems like there will be a certain amount of learning, associated with this particular program, but I think it will actually pay dividends in the future when I have it sussed.

Wednesday: analysing the results …

Today starting to use SAS to analyse what I extracted from the simulation yesterday. Today is probably going to be a case of trying to get the data into SAS, and then just starting to work out how to use the program.

NB would measuring the polarity of the group be a useful measure?

Okay, first issue: SAS doesn’t like Unix-style data files, with a \n line return character. This can be got round by using the Cygwin program unix2dos. It also appears that SAS is quite interesting when it comes to delimiters, so it may be an idea to use spaces ” ” as a delimiter. (Note to self: the find-replace in Notepad is horrifically slow — use Vim’s instead )

Now managed to get data into SAS — the following was used to import data (line numbers added by me, through HTML bullets):

1. data boids; /* this tells SAS a convenient name to use to refer to the data */
2. infile ‘path_to_data_file’;
3. input BOID RADIUS TIMESTEP X_POS Y_POS Z_POS; /* column headings */
4. proc print data=boids; /* print out the data */
5. run;

SQL in SAS seems to work pretty well also: replacing lines 4 & 5 above with

proc select * from boids (where BOID = 1)

… selects all of the data. The italicised suffix will select just the results for boid #1 — this is pretty awesome, I must say. So now to start working out the distances travelled by each boid. I have 3 coordinates for each boid, x, y, and z, so I’m going to work out the difference between two sets of coordinates — i.e. dx = x2 – x1, etc — then use Pythagoras to find h^2 = x^2 + y^2 + z^2.

After a number of hours searching, managed to work out how to work out differences between observations (SAS term for rows) in a column:

data sample;
input x;
cards;
12
15
17
18
13
;
run;

data two;
set sample;
ratio = x – lag(x);
run;

proc print data=two;
run;

The bits in the middle paragraph are the important ones, for the time being. Lag appears to a function of some importance, it seems. With a bit of playing, how to calculate the distance travelled by a bird, using Pythagoras, in SAS:

proc sql;
    create table boid1 as
    select     *
    from     boids
    where     BOID = 1;

data four;
set boid1;
h = sqrt(
        (X_POS – lag(X_POS)) * (X_POS – lag(X_POS)) +
        (Y_POS – lag(Y_POS)) * (Y_POS – lag(Y_POS)) +
        (Z_POS – lag(Z_POS)) * (Z_POS – lag(Z_POS))
        );
run;

proc print data=four;
run;

And this is how to calculate the mean distance travelled by the boid in question:

proc means data=four;
class boid;
var h;
run;

Just gone through the data in Excel, using functions I know (!), and the results come out the same, which is good. The next piece to do is to work out the mean distance travelled by all boids, at once, and not just one bird. How to do this then? Hmmm, I’m thinking of sorting the results by bird … or maybe grouping them through SQL? Anyway, this is the first post of today — expect another one later, as computer complaining about needing a reboot.

Tuesday: back from Prague, CVS-ing and re-coding …

Back from a friend’s weekend Stag-do in Prague over the bank holiday, and luckily only feeling slightly broken! Voice is a little sore, but nothing too pressing.

This week I’m aiming to get the 3D simulation of birds back up and running, where I can output the positions of birds into text files, then change flocking parameters, and do some analysis to see what differences the changes to parameters make. I also want to get a Subversion CVS up and running, to store all the code I use, so that working copies are effetively protected from my personal acts of idiocy!

As such, today’s aims are to:

• get a Subversion repository running*
• in a flash of inspiration (*cough*) how about looking to use the integration tools between Eclipse and Subversion … ? This should make life a lot easier over the future! For example, Subclipse
• get the Java simulation working again, and try to get the looping issue working as well
• just tried my original simulation with the “java -classpath .” trick, and the thing worked, saving me a bit of time

Now I seem to have got Subversion up and running — I think … I’ve got a lot of new and interesting symbols in Windows Explorer for a start.

The Java simulation I was working on before now appears to be working: I can output bird positional data from the simulation into a text file for analysis. Now the next part is to get the simulation to exit after a number of iterations — e.g. loop for 1000 timesteps then exit. Currently this does not appear to be working, using a break statement. I was having an issue in getting the timestep counter to increment correctly so added in a new public variable, which is the timestep counter: the develop of the simulation I’m using is using an Enumeration interface, which appears to only allow iterations over a set collection — I think it was this that was confusing me as to why the counters I’ve previously coded loop permenantly 1 -> 10, and then reset.

Okay, now got the simulation to exit after hit a magic number of iterations. Now wondering if I could get it to automatically change the key parameters automatically … e.g. change the bounding radius of each bird, run a simulation for n steps, increment the radius parameter, repeat … Would be a pretty neat way to generate a lot of data quickly.

14:42 Update: My Lords, Ladies, Gentlemen, Boys and Girls, we have an official Milestone alert: I’ve just created my first data set! 100,000 timesteps of 10 birds flying around, with  a boid radius of 0.1. Some stats:

• 100K timesteps takes about 10min to complete
• this produces a text file of 4MB in size

This does make me think I need to work out how to auto-increment the keys parameters: I can then leave the simulation running, and churning out data. More likely, as I have access to an old XP box, I can get the simulation up and running on that, and leave it churning away whilst I do other things on my laptop — e.g. reading, analysis, etc.

The snag with this is though that once the screen has been drawn, you have 10 birds with set qualities: e.g. their important parameters have been set. So this would surely mean that you need to wipe the simulation’s slate clean, so to speak and thinking out loud, using the new variable information? So let’s think this through:

1. Set the initial parameter under test
2. Run the simulation for a set number of timesteps
3. When the max. timesteps is reached, stop:
1. change the parameter settings
2. clear the simulation of the current birds
3. redraw the birds, setting their behaviour as per 3.1 above
4. Run the simulation again.
5. Repeat until the maximum setting of the parameter under test is reached.

Interestingly, in the Flocking3D class on line 82 there’s a line that says to create a new WrapFlocking3D class: this latter class seems to be the one that adds all the information into the simulation scene. So you would need someway of killing off the first WrapFlocking3D class and then redraw it …. Hmm, interesting problem — but aren’t they all?!? ;-)

Haha, just set up old XP boxen to find I can’t remember the password … dang. There are workarounds which I shall put into place, however …. But whilst I’m working on that, it might be a good idea to start looking at the data I have now in my possesssion. To repeat, I have a 4MB file of positional data for 10 birds with a boundary radius parameter of 0.1f — so this is the equivalent of 10 birds moving around for 10,000 discrete time intervals (100K / 10). To begin I’ll start off with working with a small data set, of 100 discrete time intervals (1000 timsteps) — now the first question is, what do I want to measure?

Let’s just think of one bird for a moment: what would be good to measure? Some ideas:

• total distance travelled
• distance compared to others

However, this shall be left alone for today, and picked up tomorrow — until then!!