Find the circle that is simultaneously tangent to 3 given circles.

This can be formulated as a search problem for a 3 dimensional (candidate) vector with the objective to minimise the function : sum of the error between distance between centres and sum of radii.

The three parameters of the perfectly-fit candidate will represent the x,y coordinates of the centre and the radius of the circle.


The search-space of a Particle Swarm Optimisation algorithm for the above problem


Comparing various single-objective optimisation algorithms for the same problem.

Parameters compared :
best scores - accuracy of the solution
#evaluations number of calls to fitness function
FPS frame-rate
iterations how quickly it gets in the region of a good score

PSO = Particle swarm optimisation
GSA = Gravitational search algorithm
GA = Genetic algorithm
GR = Gradient descent

low best score is better because it is a minimization problem.

The exercise was to qualitatively compare the behaviours of the 4 algorithms exploration of solution space and exploitation to reach a target

Turns out the PSO is a pretty nifty algorithm for this problem / similar problems : Achieving higher accuracy, lower code-size, wider exploration through solution space, and faster exploitative convergence, as the videos below show.

It should be noted that a GA couldn't be expected to do well in terms of the best scores due to its inherent discrete nature compared to the continuous nature of PSO. However the differences in exploratory behaviours of the 4 algorithms are the most interesting :
The Gradient descent minimal in its exploration . Thus, it is quite likely to get stuck in a local minima.
PSO being rather expansive in its exploration.
GSA is oscillatory around certain centroid points.
The crossover method of the GA effects the nature of its exploration. HOwever it is predominantly scan-line


Comparing code-size of the algorithms.