1887
image of Comparing the performances of four stochastic optimisation methods using analytic objective functions, 1D elastic full‐waveform inversion, and residual static computation

Abstract

ABSTRACT

We compare the performances of four stochastic optimisation methods using four analytic objective functions and two highly non‐linear geophysical optimisation problems: one‐dimensional elastic full‐waveform inversion and residual static computation. The four methods we consider, namely, adaptive simulated annealing, genetic algorithm, neighbourhood algorithm, and particle swarm optimisation, are frequently employed for solving geophysical inverse problems. Because geophysical optimisations typically involve many unknown model parameters, we are particularly interested in comparing the performances of these stochastic methods as the number of unknown parameters increases. The four analytic functions we choose simulate common types of objective functions encountered in solving geophysical optimisations: a convex function, two multi‐minima functions that differ in the distribution of minima, and a nearly flat function. Similar to the analytic tests, the two seismic optimisation problems we analyse are characterised by very different objective functions. The first problem is a one‐dimensional elastic full‐waveform inversion, which is strongly ill‐conditioned and exhibits a nearly flat objective function, with a valley of minima extended along the density direction. The second problem is the residual static computation, which is characterised by a multi‐minima objective function produced by the so‐called cycle‐skipping phenomenon. According to the tests on the analytic functions and on the seismic data, genetic algorithm generally displays the best scaling with the number of parameters. It encounters problems only in the case of irregular distribution of minima, that is, when the global minimum is at the border of the search space and a number of important local minima are distant from the global minimum. The adaptive simulated annealing method is often the best‐performing method for low‐dimensional model spaces, but its performance worsens as the number of unknowns increases. The particle swarm optimisation is effective in finding the global minimum in the case of low‐dimensional model spaces with few local minima or in the case of a narrow flat valley. Finally, the neighbourhood algorithm method is competitive with the other methods only for low‐dimensional model spaces; its performance sensibly worsens in the case of multi‐minima objective functions.

Loading

Article metrics loading...

/content/journals/10.1111/1365-2478.12532
2017-10-04
2020-04-06
Loading full text...

Full text loading...

