Сандық есептеулерде Монте-Карло әдісі

Монте-Карло әдісі: ықтималдық есептеу алгоритмі. Қайталанатын кездейсоқ үлгілер арқылы сандық нәтижелер алу, оптимизация, интегралдау, тәуекелді модельдеу.

19 мин оқу

100%

Дереккөз: Monte Carlo method — Wikipedia

Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.

Мазмұны

Кіріспе

Ықтималдық проблеманы шешу алгоритмі

Монте-Карло әдістері немесе Монте-Карло эксперименттері – сандық нәтижелер алу үшін қайталанатын кездейсоқ үлгі алуға негізделген есептеу алгоритмдерінің кең класы. Негізгі идея – принцип бойынша детерминистік болатын мәселелерді шешу үшін кездейсоқтықты пайдалану. Бұл атау Монакодағы Монте-Карло казиносынан шыққан, онда осы әдістің негізін қалаушы физик Станислав Улам өз еңісінің құмар ойындарынан шабыттанған. Монте-Карло әдістері негізінен үш түрлі проблема класында қолданылады: оптимизация, сандық интеграция және ықтималдық таратудан мәліметтер алу. Олар сондай-ақ кірістік мәліметтерде маңызды белгісіздік бар құбылыстарды модельдеу үшін де қолданылуы мүмкін, мысалы, ядролық электр станциясының істен шығуының тәуекелін есептеу үшін. Монте-Карло әдістері көбінесе компьютерлік симуляциялар арқылы іске асырылады және математикалық талдау жүргізу мүмкін болмаған немесе тым күрделі мәселелерге жуықтап шешімдер ұсынуы мүмкін. Монте-Карло әдістері ғылымның, инженерияның және математиканың, соның ішінде физика, химия, биология, статистика, жасанды интеллект, қаржы және криптография сияқты түрлі салаларында кеңінен қолданылады. Олар сондай-ақ социология, психология және саясаттану сияқты әлеуметтік ғылымдарда да қолданылған. Монте-Карло әдістері ХХ ғасырдың ең маңызды және ықпалды идеяларының бірі ретінде мойндалды және көптеген ғылыми және технологиялық жаңалықтарға жол ашты. Монте-Карло әдістерінің кейбір шектеулері мен қиындықтары бар, мысалы, дәлдік пен есептеу шығындары арасындағы тепе-теңдік, өлшемділіктің қиындығы, кездейсоқ сандар генераторларының сенімділігі және нәтижелерді тексеру мен растау.

Қолдану

Монте-Карло әдістері физикалық және математикалық мәселелерде жиі қолданылады және басқа тәсілдерді қолдану қиын немесе мүмкін емес болған кезде ең тиімді. Монте-Карло әдістері негізінен үш проблема класында қолданылады: оптимизация, сандық интеграция және ықтималдық үлестірілімінен сынамалар жасау. Физика саласындағы мәселелерде Монте-Карло әдістері көптеген байланысты еркіндік дәрежелеріне ие жүйелерді модельдеуге пайдалы, мысалы, сұйықтықтар, ретсіз материалдар, күшті байланысты қатты денелер және жасушалық құрылымдар (кеңейтілген Поттс моделі, өзара әрекеттесетін бөлшектер жүйелері, МакКин-Власов процестері, газдардың кинетикалық модельдері). Басқа мысалдарға бизнестегі тәуекелді есептеу және математикада күрделі шекаралық шарттары бар көпөлшемді нақты интегралдарды бағалау сияқты кіріс деректеріндегі маңызды белгісіздіктермен байланысты құбылыстарды модельдеу кіреді. Жүйелік инженерия мәселелерінде (ғарыш, мұнай барлау, ұшақ жобалау және т.б.), Монте-Карло негізіндегі сәтсіздік, шығындардың артуы және кестеден қалу болжамдары көбінесе адам интуициясынан немесе балама "жұмсақ" әдістерден жақсы нәтиже береді. Принцип бойынша Монте-Карло әдістерін ықтималдық тұрғысынан қарастырылатын кез келген мәселені шешу үшін қолдануға болады. Үлкен сандар заңы бойынша, кездейсоқ айнымалының күтілетін мәнімен сипатталатын интегралдарды айнымалының тәуелсіз сынамаларының эмпирикалық ортасы ("сынама ортасы") арқылы жуықтауға болады. Егер айнымалының ықтималдық үлестірілімі параметрленген болса, математиктер көбінесе Марков тізбегі Монте-Карло (MCMC) сынамасын пайдаланады. Басты идея – белгіленген стационарлық ықтималдық үлестіріміне ие тиімді Марков тізбегі моделін жасау. Яғни, шекте, MCMC әдісімен алынған сынамалар қажетті (мақсатты) үлестірілімнен алынған сынамалар болады. Эргодикалық теоремаға сәйкес, стационарлық үлестірілім MCMC сынамасының кездейсоқ күйлерінің эмпирикалық өлшемдерімен жуықталады. Басқа мәселелердегі мақсат – сызықтық емес эволюциялық теңдеуді қанағаттандыратын ықтималдық үлестірілімдер тізбегін жасау. Мұндай ықтималдық үлестірілімдер ағыны әрқашан кездейсоқ күйлердің Марков процесінің үлестірілімдері ретінде қарастырылуы мүмкін, оның ауысу ықтималдықтары ағымдағы кездейсоқ күйлердің үлестірілімдеріне байланысты (МакКин-Власов процестерін, сызықтық емес сүзгілеу теңдеуін қараңыз). Кейбір жағдайларда бізге сынамалау күрделілігінің арту деңгейімен ықтималдық үлестірілімдер ағыны беріледі (уақыт горизонті ұзарған жол кеңістіктерінің модельдері, температура төмендегендегі Болцманн-Гиббс өлшемдері және т.б.). Мұндай модельдерді сызықтық емес Марков тізбегінің кездейсоқ күйлері заңының эволюциясы ретінде де қарастыруға болады. Бұл күрделі сызықтық емес Марков процестерін модельдеудің табиғи жолы – процестің бірнеше көшірмелерін сынап, эволюциялық теңдеуде кездейсоқ күйлердің белгісіз үлестірілімдерін сынамаланған эмпирикалық өлшемдермен алмастыру. Традициялық Монте-Карло және MCMC әдістерінен айырмашылығы, бұл орташа өріс бөлшектері әдістері ретті өзара әрекеттесетін сынамаларға сүйенеді. "Орташа өріс" терминологиясы үлгілердің (бөлшектер, жеке тұлғалар, жүргіншілер, агенттер, тіршілік иелері немесе фенотиптер) процестің эмпирикалық өлшемдерімен өзара әрекеттесетінін көрсетеді. Жүйенің мөлшері шексіздікке жақындағанда, бұл кездейсоқ эмпирикалық өлшемдер сызықтық емес Марков тізбегінің кездейсоқ күйлерінің детерминистік үлестіріліміне жақындасады, сондықтан бөлшектер арасындағы статистикалық өзара әрекеттесу жоғалады.

