Stokastik simülasyon - Stochastic simulation

Bir stokastik simülasyon a, simülasyon a sistemi değiştirebilir değişkenleri olan stokastik (rasgele) tek tek olasılıkları.

Gerçekleşmeleri bu rastgele değişkenlerin üretilir ve sistemin bir model içine yerleştirilir. Modelin çıktıları kaydedilir ve daha sonra süreç yeni bir rastgele değerler seti ile tekrarlanır. Bu adımlar, yeterli miktarda veri toplanana kadar tekrarlanır. Sonuç olarak, çıktıların dağılımı , en olası tahminlerin yanı sıra, değişkenlerin hangi değer aralıklarına düşme olasılığının az ya da çok olduğuna ilişkin bir beklenti çerçevesini gösterir.

Modele eklenen rasgele değişkenler genellikle bir rasgele sayı üreteci (RNG) olan bir bilgisayarda oluşturulur . Rastgele sayı üretecinin U(0,1) düzgün dağılım çıktıları daha sonra sistem modelinde kullanılan olasılık dağılımları ile rastgele değişkenlere dönüştürülür.

etimoloji

Stokastik başlangıçta "varsayımla ilgili" anlamına geliyordu; Yunan stokhastikos'tan "tahmin edebilme, tahminde bulunma": stokhazesthai'den "tahmin"; stokhos'tan "tahmin, hedef, hedef, işaret". "Rastgele belirlenmiş" duygusu ilk olarak 1934'te Alman Stokastik'ten kaydedildi.

Ayrık olay simülasyonu

Bir stokastik simülasyonda bir sonraki olayı belirlemek için, modelin durumundaki tüm olası değişikliklerin oranları hesaplanır ve daha sonra bir dizide sıralanır. Ardından, dizinin kümülatif toplamı alınır ve son hücre R sayısını içerir, burada R toplam olay hızıdır. Bu kümülatif dizi artık ayrık bir kümülatif dağılımdır ve rastgele bir sayı z~U(0,R) seçilerek ve z o olayla ilişkili orandan küçük olacak şekilde ilk olay seçilerek sonraki olayı seçmek için kullanılabilir. .

Olasılık dağılımları

Rastgele bir değişkenin potansiyel sonucunu tanımlamak için bir olasılık dağılımı kullanılır.

Değişkenin yalnızca ayrık değerler alabileceği sonuçları sınırlar.

Bernoulli dağılımı

Bir rastgele değişken X, Bernoulli dağıtılmış iki olası genellikle 1 (başarılı ya da varsayılan) kodlanmış sonuçları ya da 0 (yetmezliği veya hayatta kalma) başarı ve başarısızlık olasılıklar vardır varsa parametre p ve .

Bir rasgele sayı üreteci tarafından yapılan U(0,1) tek biçimli dağılımdan Bernoulli dağılımına sahip bir rasgele değişken X üretmek için şunları tanımlarız:

Böyle için olasılık olduğunu ve .

Örnek: Yazı tura

Tanımlamak

X = 1 if head comes up and
X = 0 if tail comes up

Adil bir madeni para için, her iki gerçekleşme de eşit derecede olasıdır. Bu rasgele değişken X'in gerçekleşmelerini, bir rasgele sayı üreteci (RNG) tarafından sağlanan tek biçimli bir dağılımdan , RNG'nin 0 ile 0,5 arasında bir değer verip vermediğini ve RNG'nin 0,5 ile 1 arasında bir değer üretip üretmediğini elde ederek üretebiliriz .

P (X = 1) = P(0 ≤ U < 1/2) = 1/2
P (X = 0) = P(1 ≥ U ≥ 1/2) = 1/2

Tabii ki, iki sonuç eşit derecede olası olmayabilir (örneğin tıbbi tedavinin başarısı).

Binom dağılımı

n ve p parametrelerine sahip bir binom dağılımlı rastgele değişken Y , n bağımsız ve özdeş olarak Bernoulli tarafından dağıtılmış rastgele değişkenler X 1 , X 2 , ..., X n'nin toplamı olarak elde edilir.

