Wyniki wyszukiwania - BazTech

1

Misfit landforms imposed by ill-conditioned inverse parametric problems

Łoś M., Smołka M., Schaefer R., Sawicki J.

Computer Science

|

2018

|

Vol. 19 (2)

157--178

EN

In this paper, we put forward a new topological taxonomy that allows us to distinguish and separate multiple solutions to ill-conditioned parametric inverse problems appearing in engineering, geophysics, medicine, etc. This taxonomy distinguishes the areas of insensitivity to parameters called the landforms of the misfit landscape, be it around minima (lowlands), maxima (uplands), or stationary points (shelves). We have proven their important separability and completeness conditions. In particular, lowlands, uplands, and shelves are pairwise disjoint, and there are no other subsets of the positive measure in the admissible domain on which the misfit function takes a constant value. The topological taxonomy is related to the second, “local” one, which characterizes the types of ill-conditioning of the particular solutions. We hope that the proposed results will be helpful for a better and more precise formulation of ill-conditioned inverse problems and for selecting and profiling complex optimization strategies used in solving these problems.

2

On the computational cost and complexity of stochastic inverse solvers

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

Computer Science

|

2016

|

Vol. 17 (2)

225--264

EN

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.

3

An agent-oriented hierarchic strategy for solving inverse problems

Smołka M., Schaefer R., Paszyński M., Pardo D., Álvarez-Aramberri J.

International Journal of Applied Mathematics and Computer Science

|

2015

|

Vol. 25, no. 3

483--498

EN

The paper discusses the complex, agent-oriented hierarchic memetic strategy (HMS) dedicated to solving inverse parametric problems. The strategy goes beyond the idea of two-phase global optimization algorithms. The global search performed by a tree of dependent demes is dynamically alternated with local, steepest descent searches. The strategy offers exceptionally low computational costs, mainly because the direct solver accuracy (performed by the hp-adaptive finite element method) is dynamically adjusted for each inverse search step. The computational cost is further decreased by the strategy employed for solution inter-processing and fitness deterioration. The HMS efficiency is compared with the results of a standard evolutionary technique, as well as with the multi-start strategy on benchmarks that exhibit typical inverse problems’ difficulties. Finally, an HMS application to a real-life engineering problem leading to the identification of oil deposits by inverting magnetotelluric measurements is presented. The HMS applicability to the inversion of magnetotelluric data is also mathematically verified.

4

A hybrid algorithm for solving inverse problems in elasticity

Barabasz B., Gajda-Zagórska E., Migórski S., Paszyński M., Schaefer R., Smołka M.

International Journal of Applied Mathematics and Computer Science

|

2014

|

Vol. 24, no. 4

865--886

EN

The paper offers a new approach to handling difficult parametric inverse problems in elasticity and thermo-elasticity, formulated as global optimization ones. The proposed strategy is composed of two phases. In the first, global phase, the stochastic hp-HGS algorithm recognizes the basins of attraction of various objective minima. In the second phase, the local objective minimizers are closer approached by steepest descent processes executed singly in each basin of attraction. The proposed complex strategy is especially dedicated to ill-posed problems with multimodal objective functionals. The strategy offers comparatively low computational and memory costs resulting from a double-adaptive technique in both forward and inverse problem domains. We provide a result on the Lipschitz continuity of the objective functional composed of the elastic energy and the boundary displacement misfits with respect to the unknown constitutive parameters. It allows common scaling of the accuracy of solving forward and inverse problems, which is the core of the introduced double-adaptive technique. The capability of the proposed method of finding multiple solutions is illustrated by a computational example which consists in restoring all feasible Young modulus distributions minimizing an objective functional in a 3D domain of a photo polymer template obtained during step and flash imprint lithography.

5

HP-HGS strategy for inverse AC/DC resistivity logging measurement simulations

Gajda-Zagórska E., Paszyński M, Schaefer R., Pardo D.

Computer Science

|

2013

|

Vol. 14 (4)

