On the computational cost and complexity of stochastic inverse solvers

Faliszewski, P.; Smołka, M.; Schaefer, R.; Paszyński, M.

doi:10.7494/csci.2016.17.2.225

Artykuł - szczegóły

Tytuł artykułu

On the computational cost and complexity of stochastic inverse solvers

Autorzy

Faliszewski P. , Smołka M. , Schaefer R. , Paszyński M.

Treść / Zawartość

Pełne teksty:

Pobierz

Identyfikatory

DOI

10.7494/csci.2016.17.2.225

Warianty tytułu

Języki publikacji

Abstrakty

The goal of this paper is to provide a starting point for investigations into a mainly underdeveloped area of research regarding the computational cost analysis of complex stochastic strategies for solving parametric inverse problems. This area has two main components: solving global optimization problems and solving forward problems (to evaluate the misfit function that we try to minimize). For the first component, we pay particular attention to genetic algorithms with heuristics and to multi-deme algorithms that can be modeled as ergodic Markov chains. We recall a simple method for evaluating the first hitting time for the single-deme algorithm and we extend it to the case of HGS, a multi-deme hierarchic strategy. We focus on the case in which at least the demes in the leaves are well tuned. Finally, we also express the problems of finding local and global optima in terms of a classic complexity theory. We formulate the natural result that finding a local optimum of a function is an NP-complete task, and we argue that finding a global optimum is a much harder, DP-complete, task. Furthermore, we argue that finding all global optima is, possibly, even harder (#P-hard) task. Regarding the second component of solving parametric inverse problems (i.e., regarding the forward problem solvers), we discuss the computational cost of hp-adaptive Finite Element solvers and their rates of convergence with respect to the increasing number of degrees of freedom. The presented results provide a useful taxonomy of problems and methods of studying the computational cost and complexity of various strategies for solving inverse parametric problems. Yet, we stress that our goal was not to deliver detailed evaluations for particular algorithms applied to particular inverse problems, but rather to try to identify possible ways of obtaining such results.

Słowa kluczowe

hierarchic genetic strategy inverse problem hybrid method

Wydawca

Wydawnictwa AGH

Czasopismo

Computer Science

Rocznik

2016

Tom

Vol. 17 (2)

Strony

225--264

Opis fizyczny

Bibliogr. 83 poz., rys.

Twórcy

autor

Faliszewski P.

faliszew@agh.edu.pl

AGH University of Science and Technology, Krakow, Poland

autor

Smołka M.

smolka@agh.edu.pl

AGH University of Science and Technology, Krakow, Poland

autor

Schaefer R.

schaefer@agh.edu.pl

AGH University of Science and Technology, Krakow, Poland

autor

Paszyński M.

paszynsk@agh.edu.pl

AGH University of Science and Technology, Krakow, Poland

Bibliografia

1. Allender E., Rubinstein R.: P-Printable Sets. In: SIAM Journal on Computing, vol. 17(6), pp. 1193-1202, 1988.
2. Babuška I., Guo B.: The hp-version of the finite element method, Part I: The basic approximation results. In: Computational Mechanics, vol. 1, pp. 21-41, 1986.
3. Babuška I., Guo B.: The hp-version of the finite element method, Part II: General results and applications. In: Computational Mechanics, vol. 1, pp. 203-220, 1986.
4. Banks H.T., Kunisch K.: Estimation Techniques for Distributed Parameter Systems. Birkhäuser, Boston, 1989.
5. Barabasz B., Gajda E., Migórski S., Paszyński M., Schaefer R.: Studying inverse problems in elasticity by hierarchic genetic search. In: ECCOMAS thematic conference on Inverse Problems in Mechanics of Structures and Materials, pp. 9-10. 2011.
6. Barabasz B., Gajda-Zagórska E., Migórski S., Paszyński M., Schaefer R., Smołka M.: A hybrid algorithm for solving inverse problems in elasticity. In: International Journal of Applied Mathematics and Computer Science, vol. 24(4), pp. 865-886, 2014.
7. Barabasz B., Migórski S., Schaefer R., Paszyński M.: Multi-deme, twin adaptive strategy hp-HGS. In: Inverse Problems in Science and Engineering, vol. 19(1), pp. 3-16, 2011.
8. Beume N., Laumanns M., Rudolph G.: Convergence Rates of (1+1) Evolutionary Multiobjective Optimization Algorithms. In: R. Schaefer, C. Cotta, J. Kołodziej, G. Rudolph, eds., Parallel Problem Solving from Nature - PPSN XI, Lecture Notes in Computer Science, vol. 6238, pp. 597-606. Springer, 2010.
9. Boender C., Rinnoy Kan A., Stougie L., Timmer G.: A Stochastic Method for Global Optimization. In: Mathematical Programming, vol. 22, pp. 125-140, 1982.
10. Burczyński T., Beluch W.: The Identification of Cracks Using Boundary Elements and Evolutionary Algorithms. In: Engineering Analysis with Boundary Elements, vol. 25(4-5), pp. 313-322, 2001.
11. Burczyński T., Kuś W., Długosz A., Orantek P.: Optimization and defect identification using distributed evolutionary algorithms. In: Engineering Applications of Artificial Intelligence, vol. 17(4), pp. 337-344, 2004.
12. Cabib E., Davini C., Chong-Quing R.: A problem in the optimal design of networks under transverse loading. Quarterly of Appl. Math., vol. 48(2), pp. 251-263, 1990.
13. Caicedo J.M., Yun G.: A novel evolutionary algorithm for identifying multiple alternative solutions in model updating. Structural Health Monitoring, vol. 10, pp. 491-501, 2011.
14. Ciarlet G.: The Finite Element Method for Elliptic Problems. North Holland, 1978.
15. Cook S.: The complexity of theorem-proving procedures. In: Proceedings of the 3rd ACM Symposium on Theory of Computing, pp. 151-158. ACM Press, 1971.
16. Demkowicz L.: Computing with hp-Adaptive Finite Elements, Vol. I. One and Two Dimensional Elliptic and Maxwell Problems. Chapman and Hall/CRC Applied Mathematics and Nonlinear Science, 2006.
17. Demkowicz L., Kurtz J., Pardo P., Paszyński M., Rachowicz W., Zdunek A.: Computing with hp-Adaptive Finite Elements, Vol. II. Frontiers: Three-Dimensional Elliptic and Maxwell Problems with Applications. Chapman and Hall/CRC Applied Mathematics and Nonlinear Science, 2007.
18. Denkowski Z., Migórski S., Papageorgiou N.: An Introduction to Nonlinear Analysis: Applications. Kluwer Academic/Plenum, 2003.
19. Denkowski Z., Migórski S., Papageorgiou N.: An Introduction to Nonlinear Analysis: Theory. Kluwer Academic/Plenum, 2003.
20. Descloux J.: Méthode Des Éléments Finis. Ecole Polytechnique Fédérale de Lausanne, Lausanne, 1973.
21. Doerr B., Jansen T., Sudholt D., Winzen C., Zarges C.: Optimizing Monotone Functions Can Be Difficult. In: R. Schaefer, C. Cotta, J. Kołodziej, G. Rudolph, eds., Parallel Problem Solving from Nature - PPSN XI, Lecture Notes in Computer Science, vol. 6238, pp. 42-51. Springer, 2010.
22. Engl H., Hanke M., Neubauer A.: Regularization of Inverse Problems, Mathematics and its Applications, vol. 375. Springer-Verlag, Berlin Heidelberg, 1996.
23. Faliszewski P., Ogihara M.: On the Autoreducibility of Functions. In: Theory of Computing Systems, vol. 46(2), pp. 222-245, 2010.
24. Gajda-Zagórska E., Schaefer R., Smołka M., Paszyński M., Pardo D.: A hybrid method for inversion of 3D DC logging measurements. In: Natural Computing, vol. 14(3), pp. 355-374, 2015.
25.Glover F., Kochenberger G.: Handbook of Metaheuristics. Kluwer Academic Publishers, 2002.
26. Hemaspaandra L., Ogihara M.: The Complexity Theory Companion. Springer-Verlag, 2002.
27. Isakov V.: Inverse Problems for Partial Differential Equations. Springer, 2006.
28. Johnson D., Papadimitriou C., Yannakakis M.: How Easy is Local Search. In: Journal of Computer and System Sciences, vol. 37(1), pp. 79-100, 1988.
29. Kołodziej J., Jakubiec W., Starczak M., Schaefer R.: Identification of the CMM Parametric Errors by Hierarchical Genetic Strategy. In: IUTAM Symposium on Evolutionary Methods in Mechanics, pp. 187-196. Springer, 2004.
30. Kołodziej J., Schaefer R., Paszyńska A.: Hierarchical genetic computation in optimal design. In: Journal of Theoretical and Applied Mechanics, Computational Intelligence, vol. 42(3), pp. 519-539, 2004.
31. Koper K., Wysession M., Wiens D.: Multimodal function optimization with a niching genetic algorithm: A seismological example. In: Bulletin of the Seismological Society of America, vol. 89(4), pp. 978-988, 1999.
32. Ladner R., Lynch N., Selman A.: A Comparison of Polynomial Time Reducibilities. In: Theoretical Computer Science, vol. 1(2), pp. 103-124, 1975.
33. Lässig J., Sudholt D.: Experimental Supplements to the Theoretical Analysis of Migration in the Island Model. In: R. Schaefer, C. Cotta, J. Kołodziej, G. Rudolph, eds., Parallel Problem Solving from Nature - PPSN XI, Lecture Notes in Computer Science, vol. 6238, pp. 224-233. Springer, 2010. ISBN 978-3-642-15843-8.
34. Lässig J., Sudholt D.: General Scheme for Analyzing Running Times of Parallel Evolutionary Algorithms. In: R. Schaefer, C. Cotta, J. Kołodziej, G. Rudolph, eds., Parallel Problem Solving from Nature - PPSN XI, Lecture Notes in Computer Science, vol. 6238, pp. 234-243. Springer, 2010. ISBN 978-3-642-15843-8.
35. Mahfoud S.: Niching Methods. In: T. Back, D.B. Fogel, Z. Michalewicz, eds., Chapter C.6.1 in Handbook of Evolutionary Computations. Oxford University Press, 1997.
36. Meruane V., Heylen W.: Damage Detection with Parallel Genetic Algorithms and Operational Modes. In: Structural Health Monitoring, vol. 9, pp. 481-496, 2009.
37. Neri F., Cotta C., Moscato P., eds.: Handbook of Memetic Algorithms, Studies in Computational Intelligence, vol. 379. Springer-Verlag, Berlin Heidelberg, 2012.
38. Norris J.R.: Markov Chains. Cambridge University Press, Cambridge, 1997.
39. Osman I., Kelly J.: Meta-Heuristics: Theory and Applications. Kluwer Academic Publishers, 1996.
40. Papadimitriou C.: Computational Complexity. Addison-Wesley, 1994.
41. Papadimitriou C., Schäffer A., Yannakakis M.: On the complexity of local search. In: Proceedings of the 22nd ACM Symposium on Theory of Computing, pp. 84-94. ACM Press, 1990.
42. Papadimitriou C., Yannakakis M.: The Complexity of Facets (and some Facets of Complexity). In: Journal of Computer and System Sciences, vol. 28(2), pp. 244-259, 1984.
43. Pardalos P., Romeijn H.: Handbook of Global Optimization (Nonconvex Optimization and its Applications), vol. 2. Kluwer, 1995.
44. Paszyńska A., Grabska E., Paszyński M.: A Graph Grammar Model of the hp Adaptive Three Dimensional Finite Element Method. Part I. In: Fundamenta Informaticae, vol. 114(2), pp. 149-182, 2012.
45. Paszyńska A., Grabska E., Paszyński M.: A Graph Grammar Model of the hp Adaptive Three Dimensional Finite Element Method. Part II. In: Fundamenta Informaticae, vol. 114(2), pp. 183-201, 2012.
46. Paszyńska A., Paszyński M., Grabska E.: Graph Transformations for Modeling hp-Adaptive Finite Element Method with Triangular Elements. In: Lecture Notes in Computer Science, vol. 5103, pp. 604-613, 2008.
47. Paszyńska A., Paszyński M., Grabska E.: Graph Transformations for Modeling hp-Adaptive Finite Element Method with Mixed Triangular and Rectangular Elements. In: Lecture Notes in Computer Science, vol. 5545, pp. 875-884, 2009.
48. Paszyński M.: On the Parallelization of Self-Adaptive hp-Finite Element Methods: Part I: Composite Programmable Graph Grammar Model. In: Fundamenta Informaticae, vol. 93(4), pp. 411-434, 2009.
49. Paszyński M.: On the Parallelization of Self-Adaptive hp-Finite Element Methods: Part II: Partitioning Communication Agglomeration Mapping (PCAM) Analysis. In: Fundamenta Informaticae, vol. 93(4), pp. 435-457, 2009.
50. Paszyński M., Barabasz B., Schaefer R.: Efficient adaptive strategy for solving inverse problems. In: Computational Science-ICCS 2007, vol. 4487, pp. 342-349. Springer, 2007.
51. Paszyński M., Demkowicz L.: Parallel Fully Automatic hp-Adaptive 3D Finite Element Package. In: Engineering with Computers, vol. 22(3-4), pp. 255-276, 2006.
52. Paszyński M., Schaefer R.: Graph grammar-driven parallel partial differential equation solver. In: Concurrency and Computation: Practice and Experience, vol. 22(9), pp. 1063-1097, 2010.
53. Rachowicz W., Pardo D., Demkowicz L.: Fully Automatic hp-Adaptivity in Three Dimensions. In: Computer Methods in Applied Mechanics and Engineering (J.H. Argyris Memorial Issue), vol. 37-40, pp. 4816-4842, 1995.
54. Rudolph G.: Takeover Time in Parallel Populations with Migration. In: Proceedings of the Second International Conference on Bioinspired Optimization Methods and their Applications (BIOMA 2006), pp. 63-72. Josef Stefan Institute: Ljubljana, 2006.
55. Ryszka I., Paszyńska A., Grabska E., Sieniek M., Paszyński M.: Graph transformation systems for modeling three dimensional finite element method. Part I. Fundamenta Informaticae, vol. 140(2), pp. 129-172, 2015.
56. Schaefer R.: The role of heuristics in serial and parallel genetic search. In: Abstract Book of the 3rd Conf. on Numerical Analysis, Krynica, Poland, pp. 16-17. 2002. ISBN 978-3-642-15843-8.
57. Schaefer R.: Foundation of Genetic Global Optimization, with Chapter 6 by Telega H. Studies in Computational Intelligence Series 74, Springer, 2007.
58. Schaefer R., Barabasz B.: Asymptotic Behavior of hp-HGS (hp-Adaptive Finite Element Method Coupled with the Hierarchic Genetic Strategy) by Solving Inverse Problems. In: Proc. of ICCS'08 Conf., Part III, Kraków 23-25 June 2008, LNCS 5103, vol. 5103, pp. 682-691. Springer, 2008.
59. Schaefer R., Byrski A., Kołodziej J., Smołka M.: An agent-based model of hierarchic genetic search. In: Computers and Mathematics with Applications (CAMWA), vol. 64(12), pp. 3763-3776, 2012.
60. Schaefer R., Byrski A., Smołka M.: Island Model as Markov Dynamic System. In: International Journal of Applied Mathematics & Computer Science, vol. 22(4), pp. 971-984, 2012.
61. Schaefer R., Jabłoński Z.: On the convergence of sampling measures in the global genetic search. In: Parallel Processing and Applied Mathematics - PPAM IV, Lecture Notes in Computer Science, vol. 2328, pp. 593-600. Springer, 2002.
62. Schaefer R., Kołodziej J.: Genetic search reinforced by the population hierarchy. In: K. DeJong, R. Poli, J. Rowe, eds., Foundations of Genetic Algorithms 7, pp. 383-399. Morgan Kaufman, 2003.
63. Schauder J.: Der Fixpunktsatz in Funktionalräumen. In: Studia Mathematica, vol. 2, pp. 171-180, 1930.
64. Scholz D.: Deterministic Global Optimization. Geometric Branch-and-bound Methods and their Applications. Springer Optimization and Application Series 63. Springer, 2013.
65. Schraudolph N., Belew R.: Dynamic parameter encoding for genetic algorithms. In: Machine Learning Journal, vol. 9(1), pp. 9-21, 1992.
66. Schwab C.: P and hp Finite Element Methods. Oxford University Press, 1998.
67. Simon J.: On Some Central Problems in Computational Complexity. Ph.D. thesis, Cornell University, Ithaca, N.Y., 1975. Available as Cornell Department of Computer Science Technical Report TR75-224.
68. Skolicki Z., Jong K.D.: Improving Evolutionary Algorithms with Multirepresentation Island Models. In: Proc. of 8-th Int. Conf. on Parallel Problem Solving from Nature - PPSN VIII, vol. 3242, pp. 420-429. Springer, 2004.
69. Skolicki Z., Jong K.D.: The influence of migration sizes and intervals on island models. In: Proc. of Genetic and Evolutionary Computation Conference - GECCO-2005, pp. 1295-1302. ACM Press, 2005.
70. Smołka M., Gajda-Zagórska E., Schaefer R., Paszyński M., Pardo D.: A hybrid method for inversion of 3D AC logging measurements. In: Applied Soft Computing, vol. 36, pp. 442-456, 2015.
71. Stockmeyer L.: The Polynomial-Time Hierarchy. In: Theoretical Computer Science, vol. 3(1), pp. 1-22, 1976.
72. Strug B., Paszyńska A., Paszyński M., Grabska E.: Using a graph grammar system in the finite element method. In: Applied Mathematics and Computer Science, vol. 23(4), p. 839-853, 2013.
73. Sudholt D.: General Lower Bounds for the Running Time of Evolutionary Algorithms. In: R. Schaefer, C. Cotta, J. Kołodziej, G. Rudolph, eds., Parallel Problem Solving from Nature - PPSN XI, Lecture Notes in Computer Science, vol. 6238, pp. 124-133. Springer, 2010. ISBN 978-3-642-15843-8.
74. Tarantola A.: Inverse Problem Theory and Methods for Model Parameter Estimation. SIAM, 2005.
75. Telega H.: Parallel Algorithms for Solving Selected Inverse Problems. PhD Thesis, AGH University of Science and Technology, 1999.
76. Telega H., Schaefer R., Cabib E.: A Parallel Genetic Clustering for Inverse Problems. In: Applied Parallel Computing: Large Scale Scientific and Industrial Problems, Lecture Notes in Computer Science, vol. 1541, pp. 551-556, Springer, 1998.
77. Toda S.: PP Is as Hard as the Polynomial-Time Hierarchy. In: SIAM Journal on Computing, vol. 20(5), pp. 865-877, 1991.
78. Toda S., Ogiwara M.: Counting Classes are at Least as Hard as the Polynomial-Time Hierarchy. In: SIAM Journal on Computing, vol. 21(2), pp. 316-328, 1992.
79. Vose M.: The Simple Genetic Algorithm. MIT Press, 1999.
80. Whitley D., Gordon V.: Serial and Parallel Genetic Algorithms as Function Optimizers. In: Forrest S. ed. Proc. of ICGA'97, pp. 177-18. Morgan Kaufman, 1993.
81. Whitley D., Mathias K., Fitzhorn P.: Delta Coding: An Iterative search Strategy. In: Belew R.K. and Booker L.B. eds., Proc. of the 4-th Int. Conf. on Genetic Algorithms, pp. 77-84. Morgan Kaufman, 1991.
82. Whitley D., Soraya S., Heckerdorn R.: Island Model Genetic Algorithms. In: Proc. of AISB'97 Workshop on Evolutionary Computing, pp. 112-129. 1997.
83. Wierzba B., Semczuk A., Kołodziej J., Schaefer R.: Hierarchical Genetic Strategy with Real Number Encoding. In: Proceedings of the 6th Conference on Evolutionary Algorithms and Global Optimization, pp. 231-237. 2003.

Uwagi

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę.

Typ dokumentu

Bibliografia

Identyfikator YADDA

bwmeta1.element.baztech-4d68f4f5-71a3-4a8f-bb90-955933a62c2d