References

  1. AguiareH., JuniorO., IngberL., PetragliaA., PetragliaM.R. and MachadoM.A.S.2012. Stochastic Global Optimization and Its Applications with Fuzzy Adaptive Simulated Annealing. Heidelberg: Springer.
    [Google Scholar]
  2. AleardiM.2015. Seismic velocity estimation from well log data with genetic algorithms in comparison to neural networks and multilinear approaches. Journal of Applied Geophysics117, 13–22.
    [Google Scholar]
  3. AleardiM. and CiabarriF.2017. Assessment of different approaches to rock‐physics modeling: a case study from offshore Nile Delta. Geophysics82(1), MR15–MR25.
    [Google Scholar]
  4. AleardiM. and MazzottiA.2017. 1D elastic full‐waveform inversion and uncertainty estimation by means of a hybrid genetic algorithm—Gibbs sampler approach. Geophysical Prospecting65(1), 64–85.
    [Google Scholar]
  5. AleardiM., TognarelliA. and MazzottiA.2016. Characterisation of shallow marine sediments using high‐resolution velocity analysis and genetic‐algorithm‐driven 1D elastic full‐waveform inversion. Near Surface Geophysics14(5), 449–460.
    [Google Scholar]
  6. AnderssenR.S.1970. The character of non‐uniqueness in the conductivity modelling problem for the Earth. Pure and Applied Geophysics80(1), 238–259.
    [Google Scholar]
  7. BäckT. and HoffmeisterF.1991. Extended Selection Mechanisms in Genetic Algorithms. Proceedings of the 4th International Conference on Genetic Algorithms, 92–99.
    [Google Scholar]
  8. BackusG. and GilbertF.1968. The resolving power of gross Earth data. Geophysical Journal of the Royal Astronomical Society16, 169–205.
    [Google Scholar]
  9. BlickleT. and ThieleL.1995. A comparison of selection schemes used in genetic algorithms. TIK Report, 11.
  10. BulandR.1976. The mechanics of locating earthquakes. Bulletin of the Seismological Society of America66(1), 173–187.
    [Google Scholar]
  11. ChenH. and FlannN.S.1994. Parallel simulated annealing and genetic algorithms: a space of hybrid methods. In: Parallel Problem Solving from Nature. Berlin: Springer.
    [Google Scholar]
  12. ChenP.H. and ShahandashtiS.M.2009. Hybrid of genetic algorithm and simulated annealing for multiple project scheduling with multiple resource constraints. Automation in Construction18(4), 434–443.
    [Google Scholar]
  13. ClercM.1999. The swarm and queen: towards a deterministic and adaptive particle swarm optimization. Proceedings of the IEEE Congress on Evolutionary Computation, 1951–1957.
    [Google Scholar]
  14. ClercM. and KennedyJ.2002. The particle swarm—Explosion, stability, and convergence in a multidimensional complex space. IEEE Transactions on Evolutionary Computation6(1), 58–73.
    [Google Scholar]
  15. Fernández MartínezJ.L., GonzaloE.G., ÁlvarezJ.P.F., KuzmaH.A. and PérezC.O.M.2010. PSO: a powerful algorithm to solve geophysical inverse problems: application to a 1D‐DC resistivity case. Journal of Applied Geophysics71(1), 13–25.
    [Google Scholar]
  16. Fernández MartínezJ.L., MukerjiT., García GonzaloE. and Suman, A.2012. Reservoir characterization and inversion uncertainty via a family of particle swarm optimizers. Geophysics77(1), M1–M16.
    [Google Scholar]
  17. FliednerM.M., TreitelS. and MacGregorL.2012. Full‐waveform inversion of seismic data with the neighborhood algorithm. The Leading Edge31(5), 570–579.
    [Google Scholar]
  18. GoldbergD.E.1989. Genetic Algorithms in Search, Optimisation, and Machine Learning. Reading Menlo Park: Addison‐Wesley.
    [Google Scholar]
  19. HassanR., CohanimB., De WeckO. and VenterG.2005. A comparison of particle swarm optimisation and the genetic algorithm. Proceedings of the 1st AIAA Multidisciplinary Design Optimisation Specialist Conference, 18–21.
    [Google Scholar]
  20. HastingsW.K.1970. Monte Carlo sampling methods using Markov chain and their applications, Biometrika57, 97–109.
    [Google Scholar]
  21. HermanceJ.F. and GrillotL.R.1974. Constraints on temperatures beneath Iceland from magnetotelluric data. Physics of the Earth and Planetary Interiors8(1), p. 1–12.
    [Google Scholar]
  22. HollandJ.H.1975. Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence. Michigan: University Michigan Press.
    [Google Scholar]
  23. HorneS. and MacbethC.1998. A comparison of global optimisation methods for near‐offset VSP inversion. Computers and Geosciences24(6), 563–572.
    [Google Scholar]
  24. IngberL.1989. Very fast simulated re‐annealing. Mathematical and Computer Modelling12(8), 967–973.
    [Google Scholar]
  25. IngberL. and RosenB.1992. Genetic algorithms and very fast simulated reannealing: a comparison. Mathematical and Computer Modelling16(11), 87–100.
    [Google Scholar]
  26. JanikowC.Z. and Michalewicz, Z.1991. An experimental comparison of binary and floating point representations in genetic algorithms. Proceedings of International Conference on Genetic Algorithms, 31–36.
    [Google Scholar]
  27. JestinF., HuchonP. and GaulierJ.M.1994. The Somalia plate and the East‐African rift system—Present‐day kinematics. Geophysical Journal International116(3), 637–654.
    [Google Scholar]
  28. Keilis‐BorokV.I. and YanovskajaT.B.1967. Inverse problems of seismology (structural review). Geophysical Journal International13(1–3), 223–234.
    [Google Scholar]
  29. KennedyJ. and EberhartR.1995. Particle swarm optimisation. Proceedings of the IEEE International Conference on Neural Networks4, 1942–1948.
    [Google Scholar]
  30. KennedyJ., EberhartR.C. and ShiY.2001. Swarm Intelligence. San Francisco: Morgan Kaufmann.
    [Google Scholar]
  31. KennettB.L.1983. Seismic Wave Propagation in Stratified Media. Cambridge, UK: Cambridge University Press.
    [Google Scholar]
  32. KirkpatrickS., GelattC.D. and VecchiM.P.1983. Optimisation by simulated annealing. Science220(4598), 671–680.
    [Google Scholar]
  33. LagosS.R., SabbioneJ.I. and VelisD.R.2014. Very fast simulated annealing and particle swarm optimisation for microseismic event location. 84th SEG meeting, Denver, USA, Expanded Abstracts, 2188–2192.
  34. LandaE., BeydounW. and TarantolaA.1989. Reference velocity model estimation from prestack waveforms: coherency optimisation by simulated annealing. Geophysics54(8), 984–990.
    [Google Scholar]
  35. LiT. and Mallick, S.2015. Multicomponent, multi‐azimuth pre‐stack seismic waveform inversion for azimuthally anisotropic media using a parallel and computationally efficient non‐dominated sorting genetic algorithm. Geophysical Journal International200(2), 1134–1152.
    [Google Scholar]
  36. Li‐PingZ., Huan‐JunY. and Shang‐XuH.2005. Optimal choice of parameters for particle swarm optimization. Journal of Zhejiang University Science A6(6), 528–534.
    [Google Scholar]
  37. Mallick, S.1999. Some practical aspects of prestack waveform inversion using a genetic algorithm: an example from the east Texas Woodbine gas sand. Geophysics64(2), 326–336.
    [Google Scholar]
  38. MallickS. and DuttaN.C.2002. Shallow water flow prediction using prestack waveform inversion of conventional 3D seismic data and rock modeling. The Leading Edge21(7), 675–680.
    [Google Scholar]
  39. Marson‐PidgeonK., KennettB.L.N. and SambridgeM.2000. Source depth and mechanism inversion at teleseismic distances using a neighborhood algorithm. Bulletin of the Seismological Society of America90(6), 1369–1383.
    [Google Scholar]
  40. MellmanG.R.1980. A method of body‐wave waveform inversion for the determination of Earth structure. Geophysical Journal of the Royal Astronomical Society62, 481–504.
    [Google Scholar]
  41. MillsJ.M. and FitchT.J.1977. Thrust faulting and crust–upper mantle structure in East Australia. Geophysical Journal International48(3), 351–384.
    [Google Scholar]
  42. MitchellM.1998. An Introduction to Genetic Algorithms. Cambridge, MA: MIT Press.
    [Google Scholar]
  43. NolteB. and FrazerL.N.1994. Vertical seismic profile inversion with genetic algorithms. Geophysical Journal International117(1), 162–178.
    [Google Scholar]
  44. Padhi, A. and MallickS.2014. Multicomponent pre‐stack seismic waveform inversion in transversely isotropic media using a non‐dominated sorting genetic algorithm. Geophysical Journal International196(3), 1600–1618.
    [Google Scholar]
  45. PeiD., LouieJ.N. and PullammanappallilS.K.2007. Application of simulated annealing inversion on high‐frequency fundamental‐mode Rayleigh wave dispersion curves. Geophysics72(5), R77–R85.
    [Google Scholar]
  46. PressF.1968. Earth models obtained by Monte Carlo inversion. Journal of Geophysical Research73(16), 5223–5234.
    [Google Scholar]
  47. RobinsonJ. and Rahmat‐SamiiY.2004. Particle swarm optimization in electromagnetics. IEEE Transactions on Antennas and Propagation52(2), 397–407.
    [Google Scholar]
  48. RothmanD.H.1985. Nonlinear inversion, statistical mechanics, and residual statics estimation. Geophysics50(12), 2784–2796.
    [Google Scholar]
  49. RothmanD.H.1986. Automatic estimation of large residual statics corrections. Geophysics51(2), 332–346.
    [Google Scholar]
  50. RydenN. and ParkC.B.2006. Fast simulated annealing inversion of surface waves on pavement using phase‐velocity spectra. Geophysics71(4), R49–R58.
    [Google Scholar]
  51. SajevaA., AleardiM., MazzottiA., BienatiN. and StucchiE.2014. Estimation of velocity macro‐models using stochastic full‐waveform inversion. 84th SEG Meeting, Denver, USA, Expanded Abstracts, 1227–1231.
  52. SajevaA., AleardiM., StucchiE., BienatiN. and MazzottiA.2016. Estimation of acoustic macro‐models using genetic full‐waveform inversion: applications to the Marmousi model. Geophysics81(4), 1–12.
    [Google Scholar]
  53. SajevaA., AleardiM. and MazzottiA.2016. Combining genetic algorithms, Gibbs sampler, and gradient‐based inversion to estimate uncertainty in 2D FWI. 78th EAGE Conference and Exhibition, Vienna, Austria.
  54. SambridgeM.1999a. Geophysical inversion with a neighbourhood algorithm—I. Searching a parameter space. Geophysical Journal International138(2), 479–494.
    [Google Scholar]
  55. SambridgeM.1999b. Geophysical inversion with a neighbourhood algorithm—II. Appraising the ensemble. Geophysical Journal International138(3), 727–746.
    [Google Scholar]
  56. ScalesJ.A., SmithM.L. and FischerT.L.1992. Global optimisation methods for multimodal inverse problems. Journal of Computational Physics103(2), 258–268.
    [Google Scholar]
  57. Schlierkamp‐VoosenD. and MühlenbeinH.1993. Predictive models for the breeder genetic algorithm. Evolutionary Computation1(1), 25–49.
    [Google Scholar]
  58. Sen, M.K. and StoffaP.L.1991. Nonlinear one‐dimensional seismic waveform inversion using simulated annealing. Geophysics56(10), 1624–1638.
    [Google Scholar]
  59. Sen, M.K. and StoffaP.L.1992. Rapid sampling of model space using genetic algorithms: examples from seismic waveform inversion. Geophysical Journal International108(1), 281–292.
    [Google Scholar]
  60. SenM.K. and StoffaP.L.2013. Global Optimisation Methods in Geophysical Inversion. Cambridge, UK: Cambridge University Press.
    [Google Scholar]
  61. SivanandamS.N. and DeepaS.N.2008. Genetic Algorithm Optimisation Problems. Berlin: Springer.
    [Google Scholar]
  62. ShawR. and SrivastavaS.2007. Particle swarm optimisation: a new tool to invert geophysical data. Geophysics72(2), F75–F83.
    [Google Scholar]
  63. StoffaP.L. and SenM.K.1991. Nonlinear multiparameter optimization using genetic algorithms: inversion of plane‐wave seismograms. Geophysics56(11), 1794–1810.
    [Google Scholar]
  64. Voronoi, G.1908. Nouvelles applications des paramètres continus à la théorie des formes quadratiques. Premier mémoire. Sur quelques propriétés des formes quadratiques positives parfaites. Journal für die reine und angewandte Mathematik133, 97–178.
    [Google Scholar]
  65. WatheletM., JongmansD. and OhrnbergerM.2004. Surface‐wave inversion using a direct search algorithm and its application to ambient vibration measurements. Near Surface Geophysics2(4), 211–221.
    [Google Scholar]
  66. WigginsR.A.1972. The general linear inverse problem: implication of surface waves and free oscillations for Earth structure:Reviews of Geophysics and Space Physics10(1), 251–285.
    [Google Scholar]
http://instance.metastore.ingenta.com/content/journals/10.1111/1365-2478.12532
Loading
/content/journals/10.1111/1365-2478.12532
Loading

Data & Media loading...

  • Article Type: Research Article
Keywords: Optimisation; Stochastic
This is a required field
Please enter a valid email address
Approval was a Success
Invalid data
An Error Occurred
Approval was partially successful, following selected items could not be processed due to error