臺灣博碩士論文加值系統

Tsallis之分佈由C. Tsallis 於1996年提出來解決退火模擬之問題。此演算法被證明為比一般的退火模擬法；能夠更快的達到全域的最佳解。但是該函數非常之複雜，無法用一般之隨機變數的產生方法來產生。Tsallis根據R. N. Mantegna(1994)產生Levy之分佈的演算法，進而導出一個Tsallis隨機變數產生法。但是此方法有著許多問題：當參數 為1.2至1.4時，隨機變數有可能是虛數。並且當我們用蒙地卡羅(Monte Carlo)模擬法來模擬可能的隨機變數值時，我們發現其直方圖(histogram)與理論的機率密度函數並沒有完全符合。因此藉由Tsallis所提出之Tsallis隨機變數產生器並不能完全正確的代表理論之分佈，我們提出一個較佳的產生器更能代表Tsallis隨機變數。

Tsallis distribution was proposed by C. Tsallis in 1996 to solve the slow convergence problem of simulated annealing. It is shown that Tsallis’s generalized simulated annealing is much faster than the classical simulated annealing (“Boltzmann machine”) and fast simulated annealing (“Cauchy machine”). However, Tsallis distribution is very complicated and its random variable could not be generated by ordinary simulation techniques such as inversion and rejection methods. Tsallis adopts algorithm of R. N. Mantegna (1994) to produce a Tsallis random number generator. This method has many problems, however. First it could generate complex number when the parameter is near by 1.4. Second, when it is generated using Monte Carlo simulation, its histogram is not identical with the corresponding theoretical probability density (PDF). We plan to come out with a better Tsallis random number generator which can match the Tsallis’s PDF in most cases of its parameter’s ranges.

目錄
封面內頁
簽名頁
授權書 …………………………………..………..………………. iii
中文摘要 ………………………………………………………..... iv
英文摘要 ………………………………………………….…...….. v
誌謝 ……………………………………………………………. vi
目錄 ……………………………………………………………... vii
圖目錄 ………………………………………………………….… ix
表目錄 ………………………………………………………...….. xi
第一章　緒論 …………………………………………………….. 1
1.1　研究背景與動機 ……………………….……….... 1
1.2　研究目的 …………………………….…………… 2
1.3　研究範圍與限制 ……………………….………… 2
1.4　研究流程 ………………….……………………… 3
1.5　論文章節架構 …………….……………………… 6
第二章　文獻探討 ……………………………………………….. 8
2.1　Inversion ……….……..…...………..………..……. 9
2.2　Rejection ……….…..……...………..…..…..……. 11
2.3　Composition ….…..……...………..………..…….. 13
2.4　Box Muller’s method …………...….…..……….... 16
2.5　Ingenious Method for Symmetric Stable Variate.. 18
2.6　小結 …………….…....…………………..……… 19
第三章　研究方法與流程 ……………………………………. 21
3.1　Tsallis隨機變數產生器 ……...…………………. 21
3.2　Kolmogorov’s statistic檢定…….……….….……. 38
第四章　結論與建議 …………………………………………… 44
4.1　結論 ………….………………………………….. 44
4.2　建議及後續研究之方向……………….……..….. 44
參考文獻 ………………………………………………………… 46
附錄一　Algorithm TR………………………………………….... 49
附錄二　Chamber stable variate……………………………..….... 51
附錄三　Chambers和Levy之關係式………………..……..….... 53
附錄四　C.Tsallis’ Algorithm ………...……………………..….... 55
附錄五　Probability distribution of …………………..….... 57

