top of page

GeoInv Algorithm Concept

The nearest neighbour algorithm is used to solve the nonlinear inverse problem. This optimisation algorithm is a direct search (derivative-free) method in the same class of inversion techniques as, for example, simulated annealing and genetic algorithms. These methods are similar in that they use randomised decisions in exploring the multidimensional parameter space. The complexity of the cost or objective function is the limiting factor since its derivatives are not required to guide the search. 

During the search process, the nearest neighbour algorithm identifies the models with the best solutions (lower misfit value) from the current sample of models in order to perform a resample (generation of a new sample of models). 

The outcome of search stage is the generation of a number of samples. This is followed by an appraisal stage where the error analyses of sample models are performed. The salient feature of the nearest neighbour algorithm is that inference about the system is made by using the suite of all generated models, rather than a single, lowest-misfit model. The argument being that even poor-fitting models may contain information about the system. 

Voronoi cells are used to partition the parameter space. A model inside each cell is generated and solved. Then solutions are appraised and ranked based on the misfit value relative to a target solution. Then a subset consisting of the best models (the ones with lower misfit value) are used to perform a resample. With each resample, the new generated models concentrate on the cells with relatively lower misfit relative to the rest of the cells.

Comparison of samples in nearest neighbour algorithm. Sample B is closer to target solution subsequent to appraisal of Sample A solutions. 

bottom of page