Introduction

The kind of optimization problems that we usually face in exploration geophysics are non-linear, high-dimensional, with a complex search space that may be riddled with many local minima or maxima. Usually our first line of attack is linearization of the problem around some given smooth, ``easily'' computed initial model. Seismic tomography is a good example of the success of this approach. There are many cases, however, where linearization is impractical or undesirable and the full non-linear problem must be solved. Broadly speaking, there are two ways to attack these kind of problems: deterministic search methods, for example non-linear conjugate gradient, quasi-Newton methods or Levenberg-Marquardt method Gill and Murray (1981), and stochastic search methods such as Montecarlo, simulated annealing and genetic algorithms Davis (1987); Goldberg (1989a). Deterministic methods are attractive because they are natural extensions of familiar linear methods and because, in certain applications, they can be made to run extremely fast. The downside is the need to compute first and/or second order derivatives of the cost function and the dependence of the solution (and sometimes even the convergence of the method itself) on a suitable starting point. In other words, deterministic methods are extremely efficient at locating the bottom of the valley, provided they start the search somewhere inside the valley. This is a serious shortcoming since in many problems locating the valley that contains the minimum may be a problem as difficult as locating the minimum itself. We could say that deterministic methods are poor at ``exploration'' (locating the best valleys) but are very good at ``exploitation'' (given the valley, locating its floor).

Stochastic methods, on the other hand, perform a much more exhaustive search of the model space but are not as good at exploiting the early results of the search. It appears that a hybrid method combining the strengths of both techniques would be the best choice. The situation is not so clear cut, however, because it may be difficult to identify the most promising valleys and it may also be difficult to compute the derivatives of the cost function. In geophysics such a hybrid approach between a genetic algorithm and conjugate gradient was used to solve the problem of estimating velocities from refraction seismic data, although the results were not conclusively better than those obtained by the genetic algorithm alone Boschetti (1995).

An interesting alternative is the use of the so-called micro-genetic algorithms Krishnakumar (1989) which aim at improving the relatively poor exploitation characteristic of the genetic algorithms without affecting their strong exploration capabilities. In this paper I compare the results of applying both a standard and a micro-genetic algorithm to the problem of matching a seismic trace. This is part of the more interesting problem of inverting a zero-offset trace for interval velocities addressed in a companion paper in this report (). Figure  shows the input sub-sampled sonic log and the corresponding reference seismic trace obtained by a simple computation of the normal incidence reflection coefficients assuming no multiples, no absorption and no noise.

 

input
Figure 1 Left, sub-sampled sonic log used to generate the synthetic seismic trace on the right