629--644

EN

In this paper, we present resistivity-logging-measurement simulation with the use of two types of borehole logging devices: those which operate with zero frequency (direct current, DC) and those with higher frequencies (alternate current, AC). We perform simulations of 3D resistivity measurements in deviated wells, with a sharp angle between the borehole and formation layers. We introduce a hierarchical adaptive genetic strategy hp−HGS interfaced with an adaptive finite element method. We apply a strategy for the solution of the inverse problem, where we identify the resistivities of the formation layers based on a given measurement. We test the strategy on both direct and alternate current cases.

6

Asymptotic guarantee of success for multi-agent memetic systems

Byrski A., Schaefer R., Smołka M., Cotta C.

Bulletin of the Polish Academy of Sciences. Technical Sciences

|

2013

|

Vol. 61, nr 1

257-278

EN

The paper introduces a stochastic model for a class of population-based global optimization meta-heuristics, that generalizes existing models in the following ways. First of all, an individual becomes an active software agent characterized by the constant genotype and the meme that may change during the optimization process. Second, the model embraces the asynchronous processing of agent’s actions. Third, we consider a vast variety of possible actions that include the conventional mixing operations (e.g. mutation, cloning, crossover) as well as migrations among demes and local optimization methods. Despite the fact that the model fits many popular algorithms and strategies (e.g. genetic algorithms with tournament selection) it is mainly devoted to study memetic algorithms. The model is composed of two parts: EMAS architecture (data structures and management strategies) allowing to define the space of states and the framework for stochastic agent actions and the stationary Markov chain described in terms of this architecture. The probability transition function has been obtained and the Markov kernels for sample actions have been computed. The obtained theoretical results are helpful for studying metaheuristics conforming to the EMAS architecture. The designed synchronization allows the safe, coarse-grained parallel implementation and its effective, sub-optimal scheduling in a distributed computer environment. The proved strong ergodicity of the finite state Markov chain results in the asymptotic stochastic guarantee of success, which in turn imposes the liveness of a studied metaheuristic. The Markov chain delivers the sampling measure at an arbitrary step of computations, which allows further asymptotic studies, e.g. on various kinds of the stochastic convergence.

7

The island model as a Markov dynamic system

Schaefer R., Byrski A., Smołka M.

International Journal of Applied Mathematics and Computer Science

|

2012

|

Vol. 22, no. 4

971-984

EN

Parallel multi-deme genetic algorithms are especially advantageous because they allow reducing the time of computations and can perform a much broader search than single-population ones. However, their formal analysis does not seem to have been studied exhaustively enough. In this paper we propose a mathematical framework describing a wide class of island-like strategies as a stationary Markov chain. Our approach uses extensively the modeling principles introduced by Vose, Rudolph and their collaborators. An original and crucial feature of the framework we propose is the mechanism of inter-deme agent operation synchronization. It is important from both a practical and a theoretical point of view. We show that under a mild assumption the resulting Markov chain is ergodic and the sequence of the related sampling measures converges to some invariant measure. The asymptotic guarantee of success is also obtained as a simple issue of ergodicity. Moreover, if the cardinality of each island population grows to infinity, then the sequence of the limit invariant measures contains a weakly convergent subsequence. The formal description of the island model obtained for the case of solving a single-objective problem can also be extended to the multi-objective case.

8

Improving Population-Based Algorithms with Fitness Deterioration

Wolny A., Schaefer R.

Journal of Telecommunications and Information Technology

|

2011

|

nr 4

31-44

EN

This work presents a new hybrid approach for supporting sequential niching strategies called Cluster Supported Fitness Deterioration (CSFD). Sequential niching is one of the most promising evolutionary strategies for analyzing multimodal global optimization problems in the continuous domains embedded in the vector metric spaces. In each iteration CSFD performs the clustering of the random sample by OPTICS algorithm and then deteriorates the fitness on the area occupied by clusters. The selection pressure pushes away the next-step sample (population) from the basins of attraction of minimizers already recognized, speeding up finding the new ones. The main advantages of CSFD are low memory an computational complexity even in case of large dimensional problems and high accuracy of deterioration obtained by the flexible cluster definition delivered by OPTICS. The paper contains the broad discussion of niching strategies, detailed definition of CSFD and the series of the simple comparative tests.

