Genetic algorithm design for ray tracing and hardware implementation

• Main Author: Lu, Shiliang, 1982-
• Other Authors: Memorial University of Newfoundland. Faculty of Engineering and Applied Science
• Format: Thesis
• Language: English
• Published: 2008
• Subjects: Genetic algorithms; Seismic traveltime inversion; Seismic waves > Computer simulation; Newfoundland studies; University of Newfoundland
• Online Access: http://collections.mun.ca/cdm/ref/collection/theses4/id/59637

Thesis (M.Eng.)--Memorial University of Newfoundland, 2008. Engineering and Applied Science Includes bibliographical references (leaves 77-80) Over the last 30 years, seismic ray tracing methods have played the important roles in the geophysical exploration and seismology. Various seismic ray tracing methods had been proposed, including ray bending and shooting methods based on the two-point ray tracing and graph theory based on the grids-algorithms. Each of these methods has its limitations, like shadow zone problem and nonlinear issues. In this thesis, we investigate the use of the genetic algorithms (GA), which are nonlinear global search algorithms, to improve upon these existing issues. Using a simpler continuous layer (polynomial based) function representation, ray tracing is accomplished by sampling each interface for a set of intersecting points. Based on these points, a ray path is traced from the shot point to a reflector interface back to the receiver. This process is similar to ray bending. The method for the generation of the interface points is a genetic algorithm and it finds the Fermat path of the least travel time. However, it is computational intensive. In order to improve the algorithm the run times are reduced by using the genetic algorithm to generate some of the interface layers points and using Snell's Law to bend the rays at other interface layers. We validate the suitability and correctness of the two proposed methods using seismic modeling and Pre-stack Kirchhoff migration. The results of Kirchhoff migration demonstrate that the reconstructed subsurface structures fit the real model very well, and also prove that the proposed methods are very effective seismic ray tracing methods. -- In addition, the hardware implementations are powerful approaches to accelerate our proposed ray tracing algorithms. Moreover, considering that the development of the hardware implementations did not attract much attention in geophysics, a purpose built, specific hardware algorithm is developed and a hardware engine is implemented in the low-cost field-programmable gate array (FPGA) device. The fixed-point arithmetic, the functional parallel design, the high efficiency sorting engine and the memoryless design for the velocity model work together to produce a comparable performance with IBM workstation. -- All results mentioned above demonstrate that the Pre-stack Kirchhoff migration and the hardware implementations of our seismic ray tracing methods are all feasible and the proposed approaches may be further extended for the more complex media.