Örnek: Bir madeni para üç kez havaya atılıyor. Tam olarak iki tura gelme olasılığını bulun. Bu problem örnek uzaya bakılarak çözülebilir. İki kafa almanın üç yolu vardır.

HHH, HHT, HTH, THH, TTH, THT, HTT, TTT

Cevap 3/8'dir (= 0.375).

Poisson Dağılımı

Poisson süreci, olayların belirli bir zaman veya mekan aralığında rastgele meydana geldiği bir süreçtir. Zaman aralığı başına sabit oranlı λ olan poisson süreçleri için olasılık dağılımı aşağıdaki denklemle verilir.

Zaman aralığında meydana gelen olay sayısı olarak tanımlama

Olaylar için varışlar arası sürelerin kümülatif dağılım fonksiyonu (CDF) ile üstel olarak dağıtıldığı gösterilebilir . Üstel CDF'nin tersi şu şekilde verilir:

burada bir bir eşit dağılmış, rastgele değişken.

Aralıkta meydana gelen olay sayısı için sabit bir oranda bir Poisson sürecini simüle etmek, aşağıdaki algoritma ile gerçekleştirilebilir.

  1. ile başlayın ve
  2. Rastgele değişken oluşturma gelen tekdüze dağılım
  3. ile saati güncelle
  4. Eğer öyleyse, dur. Aksi takdirde 5. adıma devam edin.
  5. 2. adıma devam edin

yöntemler

Doğrudan ve ilk reaksiyon yöntemleri

Yayınlayan Dan Gillespie kümülatif dizisinde doğrusal arayıştır 1977 yılında, ve. Gillespie algoritmasına bakın .

Gillespie'nin Stokastik Simülasyon Algoritması (SSA), iyi karıştırılmış kimyasal olarak reaksiyona giren bir sistemin zaman evrimini, böyle bir sistemin doğasında var olan rastgeleliği uygun şekilde hesaba katarak sayısal olarak simüle etmek için esasen kesin bir prosedürdür.

Kimyasal ana denklemin altında yatan ve bir sistemin evriminin ODE'ler tarafından matematiksel olarak temsil edilen deterministik reaksiyon hızı denkleminden (RRE) daha gerçekçi bir temsilini veren aynı mikrofiziksel önermeye titizlikle dayanmaktadır.

Kimyasal ana denklemde olduğu gibi, SSA, çok sayıda reaktan sınırında, kütle hareketi yasasıyla aynı çözüme yakınsar.

Sonraki reaksiyon yöntemi

2000 yılında Gibson ve Bruck tarafından yayınlandı. Bu, kullanılmayan reaksiyon sürelerinin yeniden kullanıldığı ilk reaksiyon yöntemine göre bir gelişmedir. Tepkilerin örneklenmesini daha verimli hale getirmek için tepki sürelerini depolamak için indekslenmiş bir öncelik sırası kullanılır. Öte yandan, eğilimlerin yeniden hesaplanmasını daha verimli hale getirmek için bir bağımlılık grafiği kullanılır. Bu bağımlılık grafiği, belirli bir reaksiyon tetiklendikten sonra hangi reaksiyon eğilimlerinin güncelleneceğini söyler.

Optimize edilmiş ve doğrudan yöntemler sıralama

2004 ve 2005'te yayınlandı. Bu yöntemler, algoritmanın ortalama arama derinliğini azaltmak için kümülatif diziyi sıralar. İlki, reaksiyonların ateşleme sıklığını tahmin etmek için bir varsayım çalıştırırken, ikincisi anında kümülatif diziyi sıralar.

Logaritmik doğrudan yöntem

2006'da yayınlandı. Bu, kümülatif dizi üzerinde ikili bir aramadır, böylece reaksiyon örneklemesinin en kötü durum zaman karmaşıklığını O'ya (log M) düşürür.

Kısmi eğilim yöntemleri

