The group search-based parallel algorithm for the serial Monte Carlo inversion method
Wei Chao1, Li Xiao-Fan2, and Zheng Xiao-Dong1
1. Research Institute of Petroleum Exploration and Development, PetroChina, Beijing, 100083.
2. Institute of Geology and Geophysics, CAS, Beijing, 100029.
Abstract With the development of parallel computing technology, non-linear inversion calculation efficiency has been improving. However, for single-point search-based non-linear inversion methods, the implementation of parallel algorithms is a difficult issue. We introduce the idea of group search to the single-point search-based non-linear inversion algorithm, taking the quantum Monte Carlo method as an example for two-dimensional seismic wave velocity inversion and practical impedance inversion and test the calculation efficiency of using different node numbers. The results show the parallel algorithm in theoretical and practical data inversion is feasible and effective. The parallel algorithm has good versatility. The algorithm efficiency increases with increasing node numbers but the algorithm efficiency rate of increase gradually decreases as the node numbers increase.
This research was supported by National Key S &T Special Projects of Marine Carbonate (No. 2008ZX05000-004), CNPC Projects (No. 2008E-0610-10).
Cite this article:
WEI Chao,LI Xiao-Fan,ZHENG Xiao-Dong. The group search-based parallel algorithm for the serial Monte Carlo inversion method[J]. APPLIED GEOPHYSICS, 2010, 7(2): 127-134.
[1]
Aarts, E. H. L., de Bont, F. M. J., Habers, E. H. A., and van Laarhoven, P. J. M., 1986, Parallel implementations of the statistical cooling algorithm: Integration, the VLSI Journal, 4(3), 209 - 238.
[2]
Backus, G. E., and Gilbert, J. F., 1967, Numerical application of a formulism for geophysical inversion: Geophysical Journal of the Royal Astronomical Society, 13(1 - 3), 247 - 276.
[3]
———1968, The resolving power of gross earth data: Geophysical Journal of the Royal Astronomical Society, 16(2), 169 - 205.
[4]
———1970, Uniqueness in the inversion of inaccurate gross earth data: Mathematical and Physical Sciences, 266, 123 - 192.
[5]
Ceperley, D. M., and Alder, B. J., 1986, Quantum Monte Carlo: Science, 231(4738), 555 - 560.
[6]
Chen, H., Flann, N. S., and Watson, D. W, 1998, Parallel genetic simulated annealing: A massively parallel SIMD algorithm: IEEE Transactions on Parallel and Distributed Systems, 9(2), 126 - 136.
[7]
Choi, C., and Lee, J., 1998, Chaotic local search algorithm: Artificial Life and Robotics, 2(1), 41 - 47.
[8]
Teng, C. X., and Li, Z. H., 2002, Theory and application of bi-level programming: Science Press, Beijing, 84 - 92.
[9]
Donsker, M. D., and Kac, M., 1950, A sampling method for determining the lowest eigenvalue and the principal eigenfunction of the Schrödinger equation: Journal of Research of the National Bureau of Standards, 44(50), 551 - 557.
[10]
Esin, O., and Liner, O., 2001, Parallel simulated annealing algorithm in global optimization: Journal of Global Optimization, 19(1), 27 - 50.
[11]
Hammersley, J. M., and Handscomb, D. C., 1964, Monte Carlo methods: Chapman and Hall, London and New York.
[12]
Huang, L., and Li, C. H., 2003, Simulated annealing and parallel realization: Application on VLSI block placement: Journal of Xiamen University (Natural Science), 42(1), 21 - 28.
[13]
Ingber, L., 1992, Genetic algorithms and very fast simulated reannealing: a comparison: Math Computer Modeling, 16(3), 87 - 100.
[14]
Janakipam, D., Sreenivas, T. H., and Subramaniam, K. G., 1996, Parallel simulated annealing algorithms: Journal of Parallel and Distributed Computing, 37(2), 207 - 212.
[15]
Lee, S. Y., and Lee, K. G., 1992, Asynchronous communication of multiple Markov chains in parallel simulated annealing: Proceedings of the International Conference on Parallel Processing, 169 - l76.
[16]
Li, B., and Jiang, W. S., 1997, Chaos optimization algorithm and its application: Control Theory and Applications, 14(4), 613 - 615.
[17]
Li, S. Y., Du, Z. H., and Wu, M. Y., 2001, Parallel realization of simulated annealing algorithm: Modifications and applications: Acta Physica Sinica, 50(7), 1260 - 1263.
[18]
Luo, Y. Z., and Tang, G. J., 2005, Global optimization of bilevel nonlinear programming problems by parallel simulated annealing: Acta Simulata Systematica Sinica, 17(5), 1040 - 1044.
[19]
Mahfoud, S. W., and Goldberg, D. E., 1992, Parallel recombinative simulated annealing: A genetic algorithm: Illigal report 92002, University of Illinois, Urbana, IL 61801 - 2996.
[20]
Ming, T. F., Zhang, Y. X., and Piao, J. Z., 2003, Application of parallel recombination simulated annealing algorithms in fault identification: China Mechanical Engineering, 14(17), 1496 - 1498.
[21]
Onba?o?lu, E., and Özdamar, L., 2001, Parallel simulated annealing: Algorithms in global optimization: Journal of Global Optimization, 19(1), 27 - 50.
[22]
Press, W. H., Teukolsky, S. A., Vetterling, W. T., 2002, Numerical recipes in C++: The art of scientific computing: Cambridge University Press, 448 - 459.
[23]
Rothman, D. H., 1985, Nonlinear inversion statistical mechanics and residual statics correction: Geophysics, 50(12), 2784 - 2796.
[24]
———1986, Automatic estimation of large residual statics corrections: Geophysics, 51(2), 332 - 346.
[25]
Sambridge, M. S., 1999a, Geophysical inversion with a neighborhood algorithm - Ι: Searching a parameter space: Geophysics Journal International, 138(2), 479-494.
[26]
———1999b, Geophysical inversion with a neighborhood algorithm - II: Appraising the ensemble: Geophysics Journal International, 138(2), 727 - 746.
[27]
Shu, W. N., and Zheng, S. J., 2006, A parallel genetic simulated annealing hybrid algorithm for task scheduling: Wuhan University Journal of Natural Sciences, 11(5), 1378 - 1382.
[28]
Sun, X. P., and Zhang, S. H., 2004, The overall optimization algorithm based on parallel recombination simulated annealing: Journal of Xi an University of Technology, 20(4), 396 - 399.
[29]
Szu, H., and Hartly, R., 1987, Fast simulated annealing: Physics Letters A, 122(3), 157 - 162.
[30]
Tang, L. S., Xie, Y., and You, S. Y., 1994, Non-numerical parallel algorithms-simulated annealing method: Science Press, Beijing.
[31]
Wang, H., and Tang, G. J., 2005, An asynchronous parallel simulated annealing algorithm for function optimization problems: Control and Decision, 20(5), 579 - 582.
[32]
Wei, C., Li, X. F., and Zhang, M. G., 2008, Geophysical inverse method based on quantum Monte Carlo: Chinese Journal of Geophysics, 51(5), 1494 - 1502.
[33]
Wen, P. C., Xu, X. D., and He, X. G., 2003, Parallel genetic algorithm/simulated annealing hybrid algorithm and its applications: Computer Science, 30(3), 86 - 89.
[34]
Xi, Q. Y., Xie, X. P., and Huang, Q., 2006, Study on flood zoom model based on genetic algorithm and parallel recombination simulated annealing algorithm: Journal of Hydroelectric Engineering, 25(1), 108 - 113.
2010, Vol. 7 
