Littérature scientifique sur le sujet « Stochastic simulation algorithms »

Membrane Computing is a branch of computer science that was born after the introduction of Membrane Systems (or P systems) by a seminal paper by Gh. Paun. Membrane systems are computing devices inspired by the structure and functioning of living cells as well as from the way the cells are organized in tissues and higher order structures. The aim of membrane computing is to abstract computing ideas and models imitating these products of natural evolution. A typical membrane system is composed by a number of regions surrounded by membranes; regions contains multisets of objects (molecules) and rules (cellular processes) that specify how objects must be re-written and moved among regions. In spite of the fact that the initial primary goal of membrane systems concerned computability theory, the properties of membrane systems such as compartmentalisation, modularity, scalability/extensibility, understandability, programmability and discreteness promoted their use for an important task of the current scientific research: the modelling of biological systems (the topic “systems biology, including modelling of complex systems” has now appeared explicitly in the Seventh Framework Programme of the European Community for research, technological development and demonstration activities). To accomplish this task some features of membrane systems (such as nondeterminism and maximal parallelism) have to be mitigated while other properties have to be considered (e.g. description of the time evolution of the modelled system) to ensure the accurateness of the results gained with the models. Many approaches for the modelling and simulation of biological systems exist and can be classified according to features such as continuous/discrete, deterministic/stochastic, macroscopic/mesoscopic/microscopic, predictive/explorative, quantitative/qualitative and so on. Recently, stochastic methods have gained more attention since many biological processes, such as gene transcription and translation into proteins, are controlled by noisy mechanisms. Considering the branch of modelling focused at the molecular level and dealing with systems of biochemical processes (e.g. a signalling or metabolic pathway inside a living cell), an important class of stochastic simulation methods is the one inspired by the Gillespie's stochastic simulation algorithm (SSA). This method provides exact numerical realisations of the stochastic process defined by the chemical master equation. A series of methods (e.g. next reaction method, tau leaping, next subvolume method) and software (StochKit and MesoRD), belonging to this class, were developed for the modelling and simulation of homogeneous and/or reaction-diffusion (mesoscopic) systems. A stochastic approach that couples the expressive power of a membrane system (and more precisely of Dynamical Probabilistic P systems or DPPs) with a modified version of the tau leaping method in order to quantitatively describe the evolution of multi-compartmental systems in time is the tau-DPP approach. Both current membrane systems variants and stochastic methods inspired by the SSA lack the consideration of some properties of living cells, such as the molecular crowding or the presence of membrane potential differences. Thus, the current versions of these formalisms and computational methods do not allow to model and simulate all those biological processes where these features play an essential role. A common task in the field of stochastic simulations (mainly based on numerical rather than analytical solutions) is the repetition of a large number of simulations. This activity is required, for example, to characterise the dynamics of the modelled system and by some parameter estimation or sensitivity analysis algorithms. In this thesis we extend the tau-DPP approach taking into account additional properties of living cells in order to expand tau-DPPs modelling (and simulation) capabilities to a broader set of scenarios. Within this scope, we also exploit the main European grid computing platform as a computational platform usable to compute stochastic simulations, developing a framework specific to this purpose, able to manage a large number of simulations of stochastic models. In our formalism, we considered the explicit modelling of both the objects' (or molecules) and membranes' (or compartments) volume occupation, as mandated by the mutual impenetrability of molecules. As a consequence, the dynamics of the system are affected by the availability of free space. In living cells, for example, molecular crowding has important effects such as anomalous diffusion, variation of reaction rates and spatial segregation, which have significant consequences on the dynamics of cellular processes. At a theoretical level, we demonstrated that the explicit consideration of the volume occupation of objects and membranes (and their consequences on the system's evolution) does not reduce the computational universality of membrane systems. We achieved this aim showing that is it possible to simulate a deterministic Turing machine and that the volume required by the membrane systems that carry out this task is a linear function of the space required by the Turing machine. After this, we presented a novel version of both membrane systems (designated as Stau-DPPs) and stochastic simulation algorithm (Stau-DPP algorithm) considering the property of mutual impenetrability of molecules. In addition, we made the communication of objects independent from the system's structure in order to obtain a strong expressive power. After showing that the Stau-DPP algorithm can accurately reproduce particle diffusion (in a comparison with the heat equation), we presented two test cases to illustrate that Stau-DPPs can effectively capture some effects of crowding, namely the reduction of particle diffusion rate and the increase of reaction rate, considering a bidimensional discrete space domain. We presented also a test case to illustrate that the strong expressive power of Stau-DPPs allows the modelling and simulation (by means of the Stau-DPP algorithm) of processes taking place in structured environments; more precisely, we modelled and simulate the diffusion of molecules enhanced by the presence of a structure resembling the role of a microtubule (a sort of “railway” for intracellular trafficking) in living cells. Subsequently, we further extended Stau-DPPs and the respective evolution algorithm to explicitly consider the membrane potential difference and its effect over charged particles and voltage gated channel (VGC, a particular type of membrane protein) state transitions. In fact, the membrane potential difference exhibited by biological membranes plays a crucial role in many cellular processes (e.g. action potential and synaptic signalling cascades). Similarly to what we did for the Stau-DPPs, we presented the novel version of both the membrane systems (designated as EStau-DPPs) and the stochastic simulation algorithm (EStau-DPP algorithm) to capture the additional properties we had considered. In order to describe the probability of charged particle diffusion in a discrete space domain, we defined a propensity function starting from the deterministic and continuous description of charged particle diffusion due to an electric potential gradient. We showed by means of a focused test case that a model for ion diffusion between two regions, in which the number of ions is maintained at two different constant values and where an electric potential difference is available, correctly reaches the expected state as predicted by the Nernst equation. To describe the probability of transition between two VGC states, we derived a propensity function taking into consideration the Boltzmann-Maxwell distribution. We considered a model describing the state transitions of a VGC and we showed that the model predictions are in close agreement with the experimental data collected from literature. Lastly, we presented the framework to manage a large number of stochastic simulations on a grid computing platform. While creating this framework, we considered the parameter sweep application (PSA) approach, in which an application is run a large number of times with different parameter values. We ran a set of PSAs concerning the simulations of a stochastic bacterial chemotaxis model and the computation of the difference between the dynamics of one of its components (as a consequence of model parameter variation) compared to a reference dynamics of the same component. We then used this set of PSAs to evaluate the performance of the EGEE project's grid infrastructure (Enabling Grid for the E-sciencE). On the one hand, the EGEE grid proved to be a useful solution for the distribution of PSAs concerning the stochastic simulations of biochemical systems. The platform demonstrated its efficiency in the context of our middle-size test, and considering that the more intensive the computation, the more scalable the infrastructure, grid computing can be a suitable technology for large scale biological models analysis. On the other hand, the use of a distributed file system, the granularity of the jobs and the heterogeneity of the resources can present issues. In conclusion, in this thesis we extended previous membrane systems variants and stochastic simulation methods for the analysis of biological systems, and exploited grid computing for large scale stochastic simulations. Stau-DPPs and EStau-DPPs (and their respective algorithms to calculate the temporal evolution) increase the set of biological systems that can be investigated \textit{in silico in the context of the stochastic methods inspired by the SSA. In fact, compared to its precursor approach (tau-DPPs), Stau-DPPs allow the stochastic and discrete analysis of crowded systems, structured geometries, while EStau-DPPs also take into account some electric properties (membrane electric potential and its consequences), enabling, for example, the modelling of cellular signalling systems influenced by the membrane potential. In future, we plan to improve both the formalisations and the algorithms that we presented in this thesis. For example, Stau-DPPs can not model and simulate objects bigger than a single compartment, which conversely can be convenient for the analysis of big crowding agents in a tightly discretised space domain; instead, EStau-DPPs are, for instance, currently limited to the modelling of systems composed by two compartments separated by a boundary that can be assumed to act as a capacitor (e.g biological membranes). Moreover, we plan to optimize the parallel (MPI) implementation of both the Stau-DPP and EStau-DPP algorithms, which are presently based on a one-to-one relationship between processes and compartments, a limiting factor for the simulation of discrete spaces composed by a high number of compartments. Lastly, as grid computing demonstrated to be a useful approach to handle a large number of simulations, we plan to develop a solution to handle the simulations required in the context of sensitivity analysis.

Rapid developments in experiments provide promising platforms for realising quantum computation and quantum simulation. This, in turn, opens new possibilities for developing useful quantum algorithms and explaining complex many-body physics. The advantages of quantum computation have been demonstrated in a small range of subjects, but the potential applications of quantum algorithms for solving complex classical problems are still under investigation. Deeper understanding of complex many-body systems can lead to realising quantum simulation to study systems which are inaccessible by other means. This thesis studies different topics of quantum computation and quantum simulation. The first one is improving a quantum algorithm in adiabatic quantum computing, which can be used to solve classical problems like combinatorial optimisation problems and simulated annealing. We are able to reach a new bound of time cost for the algorithm which has a potential to achieve a speed up over standard adiabatic quantum computing. The second topic is to understand the amplitude noise in optical lattices in the context of adiabatic state preparation and the thermalisation of the energy introduced to the system. We identify regimes where introducing certain type of noise in experiments would improve the final fidelity of adiabatic state preparation, and demonstrate the robustness of the state preparation to imperfect noise implementations. We also discuss the competition between heating and dephasing effects, the energy introduced by non-adiabaticity and heating, and the thermalisation of the system after an application of amplitude noise on the lattice. The third topic is to design quantum algorithms to solve classical problems of fluid dynamics. We develop a quantum algorithm based around phase estimation that can be tailored to specific fluid dynamics problems and demonstrate a quantum speed up over classical Monte Carlo methods. This generates new bridge between quantum physics and fluid dynamics engineering, can be used to estimate the potential impact of quantum computers and provides feedback on requirements for implementing quantum algorithms on quantum devices.

In this thesis, we first develop a new method called penalty function with memory (PFM). PFM consists of a penalty parameter and a measure of constraint violation and it converts a discrete optimization via simulation (DOvS) problem with stochastic constraints into a series of DOvS problems without stochastic constraints. PFM determines a penalty of a visited solution based on past results of feasibility checks on the solution. Specifically, assuming a minimization problem, a penalty parameter of PFM, namely the penalty sequence, diverges to infinity for an infeasible solution but converges to zero almost surely for any strictly feasible solution under certain conditions. For a feasible solution located on the boundary of feasible and infeasible regions, the sequence converges to zero either with high probability or almost surely. As a result, a DOvS algorithm combined with PFM performs well even when optimal solutions are tight or nearly tight. Second, we design an optimal water quality monitoring network for river systems. The problem is to find the optimal location of a finite number of monitoring devices, minimizing the expected detection time of a contaminant spill event while guaranteeing good detection reliability. When uncertainties in spill and rain events are considered, both the expected detection time and detection reliability need to be estimated by stochastic simulation. This problem is formulated as a stochastic DOvS problem with the objective of minimizing expected detection time and with a stochastic constraint on the detection reliability; and it is solved by a DOvS algorithm combined with PFM. Finally, we improve PFM by combining it with an approximate budget allocation procedure. We revise an existing optimal budget allocation procedure so that it can handle active constraints and satisfy necessary conditions for the convergence of PFM.

This thesis deals with the distributed and stochastic algorithms including testing their convergence in networks. The theoretical part briefly describes above mentioned algorithms, including their division, problems, advantages and disadvantages. Furthermore, two distributed algorithms and two stochastic algorithms are chosen. The practical part is done by comparing the speed of convergence on various network topologies in Matlab.

Thesis: Ph. D. in Transportation, Massachusetts Institute of Technology, Department of Civil and Environmental Engineering, 2018.<br>Cataloged from PDF version of thesis.<br>Includes bibliographical references (pages 168-181).<br>This thesis introduces computationally efficient, robust, and scalable calibration algorithms for large-scale stochastic transportation simulators. Unlike a traditional "black-box" calibration algorithm, a macroscopic analytical network model is embedded through a metamodel simulation-based optimization (SO) framework. The computational efficiency is achieved through the analytical network model, which provides the algorithm with low-fidelity, analytical, differentiable, problem-specific structural information and can be efficiently evaluated. The thesis starts with the calibration of low-dimensional behavioral and supply parameters, it then addresses a challenging high-dimensional origin-destination (OD) demand matrix calibration problem, and finally enhances the OD demand calibration by taking advantage of additional high-resolution traffic data. The proposed general calibration framework is suitable to address a broad class of calibration problems and has the flexibility to be extended to incorporate emerging data sources. The proposed algorithms are first validated on synthetic networks and then tested through a case study of a large-scale real-world network with 24,335 links and 11,345 nodes in the metropolitan area of Berlin, Germany. Case studies indicate that the proposed calibration algorithms are computationally efficient, improve the quality of solutions, and are robust to both the initial conditions and to the stochasticity of the simulator, under a tight computational budget. Compared to a traditional "black-box" method, the proposed method improves the computational efficiency by an average of 30%, as measured by the total computational runtime, and simultaneously yields an average of 70% improvement in the quality of solutions, as measured by its objective function estimates, for the OD demand calibration. Moreover, the addition of intersection turning flows further enhances performance by improving the fit to field data by an average of 20% (resp. 14%), as measured by the root mean square normalized (RMSN) errors of traffic counts (resp. intersection turning flows).<br>by Chao Zhang.<br>Ph. D. in Transportation

A successful power system in military applications (warship, aircraft, armored vehicle etc.) must operate acceptably under a wide range of conditions involving different loading configurations; it must maintain war fighting ability and recover quickly and stably after being damaged. The introduction of energy storage for the power system of an electric warship integrated engineering plant (IEP) may increase the availability and survivability of the electrical power under these conditions. Herein, the problem of energy storage control is addressed in terms of maximizing the average performance. A notional medium-voltage dc system is used as the system model in the study. A linear programming model is used to simulate the power system, and two sets of states, mission states and damage states, are formulated to simulate the stochastic scenarios with which the IEP may be confronted. A genetic algorithm is applied to the design of IEP to find optimized energy storage control parameters. By using this algorithm, the maximum average performance of power system is found.

This thesis addresses the sampling problem in a high-dimensional space, i.e., the computation of averages with respect to a defined probability density that is a function of many variables. Such sampling problems arise in many application areas, including molecular dynamics, multiscale models, and Bayesian sampling techniques used in emerging machine learning applications. Of particular interest are thermostat techniques, in the setting of a stochastic-dynamical system, that preserve the canonical Gibbs ensemble defined by an exponentiated energy function. In this thesis we explore theory, algorithms, and numerous applications in this setting. We begin by comparing numerical methods for particle-based models. The class of methods considered includes dissipative particle dynamics (DPD) as well as a newly proposed stochastic pairwise Nosé-Hoover-Langevin (PNHL) method. Splitting methods are developed and studied in terms of their thermodynamic accuracy, two-point correlation functions, and convergence. When computational efficiency is measured by the ratio of thermodynamic accuracy to CPU time, we report significant advantages in simulation for the PNHL method compared to popular alternative schemes in the low-friction regime, without degradation of convergence rate. We propose a pairwise adaptive Langevin (PAdL) thermostat that fully captures the dynamics of DPD and thus can be directly applied in the setting of momentum-conserving simulation. These methods are potentially valuable for nonequilibrium simulation of physical systems. We again report substantial improvements in both equilibrium and nonequilibrium simulations compared to popular schemes in the literature. We also discuss the proper treatment of the Lees-Edwards boundary conditions, an essential part of modelling shear flow. We also study numerical methods for sampling probability measures in high dimension where the underlying model is only approximately identified with a gradient system. These methods are important in multiscale modelling and in the design of new machine learning algorithms for inference and parameterization for large datasets, challenges which are increasingly important in "big data" applications. In addition to providing a more comprehensive discussion of the foundations of these methods, we propose a new numerical method for the adaptive Langevin/stochastic gradient Nosé-Hoover thermostat that achieves a dramatic improvement in numerical efficiency over the most popular stochastic gradient methods reported in the literature. We demonstrate that the newly established method inherits a superconvergence property (fourth order convergence to the invariant measure for configurational quantities) recently demonstrated in the setting of Langevin dynamics. Furthermore, we propose a covariance-controlled adaptive Langevin (CCAdL) thermostat that can effectively dissipate parameter-dependent noise while maintaining a desired target distribution. The proposed method achieves a substantial speedup over popular alternative schemes for large-scale machine learning applications.