Monte Carlo methods are often used in physical and mathematical problems and are most useful when it is difficult or impossible to use other approaches. Monte Carlo methods are mainly used in three problem classes: optimization, numerical integration, and generating draws from a probability distribution. In physics related problems, Monte Carlo methods are useful for simulating systems with many coupled degrees of freedom, such as fluids, disordered materials, strongly coupled solids, and cellular structures (see cellular Potts model, interacting particle systems, McKean–Vlasov processes, kinetic models of gases). Other examples include modeling phenomena with significant uncertainty in inputs such as the calculation of risk in business and, in mathematics, evaluation of multidimensional definite integrals with complicated boundary conditions. In application to systems engineering problems (space, oil exploration, aircraft design, etc. ), Monte Carlo–based predictions of failure, cost overruns and schedule overruns are routinely better than human intuition or alternative "soft" methods. In principle, Monte Carlo methods can be used to solve any problem having a probabilistic interpretation. By the law of large numbers, integrals described by the expected value of some random variable can be approximated by taking the empirical mean ( the 'sample mean') of independent samples of the variable. When the probability distribution of the variable is parameterized, mathematicians often use a Markov chain Monte Carlo (MCMC) sampler. The central idea is to design a judicious Markov chain model with a prescribed stationary probability distribution. That is, in the limit, the samples being generated by the MCMC method will be samples from the desired (target) distribution. By the ergodic theorem, the stationary distribution is approximated by the empirical measures of the random states of the MCMC sampler. In other problems, the objective is generating draws from a sequence of probability distributions satisfying a nonlinear evolution equation. These flows of probability distributions can always be interpreted as the distributions of the random states of a Markov process whose transition probabilities depend on the distributions of the current random states (see McKean–Vlasov processes, nonlinear filtering equation). In other instances we are given a flow of probability distributions with an increasing level of sampling complexity (path spaces models with an increasing time horizon, Boltzmann–Gibbs measures associated with decreasing temperature parameters, and many others). These models can also be seen as the evolution of the law of the random states of a nonlinear Markov chain. A natural way to simulate these sophisticated nonlinear Markov processes is to sample multiple copies of the process, replacing in the evolution equation the unknown distributions of the random states by the sampled empirical measures. In contrast with traditional Monte Carlo and MCMC methodologies, these mean field particle techniques rely on sequential interacting samples. The terminology mean field reflects the fact that each of the samples ( particles, individuals, walkers, agents, creatures, or phenotypes) interacts with the empirical measures of the process. When the size of the system tends to infinity, these random empirical measures converge to the deterministic distribution of the random states of the nonlinear Markov chain, so that the statistical interaction between particles vanishes.

Есептеу шығындары

Концептуалды және алгоритмдік қарапайымдылығына қарамастан, Монте-Карло симуляциясымен байланысты есептеу шығындары өте жоғары болуы мүмкін. Әдетте, жақсы жуықтау алу үшін көптеген үлгілер қажет, ал егер бір үлгіні өңдеуге кететін уақыт көп болса, жалпы орындалу уақыты шексіз үлкен болуы мүмкін. Бұл өте күрделі мәселелерде маңызды шектеу болып табылады, бірақ алгоритмнің өте оңай параллельдік қасиеті жергілікті процессорлар, кластерлер, бұлттық есептеулер, GPU, FPGA сияқты параллель есептеу стратегияларын қолдану арқылы осы жоғары шығындарды азайтуға (мүмкін, қабылданатын деңгейге дейін) мүмкіндік береді.

Тарих

