Tuesday: spreadsheet analysis of velocity data…

Today I’m back on the case what to do regarding the velocity of the individual birds.  I have put the data into a spreadsheet,  and then now comparing the velocities for the x axes, for individual birds and the flock as a whole.

Now interestingly, the flock velocity differs for each bird.  For one bird the flock velocity might be about 0.1, but other’s it’s about -0.004.  I’m wondering out loud whether this because from each bird’s perspective, the flock velocity is going to be different.  If a particular bird is high on the x axis, the velocity of the flock is going to appear different to this bird down to how it will appear to a bird low on the same axis…  Surely?

I’ve done some playing around a spreadsheet with a piece of the data, and it’s not quite clicking with me yet.  (Today has been a balls up regarding time management…) However I do think I am a bit closer, I will pick up a spreadsheet analysis again tomorrow.

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.