基于群体搜索的串行蒙特卡罗反演方法的并行算法(英文)
|
摘要
随着并行计算技术的发展,非线性反演计算效率在不断提高,但对于基于单点搜索的非线性反演方法,其并行算法的实现则是一个难题。本文将群体搜索的思想引入到基于单点搜索的非线性反演方法,构建了并行算法,以量子蒙特卡罗方法为例进行了二维地震波速度反演及实际资料波阻抗反演,并测试了使用不同节点数进行计算的效率。计算结果表明:该并行算法在理论和实际资料反演中是可行的和有效的,具有很好的通用性;算法计算效率随着使用节点数的增加而提高,但算法计算效率的提高幅度随着使用节点数的增加逐渐减小。
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.
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.
引文
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.
Backus,G.E.,and Gilbert,J.F.,1967,Numericaapplication of a formulism for geophysical inversionGeophysical Journal of the Royal Astronomical Society13(1-3),247-276.
——1968,The resolving power of gross earth data:Geophysical Journal of the Royal Astronomical Society,16(2),169-205.
——1970,Uniqueness in the inversion of inaccurate gross earth data:Mathematical and Physical Sciences,266,123-192.
Ceperley,D.M.,and Alder,B.J.,1986,Quantum Monte Carlo:Science,231(4738),555-560.
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.
Choi,C.,and Lee,J.,1998,Chaotic local search algorithm:Artifi cial Life and Robotics,2(1),41-47.
Teng,C.X.,and Li,Z.H.,2002,Theory and application of bi-level programming:Science Press,Beijing,84-92.
Donsker,M.D.,and Kac,M.,1950,A sampling methodfor determining the lowest eigenvalue and the principaleigenfunction of the Schr?dinger equation:Journal ofResearch of the National Bureau of Standards,44(50),551-557.
Esin,O.,and Liner,O.,2001,Parallel simulated annealingalgorithm in global optimization:Journal of GlobalOptimization,19(1),27-50.
Hammersley,J.M.,and Handscomb,D.C.,1964,Monte Carlo methods:Chapman and Hall,London and New York.
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.
Ingber,L.,1992,Genetic algorithms and very fast simulated reannealing:a comparison:Math Computer Modeling,16(3),87-100.
Janakipam,D.,Sreenivas,T.H.,and Subramaniam,K.G.,1996,Parallel simulated annealing algorithms:Journal of Parallel and Distributed Computing,37(2),207-212.
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.
Li,B.,and Jiang,W.S.,1997,Chaos optimization algorithm and its application:Control Theory and Applications,14(4),613-615.
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.
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.
Mahfoud,S.W.,and Goldberg,D.E.,1992,Parallel recombinative simulated annealing:A genetic algorithm:Illigal report92002,University of Illinois,Urbana,IL61801-2996.
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.
Onba?o?lu,E.,and?zdamar,L.,2001,Parallel simulated annealing:Algorithms in global optimization:Journal of Global Optimization,19(1),27-50.
Press,W.H.,Teukolsky,S.A.,Vetterling,W.T.,2002,Numerical recipes in C++:The art of scientific computing:Cambridge University Press,448-459.
Rothman,D.H.,1985,Nonlinear inversion statistical mechanics and residual statics correction:Geophysics,50(12),2784-2796.
——1986,Automatic estimation of large residual statics corrections:Geophysics,51(2),332-346.
Sambridge,M.S.,1999a,Geophysical inversion with a neighborhood algorithm-Ι:Searching a parameter space:Geophysics Journal International,138(2),479-494.
——1999b,Geophysical inversion with a neighborhood algorithm-II:Appraising the ensemble:Geophysics Journal International,138(2),727-746.
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.
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.
Szu,H.,and Hartly,R.,1987,Fast simulated annealing:Physics Letters A,122(3),157-162.
Tang,L.S.,Xie,Y.,and You,S.Y.,1994,Non-numericalparallel algorithms-simulated annealing method:SciencePress,Beijing.
Wang,H.,and Tang,G.J.,2005,An asynchronous parallel simulated annealing algorithm for function optimization problems:Control and Decision,20(5),579-582.
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.
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.
Xi,Q.Y.,Xie,X.P.,and Huang,Q.,2006,Study on?ood zoom model based on genetic algorithm and parallelrecombination simulated annealing algorithm:Journal of Hydroelectric Engineering,25(1),108-113.
Backus,G.E.,and Gilbert,J.F.,1967,Numericaapplication of a formulism for geophysical inversionGeophysical Journal of the Royal Astronomical Society13(1-3),247-276.
——1968,The resolving power of gross earth data:Geophysical Journal of the Royal Astronomical Society,16(2),169-205.
——1970,Uniqueness in the inversion of inaccurate gross earth data:Mathematical and Physical Sciences,266,123-192.
Ceperley,D.M.,and Alder,B.J.,1986,Quantum Monte Carlo:Science,231(4738),555-560.
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.
Choi,C.,and Lee,J.,1998,Chaotic local search algorithm:Artifi cial Life and Robotics,2(1),41-47.
Teng,C.X.,and Li,Z.H.,2002,Theory and application of bi-level programming:Science Press,Beijing,84-92.
Donsker,M.D.,and Kac,M.,1950,A sampling methodfor determining the lowest eigenvalue and the principaleigenfunction of the Schr?dinger equation:Journal ofResearch of the National Bureau of Standards,44(50),551-557.
Esin,O.,and Liner,O.,2001,Parallel simulated annealingalgorithm in global optimization:Journal of GlobalOptimization,19(1),27-50.
Hammersley,J.M.,and Handscomb,D.C.,1964,Monte Carlo methods:Chapman and Hall,London and New York.
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.
Ingber,L.,1992,Genetic algorithms and very fast simulated reannealing:a comparison:Math Computer Modeling,16(3),87-100.
Janakipam,D.,Sreenivas,T.H.,and Subramaniam,K.G.,1996,Parallel simulated annealing algorithms:Journal of Parallel and Distributed Computing,37(2),207-212.
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.
Li,B.,and Jiang,W.S.,1997,Chaos optimization algorithm and its application:Control Theory and Applications,14(4),613-615.
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.
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.
Mahfoud,S.W.,and Goldberg,D.E.,1992,Parallel recombinative simulated annealing:A genetic algorithm:Illigal report92002,University of Illinois,Urbana,IL61801-2996.
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.
Onba?o?lu,E.,and?zdamar,L.,2001,Parallel simulated annealing:Algorithms in global optimization:Journal of Global Optimization,19(1),27-50.
Press,W.H.,Teukolsky,S.A.,Vetterling,W.T.,2002,Numerical recipes in C++:The art of scientific computing:Cambridge University Press,448-459.
Rothman,D.H.,1985,Nonlinear inversion statistical mechanics and residual statics correction:Geophysics,50(12),2784-2796.
——1986,Automatic estimation of large residual statics corrections:Geophysics,51(2),332-346.
Sambridge,M.S.,1999a,Geophysical inversion with a neighborhood algorithm-Ι:Searching a parameter space:Geophysics Journal International,138(2),479-494.
——1999b,Geophysical inversion with a neighborhood algorithm-II:Appraising the ensemble:Geophysics Journal International,138(2),727-746.
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.
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.
Szu,H.,and Hartly,R.,1987,Fast simulated annealing:Physics Letters A,122(3),157-162.
Tang,L.S.,Xie,Y.,and You,S.Y.,1994,Non-numericalparallel algorithms-simulated annealing method:SciencePress,Beijing.
Wang,H.,and Tang,G.J.,2005,An asynchronous parallel simulated annealing algorithm for function optimization problems:Control and Decision,20(5),579-582.
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.
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.
Xi,Q.Y.,Xie,X.P.,and Huang,Q.,2006,Study on?ood zoom model based on genetic algorithm and parallelrecombination simulated annealing algorithm:Journal of Hydroelectric Engineering,25(1),108-113.
版权所有：© 2023 中国地质图书馆 中国地质调查局地学文献中心