Монте-Карло әдісі жасалмас бұрын, симуляциялар бұрынғысынан түсінілген детерминистік мәселені сынап, симуляциялардағы белгісіздіктерді бағалау үшін статистикалық үлгі алу қолданылды. Монте-Карло симуляциясы бұл тәсілді кері айналдырады, детерминистік мәселелерді ықтималдық метаэвристика арқылы шешеді (көшірілген оттегінің симуляциясын қараңыз). Монте-Карло әдісінің ерте түрі Буффонның ине мәселесін шешу үшін құрастырылды, онда инелерді параллель, бір-бірінен тең қашықтықтағы жолақтардан жасалған еденге тастау арқылы нәтиже бағаланады. 1930 жылдары Энрико Ферми нейтронның таралуын зерттегенде Монте-Карло әдісін алғаш рет тәжірибеге салды, бірақ бұл жұмысын жарияламады. 1940 жылдардың соңында Станислав Улам, Лос-Аламос Ұлттық зертханасында ядролық қару жобаларымен жұмыс істеген кезде, Марков тізбегі Монте-Карло әдісінің қазіргі нұсқасын ойлап тапты. 1946 жылы Лос-Аламостағы ядролық физиктер ядролық қарудың ядросындағы нейтронның таралуын зерттеді. Қажетті деректердің көп бөлігі болғанына қарамастан, мысалы, нейтронның атом ядросымен соқтығысқанға дейін өтетін орташа қашықтығы және соқтығысқаннан кейін нейтронның қанша энергия беретіні, Лос-Аламос физиктері дәстүрлі, детерминистік математикалық әдістерді қолдана отырып, мәселені шеше алмады. Улам кездейсоқ тәжірибелерді пайдалануды ұсынды. Ол шабыттанғанын былай баяндайды: жұмыс құпия болғандықтан, фон Нейман мен Уламның жұмысына кодтық атау қажет болды. Фон Нейман мен Уламның әріптесі Николас Метрополис Монте-Карло деген атты қолдануды ұсынды, бұл Монакодағы Монте-Карло казиноына сілтеме жасайды, онда Уламның туысы құмар ойындар ойнау үшін туыстарынан ақша алатын еді. Монте-Карло әдістері сол кездегі есептеу құралдарымен күрт шектелгенімен, Манхэттен жобасы үшін қажетті симуляциялардың маңызды бөлігі болды. Фон Нейман, Николас Метрополис және басқалар ENIAC компьютерін 1948 жылдың көктемінде бөліну қаруының ядросының алғашқы толық автоматтандырылған Монте-Карло есептеулерін жүргізуге бағдарламалады. 1950 жылдары Монте-Карло әдістері Лос-Аламоста сутекті бомбаны әзірлеу үшін қолданылды және физика, физикалық химия және операциялық зерттеулер салаларында кеңінен танылды. Рэнд корпорациясы мен АҚШ Әуе күштері осы кезеңде Монте-Карло әдістерін қаржыландыруға және ақпарат таратуға жауапты екі ірі ұйым болды және олар оны көптеген салаларда кеңінен қолдануға мүмкіндік берді. Орташа өріс типіндегі бөлшектердің Монте-Карло әдістерінің теориясы, әрине, 1960 жылдардың ортасында Генри П. МакКиннің жұмысымен басталды. Біз Теодор Э. Харрис пен Герман Канның 1951 жылы жарық көрген, орташа өріс генетикалық типіндегі Монте-Карло әдістерін қолдану арқылы бөлшектердің таралу энергиясын бағалау туралы алғашқы мақаласын келтіреміз. Орташа генетикалық типіндегі Монте-Карло әдістемелері эволюциялық есептеулерде эвристикалық табиғи іздеу алгоритмдері (ә.қ.а. метаэвристикалық) ретінде де қолданылады. Бұл орташа өрісті есептеу әдістерінің бастауы 1950 және 1954 жылдары Алан Тьюрингтің генетикалық типтік мутациялық таңдауды үйрену машиналары туралы және Нью-Джерси штатының Принстон қаласындағы Жоғары оқу институтында Нильс Аалл Барричеллидің мақалаларымен байланысты. Кванттық Монте-Карло, және нақтырақ айтқанда, диффузиялық Монте-Карло әдістерін Фейнман-Кац жол интегралдарының орташа өріс бөлшегі Монте-Карло шамалауы ретінде де қарастыруға болады. Кванттық Монте-Карло әдістерінің бастауы көбінесе 1948 жылы нейтрондық тізбекті реакциялардың орташа өрістегі бөлшектік түсіндіруін жасаған Энрико Ферми мен Роберт Рихтмайерге жатқызылады, бірақ кванттық жүйелердің негізгі күй энергиясын бағалау үшін алғашқы эвристикалық ұқсас және генетикалық типтегі бөлшектер алгоритмі (ә.қ.а. қайта үлгіленген немесе қайта конфигурацияланған Монте-Карло әдістері) 1984 жылы Джек Х. Хезерингтон жасады. Кезекпен Монте-Карлоны жетілдірілген сигналдарды өңдеуде және Байестік қорытындыда қолдану соңғы кезде пайда болды. 1993 жылы Гордон және басқалар өздерінің маңызды жұмысында Байес статистикалық қорытындысында Монте-Карло қайта үлгілеу алгоритмін алғаш рет қолданды. Авторлар өз алгоритмін "буутстрап фильтрі" деп атады және басқа фильтрлеу әдістерімен салыстырғанда, олардың буутстрап алгоритміне күй кеңістігі немесе жүйенің шуы туралы ешқандай болжамдар қажет емес екенін көрсетті. Сонымен қатар, біз осы салада Генширо Китагаваның осыған байланысты "Монте-Карло фильтрі" және Пьер Дель Мораль мен Химилкон Карвальо, Пьер Дель Мораль, Андре Монин және Жерар Салюдің 1990 жылдардың ортасында жарияланған бөлшектер фильтрлері туралы тағы бір мақаласын келтіреміз. Бөлшектер фильтрлері 1989-1992 жылдары П. Дель Мораль, Ж.С. Нуайер, Г. Ригаль және Г. Салю тарапынан LAAS CNRS-де радар/сонар және GPS сигналдарын өңдеу мәселелері бойынша бірқатар шектеулі және жасырын зерттеу есептерімен STCAN (Service Technique des Constructions et Armes Navales), DIGILOG компаниясы және LAAS CNRS (Жүйелерді талдау және құрылымдау зертханасы) арасында әзірленді. Бұл кезекпен Монте-Карло әдістемелерін қабылдау-жобалау үлгісімен жабдықталған өзара әрекеттесетін қайта өңдеу механизмі ретінде қарастыруға болады. 1950 жылдан 1996 жылға дейін, есептеу физикасы мен молекулалық химияда енгізілген қиып тастау және қайта үлгілеу Монте-Карло әдістерін қоса алғанда, кезекпен Монте-Карло әдістемелері туралы барлық жарияланымдар, олардың дұрыстығының дәлелдері немесе бағалаулардың қателігі және генеалогиялық және ата-тектік ағаштарға негіделген алгоритмдер туралы талқылаусыз, әртүрлі жағдайларға қолданылатын табиғи және эвристикалық алгоритмдерді ұсынады. Бұл бөлшек алгоритмдердің математикалық негіздері мен алғашқы қатаң талдауы 1996 жылы Пьер Дель Мораль жазды. Өзгермелі популяция мөлшерімен тармақталу типіндегі бөлшек әдістемелері 1990 жылдардың соңында Дэн Крисан, Джессика Гейнс және Терри Лионс, сондай-ақ Дэн Крисан, Пьер Дель Мораль және Терри Лионс тарапынан әзірленді. Осы саладағы одан әрі даму 1999 жылдан 2001 жылға дейін П. Дель Мораль, А. Гионне және Л. Микло сипаттады.