1. 王舜宏, “全域最佳化演算法及其應用,” 台灣大學電機工程研究所碩士論文, 1993。
2. 陳隆熙, “一個解決TSP問題最佳解的穩定方法－以TA演算法為例,” 大葉大學工業工程研究所碩士論文, 2002。
3. 韓復華、楊智凱, “門檻接受法在TSP問題上之應用,” 運輸計劃季刊, 25(2), pp. 163-188, 1996。
4. Ahrens, J. H. and Dieter, U., “Computer method for sampling from the exponential and normal distribution,” Commun. ACM 15, pp. 873-882, 1972.
5. Althofer, I. And Koschnick, K. U., “On the convergence of threshold accepting,” Applied Mathematics and Optimization, 24, pp. 183-195, 1991.
6. Bain, L. J. and Engelhardt, M., Introduction to Probability and Mathematical Statistics, Duxbury Press, Boston, 1987.
7. Birnbaum, Z. W., “Numerical tabulation of the distribution of Kolmogorov’s statistic for finite sample size,” Journal of the American Statistical Association, 47, pp. 425-441, 1952.
8. Box, G. E. P., and Muller, M. E., “A note on the generation of random normal deviates,” Ann. Math. Stat., 29, pp. 610-611, 1958.
9. Bratley, P., Fox, B. L. and Schrage, L. E., A Guide to Simulation, 2nd ed., Springer-Verlag, New York, 1987.
10. Chambers, J. M., Mallows, C. L., and Stuck, B. W., “A method for simulating stable random variables,” JASA, 71, pp. 340-344, 1976.
11. Dekkers, A. and Aarts, E., “Global optimization and simulated annealing”, Mathematical Programming, 50, pp. 367-393, 1991.
12. Dueck, G. and Scheuer, T., “Threshold accepting: a general purpose optimizatiom algorithm appeared superior to simulated annealing,” Journal of Computational Physics, 90, pp. 161-175, 1990.
13. Feller, W., An Introduction to Probability Theory and Its Application, Volume II, , pp. 165-173, 1966.
14. Franz, A. and Hoffmann, K. H., “Threshold accepting as limit case for a modified Tsallis statistics,” Applied Mathematics Letters, 16, pp. 27-31. 2003.
15. Kirkpatrick, S., “Optimization by simulated annealing: quantitative studies,” Journal of Statistical Physics, 34(5/6), pp. 975-986, 1984.
16. Monagan M. B., Geddes K. O., Heal K. M., Labahn G., Vorkoetter S. M., McCarron J., and DeMarco P., Maple 7 Programming Guide, Waterloo Maple Inc., Canada, (2001).
17. Mantegna, R. N., “Fast, accurate algorithm for numerical simulation of Levy stable stochastic process,” Physical Review E, 49, pp. 4677-4683, 1994.
18. Marsaglia, G., “Generating a variate from the tail of the normal distribution,” Technometrics, 6, pp. 101-102, 1964.
19. Papoulis, A., Probability & Statistics, Prentice Hall, Englewood Cliffs, NJ, pp. 120-121, 1990.
20. Pardalos, P. M., Romeijn, H. E. and Tuy, H., “Recent devlopment and trends in global optimization,” Journal of Computational and Applied Mathematics, 124, pp. 209-228, 2000.
21. Penna, T. J. P., “Traveling salesman problem and Tsallis statistics,” Physical Review E, 51, pp. R1-R3, 1995.
22. Press, W. H., Teukolsky, S. A., Vetterling, W. T. and Flannery, B. P., “Numerical receipes in Fortran,” Cambridge University Press, Cambridge, 1989.
23. Rosenkrantz, D. J., Stearns, R. E. and Lewis, P. N., “An analysis of Several Heuristics for the Traveling Salesman Problem,” SIAM Journal on Computing, 6, pp. 563-581, 1977.
24. Schmeiser, B., “Generation of variates from distribution tails,” Operations Research, 28, pp. 1012-1017, 1980.
25. Szu, H. and Hartley, R., “Fast simulated annealing,” Physics Letters A, 122(3/4), pp. 157-162, 1987.
26. Tsallis, C., “Possible generalization of Boltzmann-Gibbs statistics,” Journal of Statistical Physics, 52(1/2), pp. 479-487, 1988.
27. Tasllis, C. and Stariolo, D. A., “Generalizes simulated annealing,” Physical A, 233, pp. 395-406, 1996.
28. Tian, P., J. Ma and Zhang, D. M., “Application of the simulated annealing algorithm to the combinatorial optimization problem with permutation property: an investigation of generation mechanism,” European Journal of Operational Research, 118, pp. 81-94, 1999.