2009, 2010 ve 2011'de yayınlandı (Ramaswamy 2009, 2010, 2011). Hesaplama maliyetini (daha büyük) reaksiyon sayısı yerine ağdaki tür sayısıyla ölçeklendirmek için çarpanlara ayrılmış, kısmi reaksiyon eğilimlerini kullanın. Dört varyant mevcuttur:

  • PDM, kısmi eğilim doğrudan yöntemi. Ağın birleştirme sınıfından bağımsız olarak, reaksiyon ağındaki farklı türlerin sayısı ile doğrusal olarak ölçeklenen bir hesaplama maliyetine sahiptir (Ramaswamy 2009).
  • SPDM, sıralama kısmi eğilim doğrudan yöntemi. Reaksiyon hızlarının birkaç büyüklük sırasına yayıldığı çok ölçekli reaksiyon ağlarında hesaplama maliyetinin ön faktörünü azaltmak için dinamik kabarcık sıralama kullanır (Ramaswamy 2009).
  • PSSA-CR, kompozisyon reddetme örneklemeli kısmi eğilim SSA. Kompozisyon reddetme örneklemesini (Slepoy 2008) kullanarak zayıf bağlı ağlar için (Ramaswamy 2010) hesaplama maliyetini sabit zamana (yani ağ boyutundan bağımsız) düşürür.
  • dPDM, gecikme kısmi eğilim doğrudan yöntemi. PDM'yi, gecikme-SSA yönteminin kısmi-eğilimli bir varyantını sağlayarak (Bratsun 2005, Cai 2007) zaman gecikmelerine neden olan reaksiyon ağlarına genişletir (Ramaswamy 2011).

Kısmi eğilim yöntemlerinin kullanımı, temel kimyasal reaksiyonlarla, yani en fazla iki farklı reaktan ile reaksiyonlarla sınırlıdır. Her temel olmayan kimyasal reaksiyon, ağ boyutunda doğrusal (reaksiyon sırasına göre) bir artış pahasına bir dizi temel reaksiyona eşit olarak ayrıştırılabilir.

Yaklaşık Yöntemler

Stokastik simülasyonların genel bir dezavantajı, büyük sistemler için hepsi bir simülasyonda hesaba katılamayan çok fazla olayın gerçekleşmesidir. Aşağıdaki yöntemler, bazı yaklaşımlarla simülasyon hızını önemli ölçüde artırabilir.

τ sıçrama yöntemi

SSA yöntemi her geçişi takip ettiğinden, yüksek zaman karmaşıklığı nedeniyle belirli uygulamalar için uygulanması pratik olmayacaktır. Gillespie , hesaplama süresini minimum doğruluk kaybıyla azaltan tau sıçraması yöntemi olan bir yaklaşım prosedürü önerdi . SSA yönteminde olduğu gibi her bir zaman adımında X(t)'yi takip ederek zaman içinde artan adımlar atmak yerine, tau sıçraması yöntemi bir alt aralıktan diğerine atlar ve belirli bir alt aralık sırasında kaç geçişin gerçekleştiğini tahmin eder. Sıçramanın değeri olan τ'nun, [t, t + τ] alt aralığı boyunca geçiş oranlarının değerinde önemli bir değişiklik olmayacak kadar küçük olduğu varsayılır. Bu durum sıçrama koşulu olarak bilinir. Tau-sıçrayan yöntem dolayısıyla hesaplama zamanda bir hız ile sonuçlanabilecek önemli doğruluğu kaybetmeden ise bir sıçrama birçok geçişler taklit etme avantajına sahiptir.

Koşullu Fark Yöntemi

Bu yöntem, tersinir bir işlemin karşıt olaylarının yalnızca net oranlarını hesaba katarak (rastgele yürüyüş/difüzyon işlemlerini içeren) tersinir işlemlere yaklaşır. Bu yöntemin temel avantajı, modelin önceki geçiş hızlarını yeni, etkin oranlarla değiştirerek basit bir if-ifadesi ile uygulanabilmesidir. Değiştirilen geçiş oranlarına sahip model, örneğin geleneksel SSA ile çözülebilir.