Before the Monte Carlo method was developed, simulations tested a previously understood deterministic problem, and statistical sampling was used to estimate uncertainties in the simulations. Monte Carlo simulations invert this approach, solving deterministic problems using probabilistic metaheuristics (see simulated annealing). An early variant of the Monte Carlo method was devised to solve the Buffon's needle problem, in which can be estimated by dropping needles on a floor made of parallel equidistant strips. In the 1930s, Enrico Fermi first experimented with the Monte Carlo method while studying neutron diffusion, but he did not publish this work. In the late 1940s, Stanislaw Ulam invented the modern version of the Markov Chain Monte Carlo method while he was working on nuclear weapons projects at the Los Alamos National Laboratory. In 1946, nuclear weapons physicists at Los Alamos were investigating neutron diffusion in the core of a nuclear weapon. Despite having most of the necessary data, such as the average distance a neutron would travel in a substance before it collided with an atomic nucleus and how much energy the neutron was likely to give off following a collision, the Los Alamos physicists were unable to solve the problem using conventional, deterministic mathematical methods. Ulam proposed using random experiments. He recounts his inspiration as follows:

Being secret, the work of von Neumann and Ulam required a code name. A colleague of von Neumann and Ulam, Nicholas Metropolis, suggested using the name Monte Carlo, which refers to the Monte Carlo Casino in Monaco where Ulam's uncle would borrow money from relatives to gamble. Monte Carlo methods were central to the simulations required for the Manhattan Project, though severely limited by the computational tools at the time. Von Neumann, Nicholas Metropolis and others programmed the ENIAC computer to perform the first fully automated Monte Carlo calculations, of a fission weapon core, in the spring of 1948. In the 1950s Monte Carlo methods were used at Los Alamos for the development of the hydrogen bomb, and became popularized in the fields of physics, physical chemistry, and operations research. The Rand Corporation and the U. S. Air Force were two of the major organizations responsible for funding and disseminating information on Monte Carlo methods during this time, and they began to find a wide application in many different fields. The theory of more sophisticated mean field type particle Monte Carlo methods had certainly started by the mid 1960s, with the work of Henry P. McKean Jr. on Markov interpretations of a class of nonlinear parabolic partial differential equations arising in fluid mechanics. We also quote an earlier pioneering article by Theodore E. Harris and Herman Kahn, published in 1951, using mean field genetic type Monte Carlo methods for estimating particle transmission energies. Mean field genetic type Monte Carlo methodologies are also used as heuristic natural search algorithms (a. k. a. metaheuristic) in evolutionary computing. The origins of these mean field computational techniques can be traced to 1950 and 1954 with the work of Alan Turing on genetic type mutation selection learning machines and the articles by Nils Aall Barricelli at the Institute for Advanced Study in Princeton, New Jersey. Quantum Monte Carlo, and more specifically diffusion Monte Carlo methods can also be interpreted as a mean field particle Monte Carlo approximation of Feynman–Kac path integrals. The origins of Quantum Monte Carlo methods are often attributed to Enrico Fermi and Robert Richtmyer who developed in 1948 a mean field particle interpretation of neutron chain reactions, but the first heuristic like and genetic type particle algorithm (a. k. a. Resampled or Reconfiguration Monte Carlo methods) for estimating ground state energies of quantum systems (in reduced matrix models) is due to Jack H. Hetherington in 1984. The use of Sequential Monte Carlo in advanced signal processing and Bayesian inference is more recent. It was in 1993, that Gordon et al., published in their seminal work the first application of a Monte Carlo resampling algorithm in Bayesian statistical inference. The authors named their algorithm 'the bootstrap filter', and demonstrated that compared to other filtering methods, their bootstrap algorithm does not require any assumption about that state space or the noise of the system. We also quote another pioneering article in this field of Genshiro Kitagawa on a related "Monte Carlo filter", and the ones by Pierre Del Moral and Himilcon Carvalho, Pierre Del Moral, André Monin and Gérard Salut on particle filters published in the mid 1990s. Particle filters were also developed in signal processing in 1989–1992 by P. Del Moral, J. C. Noyer, G. Rigal, and G. Salut in the LAAS CNRS in a series of restricted and classified research reports with STCAN (Service Technique des Constructions et Armes Navales), the IT company DIGILOG, and the LAAS CNRS (the Laboratory for Analysis and Architecture of Systems) on radar/sonar and GPS signal processing problems. These Sequential Monte Carlo methodologies can be interpreted as an acceptance rejection sampler equipped with an interacting recycling mechanism. From 1950 to 1996, all the publications on Sequential Monte Carlo methodologies, including the pruning and resample Monte Carlo methods introduced in computational physics and molecular chemistry, present natural and heuristic like algorithms applied to different situations without a single proof of their consistency, nor a discussion on the bias of the estimates and on genealogical and ancestral tree based algorithms. The mathematical foundations and the first rigorous analysis of these particle algorithms were written by Pierre Del Moral in 1996. Branching type particle methodologies with varying population sizes were also developed in the end of the 1990s by Dan Crisan, Jessica Gaines and Terry Lyons, and by Dan Crisan, Pierre Del Moral and Terry Lyons. Further developments in this field were described in 1999 to 2001 by P. Del Moral, A. Guionnet and L. Miclo.