9

Stochastic Dynamics of Evolutionary Multi-Agent Systems

Byrski A., Schaefer R.

Prace Naukowe Politechniki Warszawskiej. Elektronika

|

2009

|

z. 169

27-34

EN

The refined model for the biologically inspired agent-based computation system EMAS conformed to BDI standard is presented. The considerations are based on the model of the system dynamics as the stationary Markov chain already presented. In the course of paper space of the system states is modified in order assure state coherency and set of actions is simplified. Such a model allows for better understanding the behavior of the proposed complex systems as well as their limitations.

10

Stochastic Model of Evolutionary and Immunological Multi-Agent Systems: Mutually Exclusive Actions

Byrski A., Schaefer R.

Fundamenta Informaticae

|

2009

|

Vol. 95, nr 2/3

263-285

EN

The mathematical model of the biologically inspired, memetic, agent-based computation systems EMAS and iEMAS conformed to BDI standard is presented. The state of the systems and their dynamics are expressed as stationary Markov chains. Such an approach allows to better understand their complex behavior as well as their limitations.

11

Stochastic Model of Evolutionary and Immunological Multi-Agent Systems: Parallel Execution of Local Actions

Schaefer R., Byrski A., Smołka M.

Fundamenta Informaticae

|

2009

|

Vol. 95, nr 2/3

325-348

EN

The refined model for the biologically inspired agent-based computation systems EMAS and iEMAS conforming to the BDI standard is presented. Moreover, their evolution is expressed in the form of the stationary Markov chains. This paper generalizes the results obtained by Byrski and Schaefer [7] to a strongly desired case in which some agents’ actions can be executed in parallel. In order to find the Markov transition rule, the precise synchronization scheme was introduced, which allows to establish the stepwise stochastic evolution of the system. The crucial feature which allows to compute the probability transition function in case of parallel execution of local actions is the commutativity of their transition operators. Some abstract conditions expressing such a commutativity which allow to classify the agents’ actions as local or global are formulated and verified in a very simple way. The above-mentioned Markov model constitutes the basis of the asymptotic analysis of EMAS and iEMAS necessary to evaluate their search possibilities and efficiency.

12

Asymptotic guarantee of success of the hp-HGS strategy

Schaefer R., Bambosz B., Paszyński M.

Prace Naukowe Politechniki Warszawskiej. Elektronika

|

2008

|

z. 165

189-196

EN

We presented the new hp-UGS (hp adaptive FEM, Hierarchical Genetic Strategy) multi-deme, genetic strategy which cau be used for solving parametric inverse problems formulated as the global optimization ones. Its efficiency follows from the coupled adaptation of accuracy derived from the proper balance between the accuracy of hp-FEM used for solving direct problem and the accuracy of solving optimization problem. It is shown, that hp-HGS can find at least the same set of local extremes as the Simple Genetic Algorithm (SGA). Moreover, the results of asymptotic analysis that verify much less computational cost of hp-HGS are recalled from the previous papers.

13

Twin adaptive scheme for solving inverse problems

Schaefer R., Barabasz B., Paszyński M.

Prace Naukowe Politechniki Warszawskiej. Elektronika

|

2007

|

z. 160

241-249

EN

The paper deals with a class of inverse parametric problems for which the energy function may be defined. The advanced multi-deme strategy that offers an adaptive accuracy is utilized for solving associated optimal control problems. The direct problems necessary for fitness evaluation are computed by the hp-adaptive Finite Elements. The new iterative strategy balances the error of solving the direct problem and the error of solving the optimal control problem in order to descrease the total computational cost. The concept of the strategy is partially formally verified (see Lemma 3.1 and 3.2), moreover the advantages in the computational practice are mentioned.

