Monte Carlo simulation methods are becoming increasingly important for solving difficult optimization problems. Monte Carlo methods are often used when it is infeasible to determine an exact result via a deterministic algorithm, such as with NP or #P problems. Several recent Monte Carlo techniques employ the idea of importance sampling; examples include the Cross-Entropy method and sequential importance sampling. The Cross-Entropy method is a relatively new Monte Carlo technique that has been successfully applied to a wide range of optimization and estimation problems since introduced by R. Y. Rubinstein in 1997. However, as the problem size increases, the Cross-Entropy method, like many heuristics, can take an exponentially increasing amount of time before it returns a solution. For large problems this can lead to an impractical amount of running time. A main aim of this thesis is to develop the Cross-Entropy method for large-scale parallel computing, allowing the running time of a Cross-Entropy program to be significantly reduced by the use of additional computing resources. The effectiveness of the parallel approach is demonstrated via a number of numerical studies. A second aim is to apply the Cross-Entropy method and sequential importance sampling to biological problems, in particular the multiple change-point problem for DNA sequences. The multiple change-point problem in a general setting is the problem of identifying, given a particular sequence of numbers/characters, a point along that sequence where some property of interest changes abruptly. An example in a biological setting, is identifying points in a DNA sequence where there is a significant change in the proportion of the nucleotides G and C with respect to the nucleotides A and T. We show that both sequential importance sampling and the Cross-Entropy approach yield significant improvements in time and/or accuracy over existing techniques.
| Identifer | oai:union.ndltd.org:ADTP/279252 |
| Creators | Gareth Evans |
| Source Sets | Australiasian Digital Theses Program |
| Detected Language | English |
Page generated in 0.002 seconds