Academic literature on the topic 'Stochastic simulation algorithms'

Computational techniques provide invaluable tools for developing a quantitative understanding the complexity of biological systems. The knowledge of the biological system under study is formalized in a precise form by a model. A simulation algorithm will realize the dynamic interactions encoded in the model. The simulation can uncover biological implications and derive further predictive experiments. Several successful approaches with different levels of detail have been introduced to deal with various biological pathways including regulatory networks, metabolic pathways and signaling pathways. The Stochastic simulation algorithm (SSA), in particular, is an exact method to realize the time evolution of a well-mixed biochemical reaction network. It takes the inherent randomness in biological reactions and the discrete nature of involved molecular species as the main source in sampling a reaction event. SSA is useful for reaction networks with low populations of molecular species, especially key species. The macroscopic response can be significantly affected when these species involved in the reactions both quantitatively and qualitatively. Even though the underlying assumptions of SSA are obviously simplified for real biological networks, it has been proved having the capability of reproducing the stochastic effects in biological behaviour. Essentially, SSA uses a Monte Carlo simulation technique to realize temporal behaviour of biochemical network. A reaction is randomly selected to fire at a time according to its propensity by conducting a search procedure. The fired reaction leads the system to a new configuration. At this new configuration, reactions have to update their propensities to reflect the changes. In this thesis we investigate new algorithms for improving performance of SSA. First, we study the application of tree-based search for improving the search of a reaction firing, and devise a solution to optimize the average search length. We prove that by a tree-based search the performance of SSA can be sensibly improved, moving the search from linear time complexity to logarithmic complexity. We combine this idea with others from the literature, and compare the performance of our algorithm with previous ones. Our experiments show that our algorithm is faster, especially on large models. Second, we focus on reducing the cost of propensity updates. Although the computational cost for evaluating one reaction propensity is small, the cumulative cost for a large number of reactions contributes a significant portion to the simulation performance. Typical experiments show that the propensity updates contribute 65% to 85%, and in some special cases up to 99%, of the total simulation time even though a dependency graph was applied. Moreover, sometimes one models the kinetics using a complex propensity formula, further increasing the cost of propensity updates. We study and propose a new exact simulation algorithm, called RSSA named after Rejection-based SSA, to reduce the cost of propensity updates. The principle of RSSA is using an over-approximation of propensities to select a reaction firing. The exact propensity value is evaluated only as needed. Thus, the propensity updates are postponed and collapsed as much as possible. We show through experiments that the propensity updates by our algorithm is significantly reduced, and hence substantially improving the simulation time. Third, we extend our study for reaction-diffusion processes. The simulation should explicitly account the diffusion of species in space. The compartment-based reaction-diffusion simulation is based on dividing the space into subvolumes so that the subvolumes are well-mixed. The diffusion of a species between subvolumes is modelled as an additional unimolecular reaction. We propose a new algorithm, called Rejection-based Reaction Diffusion (RRD), to efficiently simulate such reaction-diffusion systems. RRD combines the tree-based search and the idea of RSSA to select the next reaction firing in a subvolume. The highlight of RRD comparing with previous algorithms is the selection of both the subvolume and the reaction uses only the over-approximation of propensities. We prove the correctness and experimentally show performance improvement of RRD over other compartment-based approaches in literature. Finally, we focus on performing a statistical analysis of the targeted event by stochastic simulation. A direct application of SSA is generating trajectories and then counting the number of the successful ones. Rare events, which occur only with a very small probability, however, make this approach infeasible since a prohibitively large number of trajectories would need to be generated before the estimation becomes reasonably accurate. We propose a new method, called splitting SSA (sSSA), to improve the accuracy and efficiency of stochastic simulation while applying to this problem. Essentially, sSSA is a kind of biased simulation in which it encourages the evolution of the system making the target event more likely, yet in such a way that allows one to recover an unbiased estimated probability. We compare both performance and accuracy for sSSA and SSA by experimenting in some concrete scenarios. Experimental results prevail that sSSA is more efficient than the naive SSA approach.