14

Architectural Principles and Scheduling Strategies for Computing Agent Systems

Grochowski M., Schaefer R., Smołka M.

Fundamenta Informaticae

|

2006

|

Vol. 71, nr 1

15-26

EN

The paper introduces the formal description of a computing multi-agent system (MAS), its architecture and dynamics. The optimal scheduling problem for the MAS as well as a way of its verification are presented in terms of such a model. A brief report of test results published previously in [13,3,4,8] is contained in the section 6.

15

The Dynamics of Human Central Arterial System

Paszyński M., Kalita P., Schaefer R.

Schedae Informaticae

|

2005

|

Vol. 14

35-59

EN

The paper presents mathematical and numerical models of the blood flow in human arteries. We describe selected modelling techniques for the mechanical phenomena occurring in the arteries: blood flow, displacement of the wall and the fluid-structure interaction be-tween the blood and the wall. The paper concentrates on the theoretical results showing the conditions of applicability of presented models. We describe variational models for the Casson flow of blood as well as stochastic Fluid Particle Model (FPM) modified for the nonlinear flows. For the artery wali we describe the model which is the physically nonlinear Koiter shell and the Finite Element Method (FEM). We also present the simulations of the fluid-structure interaction that uses the weakly coupled approach of FPM for blood with FEM for the wall.

16

Hierarchical genetic computation in optimal design

Kołodziej J., Schaefer R., Paszyńska A.

Journal of Theoretical and Applied Mechanics

|

2004

|

Vol. 42 nr 3

519-538

EN

The paper presents two examples of genetic hierarchic global optimization methods. They are two different goals of introducing hierarchy into the computational model: to perform the multi-scale search with the adapted accuracy and to better express the structure geometry in the optimal shape design. Results of the formal analysis and simple computational examples are also attached.

PL

Praca przedstawia dwa przykłady hierarchicznych, genetycznych metod optymalizacji. Sklasyfikowano dwa główne powody wprowadzenia hierarchii do modelu obliczeniowego: dla uzyskania wieloskalowego przeszukania z adaptowaną dokładnością oraz dla lepszego odwzorowania kształtu konstrukcji w zadaniach optymalnego projektowania kształtu. Zamieszczono rezultaty formalnej analizy proponowanych strategii oraz proste przykłady obliczeniowe.

17

How to gain more information from the evolving population?

Schaefer R., Jabłoński Z. J.

Prace Naukowe Politechniki Warszawskiej. Elektronika

|

2002

|

z. 139

21--33

18

Simple taxonomy of the genetic global optimization

Schaefer R.

Computer Assisted Mechanics and Engineering Sciences

|

2002

|

Vol. 9, No. 1

135-149

EN

The paper tries to show the role that can be played by genetic optimization strategies in solving huge global optimization problems in computational mechanics and other branches of high technology. Genetic algorithms are especially recommended as the first phase in two-phase stochastic optimization. The self-adaptability of genetic search is shown on the basis of the mathematical model introduced by M. Vose. Main goals of adaptation are used as leading criteria in the simple taxonomy of genetic strategies.

19

Filtration in cohesive soils : numerical approach

Schaefer R., Sędziwy S.

Computer Assisted Mechanics and Engineering Sciences

|

1999

|

Vol. 6, No. 1

15-26

EN

Paper presents a numerical method for solving the initial boundary-value problem for a certain quasilinear parabolic equation describing the low velocity filtration problem. The convergence of the method is proved.

20

Filtration in cohesive soils : mathematical model

Schaefer R., Sędziwy S.

Computer Assisted Mechanics and Engineering Sciences

|

1999

|

Vol. 6, No. 1

1-13

EN

The paper discusses the physical basis of the process of filtration of water in a case of very low velocities and presents the mathematical model of the process, based on a new constitutive formula. The existence and uniqueness of a weak solution to the resulting nonhomogeneous initial boundary-value problem is then proven.