1887
Volume 53, Issue 6
  • ISSN: 0812-3985
  • E-ISSN: 1834-7533

Abstract

This paper focuses on low computational efficiency in simulated annealing (SA) inversion of Transient Electromagnetic (TEM) data. Asynchronous multiple Markov chains (MMC) parallel strategy is a very promising SA acceleration method, which can be accelerated almost linearly. However, this method also reduces the accuracy of the solution. To overcome this problem, we added the solution set strategy to the asynchronous MMC parallel simulated annealing (PSA) algorithm for the first time. In this new algorithm, each thread independently searches for direction and exchanges data with the solution set in the shared memory. We used both the synthetic and field data to test the new algorithm. The synthetic data tests showed that the MMC PSA results are better than those of the original MMC PSA. We analyzed the efficiency of the new algorithm. Compared with the sequential VFSA, the maximum speedup of the new algorithm is approximately 10 times. The field data test also showed that the improved MMC PSA algorithm has good practicability. These tests demonstrate that the improved algorithm is effective, showing that its convergence speed is greatly improved without reducing the accuracy.

© 2022 Australian Society of Exploration Geophysicists
Loading

Article metrics loading...

/content/journals/10.1080/08123985.2022.2027730
2022-11-02
2026-01-21

  • From This Site

    /content/journals/10.1080/08123985.2022.2027730
    dcterms_title,dcterms_subject,pub_keyword
    -contentType:Journal -contentType:Contributor -contentType:Concept -contentType:Institution
    10
    5
Loading full text...

Full text loading...

