Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Một Phương Pháp Lấy Mẫu Mới Trong Tối Ưu Tổ Hợp Dưới Tình Huống Không Chắc Chắn
Tóm tắt
Phương pháp tổng quát cho tối ưu ngẫu nhiên liên quan đến hai vòng lặp đệ quy tính toán tốn kém: (1) vòng lặp tối ưu bên ngoài, (2) vòng lặp lấy mẫu bên trong. Hơn nữa, việc bao gồm các biến quyết định rời rạc cũng làm tăng thêm độ phức tạp. Mục tiêu của nghiên cứu hiện tại là giảm cường độ tính toán của hai vòng lặp đệ quy này. Nghiên cứu đạt được các mục tiêu thông qua việc cải thiện hiểu biết và mô tả về hiện tượng lấy mẫu dựa trên các khái niệm của hình học fractal và kết hợp kiến thức về độ chính xác của việc lấy mẫu (mô hình fractal) trong khuôn khổ tối ưu ngẫu nhiên, từ đó tự động hóa và cải thiện thuật toán tối ưu tổ hợp. Hiệu quả của thuật toán được trình bày trong bối cảnh một bài toán thực tiễn quy mô lớn, liên quan đến chất thải hạt nhân tại Hanford, bao gồm các biến quyết định rời rạc và liên tục, cũng như các yếu tố không chắc chắn. Những phát triển mới này đã giảm cường độ tính toán để giải quyết vấn đề này từ ước lượng 20 ngày thời gian CPU trên một máy trạm Alpha chuyên dụng xuống còn 18 giờ thời gian CPU trên cùng một máy.
Từ khóa
#tối ưu ngẫu nhiên #lấy mẫu #tối ưu tổ hợp #hình học fractal #chất thải hạt nhân #biến quyết định.Tài liệu tham khảo
F. Akesson and J.P. Lehoczky, “Path generation for quasi-Monte Carlo simulation of mortgage-backed securities,” Mangement Science, vol. 46, pp. 1171-1187, 2000.
M.H. Alrefaei and S. Andradottir, “A simulated annealing algorithm with constant temperature for discrete stochastic optimization,” Management Science, vol. 45, pp. 748-764, 1999.
J.R. Birge and F. Louveaux, Introduction to Stochastic Programming, Springer Series in Operations Research, Springer: Berlin, 1997.
J.R. Birge, “Stochastic programming computation and applications,” INFORMS Journal on Computing, vol. 9, no. 2, 1997.
P. Chaudhuri, “Process synthesis under uncertainty,” Ph.D. Thesis, Department of Environmental Engineering, Carnegie Mellon University, Pittsburgh, PA 15213, 1996.
P. Chaudhuri and U.M. Diwekar, “Synthesis under uncertainty: A penalty function approach,” AIChE Journal, vol. 42, pp. 742-752, 1996.
A.J. Crilly, R.A. Earnshow, and J. Jones, Fractals and Chaos, Springer-Verlag: Berlin, 1991.
G.B. Dantzig and P. Glynn, “Parallel processors for planning under uncertainty,” Annals of Operations Research, vol. 22, pp. 1-21, 1990.
U.M. Diwekar and J.R. Kalagnanam, “An efficient sampling technique for optimization under uncertainty,” AIChE Journal, vol. 43, pp. 440-449, 1997.
M.A. Duran and I.E. Grossmann, “An outer-approximation algorithm for a class of mixed integer nonlinear programs,” Math. Prog., vol. 36, pp. 307-339, 1988.
Falconer, Fractal Geometry: Mathematical Foundations and Applications, John Wiley &; Sons: New York, 1990.
R.E. Gephart and R.E. Lundgren, “Hanford tank clean up: A guide to understanding the technical issues,” Report BNWL-645, Richland, WA: Pacific Northwest Laboratory, 1995.
J. Higle and S. Sen, “Stochastic decomposition: An algorithm for two stage linear programs with recourse,” Mathematics of Operations Research, vol. 16, pp. 650-669, 1991.
D.F. Hopkins, M. Hoza, and C.A. Lo Presti, “FY94 optimal waste loading models development,” Report prepared for U.S. Department of Energy under contract DE-AC06-76RLO 1830, 1994.
M. Hoza, “Optimal waste loading models for vitrification of Hanford high-level waste,” Report prepared for U.S. Department of Energy under contract DE-AC06-76RLO 1830, 1993.
R.L. Iman and W.J. Conover, “Small sample sensitivity analysis techniques for computer models, with an application to risk assessment,” Communications in Statistics, vol. A17, pp. 1749-1842, 1982.
R.L. Iman and J.C. Helton, “An investigation of uncertainty and sensitivity analysis techniques for computer models,” Risk Analysis, vol. 8, no. 1, pp. 71-90, 1988.
R.J. Iman and M.J. Shortencarier, “AFORTRAN77 program and user's guide for generation of Latin hypercube and random samples for use with computer models,” NUREG/CR-3624, SAND83-2365, Sandia National Laboratories, Albuquerque, N.M., 1984.
B.A.P. James, “Variance reduction techniques,” J. Operations Research Society, vol. 36, no. 6, p. 525, 1985.
J.R. Kalgnanam and U.M. Diwekar, “An efficient sampling technique for off-line quality control,” Technometrics, vol. 39, no. 3, pp. 308-319, 1997.
D.E. Knuth, The Art of Computer Programming, Vol. 1: Fundamental Algorithms, Reading, MA: Addison-Wesley, 1973.
L. Kocis and W.J. Whiten, “Computational investigation of low-discrepancy sequences,” ACM Transactions of Mathematical Software, vol. 23, pp. 266-294, 1997.
B.B. Mandelbrot, The Fractal Geometry of Nature, W.H. Freeman: New York, 1983.
M.D. Mckay, R.J. Beckman, and W.J. Conover, “A comparison of three methods of selecting values of input variables in the analysis of output from a computer code,” Technometrics, vol. 21, no. 2, pp. 239-245, 1979.
G. Morgan and M. Henrion, Uncertainty: A Guide to Dealing with Uncertainty in Quantitative Risk and Policy Analysis, Cambridge: Cambridge University Press, 1990.
V. Narayan, U.M. Diwekar, and M. Hoza, “Synthesizing optimal waste blends,” Industrial &; Engineering Chemistry Research, vol. 35, pp. 3519-3527, 1996.
H. Niederreiter, Random Number Generation and Quasi-Monte Carlo Methods, SIAM: Philadelphia, 1992.
Nuclear News, “DOE selects Hanford tank waste cleanup plan,” Nuclear News, vol. 40, p. 49, 1997.
L.A. Painton and U.M. Diwekar, “Synthesizing optimal design configurations for a Brayton cycle power plant,” Computers and Chemical Engineering, vol. 5, pp. 369-381, 1994.
L.A. Painton and U.M. Diwekar, “Stochastic annealing under uncertainty,” European Journal of Operations Research, vol. 83, pp. 489-502, 1995.
A. Papageorgiou and G.W. Wasilkowski, “On average case complexity of multivariate problems,” Journal of Complexity, vol. 6, pp. 1-6, 1990.
H. Peitgen, H. Jurgens, and D. Saupe, Fractal for the Classroom Part One: Introduction to Fractals and Chaos, Springer-Verlag: Berlin, 1991.
C.A. Pickover and A. Khorasani, “On the fractal structure of speech waveforms and other sampled data,” Research Report No. 11305, Computer Science Dept., IBM Thomas J. Watson Research Center, Yorktown Heights, NY 10598, 1985.
R. Pitchumani and S.C. Yao, “Correlation of thermal conductivities of unidirectional fibrous composites using local fractal techniques,” ASME Journal of Heat Transfer, vol. 113, no. 4, pp. 788-796, 1991.
A. Prékopa, “Logarithmic concave measures and related topics,” in Stochastic Programming, M.A.H. Dempster (Ed.), Academic Press: New York, NY, 1980.
A. Prékopa, Stochastic Programming, Kluwer Academic Publishers: Dordrecht, Netherlands, 1995.
R. Salazar and R. Toral, “Simulated annealing using hybrid Monte Carlo,” Journal of Statistical Physics, vol. 89, pp. 1047-1060, 1997.
E. Saliby, “Descriptive sampling: A better approach to Monte Carlo simulations,” J. Operations Research Society, vol. 41, no. 12, pp. 1133-1142, 1990.
H. Szu and R. Hartley, “Fast simulated annealing,” Physics Letter A, vol. 3, pp. 157-162, 1987.
P.J.M. vanLaarhoven and E.H.L. Aarts, Simulated Annealing: Theory and Applications, Reidel Publishing Co., 1987.
R. Wang and U. Diwekar, Latin hypercube Hammersley sequence sampling and leaped Hammersley sequence sampling, in preparation.
R.-J.-B. Wets, “Stochastic programming,” in Optimization (Handbooks in Operations Research and Management Science,Vol. 1, G.L. Nemhauser, A.H.G. Rinooy Kan, and M.J. Todd (Eds.), North-Holland: Amsterdam, 1990.
R.J.B. Wets, “Challenges in stochastic programming,” Math. Progr., vol. 75, pp. 115-135, 1996.
H. Wozniakowski, “Average case complexity of multivariate integration,” Bulletin of the American Mathematical Society, vol. 24, pp. 185-194, 1991.