修正模擬退火搜尋多階質數乘餘法亂數產生器

A Modified Simulated Annealing Search for Good Multiple Recursiverandom Number Generators

10.29973/JCSA.200512.0003

唐惠欽(Hui-Chin Tang)；黃敏聖(Min-Sheng Huang)

多階質數乘餘法 ； 亂數 ； 模擬退火法 ； 光譜檢定 ； 田口方法 ； Multiple recursive generator ； random number ； simulated annealing ； spectral test ； Taguchi method

中國統計學報

43卷4期（2005 / 12 / 01）

407 - 421

繁體中文

本研究探討之問題為搜尋具長週期及健全格子結構之多階質數乘餘法亂數產生器，結合禁忌搜尋之禁忌列表和基因演算法之突變法則於模擬退火法以設計一新啟發演算法，並利用田口方法設計最佳之啟發參數組合。結果顯示，修正模擬退火法搜尋縮減三階質數乘餘法之光譜值優於前後向搜尋法。

This paper considers the problem of searching for good multiple recursive generators (MRGs) with long period and good lattice structure. We propose a new algorithm that embeds both the tabu list of tabu search and the mutation of genetic algorithm into the simulated annealing (SA) method. Taguchi method is used to find the optimal heuristic parameters in the SA such that the effectiveness of the SA can be further improved. The proposed algorithm is compared with forward/backward method, and its effectiveness is numerically confirmed by the experiments we perform on the reduced third-order MRGs.

1. Aarts, E.,Korst, J.(1989).Simulated annealing and Boltzmann machines.New York:Wiley.
2. Anily, S.,Federgruen, A.(1987).Simulated annealing methods with general acceptance probability.Journal of Applied Probability,24,657-667.
3. Bölte, A.,Thonemann, U.W.(1996).Optimizing simulated annealing schedules with genetic programming.European Journal of Operational Research,92,402-416.
4. Cassels, J.W.S.(1959).An introduction to the Geometry of Number.New York:Springer-Verlag.
5. Deng, L.Y.,Lin, D.K.J.(2000).Random number generation for the new century.American Statistician,54,145-150.
6. Deng, L.Y.,Xu, H.Q.(2003).A system of high-dimensional, efficient, long-cycle and portable uniform random number generators.ACM Transactions on Modeling mid Computer Simulation,13,299-399.
7. Eglese, R.W.(1990).Simulated annealing: a tool for operational research.European Journal of Operational Research,46,271-281.
8. Fincke, V.,Pohst, M.(1985).Improved methods for calculating vectors of short length in a lattice, including a complexity analysis.Mathematics of Computation,44,463-471.
9. Fishman, G.S.(1996).Springer Series in Operations Research.New York:Springer-Verlag.
10. Gentle, J.E.(2003).Random number generation and Monte Carlo methods.Springer-Verlag.
11. Glover, F.(1989).Tabu Search-Part Ⅰ.Operations Research Society of America Journal on Computing,1,190-206.
12. Glover, F.,Laguna, M.(1997).Tabu search.Boston:Kluwer Academic.
13. Goldberg, E.D.(1989).Genetic algorithms in search, optimization, and machine learning.Reading, Mass.:Addison-Wesley Pub. Co..
14. Kao, C.,Tang, H.C.(1997).Systematic searches for good multiple recursive random number generators.Computers and Operations Research,24,899-905.
15. Knuth, D.E.(1997).The art of computer programming vol. 2: semi-numerical algorithms.Reading MA:Addison-Wesley.
16. L`Ecuyer, P.,Blouin, F.,Couture, R.(1993).A search for good multiple recursive random number generators.ACM Transactions on Modeling and Computer Simulation,3,87-98.
17. L`Ecuyer, P.,Couture, R.(1997).An implementation of the lattice and spectral tests for multiple recursive linear random number generators.INFORMS Journal on Computing,9,206-217.
18. Law, A.M.,Kelton, W.D.(2000).Simulation modeling and analysis.New York:McGraw-Hill.
19. Lundy, M.,Mess, A.(1986).Convergence of an annealing algorithm.Mathematical Programming,34,111-124.
20. Marsaglia, G.(2003).Seeds for random number generators.Communications of the ACM,46,90-93.
21. Marsaglia, G.,Tsang, W.W.(2004).The 64-bit universal RNG.Statistics and Probability Letters,66,183-187.
22. Marsaglia, G.,Zaman, A.,Tsang, W.W.(1990).Toward a universal random number generator.Statistics and Probability Letters,8,35-39.
23. Nelson, B.L.(2004).Stochastic simulation research in management science.Management Science,50,855-868.
24. Niederreiter, H.(1992).SIAM CBMS-NSF Regional Conference Series in Applied Mathematics.Philadelphia:SIAM.
25. Osman, I.H.,Potts, C.N.(1989).Simulated annealing for permutation flow-shop scheduling.Omega,17,551-557.
26. Reeves, C.R.,Rowe, J.E.(2003).Genetic algorithms: principles and perspectives: a guide to GA theory.Boston:Kluwer Academic.
27. Tang, H.C.(2003).Using an adaptive genetic algorithm with reversals to find good second-order multiple recursive random number generators.Mathematical Methods of Operations Research,57,41-48.
28. Tang, H.C.,Kao, C.(2004).Searching for good multiple recursive random number generators via a genetic algorithm.INFORMS Journal on Computing,16,284-290.
29. 李輝煌(2002)。田口方法。高立圖書有限公司。
30. 蘇鴻潤(1997)。碩士論文(碩士論文)。國立台灣工業技術學院機械工程技術研究所。