Монте-Карло симуляциясы мен "егер" сценарийлері

Бәлкімдіктерді пайдаланудың тәсілдері бар, олар, әрине, Монте-Карло симуляциялары емес – мысалы, бірлік бағалауларды қолдана отырып, детерминистік модельдеу. Модельдегі әрбір белгісіз айнымалыға "нақтырақ болжам" бағасы беріледі. Әрбір кіріс айнымалысы үшін сценарийлер (мысалы, ең жақсы, ең нашар немесе ең мүмкін жағдай) таңдалады және нәтижелер тіркеледі. Ал, Монте-Карло симуляциясы әрбір айнымалының ықтималдық таралуынан жүздеген немесе мыңдаған мүмкін нәтижелерді алу үшін үлгі алады. Нәтижелер түрлі нәтижелердің болу ықтималдығын анықтау үшін талданады. Мысалы, дәстүрлі "не болса" сценарийлерін қолдана отырып, электрондық кестедегі шығындарды құру моделін салыстыру, содан кейін Монте-Карло симуляциясы және үшбұрышты ықтималдық таратуларын қолдана отырып, салыстыруды қайта жасау Монте-Карло талдауының "не болса" талдауына қарағанда тар ауқымды екенін көрсетеді. Бұл себебі "не болса" талдауы барлық сценарийлерге тең салмақ береді (корпоративтік қаржыдағы белгісіздікті сандық бағалауға қараңыз), ал Монте-Карло әдісі өте төмен ықтималдық аймақтарында сирек үлгі алады. Мұндай аймақтардағы үлгілер "сирек оқиғалар" деп аталады.

Қолданбалар

Монте-Карло әдістері, ең әсіресе, кірістерінде маңызды белгісіздік бар және көптеген байланысты еркіндік дәрежесіне ие жүйелерді модельдеуге өте пайдалы. Қолданылу салалары:

Физикалық ғылымдар

Монте-Карло әдістері есептеу физикасында, физикалық химияда және осымен байланысты қолданбалы салаларда өте маңызды, және күрделі кванттық хромодинамика есептеулерінен бастап, жылу қалқандарын және аэродинамикалық пішіндерді жобалауға дейін, сондай-ақ сәулелену дозиметриясы есептеулері үшін сәулелену тасымалын модельдеуге дейін алуан түрлі қолданысқа ие. Статистикалық физикада Монте-Карло молекулалық модельдеуі есептеу молекулалық динамикасына балама болып табылады, ал Монте-Карло әдістері қарапайым бөлшектер мен полимерлік жүйелердің статистикалық өріс теорияларын есептеу үшін қолданылады. Кванттық Монте-Карло әдістері кванттық жүйелер үшін көп денелік проблеманы шешеді. Эксперименталды бөлшектер физикасында Монте-Карло әдістері детекторларды жобалау, олардың қалай жұмыс істейтінін түсіну және эксперименталдық деректерді теориямен салыстыру үшін пайдаланылады. Астрофизикада олар галактикалардың эволюциясын және микротолқындық сәулеленудің кедір-бүдыр планета бетінен өтуін модельдеу сияқты алуан түрлі мақсаттарда қолданылады. Монте-Карло әдістері сондай-ақ қазіргі заманғы ауа райын болжаудың негізін құрайтын жиынтық модельдерде қолданылады.

Инженерлік

Монте-Карло әдістері инженерияда сезімталдық талдау және процесті жобалауда сандық ықтималдық талдау үшін кеңінен қолданылады. Бұл қажеттілік, әдеттегі процесс симуляцияларының өзара әрекеттесетін, коллинеарлы және сызықтық емес мінез-құлқынан туындайды. Мысалы, микроэлектроника инженериясында Монте-Карло әдістері аналогтық және цифрлық интегралдық тізбектердегі байланысты және байланыссыз өзгерістерді талдау үшін қолданылады. Геостатистика және геометаллургияда Монте-Карло әдістері минералдық өңдеу ағымдық схемаларын жобалаудың негізін құрайды және сандық тәуекел талдауына үлес қосады. Сұйық динамикасында, әсіресе сирек газ динамикасында, Болцман теңдеуі шекті Кнудсен саны бар сұйық ағындары үшін тікелей симуляциялық Монте-Карло әдісімен және жоғары тиімді есептеу алгоритмдерімен біріктіріліп шешіледі. Автономды робототехникада Монте-Карло локализациясы роботтың орнын анықтай алады. Ол көбінесе SLAM (бір мезгілде локализация және карта жасау) алгоритмінің негізін құрайтын Калман сүзгісі немесе бөлшектік сүзгі сияқты стохастикалық сүзгілерге қолданылады. Телекоммуникацияда, сымсыз желіні жоспарлау кезінде, жобаның пайдаланушылар санына, олардың орналасқан жеріне және қолданатын қызметтеріне байланысты әртүрлі сценарийлерде жұмыс істейтінін дәлелдеу қажет. Монте-Карло әдістері әдетте осы пайдаланушыларды және олардың күйлерін жасау үшін қолданылады. Желінің өнімділігі бағаланады және нәтижелер қанағаттанарлық болмаса, желі жобасы оңтайландыру процесінен өтеді. Сенімділік инженериясында Монте-Карло симуляциясы компонент деңгейіндегі жауапты ескере отырып, жүйе деңгейіндегі жауапты есептеу үшін қолданылады. Сигналды өңдеу және Байес қорытындысында бөлшектік сүзгілер және тізбекті Монте-Карло әдістері – өзара әрекеттесетін эмпирикалық өлшемдерді пайдалана отырып, шулы және толық емес байқаулар негізінде сигнал процесінің кейінгі үлестірімін үлгілеу және есептеуге арналған орташа өріс бөлшектік әдістерінің класы болып табылады.

