Evolutionary algorithms

Our problem: How to optimise a geometrical model to fit physical observations?

A big problem in optimising geometry models is the fact that changes (e.g. mutations) of the model leads often to invalid topological changes. This is especially problematic if models are constructed of huge amounts of triangles (= model parameters). Such models can be treated as invalid models but soon the number of invalid models will increase during optimisation attempts and the general probability for generating valid models thus decreases dramatically. Furthermore smooth horizons will not necessarily stay smooth, since the automated optimization algorithm does not know anything about smoothness. Formulating all this as constraints (triangles may not illegally cross each other and smoothness has to be kept “somehow”) shifts the problem only gradually since crossing triangles have to be corrected or smoothness operators have to be applied. In both cases (self adopting) algorithm of CMA-ES (Covariance Matrix Adoption Evolutionary Strategies) will be disturbed, since corrections cannot (yet) be “reported” back to the algorithm.

Our solution: Change the space, preserve the topology, use mutations!

The idea is therefore to transform the problem in a way that mutations cannot intrinsically lead to a damaged topology and – to some less strictness – avoid edgy and/or rough model geometries where smoothness is expected. One way of doing so is changing the space rather than changing the model itself. The following figures show a simple way of applying a grid (in 2D). It can be seen that the length of the edges of the grid-elements are now optimization parameters. The only restriction is to keep the values greater than zero, so (part of) a grid can almost but not fully disappear. So topology is kept and the grid size controls (in a way) resolution (or roughness). The problems rising with this method are of practical nature: where to pin point the grid ? (as done as an example in the figure’s lower left corner). Also the edges of the grid elements are not independent: if the edge cd is changed, the edge ab is changed as well. Therefore the strategy destroys it’s own ‘moves’ and can (supposedly) not learn anymore.

SP4 Change the space Source: AIDA Team

To overcome these limitations one can apply mutations on grid nodes. But this just shifts the original problem of model inconsistencies to the grid.

So the need of a transformation raises which keeps topology and can be tuned in aspects of smoothness. A solution is using self-organizing maps (SOM). The following figure shows a three-dimensional space mapped to a two-dimensional space (a map) in a way that neighbours are mapped close to each other: in other words topology is conserved. The thin lines show the neighbour relations in the 2D map back-projected in the 3D space.

SP4 Map 3D to 2D Source: AIDA Team

Where for a projection from higher dimensional spaces to a lower dimensional spaces it can (of course) not always be guaranteed to preserve topology (there is a reason why we have more dimensions ;-). But it can be proven, that a projection from one space to another with the same dimension, topology is always preserved. The clou is now to use that property to (first) map the two- or three dimensional space (R^2/3) to the same dimensional (but different) space (R^2/3) and apply a “tailored” training in order to achieve what is called magnification. The following figure shows an example of transforming the salt-dome-containing space (left) to a space, with kept topology and applied magnification (right).

SP4 Change a salt dome model Source: AIDA Team

The following two figures show again the effect of magnification applied to a two dimensional cross-section of a three dimensional model both based on the original model having a rectangular grid to start with.

SP4 Magnify salt dome regions Source: AIDA Team

The model geometry is changed in favor to the quality function. The salt dome became a smaller waist.

Self-organizing maps have some disadvantages e.g. the need for the grid-map (by definition). A successor with two advantages over SOM is Neural Gas (NG). First in NG magnification is done on model parameters (and not on a rather artificial grid) and second convergence speed of NG is higher and more reliable than SOM. The following figure shows the principal ideas.

SP4 Minimize cost function Source: AIDA Team

Applying all techniques to a real world model (including geological constraints) is a non-trivial task. For now a scheme as shown in the following figure is applied.