Analysis and development of the Bees Algorithm for primitive fitting in point cloud models

Baronti, Luca ORCID: 0000-0002-2883-706X (2020). Analysis and development of the Bees Algorithm for primitive fitting in point cloud models. University of Birmingham. Ph.D.

Preview

Baronti2020PhD.pdf
Text - Accepted Version
Available under License All rights reserved.
Download (11MB) | Preview

Abstract

This work addresses the problem of fitting a geometrical primitive to a point cloud as a numerical optimisation problem. Intelligent Optimisation Techniques like Evolutionary Algorithms and the Bees Algorithm were here adapted to select the most fit primitive out of a population of solutions, and the results compared.

The necessity of understanding the dynamics of the Bees Algorithm to improve its performances and applicability led to an in-depth analysis of its key parts. A new mathematical definition of the algorithm led to the discovery and formalisation of several properties, many of which provided a mathematical answer to behaviours so far only observed in empirical tests. The implications of heuristics commonly used in the Bees Algorithm, like site abandonment and neighbourhood shrinking, were statistically analysed. The probability of a premature stalling of the local search at a site has been quantified under certain conditions. The effect of the choice of shape for the local neighbourhood on the exploitative search of the Bees Algorithm was analysed. The study revealed that this commonly overlooked aspect has profound consequences on the effectiveness of the local search, and practical applications have been suggested to address specific search problems.

The results of the primitive fitting study, and the analysis of the Bees Algorithm, inspired the creation of a new algorithm for problems where multiple solutions are sought (multi-solution optimisation). This new algorithm is an ex- tension of the Bees Algorithm to multi-solution optimisation. It uses topological information on the search space gathered during the cycles of local search at a site, which is normally discarded, to alter the fitness function. The function is altered to discourage further search in already explored regions of the fitness landscape, and force the algorithm to discover new optima.

This new algorithm found immediate application on the multi-shape variant of the primitive fitting problem. In a series of experimental tests, the new algorithm obtained promising results, showing its ability to find many shapes in a point cloud. It also showed its suitability as a general technique for the multi-solution optimisation problem.

Type of Work:

Thesis (Doctorates > Ph.D.)

Award Type:

Doctorates > Ph.D.

Supervisor(s):