Notes from meeting with Will, 26 April (F2F @ Reading) …

Firstly some quick notes from meeting with Will, before I move into the feedback I received about my Complexity Theory report:

• With 3-D coordinates, the Z coordinate is usually the vertical axis
• always run things 10 times to be statistically reliable
• when creating new reports, papers, reviews, etc, feel free to put drafts onto the web, and that he will review it ahead of publishing
• everythingclassified.com did work on deep search
• stochastic diffusion search was a predecessor to PSO

Feedback on Complexity Theory report:

• Only report quotes, not sayings
• be careful of the word “famous” and other flowery terms
• triple check “it’s”: make sure the word is actually ownative
• when dealing with definitions, indent it as a separate entity (think of how definitions are laid out in Rui Mendes’ PhD thesis)
• check the tense of statements
• backup statements like “fail”: explain the logic behind these statements
• state things that could be seen as criticism blandly: get into the mindset of thinking that you refereeing instead of picking sites
• “results did not show understanding”…  Of what?
• Always try to be clear and concise
• cutout sayings such as “against the grain”, etc.  These sorts of things are fine if you are the expert in the field, but before then get the paper technical and clear first
• consistency with references: for example using the surname of one person throughout, as opposed using the first name and surname of an individual in certain locations.  Only change this if you have common names e.g. Smith
• increase the length of the background: why did the field start, when did it start, major milestones in the field, key researchers.  Keep this neutral, and keep the introduction neutral also
• in the discussion, compare and discuss: discuss the arguments here
• do not start sentences with conjunctions: “and”, “but”
• do not use words like “seems”, indeed, in fact: something like “considered” is better
• State the hard fact: then state the evidence
• remember to use ibid when quoting from the same source sequentially
• if you are going to use layman’s definitions, check that they are correct and cite them (tried to remember that when you cite a source, you are effectively passing the “blame” onto the source you are quoting: if what they’ve put is wrong, it’s their problem”
• instead of using “one returning thought ” use “one central theme “
• with section 3.3: why is emergence relevant?  The why part of this is not understood
• use “take note” or “it is noted” as opposed of pointed
• again ensure the validity of the statements, definitions of needlework
• make sure references are in the correct place throughout the document: ensure consistency when using them
• check for missing out nouns
• feel free to include diagrams, figures, images, etc, as long as you cite some
• use terminology along the lines of “it is considered/estimated” instead of “it is thought/guessed “
• don’t write “we” and “you”
• always question why what you’ve stated important/relevant
• use ” do not ” instead of “don’t”
• remove superfluous words
• remove “in fact”, “of course”, “on the other hand”, “as I was saying”
• footnote: use them where additional information would break the flow of an argument — not to explain the organisation of a paper or report
• do not use the word “apparently”
• in the conclusion clarify the first sentence
• do not use split infinitives: avoid ambiguity

Wednesday: looking at a flock’s polarisation …

Ok, it’s taken a while but I think we are finally there.  Following on from the SAS code documented yesterday, the outstanding task is to work out the standard deviation of the flock: this can be achieved through the means procedure, the syntax of which is as follows:

proc means data=boids;
var vel_atan_theta; * variable to run the calculations on;
run;

…  And this led me back to the actual data itself.I had run some simulations previously, adjusting the radius parameter of the birds each time, but I had not recorded the flock velocity information in this data, so would need to do them again.  As such, this in turn led me back to the simulation code itself.

After running a couple of simulations, changing the radius settings, I noticed that there didn’t appear to be any difference in what I was visually observing the simulation when I changed the radius setting.  As such, I start to look through the code in a little bit more detail.  Upon doing this, it dawned on me that the radius parameter actually has nothing to do with the flocking behaviour witnessed: from my reading a couple weeks ago in 3-D programming, it hit me that the radius parameter was actually there to be used in collision detection calculations — nothing to do with flocking per se.

As such the remainder of today was spent adjusting the simulation to be able to gather the parameters I think will be of value: namely the different weightings used in the flocking calculations (separation, alignment, cohesion), and the proximity parameter.  I also modified the simulation so that it is now toroidal.

Although I did spend some time messing around with what has proved to be a fruitless parameter setting, at least I now know more about the simulation, and have come up with a way of being able to measure the amount of polarisation in the flock.  I’ll pick this up again on Friday, as my daytrip to Reading campus. 

More Tuesday SAS-related notes …

Some additional quick points, namely the addresses of the websites which I gleaned the information to do this from:

• SAS: What You Need to Know to Write a SAS Program
• didn’t use but seems to go into more detail than the following 2
• Introduction To SAS
• logical operators, etc
• How to use SAS
• shows basic transformation of data — good starting point

Tuesday: SASing the polar coordinates …

Today some success with the conversion of Cartesian coordinates into polar coordinates in SAS.  Another short post today, but it appears all the transformation action takes place in the initial data step — the transformations I used in the first data step is as follows:

data boids;
infile ‘C:\tempy\boidposition_out.txt’;
input Bird_ID Radius Timestep
    B_Pos_x B_Pos_y B_Pos_z
    B_Vel_x B_Vel_y B_Vel_z
    F_Pos_x F_Pos_y F_Pos_z
    F_Vel_x F_Vel_y F_Vel_z
    ;

    vel_theta = b_vel_y/b_vel_x;
    vel_atan_theta = (atan(vel_theta) * (180/3.14));

    if (b_vel_x > 0) and (b_vel_y < 0) then vel_atan_theta = vel_atan_theta + 360;
    if (b_vel_x < 0) and (b_vel_y > 0) then vel_atan_theta = vel_atan_theta + 180;
    if (b_vel_x < 0) and (b_vel_y < 0) then vel_atan_theta = vel_atan_theta + 180;

This means on the initial data upload we create two new columns called vel_theta and vel_atan_theta. We then have three IF statements to modify the data as required.  This generates output with 17 columns of information.  The next stage is to calculate the standard deviation for the flock, based on the above syntax — and this will be tomorrow’s task!

Monday: understanding the PSO algorithm ….

A very quick post today, as time is short. From looking at some of the papers on particle swarm optimisation, I’m trying to understand exactly how the algorithm works.  I think that if I can pick up a copy of Swarm Intelligence from Reading library on Thursday, from what I gather on the Internet, that tome explains the algorithm in quite some detail.  Until that point, I have found the particle swarm optimisation algorithm written in Python — link.  This will give me the opportunity to have a look at how the algorithm works in more detail.   Also, the Perl implementation of particle swarm optimisation has quite a good write up on the download page in CPAN.

Friday: cracking the velocity issue…

Right, although no post yesterday, progress has been made on the velocity issue, namely converting Cartesian coordinates to polar coordinates.  (In all fairness, my memory is far rustier than I actually anticipated…) The plan of attack is as follows:

• Convert the Cartesian velocities into polar velocities, using theta = tan^-1(y/x) — this gives the result in radians, so remember to be convert into degrees.
• Once the polar velocities of the entire flock have been calculated, calculate the standard deviation for the flock.  Flock with a small standard deviation should indicate high polarisation amongst the flock: they should all be pointing in the same direction.

That’s the plan anyway.  It works in a spreadsheet practice run anyway — now the challenge is to get it to work in SAS!

Thursday: PSO reading and searching…

1. Today more reading about PSO.  I had a comment on my blog yesterday saying that the PSO journal I was reading, by Kennedy and Eberhart, is pretty old and recommended I go look at other papers.  As I’m going to quickly skim through the remainder, before looking at more recent articles:
1. (JE — it seems section 3.3 — 3.7 discuss how the final PSO algorithm came to be, and mentions other things that were tried and didn’t prove to be as successful.  Ergo, no notes)
2. Perhaps an interesting reference: Millonas, M. M. (1994). Swarms, phase transitions, and collective intelligence. In C. G. Langton, Ed., Artificial Life III. Addison Wesley, Reading, MA.
3. Conclusion
1. Interesting quote by the authors: “The authors of this paper are a social psychologist and an electrical engineer. The particle swarm optimizer serves both of these fields equally well. Why is social behavior so ubiquitous in the animal kingdom? Because it optimizes. What is a good way to solve engineering optimization problems? Modeling social behavior.”
2. PSO simple algorithm that seems effective for optimising a wide range of functions, that seems to exist between evolutionary search (takes long time) and neural processing (short timeframe)
3. PSO seems similar to both genetic algorithms and evolutionary programming: it’s highly dependent on stochastic processes like evolutionary programming; the adjustment towards pbest and gbest is conceptually similar to the crossover operations utilise by genetic algorithms; and the concept of fitness is used by all evolutionary computation paradigms.
4. PSO has a unique concept of potential solutions flying through hyperspace, accelerating toward better solutions
5. it appears that PSO solutions overshoot their targets, which introduces random exploration of the search space: this enables a thorough search of the space between regions that have been found to be relatively good

As such, time to do some more searching…

1. From a tipoff, the following webpages seem fruitful for PSO related information:

1. Rui Mendes (http://www.di.uminho.pt/~rcm/pubs.html)
2. Andries P. Engelbrecht (http://cirg.cs.up.ac.za/index.php), a few papers of which I had downloaded already
1.     also see this book, Fundamentals of Computational Swarm Intelligence (http://si.cs.up.ac.za/?page=about_author)
3. I’ve also had a look to see what conference papers are available as well, using this website: http://www.library.rdg.ac.uk/help/conferences/index.html.  I’ve saved the search results as text files on my computer for later analysis.  It’s been suggested that recent Congresses on Evolutionary Computation proceedings would be useful (checking GECCO proceedings would be quite useful as well I suspect)
4. this page could be useful as well: http://clerc.maurice.free.fr/pso/

Tomorrow the plan is to read through some of these, just to see what sort of topics they are covering.  The ones involving topologies look quite interesting, and it was interesting to note that someone has referenced Watt’s Small World Theory book. 

Wednesday: playing with vectors…

~~~~~~~~~~~~~~~~~~~~
Today more investigation around what the velocity data means.  (BTW I looked at the velocity data for one dimension last night: agreeing with my assumptions, the data proved not to be Gaussian)..

Now I’m thinking that the velocity should be related to how quickly a bird is moving in each time step.  From looking at the positional data generated by the simulation, I’ve spotted that if you take the positional data for one dimension at one time step, and the velocity data for one dimension at the same time step, and sum these, you get the positional data for this dimension at the next time step.  This is pretty obvious when you think about it, but I’ve only just noticed that this is what happens.

However, now I’m back to my original question: how do you calculate the polarisation of the flock as a whole?  Let’s imagine one axis for the time being: let’s say that this axis is that the x axis, running perfectly parallel to the floor.  A positive velocity would move something along the right of this axis; a negative velocity would move something in the opposite direction to the left.

Let’s say you have two agents, i and j.  i has a velocity of +1; j. has a velocity of +4. This means that the direction of their velocities is the say: they are both going to move towards the right-hand side of the axis.  However, the magnitude of i is four times greater than that of j.  So how do you compare their polarisation?  Surely it’s identical?

Now as a quick definition, I’m using polarisation here to describe whether the birds are pointing in the same direction or not.  In the above example of i and j., they are both moving the same direction: so I would describe their percentage polarisation as 0% — there’s no difference between them, as they are pointing in the same direction.  The only difference is the difference between magnitudes.

However, I think my notes that I took on Friday will come to the rescue here.  My vectors are not free vectors, in that they are not rooted at the origin.  Also they are not normalised/unit vectors, because from what I can tell they do not have a length equal to one: I’m working on this principle because all vectors are less than one.  From Friday’s notes, a unit vector is a vector with the length equal to one: it can store direction with out regard to the velocity, or should I say magnitude, of the vector.  And if I’m only dealing with unit vectors, surely these will be easier to compare…?

Needless to say, when I tried calculating the unit vectors of these, it didn’t quite work as I hoped… more tomorrow.

Wednesday: PSO reading …

1. Today, more reading about PSO — I’m continuing to look at swarmintelligence.org’s tutorial page (http://www.swarmintelligence.org/tutorials.php):
1. PSO simulate the behaviour of flocking birds.
2. Imagine the following scenario: group of birds randomly searching food in the area.  There is only one piece of food in the area being searched.  All the birds do not know where the food is.  But they know how far the food is in each iteration.  What is the best strategy to find food?  The effective solution is to follow the bird who is nearest to the food.
3. PSO took this imaginary scenario and used to solve the optimisation problems.  In PSO, each single solution is any “bird” in the search space, called a “particle”.
4. All particles have fitness values which are evaluated by the fitness function to be optimised, and have velocities which direct the flying the particle.
5. Particle fly through the problem space by following the current optimum particle.
6. PSO is initialised with a group of random particles, or solutions, and then searches for optima by updating generations.
7. In each iteration, each particle is updated by following 2 “best” values
8. The first of these values is the best solution (fitness) it has achieved so far (the fitness value is also stored) — this value is called pbest
9. The second “best” value that is tracked by the particle swarm optimiser is the best value, obtained so far by any particle in the population — this best value the global best, called that gbest.
10. When a particle takes part of the population as its topological neighbours, the best value as a local best and is called lbest.
11. After finding the two best values, the particle update its velocity and positions with the following two equations a/ and b/.
12. v[] = v[] + c1 * rand() * (pbest[] – present[]) + c2 * rand() * (gbest[] – present[]) (a)
13. present[] = present[] + v[] (b)
14. …  where v is the particle velocity, presence is the current particle (solution), pbest and bgest are defined as stated before, rand is a random number between zero and one, c1 and c2 learning factors, usually c1 = c2 = 2 (JE –?)
15. (JE — the article then contains pseudocode of the procedure, ignored for the time being)
16. Particles’ velocities on each by mention are clamped to a maximum velocity Vmax.  If the sum of accelerations would cause the velocity on that dimension to exceed Vmax, parameters specified by the user, then the velocity on that dimension is limited to Vmax.
17. (JE — the tutorial then goes to compare genetic algorithms with PSO: I’m skipping this bit for the time being)
18. (JE — the article then goes on to discuss artificial neural networks and PSO: again, I’m skipping this bit for the time being)
19. PSO parameter control
1. There are two key steps when applying PSO to optimisation problems, the representation of the solution and the fitness function.
2. One of the advantages are PSO is that PSO takes real numbers particles.  (Unlike genetic algorithms, which need to change to binary encoding or special genetic operators have to be used)
3. e.g. if we try to find a solution to f(x) = x1^2 + x2^2+x3^2, the particle can be set as (x1, x2, x3), and fitness function is f(x).
4. Then we can use a standard procedure to find the optimum.
5. The search is a repeat process, and stop criteria are that the maximum iteration is reached all the minimum error condition is satisfied.
6. There are not many parameters that need to be tuned in PSO — a list of the parameters and their typical values follows below:
7. the number of particles: typical range is 20 to 40.  For most problems 10 particles is large enough to get good results.  For some difficult or special problems, one can try a hundred or 200 particles as well.
8. Dimension of particles: it is determined by the problem of the optimised.
9. Range of particles: it is also determined by the problems the optimised, you can specify different ranges for different dimension of particles.
10. Vmax: it determines the maximum change one particle can take during one iteration.  Usually we set the range of the particle as the Vmax for example, the particle (x1, x2, x3): x1 belongs [-10, 10], then Vmax = 20 (JE –?)
11. Learning factors: c1 and c2 usually equal to 2.  However, other settings were also used in different papers, but usually c1 equals c2 and ranges from [0, 4].
12. The stop condition: the maximum number of iterations the PSO execute and the minimum error requirement.  The stop condition depends on the problem to be optimised.
13. Global version versus local version: two versions of PSO were introduced, global and local versions.  The global version is faster but might converge to local optimum for some problems; local version is a little bit slower, but not easy to be trapped into local optimum.  One can use the global version to get quick results, and then use the local version to refine the search.

The article concludes with some online resources for PSO, and some paper references relevant PSO.

I also came across a MSc thesis randomly, on the topic of PSO (http://wwwcs.uni-paderborn.de/cs/ag-klbue/de/courses/ws04/ea/students/PSO_report.pdf). Pages 9 to 11 has an interesting discussion on the PSO algorithm — maybe want to come back to, when looking at the algorithm in more detail.  The paper also has an interesting quote by Jesper Hoffmeyer: ” a swarm has been defined as a set of (mobile) agents which are liable to communicate directly or indirectly (by acting on the local environment) with each other, and which can collectively carry out a distributed problem-solving.” (from J. Hoffmeyer; The Swarming Body: in: Semiotics Around the World; Proceedings of the Fifth Congress of the International Association of Semiotics Studies; Berkley; 1994).

Next up, is the paper that started all this off: http://www.engr.iupui.edu/~shi/Coference/psopap4.html:

1. the paper introduces a method for optimisation of continuous nonlinear functions
2. it was discovered through simulation the simplified social model
3. PSO requires only primitive mathematical operators, and is computationally inexpensive in terms of both memory requirements and speed
4. early testing found that the implementation is effective with several kinds of problems
5. the paper discusses application of the algorithm to the training of artificial neural network ways
6. stimulating social behaviour
1. a number of scientists are investigated the movement of organisms in a bird flocks and fish schools, notably Reynolds and Heppner and Grenander
2. these scientists have the insight that local processes, such as those model by cellular automata, and I underlie the unpredictable group dynamics of birds social behaviour
3. both models relied heavily on manipulation of inter-individual distances: i.e. the synchrony of flocking behaviour was thought to be a function of birds efforts to maintain an optimum distance between themselves and their neighbours.
7. Precursors: the etiology of particle swarm optimisation
1. the PSO algorithm began as a simulation of simplified social milieu
2. agents were thought of collision-proof birds, with the original intent to graphically it used to the choreography of a bird flock.
3. Nearest neighbour velocity matching and craziness
1. a stochastic variable called craziness was introduced, to prevent flocks quickly settling on a unanimous changing direction
4. the Cornfield vector
1. Heppner’s bird simulation had a feature which introduced a dynamic force into the simulation: his bird flocked around a roost, positional the pixel screen attracting them until they finally landed there.  This location eliminated the need for variable like craziness, as a simulation talk on a life of its own.
2. (A sociobiologist E. O. Wilson wrote in reference to fish schooling “in theory at least, individual members of the school can profit from the discoveries and previous experience of all other members of the school during the search for food.  This ad vantage can become decisive, outweighing the disadvantages of competition for food items, whenever the re source is unpredictably distributed in patches” (p 209) (Wilson, E.O. (1975). Sociobiology: The new synthesis. Cambridge, MA: Belknap Press.))
3. The second variation of the simulation defined a “Cornfield vector”, a two-dimensional vector of XY coordinates on the pixel plane.
4. Each agent was programmed to evaluate its present position in terms of the equation: so that at the (100, 100) position the value was zero.
5. Each agent “remembered” the best value and the XY position that had resulted in that value.
6. The value was called pbest [], and the positions pbestx[] and pbesty[] ( the square brackets indicate that these are arrays, with the number of elements equal to the number of agents)
7. as each agent moves through the pixel space evaluating positions, its x and y velocities were adjusted in a simple manner:
8.     if it was to the right of its pbestx, then its x velocity (call it vx) was adjusted negatively by a random amount weighted by a parameter of the system: vx[] = vx[] – rand()*p_increment.
9.     If it was to the left of pbestx, rand()*p_increment was added to vx[]
10. similarly y velocities vy[] were adjusted up and down, depending on whether the agent was above or below besty
11. secondly each agent “knew” the globally best position that one member of the flocking had found, and its value: this was accomplished by simply assigning the array index of the agent with the best value to a variable called gbes, so that pbestx[gbest] was the group’s best x position, and pbesty[gbest] its best y position, and this information was available to all flock members.
12. Each member’s vx[] and vy[] were adjusted as follows, where g_increment is a system parameter:

if presentx[] > pbestx[gbest] then vx[] = vx[] – rand()*g_increment
if presentx[] < pbestx[gbest] then vx[] = vx[] + rand()*g_increment
if presenty[] > pbesty[gbest] then vy[] = vy[] – rand()*g_increment
if presenty[] < pbesty[gbest] then vy[] = vy[] + rand()*g_increment

1. (numbering contd. from above: i + 12 ) the results from initial runs of the simulation was surprising: with p_increment and g_increment set relatively high, the flock seemed to be sucked violently into the Cornfield.  In a very few iterations the entire flock, usually 15 to 30 individuals, was seen to be clustered within the tiny circle surrounding the goal.
2. With p_increment and g_increment set low, the flock swirled around the goal, realistically approaching it, swinging out rhythmically with subgroups synchronised and finally “landing” on the target

And that’s where I got to today: tomorrow more of the same paper –I’m down to section 3.3, Eliminating Ancillary Variables

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.