References

  1. Aarts, E., and J.Korst. 1988. Simulated annealing and boltzmann machines. New York: John Wiley & Sons. 272
  2. Arkat, J., M.Saidi, and B.Abbasi. 2007. Applying simulated annealing to cellular manufacturing system design. International Journal of Advanced Manufacturing Technology32 no. 5-6: 531–536. doi:10.1007/s00170‑005‑0358‑5.
     https://doi.org/10.1007/s00170-005-0358-5 [Google Scholar]
  3. Banerjee, P., and M.Jones. 1986. A parallel simulated annealing algorithm for standard cell placement on a hypercube computer. IEEE International Conference On Computer-Aided Design: Iccad-86. A Conference for the Ee Cad Professional. Digest of Technical Papers, 34–37.
  4. Beaty, K.S., D.R.Schmitt, and M.Sacchi. 2002. Simulated annealing inversion of multimode Rayleigh wave dispersion curves for geological structure. Geophysical Journal International151 no. 2: 622–631. doi:10.1046/j.1365‑246X.2002.01809.x.
     https://doi.org/10.1046/j.1365-246X.2002.01809.x [Google Scholar]
  5. Bhattacharya, B.B., Shalivahan, and M.K. Sen. 2003. Use of vfsa for resolution, sensitivity and uncertainty analysis in 1d dc resistivity and ip inversion. Geophysical Prospecting51 no. 5: 393–408. doi:10.1046/j.1365‑2478.2003.00379.x.
     https://doi.org/10.1046/j.1365-2478.2003.00379.x [Google Scholar]
  6. Chandy, J., S.Kim, B.Ramkumar, S.Parkes, and P.Banerjee. 1997. An evaluation of parallel simulated annealing strategies with application to standard cell placement. IEEE Transactions On Computer-Aided Design of Integrated Circuits and Systems16 no. 4: 398–410. doi:10.1109/43.602476.
     https://doi.org/10.1109/43.602476 [Google Scholar]
  7. Chang, Y.L., K.S.Chen, B.Huang, W.-Y.Chang, J.A.Benediktsson, and L.Chang. 2011. A parallel simulated annealing approach to band selection for high-dimensional remote sensing images. IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing4 no. 3: 579–590. doi:10.1109/JSTARS.2011.2160048.
     https://doi.org/10.1109/JSTARS.2011.2160048 [Google Scholar]
  8. Chauhan, M.S., M.Fedi, and M.K.Sen. 2018. Gravity inversion by the multi-homogeneity depth estimation method for investigating salt domes and complex sources. Geophysical Prospecting66: 175–191. doi:10.1111/1365‑2478.12603.
     https://doi.org/10.1111/1365-2478.12603 [Google Scholar]
  9. Chen, W., H.Li, G.Xue, K.Chen, and H.-S.Zhong. 2017. 1D occam inversion of SOTEM data and its application to 3D models. Chinese Journal of Geophysics-Chinese Edition60 no. 9: 3667–3676. doi:10.6038/cjg20170930.
     https://doi.org/10.6038/cjg20170930 [Google Scholar]
  10. Constable, S., R.Parker, and C.Constable. 1987. Occam’s inversion: A practical algorithm for generating smooth models from electromagnetic sounding data. Geophysics52 no. 3: 289–300. doi:10.1190/1.1442303.
     https://doi.org/10.1190/1.1442303 [Google Scholar]
  11. Dantas, B.D., and E.N.Caceres. 2016. A parallelization of a simulated annealing approach for 0-1 multidimensional knapsack problem using gpgpu. 28th IEEE International Symposium on Computer Architecture and High Performance Computing (SBAC-PAD), 134–140. doi:10.1109/SBAC‑PAD.2016.25.
     https://doi.org/10.1109/SBAC-PAD.2016.25
  12. Datta, D., M.Sen, F.Liu, and S.Morton. 2019. Full-waveform inversion of salt models using shape optimization and simulated annealing. Geophysics84 no. 5: R793–R804. doi:10.1190/GEO2018‑0175.1.
     https://doi.org/10.1190/GEO2018-0175.1 [Google Scholar]
  13. Defersha, F., and M.Chen. 2008. A parallel multiple markov chain simulated annealing for multi-period manufacturing cell formation problems. International Journal of Advanced Manufacturing Technology37 no. 1-2: 140–156. doi:10.1007/s00170‑007‑0947‑6.
     https://doi.org/10.1007/s00170-007-0947-6 [Google Scholar]
  14. Di, Q., H.Li, G.Xue, and L.Zhang. 2020. Pseudo-2D Trans-dimensional Bayesian inversion of the full waveform TEM response from PRBS source. IEEE Transactions on Geoscience and Remote Sensing58 no. 11: 7602–7610. doi:10.1109/TGRS.2020.2982442.
     https://doi.org/10.1109/TGRS.2020.2982442 [Google Scholar]
  15. Dittmer, J., and J.Szymanski. 1995. The stochastic inversion of magnetics and resistivity data using the simulated annealing algorithm. Geophysical Prospecting43 no. 3: 397–416. doi:10.1111/j.1365‑2478.1995.tb00259.x.
     https://doi.org/10.1111/j.1365-2478.1995.tb00259.x [Google Scholar]
  16. Gokturkler, G., and C.Balkaya. 2012. Inversion of self-potential anomalies caused by simple-geometry bodies using global optimization algorithms. Journal of Geophysics and Engineering9 no. 5: 498–507. doi:10.1088/1742‑2132/9/5/498.
     https://doi.org/10.1088/1742-2132/9/5/498 [Google Scholar]
  17. Goffe, W.L., G.D.Ferrier, and J.Rogers. 1994. Global optimization of statistical functions with simulated annealing. Journal of Econometrics60 no. 1-2: 65–99. doi:10.1016/0304‑4076(94)90038‑8.
     https://doi.org/10.1016/0304-4076(94)90038-8 [Google Scholar]
  18. Greening, D.1990. Parallel simulated annealing techniques. Physica D: Nonlinear Phenomena42 no. 1-3: 293–306. doi:10.1016/0167‑2789(90)90084‑3.
     https://doi.org/10.1016/0167-2789(90)90084-3 [Google Scholar]
  19. Gribenko, A., and M.Zhdanov. 2007. Rigorous 3d inversion of marine csem data based on the integral equation method. Geophysics72 no. 2: WA73–WA84. doi:10.1190/1.2435712.
     https://doi.org/10.1190/1.2435712 [Google Scholar]
  20. Hajek, B.1988. Cooling schedules for optimal annealing. Mathematics of Operations Research13 no. 2: 311–329. doi:10.1287/moor.13.2.311.
     https://doi.org/10.1287/moor.13.2.311 [Google Scholar]
  21. He, Z., X.Suo, Z.Hu, Y.Shi, D.Shi, and W.Dong. 2019. Time-frequency electromagnetic method for exploring favorable deep igneous rock targets: a case study from north xinjiang. Journal of Environmental and Engineering Geophysics24 no. 2: 215–224. doi:10.2113/JEEG24.2.215.
     https://doi.org/10.2113/JEEG24.2.215 [Google Scholar]
  22. Holland, J.H.1975. Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence. Michigan: University of Michigan Press. 183
  23. Ingber, L.1989. Very fast simulated re-annealing. Mathematical and Computer Modelling12 no. 8: 967–973. doi:10.1016/0895‑7177(89)90202‑1.
     https://doi.org/10.1016/0895-7177(89)90202-1 [Google Scholar]
  24. Kennedy, J., and R.Eberhart. 1995. Particle swarm optimization. 1995 IEEE International Conference on Neural Networks Proceedings, 1942-1948. doi:10.1109/ICNN.1995.488968.
     https://doi.org/10.1109/ICNN.1995.488968
  25. Kirkpatrick, S., C.D.Gelatt, and M.P.Vecchi. 1983. Optimization by simulated annealing. Science220 no. 4598: 671–680. doi:10.1126/science.220.4598.671.
     https://doi.org/10.1126/science.220.4598.671 [Google Scholar]
  26. Lee, S.Y., and K.G.Lee. 1996. Synchronous and asynchronous parallel simulated annealing with multiple markov chains. IEEE Transactions On Parallel and Distributed Systems7 no. 10: 993–1008. doi:10.1109/71.539732.
     https://doi.org/10.1109/71.539732 [Google Scholar]
  27. Li, N., J.Cha, and Y.Lu. 2010. A parallel simulated annealing algorithm based on functional feature tree modeling for 3d engineering layout design. Applied Soft Computing10 no. 2: 592–601. doi:10.1016/j.asoc.2009.08.033.
     https://doi.org/10.1016/j.asoc.2009.08.033 [Google Scholar]
  28. Li, H., G.Xue, and L.Zhang. 2020. Accelerated Bayesian inversion of transient electromagnetic data using MCMC subposteriors. IEEE Transactions on Geoscience and Remote Sensing59 no. 12: 10000–10010. doi:10.1109/TGRS.2020.3035390.
     https://doi.org/10.1109/TGRS.2020.3035390 [Google Scholar]
  29. Li, H., G.Xue, P.Zhao, N.Zhou, and H.Zhong. 2016. Inversion of arbitrary segmented loop source TEM data over a layered earth. Journal of Applied Geophysics128: 87–95. doi:10.1016/j.jappgeo.2016.03.017.
     https://doi.org/10.1016/j.jappgeo.2016.03.017 [Google Scholar]
  30. Metropolis, N., A.W.Rosenbluth, M.N.Rosenbluth, A.H.Teller, and E.Teller. 1953. Equation of state calculations by fast computing machines. Journal of Chemical Physics21 no. 6: 1087–1092. doi:10.1063/1.1699114.
     https://doi.org/10.1063/1.1699114 [Google Scholar]
  31. Mirkin, G., K.Vasudevan, F.A.Cook, W.G.Laidlaw, and W.G.Wilson. 1993. A comparison of several cooling schedules for simulated annealing implemented on a residual statics problem. Geophysical Research Letters20 no. 1: 77–80. doi:10.1029/92GL03024.
     https://doi.org/10.1029/92GL03024 [Google Scholar]
  32. Moharil, S., and S.Y.Lee. 2011. Load balancing on temporally heterogeneous cluster of workstations for parallel simulated annealing. Cluster Computing-the Journal of Networks Software Tools and Applications14 no. 4: 295–310. doi:10.1007/s10586‑010‑0148‑1.
     https://doi.org/10.1007/s10586-010-0148-1 [Google Scholar]
  33. Mundim, K.C., T.J.Lemaire, and A.Bassrei. 1998. Optimization of non-linear gravity models through generalized simulated annealing. Physica A: Statistical Mechanics and its Applications252 no. 3-4: 405–416. doi:10.1016/S0378‑4371(97)00634‑1.
     https://doi.org/10.1016/S0378-4371(97)00634-1 [Google Scholar]
  34. Munkholm, M.S., and E.Auken. 1996. Electromagnetic noise contamination on transient electromagnetic soundings in culturally disturbed environments. Journal of Environmental and Engineering Geophysics1 no. 2: 119–127. doi:10.4133/JEEG1.2.119.
     https://doi.org/10.4133/JEEG1.2.119 [Google Scholar]
  35. Onbasoglu, E., and L.Ozdamar. 2001. Parallel simulated annealing algorithms in global optimization. Journal of Global Optimization19 no. 1: 27–50. doi:10.1023/A:1008350810199.
     https://doi.org/10.1023/A:1008350810199 [Google Scholar]
  36. Parnow, S., B.Oskooi, and G.Florio. 2021. Improved linear inversion of low induction number electromagnetic data. Geophysical Journal International224 no. 3: 1505–1522. doi:10.1093/gji/ggaa531.
     https://doi.org/10.1093/gji/ggaa531 [Google Scholar]
  37. Sait, S.M., A.M.Zaidi, M.I.Ali, K.S.Khan, and S.Syed. 2011. Exploring asynchronous mmc-based parallel sa schemes for multiobjective cell placement on a cluster of workstations. Arabian Journal for Science and Engineering36 no. 2: 259–278. doi:10.1007/s13369‑010‑0024‑6.
     https://doi.org/10.1007/s13369-010-0024-6 [Google Scholar]
  38. Sharifi, F., A.Arab-Amiri, A.Kamkar-Rouhani, and R.-U.Börner. 2020. Development of a novel approach for recovering sip effects from 1-d inversion of hem data: case study from the alut area, northwest of Iran. Journal of Applied Geophysics174, doi:10.1016/j.jappgeo.2020.103962.
     https://doi.org/10.1016/j.jappgeo.2020.103962 [Google Scholar]
  39. Trapp, M., and T.Nestorovic. 2020. Reconstruction of structural anomalies out of seismic measurements by means of a non-deterministic full waveform inversion approach for application in mechanized tunneling. Journal of Applied Geophysics182, doi:10.1016/j.jappgeo.2020.104180.
     https://doi.org/10.1016/j.jappgeo.2020.104180 [Google Scholar]
  40. Wang, R., C.C.Yin, M.Y.Wang, and G.Wang. 2012. Simulated annealing for controlled-source audio-frequency magnetotelluric data inversion. Geophysics77 no. 2: E127–E133. doi:10.1190/GEO2011‑0106.1.
     https://doi.org/10.1190/GEO2011-0106.1 [Google Scholar]
  41. Witte, E.E., R.D.Chamberlain, and M.A.Franklin. 1991. Parallel simulated annealing using speculative computation. IEEE Transactions On Parallel and Distributed Systems2 no. 4: 483–494. doi:10.1109/71.97904.
     https://doi.org/10.1109/71.97904 [Google Scholar]
  42. Yang, J., Z.Luo, and L.Tu. 2020. Ocean access to zachari ae isstrom glacier, northeast Greenland, revealed by omg airborne gravity. Journal of Geophysical Research-Solid Earth125 no. 11, doi:10.1029/2020JB020281.
     https://doi.org/10.1029/2020JB020281 [Google Scholar]
  43. Yin, C.C., and G.Hodges. 2007. Simulated annealing for airborne em inversion. Geophysics72 no. 4: F189–F195. doi:10.1190/1.2736195.
     https://doi.org/10.1190/1.2736195 [Google Scholar]
  44. Zhang, L., T.Koyama, H.Utada, P.Yu, and J.Wang. 2012. A regularized three-dimensional magnetotelluric inversion with a minimum gradient support constraint. Geophysical Journal International189 no. 1: 296–316. doi:10.1111/j.1365‑246X.2012.05379.x.
     https://doi.org/10.1111/j.1365-246X.2012.05379.x [Google Scholar]
/content/journals/10.1080/08123985.2022.2027730
Loading
Asynchronous MMC PSA inversion of transient electromagnetic data
Exploration Geophysics 53, 602 (2022); https://doi.org/10.1080/08123985.2022.2027730
/content/journals/10.1080/08123985.2022.2027730
/content/journals/10.1080/08123985.2022.2027730
Loading

Data & Media loading...

  • Article Type: Research Article
Keyword(s): asynchronous multiple Markov chains; Ground transient electromagnetic; inversion; parallelization; solution set; very fast simulated annealing

Most Cited This Month Most Cited RSS feed

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