Stochastic Diffusion Search

Stochastic diffusion search (SDS) is a swarm intelligence based algorithm that fundamentally differs to DFO (implemented last week) in the following ways:

• Agents’ features define a hypothesis in the search space; a set of ‘microfeatures’ which together are a candidate for the solution
• In the ‘test phase’, random microfeatures in the hypotheses are used in partial evaluation instead of calculating the fitness of the whole
• Boolean (true/false) information is shared directly between random agents during the ‘diffusion phase’, unlike DFO agents’ results which is continuous

When each negatively-evaluated agent communicates with a single random agent in the diffusion phase of SDS, it can either adopt the partner’s positively-evaluated hypothesis or (if the partner is also negative) a new random hypothesis is set. Positively evaluated agents stick to their hypotheses in the diffusion step, leading to signifigant numbers of agents congregating around the best hypothesis quickly.

Efficiency and Results

Using partial evaluation contributes to the speed of clusters forming because it lets agents get an idea of their hypothesis’ fitness while skipping most of the computation. Additionally, calculating and sharing results of fitness functions may be faster when the result is just true/false as is the case with SDS.

Obtaining solutions to problems using SDS can be implemented as a congregation size threshold at which to stop iterating. For example by continuing the cycle of 1) test phase 2) diffusion phase until at least 75% of the population share the same hypothesis. The best solutions should come from many SDS iterations, as a repeating partial evaluation on the same hypothesis is equivilent to full evaluation (if every microfeature is eventually evaluated positively).

Applications

SDS seems most frequently applied to computer vision tasks such as image recognition/tracking, which is typically very computationally expensive. For these tasks, a ‘model’ subsection of an image can be searched for within a larger image. The fitness function compares microfeatures from hypotheses in each image. Overlapping images may be aligned using SDS with a similar fitness function, with practical applications in medical imaging and robotics.

Our lecture and lab session this week looked at simple symmetry detection i.e. locating vertical/horizontal lines of symmetry in a computer generated image (noise really complicates things):

• Each agent is initialised with a random number corresponding to the position of a possible line of symmetry
• Every pixel adjacent to the agent’s value in opposite directions are microfeatures in the hypothesis
• The fitness function compares two neighbouring pixels at a random distance n from the middle of the hypothesised line in the test phase
• When pairs of pixels don’t match it is assumed that the agent isn’t on a line of symmetry, so the agents randomly choose another agent in the population to get its fitness
  • If the random agent has also failed it’s fitness function for symmetry, our agent will randomly choose a new hypothesis
  • Else if the random agent seems to be on a line of symmetry then our agent will copy its hypothesis

Moving On

I think swarm intelligence could be used in the following problem:

• Problem: locating the most in-focus region in a photo
• Search space: a two-dimensional greyscale image
• Agent parameters: a 2D coordinate for the top left of a 5x5 subsection of the search space
• Fitness function: gets the brightness values of the 5x5 pixels and returns the standard deviation

Extending the concept to video could work as a sort of focal point tracker with potential value in data visualisation?

For Natural Computing (IS53052A)