Kỹ thuật mô phỏng Monte Carlo

Các kỹ thuật Monte Carlo là nhóm thuật toán dùng để giải quyết nhiều vấn đề trên máy tính bằng cách sử dụng các số ngẫu nhiên (thường là số giả ngẫu nhiên), khác với các thuật toán xác định. Một ứng dụng truyền thống của kỹ thuật này là tính toán tích phân, đặc biệt là các tích phân nhiều chiều với điều kiện biên phức tạp.

Kỹ thuật Monte Carlo đóng vai trò quan trọng trong vật lý tính toán và nhiều lĩnh vực khác, từ tính toán trong động lực học lượng tử, mô phỏng hệ spin tương tác mạnh, đến thiết kế vỏ bọc nhiệt và hình dáng khí động học. Phương pháp này đặc biệt hiệu quả trong giải quyết các phương trình vi-tích phân, như trong mô tả trường bức xạ hoặc ánh sáng trong mô phỏng hình ảnh 3D trên máy tính, với ứng dụng trong trò chơi điện tử, kiến trúc, thiết kế, phim hoạt hình máy tính, hiệu ứng đặc biệt trong điện ảnh, nghiên cứu khí quyển và các nghiên cứu vật liệu bằng laser.

Trong toán học, thuật toán Monte Carlo là phương pháp số hiệu quả cho nhiều bài toán với nhiều biến số khó giải bằng các phương pháp khác, chẳng hạn như tính tích phân. Hiệu quả của phương pháp này tăng khi số chiều của bài toán tăng. Monte Carlo cũng được áp dụng cho nhiều bài toán tối ưu hóa, như trong ngành tài chính.

Đôi khi, phương pháp Monte Carlo có hiệu quả hơn khi sử dụng số giả ngẫu nhiên thay vì số ngẫu nhiên thực, vì số thực rất khó tạo ra bằng máy tính. Các số giả ngẫu nhiên, vốn được sinh ra từ chuỗi quy luật, có thể dùng để thử nghiệm hoặc mô phỏng lại các điều kiện giống như trước. Chúng chỉ cần có vẻ 'ngẫu nhiên đủ', nghĩa là phân bố đều hoặc theo quy luật định trước khi số lượng lớn.

Phương pháp Monte Carlo thường thực hiện hàng triệu bước đơn giản đồng thời, điều này phù hợp với máy tính. Kết quả của phương pháp càng chính xác (tiệm cận giá trị thực) khi số lần lặp lại các bước càng nhiều.

Lịch sử

Tính tích phân

Các phương pháp kiểu Monte-Carlo

• Monte Carlo lượng tử
• Phương pháp mô phỏng Monte Carlo
• Phương pháp động học Monte Carlo
• Xích Markov

Tối ưu hóa

• Ống ngẫu nhiên (Stochastic tunneling)
• Mô phỏng luyện thép (Simulated annealing)
• Thuật toán di truyền
• Xáo trộn song song (Parallel tempering)

Tích phân

• Tích phân Monte-Carlo
• Lấy mẫu có trọng số
• Lấy mẫu phân tầng
• Lấy mẫu phân tầng lặp lại
• Thuật toán VEGAS
• Bước ngẫu nhiên Monte Carlo
• Thuật toán Metropolis-Hastings
• Lấy mẫu Gibbs

Ứng dụng

• Monte Carlo trong tài chính
• LURCH
• Monte Carlo cho các mối quan hệ nhiều lớp

(tiếng Anh)

• Gamerman, D. Markov Chain Monte Carlo: Mô phỏng ngẫu nhiên cho suy diễn Bayesian. Boca Raton, FL: CRC Press, 1997.
• Gilks, W. R.; Richardson, S.; và Spiegelhalter, D. J. (Biên tập). Markov Chain Monte Carlo trong Thực hành. Boca Raton, FL: Chapman & Hall, 1996.
• Harvey Gould & Jan Tobochnik, Giới thiệu về các phương pháp mô phỏng máy tính, Phần 2, Ứng dụng cho các hệ thống vật lý, 1988, ISBN 0-201-16504-X
• Hoffman, P. Người yêu thích số học: Câu chuyện về Paul Erdos và cuộc tìm kiếm sự thật toán học. New York: Hyperion, tr. 238–239, 1998.
• Kuipers, L. và Niederreiter, H. Phân phối đồng đều của các chuỗi. New York: Wiley, 1974.
• Manno, I. Giới thiệu về Phương pháp Monte Carlo. Budapest, Hungary: Akadémiai Kiadó, 1999.
• MacKeown, P.K., Mô phỏng ngẫu nhiên trong Vật lý, 1997, ISBN 981-3083-26-3
• Metropolis, N. và Ulam, S. 'Phương pháp Monte Carlo.' J. Amer. Stat. Assoc. 44, 335-341, 1949.
• Metropolis, N. 'Khởi đầu của phương pháp Monte Carlo.' Los Alamos Science, No. 15, tr. 125. http://jackman.stanford.edu/mcmc/metropolis1.pdf Lưu trữ 2005-10-30 tại Wayback Machine.
• Mikhailov, G. A. Các ước lượng tham số bằng phương pháp Monte Carlo. Utrecht, Hà Lan: VSP, 1999.
• Niederreiter, H. và Spanier, J. (Biên tập). Monte Carlo và Các phương pháp Quasi-Monte Carlo 1998, Tài liệu hội thảo tại Đại học Claremont Graduate, Claremont, California, USA, 22-26 tháng 6 năm 1998. Berlin: Springer-Verlag, 2000.
• C.P. Robert và G. Casella. 'Phương pháp thống kê Monte Carlo' (ấn bản thứ hai). New York: Springer-Verlag, 2004, ISBN 0-387-21239-6
• Sobol, I. M. Một hướng dẫn cơ bản cho phương pháp Monte Carlo. Boca Raton, FL: CRC Press, 1994.