Natural Computing Blog

Dispersive Flies Optimisation

What is DFO?

Dispersive Flies Optimisation Research (DFO) [1] is a swarm intelligence algorithm. That is, it is an algorithm where individual agents follow simple instructions to search for a solution in in a matrix representing an N-dimensional search space [2]. The agents are set up so that they can communicate with one another and adapt their search trajectory based on the behaviour of their neighbours.

The algorithm aims to exploit the emergent adaptive intelligence of the swarm to find an optimal solution to a given search problem. Its behaviour is inspired by the swarming behaviour of flies hovering over food sources and it has been shown to find optimal or “good enough” solutions [3] faster than randomness and of the standard versions of the well-known Particle Swarm Optimisation, Genetic Algorithm (GA) as well as Differential Evolution (DE) algorithms on an extended set of benchmarks over three performance measures of error, efficiency and reliability [4].

The algorithm was first proposed by Mohammad Majid al-Rifaie, a computing lecturer at Goldsmiths, University of London, in his paper published in 2014.

How does it work?

Just like flies hovering over food, animals, your face, or p– ehm — feces, the algorithm creates a swarm of agents are initially scattered at random, but that eventually converge towards that agent which has found the most interesting feature in the space they are in.

The algorithm does not centrally coordinate the agents’ movements but lets communication between neighbouring flies decide where each of them will move towards. The agents are also programmed to disperse if a certain stochastic function exceeds a preset output threshold, so as to mimic flies running away from a threat and -possibly- finding an even more interesting point of interest.

As described in its original paper,

DFO consists of two tightly connected mechanisms, one is the formation of the swarms and the other is its breaking or weakening.

Unlike real life flies, the agents in the algorithm are not just hunting for food across a 3D search space but live in a matrix made up of all the dimensions that we want. This is because the position vector of each virtual fly represents the variables of a problem that we are trying to solve and for which we don’t have a mathematical formula to compute the solution(s). An example of this could be the identification of certain patterns in a data set, or finding a viable (if not optimal) solution to unsolved path-finding problems. It’s been shown, for example, that it is possible to achieve a good automatic identification of microcalcifications on mammographs using DFO as a method of image analysis[6].

The hunt

Nature has equipped flies with a nervous system that scans their sensory world in search for salient markers that can the  food. When a fly finds something interesting, its flight behaviour is picked up by neighbouring flies, which then converge towards the position of the first fly.

In DFO, the search for food is carried out by a fitness function that tests how good the position values of the fly are at solving the problem at hand –Remember: the position vector of each fly is the set of variables whose variance describe (within reason) all the possible cases in our problem. We could then say that the position of the fly in the global search space is the fly’s attempt (hypothesis) at solving the problem by trial and error.

Once a fly has checked how good its location is as compared to a certain reference fitness value, it scans its two closest neighbours to see whether they have found a better set of variables (position vectors) and it then moves across the search space on the basis of the knowledge it has. The algorithm also stores the position of the fly that has found the best solution so far and uses it to randomly drags other flies towards is direction.

Finally, each fly runs a dispersive stochastic method that may push them to fly away in a random direction. This is to simulate the arrival of a threat in the real world and it helps the algorithm avoid getting stuck on a local optima.

The mathematical description of the fly’s position update method (for each coordinate) is as follows:

x_{i}^{t=n} = x_{\text{i BN}}^{t=n-1} + U(0,1)\cdot(x_{\text{i SB}}^{t=n-1} - x_i^{t=n-1})

Where:

  •  x_{i} ^ {t=n} is the dimension, or coordinate, ” i ” of the fly’s position at time ” n “ that we want to find.
  •  x_{\text{i BN}} ^ {t=n-1} is the same coordinate but in the current position of the best of the two neighbouring flies
  •  x_{\text{i SB}}^{t=n-1} is as above but of the best fly in the swarm (elitist approach)
  •  U(0,1) is the denomination for a a random number between 0 an 1 as chosen by a normal distribution function

If,  however, the random function responsible for mimicking the arrival of a threat outputs a value higher than a certain threshold, the update function will randomise the specific fly’s coordinate as below:

x_{i}^{t=n} = x_{\text{i min}} + U(0,1)\cdot(x_{\text{i max}} - x_{\text{i min}})

Where  x_{\text{i min}} is the minimum value that the dimension, or coordinate, ” i ” of the fly’s position can take in the whole space and  x_{\text{i max}} is the maximum.

Below we can see an example for a 2 dimensional problem-space where the current fly we are examining updates its position. We assumed that the random number generating function returned 0.3 for the first dimension and 0.8 for the second dimension –you can ignore the top left and bottom right drawings on the picture.

 

The overall behaviour is therefore expected to be that of convergence (of the swarm) towards optimal points. Flies will in fact tend to go gravitate (hover) in the direction of those other flies that are in better positions as evaluated by a given fitness function.

In the above visualisation, flies are hovering towards a better and better positions. However, they are also getting stuck in a local optima.

With DFO we hope that by exploring other areas at random every time the dispersion threshold is met, the swarm will eventually converge to a good enough if not globally optimal solution of the problem within a reasonable amount of time.

Possible Applications

We have mentioned that DFO has been used with positive results for searching an image-function (search space) in order to find certain patterns [6]. Being a promising search algorithm within the so-called Swarm Intelligence (SO) branch of computer science research, DFO could also work well in data mining, where Ant Colony Optimization (ACO) and Particle Swarm Optimization (PSO) have already been deployed with interesting results [7].

As a Music Computing student, I personally would be interested to see if DFO could be used to come up with musical structures that can be considered musical by our standards. To achieve this I think that one are of the musical experience should be selected as the focus, for example the melodic/harmonic structure of a piece of music.

Last year I have exploited with some interesting results a Genetic Algorithm coupled with a tree-structured grammar of Western notes to automatically generate melodic phrases. Since it’s been shown that Swarm Intelligence can be applied as an extension of Lyndenmayer grammars [8], it would be interesting to test out DFO’s performance when asked to come up with meaningful structures.

As always with perceptual experiences and aesthetic art, one of the hardest problems with the above application would be to come up with a meaningful fitness function and a correct set of problem variables and algorithm parameters. In this respect though I think that a possible approach could be the coupling up of DFO with some Deep Learning [9] strategies. This way we might try to approximate the “arousal” and “linking” function of certain melodic/harmonic patterns based on the average response by some chosen population sample.

Another area I am interested in at the moment is detecting meaningful patterns in a stream of data, such as extracting meaningful information from noisy market charts (as in ForEx, Stocks, Bitcoin, etc) or video analysis in a moving image. Again I can see DFO being a good candidate for exploring the data-field in search for specific patterns. Those patterns might then be quickly pointed out to the user as well as used for making some sort of automatic informed decision. Particle Swarm Optimization (PSO) has already produced some interesting results when applied to Computer Vision [10], so DFO may also provide a promising problem-solving vehicle in those files.

 

Implementing DFO

I implemented a version of DFO in C++ that is now available on my gitHub. This is basically a porting of the original java code as created by Mohammad Majid al-Rifaie, which has helped me understand how the different elements of the algorithm can be coded as different classes (in a OOP fashion) that can then be set to explore any problem’s space-function that we like.

The repository includes a README and the code is thoroughly commented.

Using the algorithm I then went on and tried to tackle the following minimisation problem:

fitness function = 12/x + 18/y * xy

x & y are positive

 

 

Leave a Reply

Your e-mail address will not be published. Required fields are marked *