Metoda Monte Carlo

Ti Wikipédia, énsiklopédia bébas
Luncat ka: pituduh, sungsi

Metoda Monte Carlo nyaeta algoritma keur ngarengsekeun rupa-rupa masalah dina itung-itungan make komputer ngagunakeun wilangan acak (atawa leuwih sering disebut wilangan bayangan), ngarupakeun hal sabalikna tina algoritma deterministik. Metoda Monte Carlo penting kacida dina komputasi fisik sarta aplikasi nu pakait, jeung bisa dipake dina rupa-rupa itungan kromodinamika kuantum keur ngarancang pamisah panas sarta bentuk aerodinamika. Metoda ieu geus kabuktian efisien keur ngarengsekeun persamaan integro-differential di kondisi medan radian, sarta metoda ieu geus digunakeun keur "itungan" iluminasi global nu ngahasilkeun photo-realistic images of virtual 3d models, digunakeun dina video games, arsitektur, disain, animasi komputer dina film sarta efek hususna, sarta widang-widang sejenna.

Monte Carlo, kawentar keur kasino, nginjeum istilahna sabab metoda ieu ngagunakeun kaayaan acak sarta ngagunakeun "pengulangan" keur manggihkeun solusi nu panghadena. Narikna, metoda Monte Carlo teu merlukeun random numbers nu sabenerna keur digunakeun dina "perhitungan". Teknik ieu leuwih gampang dipake tinimbang deterministik, sekuen pseudo-random, gampang keur diuji sarta simulasi ulang. Sakadar kualitas nu penting keur nyieun simulasi nu hade keur nyieun sekuen pseudo-random deukeut kana kaayaan "acak" nu dipikahayang. Metoda ieu bakal kasebar seragam atawa nuturkeun sebaran nu dipikahayang lamun jumlah wilanganna gede tina sekuen nu ditempo.

Sabab merlukeun algoritma "pengulangan" sarta number nu loba keur kaperluan perhitungan, Monte Carlo ngarupakeun metoda penyeimbang keur komputasi make komputer, make sababaraha teknik simulasi komputer.

Algoritma Monte Carlo nyaeta bentuk numeris metoda Monte Carlo nu dipake keur manggihkeun solusi dina masalah mathematika (nu ngabogaan variabel loba) nu harese direngsekeun, contona, make kalkulus integral, atawa metoda numeris sejenna. Metoda ieu leuwih hade tinimbang metoda sejenna lamun dimensi tina masalah leuwih loba.

Sajarah[édit | sunting sumber]

Metoda Monte Carlo asalna tina "pemakaian" praktis dina ngaran nu leuwih umum saperti "statistical sampling". Sabaraha ahli nyebutkeun yen "Monte Carlo" ngarupakeun referensi kawentar dina kasino, sarta dipopulerkeun ku ahlina dina widang eta saperti Stanislaw Marcin Ulam, Enrico Fermi, John von Neumann sarta Nicholas Metropolis. Ahli sejenna nyebutkeun yen metoda ieu mimiti didiskusikeun ku ahli nu hadir dina konferensi di Monte Carlo.

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

Integrasi[édit | sunting sumber]

Metoda deterministic numerical integration dipake ku cara nyokot sajumlah kajadian dina ruang sampel tina hiji fungsi. Sacara umum, hasil tina pagawean ieu hade keur fungsi hiji variabel. Kusabab kitu, keur fungsi vectors, metoda 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 ngabogaan 100 dimensi, jarak grid nu sarua merlukeun 10100 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.

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

Perbaikan tina metoda ieu nyaeta 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 sejen, titik sahenteuna ngagambarkeun bentuk nu hampir sarua jeung integrand. Teu salawasna dina pemodelan komputer mere hasil nu nyugemakeun dina integrasi mimiti, sanajan kitu aya metoda sejen 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. Metoda Quasi-Monte Carlo sok leuwih efisien dina integrasi numeris sabab sekuen "ngeusi" wewengkon leuwih hade dina rasa sarta sampel penting nu dijieun tina simulasi konvergen keur ngahasilkeun solusi jadi leuwih gancang.

Metoda Integrasi[édit | sunting sumber]

Optimisasi[édit | sunting sumber]

Hal sejen anu kuat sarta kawentar dina aplikasi keur random numbers dina simulasi numeris nyaeta numerical optimisation. Masalah ieu salawasna make fungsi nga-minimal-keun vektor dina dimensi anu gede. Loba masalah anu bisa direngsekeun ku cara ieu; contona program computer chess geus nunjukeun kumaha carana langkah nu optimal keur meunangkeun tarung, sebutkeun, 10 langkah nu ngahasilkeun evaluasi panghadena ka tahap ahir. Traveling salesman problem contoh lain dina masalah optimasi. Didieu oge aya sababaraha conto aplikasi dina masalah desain 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[édit | sunting sumber]

Metoda sejen[édit | sunting sumber]

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

Tempo oge[édit | sunting sumber]

Tumbu kaluar jeung sumber séjén[édit | sunting sumber]

  • P. Kevin MacKeown, 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