Particle Swarm Optimisation
For the final blog of the natural computing module, I have chosen to write about my experiments with Particle Swarm Optimisation (PSO). My recent blogs have focused on applications of nature-inspired algorithms for optimisation in problem solving and so I wanted to focus instead on creative applications. PSO was created to simulate the choreography of social animals such as fish and birds.
PSO is in many ways similar to dispersive flies optimisation (DFO). Both are population-based metaheuristics that update each individual simultaneously upon each iteration of running. Both nature-inspired algorithms lack stigmergy, unlike ant colony optimisation, in that the populations do not communicate or interfere with the environment in some way to aid achieving its goal. Stochasticity is used to an extent in both optimisers to ensure a wide exploration of the problem search space. A level of elitist communication is used to share the value of the best individual of population to influence the update of the population. PSO however does not feature the same ring topology network that DFO possesses but instead utilises a component of memory and velocity for each particle.
Upon initialisation, each individual creates a randomised position solution similar to that of a feature vector that flies within DFO possess. Each particle also creates a random velocity in the range of [-r, r]. This range is dependent on the size of the search space and determines the level of velocity magnitude the particles will have when created. Each particle’s best known position is set to its initial randomly created position.
For each iteration, the velocity of each particle is updated utilising its best found individual position and the best found position of the swarm. A constriction factor is used to act as a limiter for the movement of each particle. The learning rates c1 and c2 act also as limiters, c1 for the influence that an individual’s own best known position will have upon its new velocity and c2 for the influence that the best particle in the swarm will have on others.
Get Becky Johnson’s stories in your inbox
Join Medium for free to get updates from this writer.
A simple example of PSO is shown below, the swarm is directed to locate the centre of the canvas window to highlight the impact of different constriction factor values. A lower constriction factor creates a lower rate of convergence over a targeted solution.
Also shown in the animation are the directional velocities of each particle. The magnitude is displayed by the length of each particle’s line. Upon initialisation, the velocities are randomised for both the horizontal and vertical axis of each particle. The swarm then quickly synchronise their movement towards the targeted solution due to the knowledge of both their personal best position and the personal best position of the best particle in the swarm.
For the application of tracking a moving object, I found an issue in that if the target rapidly changes direction that the swarm is not able to alter its combined velocity to keep up with this sudden change. For real world applications of object tracking where objects may not follow linear or predictable movements, this seems to be a big disadvantage that PSO may have. Using an object with the same trajectory, a shortcut to this problem involves resetting the velocities and best known positions of each particle. This resetting enables the particles to be able to dynamically change their velocities, due to the range of the randomly initialised velocities, in order to follow unexpected and drastic movements.
I was then interested by the combined use of shaders and PSO and implemented a simple test in openFrameworks. Each pixels colour is determined by its distance from the position of the best particle. I hope to experiment more with shaders and swarm intelligence algorithms when I have the opportunity. PSO’s feature of velocity seems to be a very attractive component of the algorithm as this can be directed and mapped into many visual possibilities. I hope to experiment with this velocity within both vertex and fragment shaders, using this to morph features of colour, shape, and texture based upon the combined velocity of the swarm.
Overall, this module has enabled myself to develop a range of valuable and transferable skills and knowledge. The act of writing a weekly blog has been very useful as being able to articulate my thoughts and experiments is required for all of my projects but I find it very easy to fall out of habit with writing when not having to regularly do so. I have a new found interest in algorithms in general, both in designing and analysing their performance, as no other previous module has required that I study this heavily. Coming from a creative perspective, despite enjoying the logical or computer science approach, I would have enjoyed to have spent a lecture or lab focusing on the creative potential of nature-inspired algorithms. I understand that this may not be what others who have taken the module would have wanted due to the mix of computer scientists, artists, and musicians who are enrolled. This module has been extremely useful in regards to my final year project where I feel I am comfortable in discussing swarm intelligence and evolutionary algorithms.
