Metoda Monte Carlo

métodeu Monte Carlo nyaéta algoritma keur ngarengsekeun rupa-rupa masalah dina itung-itungan make komputer ngagunakeun wilangan acak (atawa leuwih sering disebut wilangan bayangan), mangrupa hal sabalikna tina algoritma deterministik. métodeu Monte Carlo penting kacida dina komputasi fisik sarta aplikasi nu pakait, jeung bisa dipaké dina rupa-rupa itungan kromodinamika kuantum keur ngarancang pamisah panas sarta bentuk aerodinamika. métodeu ieu geus kabuktian efisien keur ngarengsekeun persamaan integro-differential di kondisi medan radian, sarta métodeu ieu geus digunakeun keur "itungan" iluminasi global nu ngahasilkeun photo-réalistic images of virtual 3d modéls, digunakeun dina video games, arsitektur, disain, animasi komputer dina film sarta efek hususna, sarta widang-widang séjénna.

Monte Carlo, kawentar keur kasino, nginjeum istilahna sabab métodeu ieu ngagunakeun kaayaan acak sarta ngagunakeun "pengulangan" keur manggihkeun solusi nu panghadéna. Narikna, métodeu Monte Carlo teu merlukeun random numbers nu sabenerna keur digunakeun dina "perhitungan". téhnik ieu leuwih gampang dipaké tinimbang deterministik, sekuen pseudo-random, gampang keur diuji sarta simulasi ulang. Sakadar kualitas nu penting keur nyieun simulasi nu hadé keur nyieun sekuen pseudo-random deukeut kana kaayaan "acak" nu dipikahayang. métodeu ieu bakal kasebar seragam atawa nuturkeun sebaran nu dipikahayang lamun jumlah wilanganna gedé tina sekuen nu ditempo.

Sabab merlukeun algoritma "pengulangan" sarta number nu loba keur kaperluan perhitungan, Monte Carlo mangrupa métodeu penyeimbang keur komputasi maké komputer, maké sababaraha téhnik simulasi komputer.

Algoritma Monte Carlo nyaéta bentuk numeris métodeu Monte Carlo nu dipaké keur manggihkeun solusi dina masalah mathematika (nu mibanda variabel loba) nu harese direngsekeun, contona, maké kalkulus integral, atawa métodeu numeris séjénna. métodeu ieu leuwih hadé tinimbang métodeu séjénna lamun dimensi tina masalah leuwih loba.

Sajarah

métodeu Monte Carlo asalna tina "pemakaian" praktis dina ngaran nu leuwih umum saperti "statistical sampling". Sabaraha ahli nyebutkeun yén "Monte Carlo" mangrupa referensi kawentar dina kasino, sarta dipopulerkeun ku ahlina dina widang éta saperti Stanislaw Marcin Ulam, Enrico Fermi, John von Neumann sarta Nicholas Metropolis. Ahli séjénna nyebutkeun yén métodeu ieu mimiti didiskusikeun ku ahli nu hadir dina konferensi di Monte Carlo.

métodeu ngitung random mimiti loba nu maké dina mangsa pre-electronic computing. métodeu ieu beuki kawentar sanggeus digunakeun Fermi dina 1930, waktu anjeunna maké métodeu random keur ngitung sifat anyar neutron. métodeu Monte Carlo jadi inti simulations nu diperlukeun dina Manhattan Project. Sanajan kitu, sanggeus komputer elektronik dijieun (mimiti taun 1945) métodeu Monte Carlo mimiti ditalungtik leuwih jero.

Integrasi

métodeu deterministic numerical integration dipaké ku cara nyokot sajumlah kajadian dina ruang sampel tina hiji fungsi. Sacara umum, hasil tina pagawéan ieu hadé keur fungsi hiji variabel. ku sabab kitu, keur fungsi vectors, métodeu deterministic quadrature teu efisien. Keur integrsi numerik vektor dua-dimensi, diperlukeun ruang titik grid anu sarua dina "permukaan" dua dimensi. Contona keur grid 10x10 diperlukeun 100 titik. Lamun vektor mibanda 100 dimensi, jarak grid nu sarua merlukeun 10¹⁰⁰ titik – hal ieu taya alesan keur bisa diitung. 100 dimensions hartina teu mungkin keur diitung, saperti dina loba masalah fisik, "dimension" sarua jeung degree of freedom, sarta dina simulasi tilu-dimensi, di dinya aya tilu degrees of freedom per partikel.