Sürekli simülasyon

Ayrık durum uzayında belirli durumlar (değerler) arasında açıkça ayırt edilirken, sürekli uzayda belirli süreklilik nedeniyle mümkün değildir. Sistem genellikle zamanla değişir, modelin değişkenleri, daha sonra da sürekli değişir. Böylece sürekli simülasyon , durum değişkenlerinin değişim oranlarını belirleyen diferansiyel denklemler verilerek sistemi zaman içinde simüle eder . Sürekli sistem örneği , avcı/av modeli veya araba-direği dengelemesidir.

Olasılık dağılımları

Normal dağılım

Rasgele X değişkeni olduğu söylenen normal dağılım parametreleri μ ve s, (σ u, X, ∈ N kısaltılmış ile 2 yoğunluğu ise), rastgele değişkenin formül ile verilir X ∈ R

Pek çok şey aslında normal olarak dağıtılır veya buna çok yakındır. Örneğin, boy ve zeka yaklaşık olarak normal dağılmıştır ; ölçüm hataları da genellikle normal dağılıma sahiptir .

üstel dağılım

Üstel dağılım , bir Poisson sürecindeki olaylar arasındaki süreyi , yani olayların sürekli ve bağımsız olarak sabit bir ortalama oranda meydana geldiği bir süreci tanımlar .

Üstel dağılım içinde, örneğin, popüler teoriyi kuyruk biz belli bir olay gerçekleşir kadar beklemek zorunda zaman modellemek istediğinizde. Örnekler, bir sonraki müşterinin mağazaya girmesine kadar geçen süreyi, belirli bir şirketin temerrüde düşmesine kadar geçen süreyi veya bir makinenin kusurlu olmasına kadar geçen süreyi içerir.

Öğrencinin t-dağılımı

Student'ın t-dağılımı , finansta varlık getirilerinin olasılıklı modelleri olarak kullanılır. Yoğunluk fonksiyonu t-dağılımı aşağıdaki denklemle verilir:

burada sayısıdır serbestlik derecesi ve bir gama fonksiyonu .

Büyük n değerleri için , t-dağılımı standart bir normal dağılımdan önemli ölçüde farklı değildir . Genellikle, n > 30 değerleri için t-dağılımı , standart normal dağılıma eşit olarak kabul edilir .

Diğer dağıtımlar

Kombine simülasyon

Tamamen farklı dünya görüşlerini kullanarak tek ve aynı sistemi modellemek çoğu zaman mümkündür. Bir problemin ayrık olay simülasyonu ve bunun sürekli olay simülasyonu (sürekli akışı bozan ayrık olaylarla sürekli simülasyon) sonunda aynı cevaplara yol açabilir. Ancak bazen teknikler bir sistemle ilgili farklı soruları yanıtlayabilir. Tüm soruları cevaplamamız gerekiyorsa veya modelin hangi amaçlar için kullanılacağını bilmiyorsak, birleşik sürekli/ayrık metodolojiyi uygulamak uygundur . Benzer teknikler, ayrık, stokastik bir tanımlamadan, zamana ve mekana bağlı bir şekilde deterministik, sürekli bir tanımlamaya dönüşebilir. Bu tekniğin kullanımı, geleneksel Gillespie algoritmasından çok daha hızlı benzetim yaparken, küçük kopya sayılarından kaynaklanan gürültünün yakalanmasını sağlar. Ayrıca, deterministik süreklilik tanımının kullanılması, keyfi olarak büyük sistemlerin simülasyonlarını mümkün kılar.

Monte Carlo simülasyonu