Климаттың өзгеруі және радиациялық әсер

Климаттың өзгеруі жөніндегі үкіметаралық топ радиациялық күштеудің ықтималдық тығыздық функциясын талдау кезінде Монте-Карло әдістерін қолданады.

Есептеу биологиясы

Монте-Карло әдістері есептеу биологиясының түрлі салаларында қолданылады, мысалы, филогенездегі Байес қорытындысында немесе геномдар, ақуыздар немесе мембраналар сияқты биологиялық жүйелерді зерттеуде. Жүйелерді қажетті дәлдік деңгейіне қарай ірі зертілді немесе бастапқы қағидалар негізінде зерттеуге болады. Компьютерлік модельдеу белгілі бір молекуланың жергілікті ортасын қадағалауға мүмкіндік береді, мысалы, қандай-да бір химиялық реакция жүзеге асып жатыр ма екенін анықтау үшін. Физикалық эксперимент жүргізу мүмкін болмаған жағдайда, ойша эксперименттер жүргізуге болады (мысалы: байланыстарды үзу, белгілі бір жерлерге қосымша заттар енгізу, жергілікті/жалпы құрылымды өзгерту немесе сыртқы өрістерді қолдану).

Компьютерлік графика

Жолды іздеу, кейде Монте-Карло сәулелі іздеу деп те аталады, 3D көріністі мүмкін жарық жолдарының үлгілерін кездейсоқ іздеу арқылы көрсетуді жүзеге асырады. Кез келген пикселдің көп рет үлгіленуі нәтижесінде алынған үлгілердің орташа мәні рендерлеу теңдеуінің дұрыс шешіміне жақындайды, осылайша бұл әдіс қазіргі кездегі ең физикалық тұрғыдан дәл 3D графикалық рендерлеу әдістерінің бірі болып табылады.

Қолданбалы статистика

Статистикадағы Монте-Карло эксперименттерінің стандарттарын Савиловский белгіледі. Қолданбалы статистикада Монте-Карло әдістерін кем дегенде төрт мақсатта қолдануға болады: реалистік деректер жағдайында шағын үлгілер үшін бәсекелес статистиканы салыстыру. Статистиканың I типті қателік және қуат қасиеттерін классикалық теориялық үлестірімдерден алынған деректер үшін (мысалы, қалыпты қисық, Коши үлестірімі) асимптотикалық жағдайларда (яғни, шексіз үлгі көлемі және өте кішкентай әсер ету) есептеуге болады. Бірақ, нақты деректер көбінесе мұндай үлестірімдерге ие болмайды. Пермутациялық сынақтар сияқты нақты сынақтардан тиімдірек (бірақ оларды есептеу мүмкін емес) және асимптотикалық үлестірімдерге сәйкес сыни мәндерден дәлдірек болатын гипотезалық сынақтарды жүзеге асыру. Байестік қорытындыдағы артқы таралудан кездейсоқ үлгі алу. Бұл үлгі кейіннен артқы таралудың барлық маңызды ерекшеліктерін шамалап, қорытындылайды. Теріс логарифмдік ықтималдық функциясының Гессиан матрицасының тиімді кездейсоқ бағалауларын ұсыну, оларды Фишер ақпарат матрицасының бағалауын алу үшін орташалауға болады. Монте-Карло әдістері шамамен кездейсоқтық және пермутациялық сынақтар арасындағы шартты келісім болып табылады. Шамамен кездейсоқ сынақ барлық пермутациялардың белгіленген ішкі жиынына негізделген (бұл қай пермутациялар қарастырылғанын қадағалауды қажет етеді, бұл үлкен шаруашылық болады). Монте-Карло тәсілі кездейсоқ таңылған пермутациялардың белгіленген санына негізделген (бір пермутация екі рет немесе одан да жиі таңылса, нақтылықтың шамалы жоғалуына жол береді, бірақ қай пермутациялар таңылғанын қадағалау қажеттігінен құтылу арқылы тиімділікке қол жеткізеді).

Дизайн және визуалдық

Монте-Карло әдістері сәулелену өрістері мен энергия тасымалдаудың біріктірілген интегралды-дифференциалдық теңдеулерін шешуде де тиімді, сондықтан бұл әдістер виртуалды 3D модельдерінің фотореалистік суреттерін жасайтын жаһандық жарықтандыру есептеулерінде қолданылады, олар бейнеойындарда, сәулетте, дизайнда, компьютерлік фильмдерде және киноарнайы эффектілерде пайдаланылады.

Іздеу және құтқару

