Dispersive Flies Optimisation
In my module, Natural Computing, the first swarm intelligence algorithm discussed extensively was Dispersive Flies Optimisation (DFO) by Mohammad Majid al-Rifaie. It is a population-based stochastic algorithm that simulates the collective behaviour of flies searching for food. The algorithm consists of a topology network that allows the flies to communicate to each other the best found result. A dynamic rule updates each fly’s position based on the location of it’s best neighbouring fly and also the best fly in the swarm. This communication allows the swarm to share information about optima amongst the network and converge at this point.
To prevent the likelihood of discovering only local optima rather than global, the algorithm also simulates the presence of threat that flies experience in nature. This disturbance is the stochastic element which forces the swarm to disperse and possibly discover better locations by doing so. A random number on the uniform interval [0,1] is generated and tested against this threshold. If the number is lower, the fly will be assigned a completely new position based upon no communication, if it is higher then it will update it’s position based upon the other flies’ locations. As advised in the lecture, the disturbance threshold is an ongoing debate in natural computing as there is no known best threshold. This relates partly back to the discussion of the No Free Lunch theorem, where dependent on the problem, search space, and known information, exploration may be favoured over exploitation and vice versa.
After the lecture, I used the pseudocode present in the DFO paper to implement a simple one-dimensional application using the algorithm. Each fly had a feature for it’s x position and it’s fitness was calculated by it’s distance from the centre of the window.
For this simple example, I found that increasing the size of the fly population resulted in the flies finding the solution faster. I also found that altering the disturbance threshold for this example did not seem to have much benefit as there was only one optimum to be found and resulted in the flies taking longer to find it. I can see that for a search space where there may be multiple solutions, increasing the possibility of disturbance would be advantageous to ensure that the flies would have the ability to find it. I extended the program to include another dimension, the y position of each fly, and felt the same about the effect of the disturbance threshold and fly population as I did for the one-dimensional example.
I tried to add some interactivity to these programs by changing the fitness function to sum the distance between each fly and the mouse position. This required slightly different, but very simple, fitness functions for the x and y dimensions in which the distance from the mouse was summed from either it’s x or y coordinate.
After the lab, where we evaluated DFOs optimisation using different test functions, I tried to implement a simple application that would deploy a swarm to find the brightest area of an image. What I thought would be a simple task actually turned out to be rather difficult. The fitness function consisted of mapping each fly’s position to it’s corresponding index in the image’s pixel array and using that pixel’s brightness to define it’s fitness. However, some flies would escape the boundaries of the image and then become “lost”. At first I thought that DFO seems to be very useful as an optimiser over a continuous search space, however is not as efficient when using a limited one. My lecturer then explained that for discrete spaces, a clamping method must be used to ensure that the flies stay inside the valid search area in order to find solutions. By implementing functionality to generate a random position for a fly when it escapes the search space limits, the flies then successfully converged to the areas of brightness within the image.
This exercise was very useful in understanding how search spaces must be modified when using DFO. It also made me think further about my ideas for my third year project in generating audio using swarm intelligence in terms of the features, search space, and fitness functions I would need to use. I am incredibly happy that DFO works as well in optimisation for discrete spaces, as the features of audio that I want to explore will lie within constricted search areas also.
For the application of audio generation, I understand now that for each feature I want to analyse, i.e. frequency, repetition, rhythm, I need to set specific constraints on the search space to ensure that the swarm stays within a valid range. For example, to replicate the frequency range of a piano, the dimension related to frequency would range from 26 Hz to 4186 Hz. The fitness function could then test whether the fly has reached a value that corresponds with the frequency value of another piano key. With additional knowledge of previous notes and the key that the swarm is composing in, each fly would be able to communicate whether a certain frequency is the best solution to generate next.
After discussions and experiments of DFO, I am excited to have developed an understanding of swarm intelligence algorithms to be able to start applying it for creative practise. Possible ideas include image analysis to alter or glitch images or real-time input. I am sure that with more discussion on disturbance, exploitation, exploration, and emergence of intelligence that more ideas will materialise.