Dispersive Flies Optimisation ( DFO )

Dispersive Flies Optimisation (DFO) is a global optimisation algorithm that is inspired by observing behaviour of swarming flies in the real world. The algorithm is going through a defined search space and it’s trying to find the most optimal value, which will converge the flies towards their target. We use the DFO to benchmark different test functions for our optimisation.
The swarming behaviour of the flies optimisation is based on a value called ‘fitness’. This value judges how optimal the data is and based on the value of the ‘fitness’, it will attract the swarm of flies towards the new found optimal position. During the test of finding the most optimal fitness value, the algorithm is also applying random values to disburse the flies across the search space and away from the best fitness value. This is an attempt to further explore the search space and perhaps find a better potential fitness value.
Together with Terry, we implemented the algorithm that was given to us in the lab, using C++ in OpenFrameworks. The whole visualisation part of this algorithm was a bit unclear to me in the lab, but after digging through the program and by implemented it ourselves, it made much more sense. Especially when it’s applied in two dimensions. ( shown in the gif below )
The conclusion of implementing the algorithm was that we managed to successfully create a program that basically creates a way for us to measure the performance of each fitness function. So to experiment with this program further we need to assign it to a specific problem.
During the lecture we discussed how the DFO works based on this mathematical formula:
What this translate to in words:


New current fly position = best neighbour position + randomNumber( 0, 1 ) x ( best fly position - current fly position )
This is how it would look in code:
for (int d = 0; d < dim; d++) {
         temp[d] = flies[chosen].getPos(d) + ofRandom(0,1) * (flies[bestIndex].getPos(d) - flies[i].getPos(d));
}
What we're doing in this loop is that we're calculating where the current fly needs to go based on the position on the best nearest fly, the best fly in the swarm and based by its own position.
Depending on the dispersive random value, the flies will be dispersed from their current position to explore more of the search space, as mention earlier. The dispersive value is also to make sure that none of the flies get stuck in a local minima in order to find the globally optimised position.


Output : Programmed in C++ with OpenFrameworks using the sphere function.
As you can see the fitness is decreasing. This is just a short gif but I found it very interesting to test different functions and see how the behaviour changed.
DFO.gif
Possible usages:
I see this being used in many different fields of study, for example in games where you can for example use it for pathfinding.
Another useful application for this type of behaviour would be in image processing where you can possibly identify specific colours within an image or a video by using all the pixels as your search space to for example find specific colour areas or specific coloured objects.

For my own personal interest I would love to use swarm behaviour to interact with the user in VR. I believe that it would be a powerful effect to use a natural phenomenon inside a virtual world, and I will most likely develop this further using the Unity game engine.

Resources:

 Original paper & source code:
http://doc.gold.ac.uk/mohammad/DFO/

Comments

Post a Comment

Popular posts from this blog

Physical Computing, Final Project

Image
Physical Computing Final Project Technical Details For my final project, I have made a set of analog synthesizers. What I mean by analog is that I haven’t used any microcontrollers for this project. I will only be working with 9V batteries and a series of different IC’s ( Integrated circuits ). These are the IC chips I have used for my final build: CD4046 CD40106 CD4066 CD4017 LM386 The Synthesizer This is a very simple circuit that is generating a square wave. The small yellow 0.1uF capacitor is the capacitor that is setting the frequency range of the oscillator. The potentiometer is adjusting the fundamental frequency. First oscillator prototype This is how the oscillator sounds: https://youtu.be/j2es7WL2imU The next step is to add more effects to the synthesizer so it sounds a bit more interesting. Next I am setting up another oscillator using the CD40106 chip. The CD40106 is a Hex Schmitt Trigger or more eas
Read more

Image alignment & finding symmetry with DFO

Image
This week we are continuing working with SDS and DFO, but we are shifting our focus on a new set of problems. An interesting topic we discussed in the lecture was how SDS could be used for image alignment. Say we have two images as our search space and we want our SDS system to find a specific section of our image, we then want to align it section with the other image. One way we can do this is to take our selected part of our search space and split this selected section up into multiple segments. Each segments will then work as our micro features, just like we did for our locations within our hills from last week's post. One way of simplifying it would be to use each pixel within our selected section as our micro features, but we can also grab a larger area and take the average of all the pixel values within that area. By using this technique we can find the pixel values and we can align the images based on the matched pixel values. We also discussed anoth
Read more