АҚШ жағалау күзет қызметі іздеу және құтқару операциялары кезінде кемелердің болжамды орналасқан жерін анықтау үшін SAROPS компьютерлік модельдеу бағдарламасында Монте-Карло әдістерін пайдаланады. Әрбір модельдеуде берілген параметрлерге сүйенген, он мыңға дейін кездейсоқ таратылған дерек нүктесі жасалуы мүмкін. Іздеу жолдары осы деректерді экстраполяциялау арқылы құрылады, бұл оқшаулау ықтималдығын (POC) және анықтау ықтималдығын (POD) оңтайландыруға мүмкіндік береді, олардың қосындысы табысқа жетудің жалпы ықтималдығын (POS) құрайды. Нәтижесінде, бұл ықтималдық таралудың практикалық қолданысы болып табылады, ол құтқаруды ең жылдам және тиімді етуге, соның ішінде адам өмірін және ресурстарды сақтауға бағытталған.

Қаржы және бизнес

Монте-Карло симуляциясы әртүрлі шешімдердің нәтижелеріне әсер ететін тәуекел мен белгісіздікті бағалау үшін кеңінен қолданылады. Монте-Карло симуляциясы бизнес тәуекелдерді талдаушыға сату көлемі, тауарлар мен еңбекақы бағалары, пайыздық және валюта бағамдары сияқты өзгермелі шамалардағы белгісіздіктің жалпы әсерін, сондай-ақ келісімшартты тоқтату немесе салық заңнамасының өзгеруі сияқты жеке тәуекел оқиғаларының әсерін ескеруге мүмкіндік береді. Қаржы саласындағы Монте-Карло әдістері көбінесе бизнес-бөлімше немесе корпоративтік деңгейдегі жобаларға инвестициялауды немесе басқа да қаржылық бағалауларды жүргізу үшін қолданылады. Оларды жоба кестелерін модельдеу үшін де пайдалануға болады, онда симуляциялар әрбір тапсырманың нашар жағдай, жақсы жағдай және ең мүмкін болатын ұзақтығы бойынша бағалауларды жинақтап, жобаның жалпы нәтижесін анықтайды. Монте-Карло әдістері опция бағасын анықтау, дефолттық тәуекелді талдау үшін де қолданылады. Бұдан өзге, олар медициналық араласулардың қаржылық әсерін бағалауға да пайдаланылуы мүмкін.

Заң

Висконсин штатында әйелдер арыз берушілерге қатысты зорлық-зомбылық және отбасылық зорлық-зомбылықтан қорғау бұйрықтарын алудағы табыстылығын арттыруға бағытталған ұсынылған бағдарламаның әлеуетті құндылығын бағалау үшін Монте-Карло әдісі қолданылды. Бағдарлама әйелдерге күштірек қолдау көрсету арқылы, зорлау және физикалық шабуыл қаупін азайтуға көмектесуді мақсат етті. Дегенмен, бағалау мүмкін болмайтын көптеген факторлар болды, оларға қорғау бұйрықтарының тиімділігі, қолдау көрсетілген және көрсетілмеген арыз берушілердің табыстылық деңгейі және тағы да басқалары жатты. Зерттеу осы факторларды өзгерте отырып, ұсынылған бағдарламаның жалпы табыстылық деңгейін анықтау үшін бірнеше сынақтар жүргізді.

Кітапханалық ғылым

Монте-Карло әдісі Малайзияда кітап жанры бойынша жарық көрген кітаптар санын модельдеу үшін де қолданылды. Монте-Карло симуляциясы бұрын жарияланған Ұлттық кітаптар туралы деректерді және жергілікті нарықтағы кітап жанрына қарай кітап бағасын пайдаланды. Монте-Карло нәтижелері малайзиялықтардың қай кітап жанрларын ұнататынын анықтауға және Малайзия мен Жапониядағы кітап басылымдарын салыстыруға қолданылды.

Басқа

Нассим Николас Талеб 2001 жылы жазған "Randomness-бен алдану" кітабында Монте-Карло генераторларын кері Тьюринг тестісінің нақты мысалы ретінде келтіреді: егер адамның жазуы жасалған нәрседен ажыратылмаса, онда ол адамның интеллектуалдық қабілеті төмен деп есептелуі мүмкін.

Математикада қолдану

Жалпы алғанда, Монте-Карло әдістері математикада түрлі мәселелерді шешу үшін тиісті кездейсоқ сандарды жасау (сонымен қатар, Кездейсоқ сандар генерациясын қараңыз) және белгілі бір қасиеттерге немесе қасиеттерге сай келетін сандардың үлесін анықтау арқылы қолданылады. Бұл әдіс, аналитикалық жолмен шешуге тым қиын мәселелердің сандық шешімдерін алуға көмектеседі. Монте-Карло әдісінің ең көп қолданылатын түрі – Монте-Карло интеграциясы.

Интеграциялау

