Genetic Algorithm

We use knowledge of surface geology to divide the investigated region (the earth's cross-section) into N_x segments horizontally and N_z segments vertically. Velocities in the model are allowed to vary between 1.8 and 7.2 km/sec which is a reasonable range for seismic waves [Pullammanappallil, 1994]. Instead of using a binary string encoding, we use a real number 2D chromosome representing the velocity at each cell.

We try to find an optimal velocity model to fit synthetic seismic data sets. The C source code which calculates the error between the calculated travel times and the observed travel times was provided to us. It simulates the path of a seismic wave through the candidate model from each source to all receivers. The genetic algorithm minimizes the error between the times taken by seismic waves through the candidate model and the observed travel times. The error is given by the function:

$$E = {1 \over n}\sum\nolimits^{n}_{j=1}({t_j}^{obs}-{t_j}^{cal})^2$$

where n is the number of observations, j denotes each observation, and t^obs and t^cal are the observed (data) and calculated travel times respectively. Individuals in the initial population are randomized constant velocity models in which velocities in all cells are assigned to the same randomly generated value between 1.8 and 7.2 km/sec.

Selection, crossover and mutation together act on the old population to produce the new population. We use elitist selection and randomly choose individuals to mate. Each pair of parents produces two children through crossover and/or mutation. After sorting the new individuals together with the old individuals, we choose the best N (population size) individuals to be in the new population [Eshelman, 1990]. The velocity estimation problem has a very large search space. If we use five bits to encode the velocity range from 1.8 to 7.2 km/sec, the total number of possible models is ${2^{5 \times N_x \times N_z}}$. Since N_x and N_z are 40 and 8 or 9 in our experiments (and can be much larger) leading to a 2¹⁸⁰⁰ sized search space, we shift the balance toward more exploitation by using elitist selection and our partially random initialization.

We use four types of crossover operators in this paper, 1D simple real crossover (1Ds), 1D real crossover (1D), 2D simple real crossover (2Ds), and 2D real crossover (2D). When we apply crossover to real chromosomes, the crossover point can be allowed to fall only between the binary codes for two parameters or also within the binary code for a parameter. We call the former simple real crossover, and the latter real crossover [Wright, 1990]. When we consider the velocity model a 1D array, the 1D crossover operator implements one-point real crossover and the 1Ds crossover operator implements one-point simple real crossover.

The 2D crossover operator is presented in Figure 3 [Li et al., 1995]. We flip a coin to decide whether to do crossover vertically or horizontally. If we do crossover vertically, we randomly choose two different numbers which are smaller than N_x*B where B is the number of bits to represent a real number velocity in the range from 1.8 to 7.2 km/sec. A similar approach is used for the horizontal direction. The 2Ds crossover operator is a special case for the 2D crossover where simple real crossover is implemented in choosing the crossover points.

  

Figure 3: The two dimensional crossover operators: Crossovers along the horizontal direction and the vertical direction.

The mutation operator used in this paper is different from that used in simple GAs. For the velocity estimation problem, we randomly choose two points in the velocity model plane to form a rectangular block region, and velocities in the block are set to a constant random value in the range of 1.8 to 7.2 km/sec.