Inverse problems for partial differential equations play a crucial role in numerous tasks in science, technology and medicine. There is a plethora of inverse problem applications such as gas and oil exploration, structure health monitoring or cancer tissue diagnosis. A great many problems of this kind are inherently ill-posed. This makes a numerical approach to such problems a challenging task. Experienced difficulties hamper the use of both fast local optimization methods and stochastic global optimization strategies.
To overcome these obstacles we propose a hybrid parallel autonomous strategy, called the Hierarchic Memetic Strategy (HMS) that combines a stochastic global search, gradient-based local methods and some knowledge mining techniques such as the sample clustering and the deterioration of the objective function. This hybrid is crafted carefully to combine the advantages of component methods and avoid their drawbacks. As a global method we take a hierarchic multi-population strategy, that possesses good exploration and exploitation capabilities even with small-size populations. To solve the forward problem, which is the main burden of the whole strategy, we employ an up-to-date hp-adaptive Finite Element Method solver offering the possibility of adjusting its accuracy to an assumed level of inverse problem accuracy. The knowledge mining methods are used for better recognition of the objective function landscape and still further cost reduction.
The strategy is successfully verified through a series of experiments, comprising both classical multimodal optimization benchmarks and real-world engineering problems. Just as important is to provide the strategy with solid theoretical background. To this end we prove the existence of forward solutions and appropriate estimates needed for the above-mentioned accuracy adjustment. Second, we show results concerning the asymptotic guarantee of success. Third, we prove good concurrency properties of our solver, namely the independence of some crucial operations that, as a result, can be scheduled in parallel. Finally, we consider the problem of the parallel execution of forward problem instances in a distributed environment. To make a real profit of such an environment we have to employ a decent scheduling algorithm that would dispatch computation requests to appropriate, i.e. lightly loaded, instances and synchronize the retrieval of results. To estimate the optimality of a used scheduling policy we propose a formal definition of the optimal scheduling accompanied by a characterization of the optimal scheduler.
Problemy odwrotne dla równań różniczkowych cząstkowych odgrywają kluczową rolę w licznych zadaniach nauki, inżynierii i medycyny takich jak np. poszukiwania ropy naftowej i gazu ziemnego, monitorowanie stanu technicznego konstrukcji czy też diagnoza tkanek nowotworowych. Przeważająca część problemów tego rodzaju jest źle postawiona. To sprawia, że ich numeryczne rozwiązywanie jest sporym wyzwaniem. Pojawiające się przeszkody poważnie utrudniają zastosowanie zarówno stochastycznych strategii optymalizacji globalnej, jak i szybkich metod lokalnych.
W celu pokonania tych trudności zaproponowano hybrydową równoległą strategię autonomiczną, nazwaną hierarchiczną strategią memetyczną (HMS), łączącą stochastyczną metodę poszukiwania globalnego, lokalne metody gradientowe i dodatkowe techniki inżynierii wiedzy, takie jak klastrowanie populacji i deterioracja funkcji celu. Proponowana hybryda łączy zalety metod składowych i eliminuje ich wady. Jako metodę globalną zastosowano hierarchiczną strategię wielopopulacyjną o dobrych własnościach w zakresie eksploracji i poszukiwania lokalnego nawet przy małym rozmiarze populacji. Do rozwiązywania problemu prostego, który jest głównym obciążeniem obliczeniowym całej strategii, użyto nowoczesnego hp-adaptacyjnego solwera metody elementów skończonych dającego możliwość dostosowania własnej dokładności do przyjętego poziomu dokładności rozwiązania problemu odwrotnego. Zadaniem metod inżynierii wiedzy jest lepsze rozpoznanie kształtu funkcji celu i dalszą redukcja kosztu obliczeniowego.
Powstałą strategię zweryfikowano pomyślnie za pomocą eksperymentów obejmujących zarówno klasyczne wielomodalne funkcje testowe, jak i praktyczne problemy inżynierskie. Równie istotne było zapewnienie solidnych podstaw teoretycznych. W tym celu wykazano istnienie rozwiązań problemów prostych oraz odpowiednie oszacowania umożliwiające wspomniane sterowanie dokładnością. Następnie udowodniono asymptotyczną gwarancję sukcesu dla nowej strategii. Wykazano ponadto jej dobre własności jako systemu współbieżnego, mianowicie możliwość równoległego wykonania kluczowych operacji. Rozważono także problem równoległego uruchomienia instancji solwera problemu prostego w środowisku rozproszonym, kiedy istotną rolę odgrywa algorytm szeregujący zlecenia uruchomienia obliczeń. Podano formalną definicję oraz charakteryzację optymalnego szeregowania w środowisku rozproszonym. Zaproponowana charakteryzacja może być użyta do oceny optymalności danego algorytmu szeregującego.
Wydawnictwa nie prowadzą sprzedaży książek z serii "Rozprawy Monografie". Zainteresowanych prosimy o kontakt z ich autorami.
- Contents
-
Abstract 11
Streszczenie 12
Symbols 13
Acronyms 16
List of Figures 19
List of Tables 21
List of Algorithms 23
Acknowledgments 25I Introduction 27
1. Motivation 29
2. Structure of this book 31
3. State of the art 33
3.1. Inverse problems: theoretical background 33
3.2. Adaptive forward solvers 42
3.3. Inverse problems: stochastic numerical approaches 44
3.4. Inverse problems: hybrid approaches 51
3.5. Autonomous computational systems 53
3.6. Scheduling strategies in distributed environments 54
4. Open problems and main thesis 58II Architectures and strategies for inverse problem solution 61
5. Autonomous stochastic inverse solvers 63
5.1. Double-adaptive Hierarchic Genetic Search (hp-HGS) 63
5.2. Double-adaptive Hierarchic Memetic Strategy (hp-HMS) 69
6. Autonomous scheduling system in a stochastic distributed environment 79
6.1. Considered architecture of a computing multi-agent system 79
6.2. Diffusive scheduling strategy 81
7. Case studies: problem statements and theoretical results 84
7.1. 3D resistivity logging measurements: DC antennae 84
7.2. 3D resistivity logging measurements: AC antennae 94
7.3. Magnetotelluric measurements 103
7.4. Step-and-Flash Imprint Lithography 108
8. Experiments 113
8.1. Benchmark tests 113
8.2. Inversion of DC measurements 117
8.3. Inversion of AC measurements 122
8.4. Inversion of MT measurements 130
8.5. Inversion of MT measurements: twin-objective case 132
8.6. Young moduli identification in SFIL process 135
8.7. Diffusive scheduling experiments 141
9. Summary 148III Asymptotic behavior and concurrency in stochastic strategies 149
10. Action concurrency and asymptotic guarantee of success in multi-deme memetic strategies 151
10.1. System architecture 151
10.2. Action categories 157
10.3. Agent-based management 159
10.4. System dynamics 161
10.5. Sample actions 164
10.6. Asymptotic features 165
10.7. Extension to continuous state space 167
11. Island model as an ergodic Markov chain 170
11.1. Single-population succession schemes 170
11.2. Multi-population sampling measures 172
11.3. Migration with common selection 173
11.4. Agent-based synchronization 178
11.5. Stochastic system evolution 182
12. Stochastic dynamics of Hierarchic Genetic Search 185
12.1. Efficiency stopping condition 185
12.2. Model foundations 186
12.3. System states 188
12.4. Agent-based synchronization 190
12.5. Stochastic operators associated to the agent actions 194
12.6. Global dynamics 197
13. Heuristic operator in multi-objective evolutionary algorithms 202
13.1. Preliminaries 202
13.2. Selection operator 205
13.3. Heuristic 206
13.4. Asymptotic behavior 207
14. Existence and characterization of optimal scheduling in autonomous stochastic environments 209
14.1. A formal model of computational multi-agent systems 209
14.2. Optimal scheduling problem 218
15. Summary 222
Final remarks 225
16. Summary of all the achieved goals 227
17. Conclusions and future works 229
Appendices 231
A. AC, DC and MT problems: theoretical details 233
A.1. Propagation of electromagnetic waves 233
A.2. Ground layer resistivity problem: AC antennae 236
A.3. Ground layer resistivity problem: DC antennae 243
A.4. Ground layer resistivity problem: MT measurements 248
B. Mathematical details of the SFIL problem 250
B.1. Forward problem and energy functional 250
B.2. Linear elasticity model with thermal expansion coefficient 251
C. EMAS model details and extensions 253
C.1. Proof of the commutativity of local actions: discrete case 253
C.2. EMAS action details 254
C.3. Proof of the commutativity of local actions: continuous case 260
Bibliography 263