Random number generators: MC integration and TSP-solving by simulated annealing, genetic, and ant system approaches.

摘要

Pseudo-random number generators (PRNGs) based on linear congruential, combined linear congruential, generalized feedback shift register, and subtract with borrow procedures and Quasi-random number generators (QRNGs) such as Halton, Sobol, Faure, and Niederreiter are used for simulating Monte Carlo integration (MCI) and Traveling Salesman Problem (TSP). MCI can be used for evaluation of integrals and integral equations, boundary value problems for partial differential equations in heat conduction and radiation, and ordinary stochastic differential equations occurring in option pricing. TSP occurs in VLSI design, network routing problems including airlines, vehicle and telecommunication systems, and job scheduling problems.; Integration based on MC methods and polynomial time algorithms for TSP are randomized and so rely heavily on the random number (RN) generation. It is believed that the solutions of the algorithms are sensitive with the quality of RNs which lead to the urge of developing different methods to produce RNs. This research tries to find whether the choice of RNGs affects the final solution of the algorithm, the reason behind that and rank the RNGs based on the solutions of the problem.; The performances of the RNGs have been compared with some available statistical tests, viz., Chi-square test, Kolmogorov-Smirnoff test, Spectral test, cycle length and generation time. The performances of the RNGs are then compared based on the solution of one, two, and three dimensional MCIs. The RNGs are also implemented on three heuristic methods for TSP-solving, viz., 2-Opt and 3-Opt based Simulated Annealing (SA), Genetic Algorithm (GA), and Ant System (AS) technique. Their performances are compared statistically.; This study finds that the QRNGs (more uniform but less random) performs much better in terms of the accuracy of result than PRNGs (less uniform but more random) in MCIs. PRNGs are found to perform better than QRNGs in SA, while choosing of PRNGs and QRNGs did not effect in the GA. In AS approach the QRNGs were found to be a little better than the PRNGs. It is often felt that the performances of these generators are controversial mainly because of the experience that from one problem to another problem of the same type the same generator behaves sometimes better and sometimes worse than another generator. In addition, there was an attempt to suggest pre-generation of RNs to reduce time complexity of the algorithms.