Next: Generalized Simulated Annealing Up: Optimization of Non-Linear Gravity Previous: Optimization of Non-Linear Gravity
Next: Generalized
Simulated Annealing Up: Optimization
of Non-Linear Gravity Previous: Optimization
of Non-Linear Gravity
The search of a global extremum of a cost function (f) is, in general, a very difficult task that appears frequently in the most different fields of the knowledge. Physicists, engineers, geophysicists and economists are particularly concerned with constrained optimization, where a priori limitations are imposed on the allowed values of the variables to be optimized.
There are different methods to attack this problem. The most usual technique is based on gradient methods principally if the cost function (f) is convex, i.e. has a single minimum. But if f has multiple extrema (nonconvex function), more sophisticated methods must be used, in order to not get trapped in one of the local minima. This kind of method has the advantage to map local and global minima.
Recently, the called ``Simulated Annealing methods'' [1, 2] have demonstrated important successes for a variety of global minimization problems [3]. The underlying principle of the simulated annealing method is in its analogy with the thermodynamics, especially with the way that liquids freeze and crystallize or metals cool and anneal. Kirkpatrick has proposed this method based in the quasi-equilibrium Boltzmann-Gibbs statistics using a Gaussian visiting distribution which is sometimes referred as Classical Simulated Annealing (CSA) or Boltzmann machine. The next interesting step in this subject was proposed by Szu and Hartley [4] using a Cauchy-Lorentz visiting distribution, instead of the Gaussian one. This algorithm is referred to Fast Simulated Annealing (FSA) or Cauchy machine.
More recently Stariolo and Tsallis [5], based on the thermostatistic theory [6, 7] have generalized this approach which is referred to Generalized Simulated Annealing (GSA). It contains both Boltzmann and Cauchy machines as particular cases, with the supplementary bonus of providing an algorithm which is even quicker than that of Szu and Hartley. One of us has successfully applied this new method in the geometry optimization of molecular systems and conformational analysis study [8]. Other important applications of this technique deal with; genetics [9] and the classical traveling salesman problem [10].
The inversion of gravity data can lead to either linear or non-linear problems. The latter deals with a situation where any coordinate of the anomalous body is unknown, and for the former the only unknown is usually the density distribution. This work deals with the non-linear case, which is the main target of global search methods. However, in order to compare our result to a standard inversion method, one of our examples considers a linear problem. Among the recent works concerning 2-D gravity inversion we have García-Abdeslem [11], who used vertical prisms, with fixed width, and used the Marquardt-Levenberg approach for the non-linear inversion. But in his case the knowledge of the density variation with depth was necessary. Pan [12], in a study of resolving power and bias effects used also the non-linear approach for the 2-D gravity inversion problem, again with vertical prisms with known density in order to determine the upper bound of the prisms. Guspí [13], for instance, considered a 2-D gravity inversion problem where the density contrast varied with depth in a form of polynomial function, as did Rao et al. [14] where they considered a hyperbolic density contrast. As far as annealing techniques are concerned, we quote here two recent applications in inverse problems in geophysics. Sen et al. [15] employed the Simulated Annealing (SA) [1] in non-linear inversion of resistivity data, where basically the problem is the determination of resistivity as a function of depth from the apparent resistivity values measured in the field as a function of electrode separation. Dittmer and Szymanski [16] used the SA in the inversion of linear magnetic data, and also non-linear resistivity data. They used small blocks with unform magnetization or conductivity to parametrize the medium, differently from [15] who considered a plane layered earth model.
In the present work we apply the GSA in three examples with synthetic data, where each one deals with a different situation. This is the first time that the GSA is applied in inverse problems in geophysics, and to our knowledge, the first time that some annealing method is applied in a gravity inverse problem. We verified the feasibility of this approach to solve inverse gravity problems. This technique can be used to other geophysical areas, where very frequently one deals with non-linear problems. Pullammanappallil and Louie [17, 18] used an extension of the SA also called generalized simulated annealing based on the work of Bohachevsky et al. [19] to invert seismic reflection and refraction data. Note that although both [19] and [5] use the term generalized the two approaches are different.