Computational techniques provide invaluable tools for developing a quantitative understanding the complexity of biological systems. The knowledge of the biological system under study is formalized in a precise form by a model. A simulation algorithm will realize the dynamic interactions encoded in the model. The simulation can uncover biological implications and derive further predictive experiments. Several successful approaches with different levels of detail have been introduced to deal with various biological pathways including regulatory networks, metabolic pathways and signaling pathways. The Stochastic simulation algorithm (SSA), in particular, is an exact method to realize the time evolution of a well-mixed biochemical reaction network. It takes the inherent randomness in biological reactions and the discrete nature of involved molecular species as the main source in sampling a reaction event. SSA is useful for reaction networks with low populations of molecular species, especially key species. The macroscopic response can be significantly affected when these species involved in the reactions both quantitatively and qualitatively. Even though the underlying assumptions of SSA are obviously simplified for real biological networks, it has been proved having the capability of reproducing the stochastic effects in biological behaviour. Essentially, SSA uses a Monte Carlo simulation technique to realize temporal behaviour of biochemical network. A reaction is randomly selected to fire at a time according to its propensity by conducting a search procedure. The fired reaction leads the system to a new configuration. At this new configuration, reactions have to update their propensities to reflect the changes. In this thesis we investigate new algorithms for improving performance of SSA. First, we study the application of tree-based search for improving the search of a reaction firing, and devise a solution to optimize the average search length. We prove that by a tree-based search the performance of SSA can be sensibly improved, moving the search from linear time complexity to logarithmic complexity. We combine this idea with others from the literature, and compare the performance of our algorithm with previous ones. Our experiments show that our algorithm is faster, especially on large models. Second, we focus on reducing the cost of propensity updates. Although the computational cost for evaluating one reaction propensity is small, the cumulative cost for a large number of reactions contributes a significant portion to the simulation performance. Typical experiments show that the propensity updates contribute 65% to 85%, and in some special cases up to 99%, of the total simulation time even though a dependency graph was applied. Moreover, sometimes one models the kinetics using a complex propensity formula, further increasing the cost of propensity updates. We study and propose a new exact simulation algorithm, called RSSA named after Rejection-based SSA, to reduce the cost of propensity updates. The principle of RSSA is using an over-approximation of propensities to select a reaction firing. The exact propensity value is evaluated only as needed. Thus, the propensity updates are postponed and collapsed as much as possible. We show through experiments that the propensity updates by our algorithm is significantly reduced, and hence substantially improving the simulation time. Third, we extend our study for reaction-diffusion processes. The simulation should explicitly account the diffusion of species in space. The compartment-based reaction-diffusion simulation is based on dividing the space into subvolumes so that the subvolumes are well-mixed. The diffusion of a species between subvolumes is modelled as an additional unimolecular reaction. We propose a new algorithm, called Rejection-based Reaction Diffusion (RRD), to efficiently simulate such reaction-diffusion systems. RRD combines the tree-based search and the idea of RSSA to select the next reaction firing in a subvolume. The highlight of RRD comparing with previous algorithms is the selection of both the subvolume and the reaction uses only the over-approximation of propensities. We prove the correctness and experimentally show performance improvement of RRD over other compartment-based approaches in literature. Finally, we focus on performing a statistical analysis of the targeted event by stochastic simulation. A direct application of SSA is generating trajectories and then counting the number of the successful ones. Rare events, which occur only with a very small probability, however, make this approach infeasible since a prohibitively large number of trajectories would need to be generated before the estimation becomes reasonably accurate. We propose a new method, called splitting SSA (sSSA), to improve the accuracy and efficiency of stochastic simulation while applying to this problem. Essentially, sSSA is a kind of biased simulation in which it encourages the evolution of the system making the target event more likely, yet in such a way that allows one to recover an unbiased estimated probability. We compare both performance and accuracy for sSSA and SSA by experimenting in some concrete scenarios. Experimental results prevail that sSSA is more efficient than the naive SSA approach.

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.