Детерминистік сандық интеграция алгоритмдері аз сандағы өлшемдерде жақсы жұмыс істейді, бірақ функцияларда көптеген айнымалылар болған кезде екі проблема туындайды. Біріншіден, функцияны бағалау қажеттілігі өлшемдер санымен бірге экспоненциалды түрде өседі. Мысалы, егер бір өлшемде 10 бағалау жеткілікті дәлдік беретін болса, 100 өлшем үшін 10100 нүкте қажет болады – есептеуге тым көп. Бұл өлшемдік қарғыс деп аталады. Екіншіден, көп өлшемді аймақтың шекарасы өте күрделі болуы мүмкін, сондықтан мәселені қайталама интегралға дейін келтіру мүмкін болмайды. 100 өлшемділік ешқандай ерекшелік емес, себебі көптеген физикалық мәселелерде "өлшем" еркіндік дәрежесімен тең. Монте-Карло әдістері есептеу уақытының экспоненциалды өсуінен шығудың жолын ұсынады. Егер функция жақсы қасиеттерге ие болса, оны 100 өлшемді кеңістікте кездейсоқ нүктелерді таңдап, осы нүктелердегі функция мәндерінің орташасын алу арқылы бағалауға болады. Орталық шектеу теоремасы бойынша, бұл әдіс конвергенцияны көрсетеді, яғни, үлгіленген нүктелердің санын төрт еселеу қателікті екі есеге азайтады, өлшемдер санына қарамастан. VEGAS алгоритмі де осыған ұқсас. Ұқсас тәсіл – квази Монте-Карло әдісі, төмен диссонансты тізбектерді қолданады. Бұл тізбектер аумақты жақсырақ "толтырады" және ең маңызды нүктелерді жиірек үлгілейді, сондықтан квази Монте-Карло әдістері интегралды жылдамырақ конвергенциялай алады. Көлемдегі нүктелерді іріктеудің тағы бір класы – оның үстінен кездейсоқ қозғалыстарды (Марков тізбегі Монте-Карло) модельдеу. Мұндай әдістерге Метрополис-Хестингс алгоритмі, Гиббс үлгілеуі, Ван және Ландау алгоритмі, сондай-ақ ретті Монте-Карло үлгілеуіштер сияқты өзара әрекеттесетін MCMC әдістемелері кіреді.

Эмоция және оңтайландыру

Сандық модельдеудегі кездейсоқ сандардың тағы бір қуатты және кең таралған қолданылуы – сандық оңтайландыру. Мәселе, көбінесе көп өлшемді болатын белгілі бір вектордың функцияларын азайту (немесе арттыру) болып табылады. Көптеген мәселелерді осылай қоюға болады: мысалы, компьютерлік шахмат бағдарламасын, соңында ең жақсы бағалау функциясын беретін, мысалы, 10 қозғалыстан тұратын жиынтықты табуға тырысу ретінде қарастыруға болады. Саяхатшы сатушы мәселесіндегі мақсат – жүрілген қашықтықты азайту. Инженерлік жобалауда да қолданылулар бар, мысалы, көп салалы жобалауды оңтайландыру. Бұл квазибірөлшемді модельдерді пайдаланып, кең конфигурациялық кеңістікті тиімді зерттеу арқылы бөлшектер динамикасы мәселелерін шешу үшін қолданылған. Сілтеме – модельдеу және оңтайландыруға қатысты көптеген мәселелерді жан-жақты қарастырады. Саяхатшы сатушы мәселесі – дәстүрлі оңтайландыру мәселесі болып табылады. Яғни, оңтайлы маршрутты анықтау үшін қажетті барлық мәліметтер (әрбір пункт арасындағы қашықтықтар) белгілі және мақсат – ең аз жалпы қашықтықты табу үшін барлық мүмкін маршруттарды қарастыру. Дегенмен, әрбір қалаған пунктке бару үшін жүрілген жалпы қашықтықты азайтудың орнына, әрбір пунктке жету үшін қажетті жалпы уақытты азайтуды қалайық. Бұл дәстүрлі оңтайландырудан асып түседі, себебі жол жүру уақыты өзіндік белгісіздікке ие (жол ағлақтары, тәуліктің уақыты және т.б.). Осылайша, оңтайлы маршрутымызды анықтау үшін біз алдымен симуляция-оңтайландыруды қолданып, бір нүктеден екінші нүктеге өту үшін қажетті ықтимал уақыт диапазонын түсінуіміз керек (бұл жағдайда нақты қашықтық емес, ықтималдық таралымымен бейнеленеді), содан кейін осы белгісіздікті ескере отырып, ең жақсы маршрутты анықтау үшін саяхат шешімдерін оңтайландыруымыз керек.

Кері проблемалар

Кері проблемалардың ықтималдық тұжырымы модель кеңістігінде ықтималдық үлестірімін анықтауға алып келеді. Бұл ықтималдық үлестірімі, кейбір өлшенетін параметрлер (деректер) арқылы алынған жаңа ақпаратты, бұрынғы ақпаратпен үйлестіреді. Теория, деректерді модель параметрлерімен байланыстырғанда, жалпы жағдайда сызықтық емес болғандықтан, модель кеңістігіндегі кейінгі ықтималдықты сипаттау қиын болуы мүмкін (оның көп нүктесі болуы мүмкін, кейбір моменттері анықталмауы мүмкін және т.б.). Кері проблеманы талдағанда, ең жоғары ықтималдық модельді алу көбінесе жеткіліксіз, себебі деректердің ажыратымдылық күші туралы ақпаратты да алу қажет. Жалпы жағдайда көптеген модель параметрлері болуы мүмкін, ал қызығушылық тудыратын шеттік ықтималдық тығыздықтарын қарастыру тиімсіз немесе тіпті бессздік болуы мүмкін. Бірақ кейінгі ықтималдық үлестіріміне сәйкес модельдердің үлкен жиынтығын псевдо-кездейсоқ түрде жасауға және модельдерді талдап, көрсетуге болады, осылайша модель қасиеттерінің салыстырмалы ықтималдығы туралы ақпаратты көрерменге жеткізуге болады. Бұл тиімді Монте-Карло әдісі арқылы жүзеге асырылуы мүмкін, тіпті априорлық үлестірудің нақты формуласы болмаған жағдайларда да. Ең белгілі маңызды үлгі алу әдісі – Метрополис алгоритмі, жалпыланып, күрделі априорлық ақпаратты және кездейсоқ шумен деректерді (мүмкін жоғары сызықтық емес) кері проблемаларды талдауға мүмкіндік беретін әдіс береді.

Философия

Монте-Карло әдісін танымал түрде баяндаған МакКраккен. Әдістің жалпы философиясын Елишаков, Грюне Янов және Вейрих талқылады.