métodeu Monte Carlo nunjukkeun cara maké exponential time-increase. Saperti fungsi anu mibanda alesan well-behaved, hal ieu bisa di-estimasi ku milih sacara random tina ruang 100-dimensi, sarta nyokot sababaraha tipe average. maké central limit theorem, métodeu ieu bakal ditempokeun ku konvergen-na $1/{\sqrt {N}}$ – contona titik sampel lipat opat bakal boga satengah kasalahan, gumantung kana jumlah dimenasi.

Perbaikan tina métodeu ieu nyaéta cara nyieun atawa milih titik random, tapi leuwih dipikaresep datangna kana integral ti wewengkon nu konsentrasi loba tinimbang ti wewengkon nu konsentrasi saeutik. Dina basa séjén, titik sahenteuna ngagambarkeun bentuk nu hampir sarua jeung integrand. Teu salawasna dina pemodélan komputer méré hasil nu nyugemakeun dina integrasi mimiti, sanajan kitu aya métodeu séjén keur masalah ieu; dimimitian ku nyieun fungsi integrasi anu sederhana, salah sahijina bakal didiskusikeun dina topik di handap ieu.

Pendekatan anu ampir sarua ngagunakeun low-discrepancy sequences ku quasi-Monte Carlo method. métodeu Quasi-Monte Carlo sok leuwih efisien dina integrasi numeris sabab sekuen "ngeusi" wewengkon leuwih hadé dina rasa sarta sampel penting nu dijieun tina simulasi konvergen keur ngahasilkeun solusi jadi leuwih gancang.

Metoda Integrasi

• métodeu sampling langsung
  • Importance sampling
  • Stratified sampling
  • Recursive stratified sampling
  • VEGAS algorithm
• Random walk Monte Carlo kaasup Markov chains
  • Metropolis-Hastings algorithm

Optimisasi

Hal séjén anu kuat sarta kawentar dina aplikasi keur random numbers dina simulasi numeris nyaéta numerical optimisation. Masalah ieu salawasna maké fungsi nga-minimal-keun vektor dina dimensi anu gedé. Loba masalah anu bisa direngsekeun ku cara ieu; contona program computer chess geus nunjukkeun kumaha carana langkah nu optimal keur meunangkeun tarung, sebutkeun, 10 langkah nu ngahasilkeun evaluasi panghadéna ka tahap ahir. Traveling salesman problem contoh lain dina masalah optimasi. di dieu ogé aya sababaraha conto aplikasi dina masalah désain rekayasa, saperti multidisciplinary design optimization.

Lolobana optimasi Monte Carlo didasarkeun kana random walks. Intina, program ieu bakal dijieun dina wanda ruang multi-dimensi, condong pindah ti fungsi luhur ka fungsi handap, sanajan kitu kadang-kadang pindahna tibalik tina gradient.

Metoda Optimasi

• Stochastic tunneling
• simulated annealing
• genetic algorithms
• Parallel Tempering

Metoda sejen

• Diffusion and quantum Monte Carlo
• Semiconductor charge transport and the like
• Quasi-random numbers and self avoiding walks
• Assorted random modéls, e.g. self-organised criticality

Tempo oge

• LURCH
• Quasi-Monte Carlo method

Tumbu kaluar jeung sumber séjén

• P. Kevin MacKéown, Stochastic Simulation in Physics, 1997, ISBN 981-3083-26-3
• Harvey Gould & Jan Tobochnik, An Introduction to Computer Simulation Methods, Part 2, Applications to Physical Systems, 1988, ISBN 020116504X