Monte Carlo bir tahmin prosedürüdür. Ana fikir, eğer bazı rasgele değişkenlerin ortalama değerini bilmek gerekiyorsa ve dağılımı ifade edilemiyorsa ve dağılımdan örnek almak mümkünse, örnekleri bağımsız olarak alarak ve ortalamasını alarak tahmin edebiliriz. onlara. Yeterli örnek varsa, o zaman büyük sayılar yasası, ortalamanın gerçek değere yakın olması gerektiğini söyler. Merkezi limit teoremi, ortalamanın gerçek değer etrafında bir Gauss dağılımına sahip olduğunu söyler .

Basit bir örnek olarak, karmaşık, düzensiz bir anahatla bir şeklin alanını ölçmemiz gerektiğini varsayalım. Monte Carlo yaklaşımı, şeklin etrafına bir kare çizmek ve kareyi ölçmektir. Sonra dartları mümkün olduğunca eşit bir şekilde kareye atıyoruz. Şeklin üzerine düşen dart oranı, şeklin alanının karenin alanına oranını verir. Aslında, hemen hemen her integral problemini veya herhangi bir ortalama alma problemini bu forma dönüştürmek mümkündür. Çerçevenin içinde olup olmadığınızı söylemenin iyi bir yolunun ve kaç tane dart atacağınızı bulmanın iyi bir yolunun olması gerekir. Son olarak, dartları düzgün bir şekilde, yani iyi bir rastgele sayı üreteci kullanarak atmamız gerekiyor .

Başvuru

Monte Carlo Metodu'nun kullanım olanakları geniştir:

Rastgele sayı üreteçleri

İçin simülasyon (Monte Carlo dahil) deney onu üretmek için gerekli olan rasgele (değişkenlerin değerleri olarak) numaraları. Sorun, bilgisayarın son derece deterministik bir makine olmasıdır—temelde, her sürecin arkasında her zaman bir algoritma vardır, girdileri çıktılara çeviren deterministik bir hesaplama; bu nedenle, tanımlanmış bir aralık veya küme üzerinde düzgün bir şekilde yayılmış rasgele sayılar üretmek kolay değildir .

Bir rastgele sayı üreteci "kolayca" ile tespit edilemez bir sayı dizisi üretme yeteneğine sahip bir cihazdır belirleyici özellikleri. Bu diziye daha sonra stokastik sayılar dizisi denir .

Algoritmalar tipik olarak , bir işlemin olası bir sonucu olan bir gerçekleştirme oluşturmak için gerçek rastgele sayıları taklit eden bilgisayar tarafından üretilen sayılar olan sözde rasgele sayılara dayanır .

Rastgele sayıları elde etme yöntemleri uzun süredir var ve birçok farklı alanda ( oyun oynamak gibi ) kullanılmaktadır. Ancak, bu sayılar belirli bir önyargıdan muzdariptir. Şu anda gerçekten rastgele diziler üretmesi beklenen en iyi yöntemler, kuantum fenomenlerinin rastgele doğasından yararlanan doğal yöntemlerdir .

Ayrıca bakınız

Referanslar

Dış bağlantılar

Yazılım
  • cayenne - Stokastik simülasyonlar için hızlı, kullanımı kolay Python paketi. Doğrudan, tau sıçramalı ve tau uyarlamalı algoritmaların uygulamaları.
  • StochSS - StochSS: Stokastik Simülasyon Hizmeti - Stokastik Biyokimyasal Sistemlerin Modellenmesi ve Simülasyonu için Bulut Bilişim Çerçevesi.
  • ResAssure - Stokastik rezervuar simülasyon yazılımı - her jeolojik gerçekleştirme için tamamen örtük, dinamik üç fazlı sıvı akışı denklemlerini çözer.
  • Cain - Kimyasal kinetiğin stokastik simülasyonu. Doğrudan, sonraki reaksiyon, tau sıçraması, hibrit vb.
  • pSSAlib - Tüm kısmi eğilim yöntemlerinin C++ uygulamaları.
  • StochPy - Python'da stokastik modelleme
  • ADIMLAR - C/C++ koduna Python arayüzü oluşturmak için swig kullanan Yol Simülasyonu için Stokastik Motor