1 lako informativno pitanje u vezi Metropolis algoritma i metoda koji se koriste

pozdrav svima!

moze li mi neko napisti da li se kod Metropolis algoritma (onog koji se koristi u matematichkim simulacijama za generaciju niza (sequence) uzoraka iz neke distribucije verovatnocje :) )

u cilju optimizacije memorijske i vremenske iskorishcjenosti algoritma koriste neki od ovih metoda:

a) Brute-force metod
b) Sorted-lists metod
c) Bit-per-spin metod

ili neshto chetvrto? Ukoliko je mogucje voleo bih i da chujem neko kracje pojashnjenje

hvala!

Koliko sam ja upoznat sa tom tematikom metropolis algoritam jeste samo jedna od varijacija na temu simulirano kaljenje, postupak koji sluzi minimizaciju funkcije a da se pri tome ne upadne u lokalni ekstrem. Ideja je vrlo prosta: funkcija ima skup varijabli na osnovu koje se racuna, uzme se neko pocetno stanje za taj skup promenljivih i naracuna se funkcija, potom se svaka promenljiva promeni za malu random vrednost i ponovo se naracuna funkcija. Ukoliko je vrednost funkcije manja onda zadrsis to stanje i proglasis ga za trenutno dobro, ali ne samo u tom slucaju, postoji i temperatura tog sistema koja se u iterativnom koraku u kom se vrti ova tranzicija smanjuje po nekoj funkciji. Iako su ti parametri mozda losi ti ces zadrzati po nekoj verovatnoci u kojoj figurise temperatura novo stanje promenljivih (to ti obezbedjuje da ne upadnes u ekstrem). Naravno kako se odvija iteracija ta verovatnoca je sve manja. Algoritam se vrti u N iteracija, pri cemu ti biras N, sto vece N to bolji rezultati, greske se uglavnom skaliraju kao jedan sa koren iz N.

Metropolis algoritam koristi generator slucajnih brojeva tako da sumnjam da se on koristi koristi kao generator istih :)

Inace generisanje slucajnih brojeva po nekoj raspodeli je trivijalno ukoliko imas dobar generator random brojeva iz intervala [0 .. 1] koji generise random brojeve po uniformnoj raspodeli.. Za detalje najbolje da pogledas Numerical Recepies in STAGOD

Jedno pitanje: sta je to sorted-list metod, a sta je bit per spin metod?

Bit-per spin mi jako lici na modeliranje celularnim automatima, pri cemu svaka celija ima neko diskretno stanje (spin). Ne vidim kako se to moze uglaviti u jedan numericki algoritam, mada svaku traniziciju u metropolis algoritmom mozes da predstavis jednim vektorom, ali takvih spinova u tom slucaju nema konacno.

pozdrav josh jednom,

pre svega hvala vam na interesovanju!

sada radim diplomski na temu "isingov model u sluchajnom polju" i upravo sam iskoristio simulaciju isingovog modela zvanu Ising koju je napravio amerikanac dan schroeder (dobio sam email da smem da upotrebim ovaj prog.) , evo linkova:

http://physics.weber.edu/schroeder/software
http://physics.weber.edu/schroeder/software/ising.zip

u kojoj je urachunata interakcija susednih cjelija (naravno poshto je ising) i termalna fluktuacija a spoljno magnetno polje moze se zadavati. na sajtu je dat i source... autor je napisao da je ovo monte karlo, simulacija uz upotrebu metropolis algoritma.

ono shto mene interesuje je kako da klasifiqjem taj metropolis algoritam u neku od ove tri kategorije koje sam na pochetq pomenuo ili je to neka chetvrta ?!

inache (kol'ko ja znam - a to nije bash previshe B) ):

Sorted-lists metod => u odnosu na brute force je brzi jer problem sa brute force-om u tome shto je svaki put pri trazenju novog mesta na kome cje pocheti nova lavina, neophodno pretraziti celu resetku, neefikasnost ovog algoritma moze se otkloniti primenom ideje skladishtenja liste spinova gde je kriterijum za rangiranje prvog sledecjeg mogucjeg mesta na kome cje pocheti lavina, broj njegovih preokrenutih suseda. za spinove u istoj klasi, tj. spinove koji imaju isti broj preokrenutih suseda, rangiranje se vrshi po najvecjoj vrednosti sluchajnog polja.
nedostatak ovog algoritma je u tome što je potrebno mnogo mesta za skladishtenje sluchajnih polja ...

a shto se Bit-per-spin metoda tiche samo je fora (bi trebalo da bude B) ) shto smeshta informaciju u jedan bit (orijentaciju spina atoma (- odnosno cjelije superkubne reshetke u isingovom modelu) te time shtedi memoriju pa je bolji od gore pomenutog...

btw sve mi je bilo jasno dok nisam nashao ovu simulaciju a sada poshto nisam vichan preteranom programiranju - pogotovu ne u real basicu nije mi najjasnije kako ovaj program radi odnosno kako koristi metropolis. B(

Pa onda tebi treba i sorted-list i bit-per spin metod, samo sto je bit-per spin zaista metod a sorted-list je samo njegova optimizacija.
Isingov model najlakse mozes realizovati kao celularni automat (matrica, svaki element matrice je celija, operacije nad celijom su lokalnog tipa). Svaka celija ima spin (gore, dole), na pocetku sa nekom distribucijom verovatnoce postavis
inicijalno stanje svake celije. U svakoj iteraciji stanje (spin) celije se menja u zavisnosti od stanja susednih celija i to vrlo diskretno bez ucesca bilo kakvih random promenljivih (jedino ako neces da zakomplikujes model a za tim nema potrebe). Lavine ces lako detektovati, samo pratis koliko je ukupno spinova promenjeno u jednoj iteraciji, onog trenutka kada na tom grafiku funkcije budes imao fazni prelaz eto ti je lavina.

Optimizacija svega ovoga jeste to sto zoves sorted-list.

Inace ovo je vrlo lako za isprogramirati a i postoji gomila radova na ovu temu, imas i neke studentske srednjoskolske projekte na istu ovu temu (Samoorganizovana kriticnost u game of life je jedan srednjoskolski projekat koji je veoma slican ovome, probaj da nadjes na netu, autor je Jelena Grujic)

Pogledao sam program, jos bi bilo bolje da ima source, ali zakljucak koji mogu da donesem na osnovu pokretanja simulacije i citanja helpa jeste da algoritam simuliranog kaljenja tu sluzi da se odredi kriticna temperatura na kojoj se model ponasa na ivici haosa. Nebitno je u koju ces ti navedenu klasu da stavis taj algoritam posto je to programersko pitanje realizacije/optimizacije a ne pitanje samog modela.

ahoy

ima i source za program da se skine:

http://physics.weber.edu/schroeder/software/IsingSource.sit // u real basicu
http://physics.weber.edu/schroeder/software/IsingSource.txt // plain text
http://physics.weber.edu/thermal/Ising.java // java

mada sam nashao josh jedan lep sajt gde sam prochitao dosta toga o metropolisu...

hvala josh jednom!

Evo pogledao sam kod i on radi sledece:

- polje je predstavljeno matricom. Svaka celija matrice ima dva stanja (spin up i spin down)
- celije matrice se na pocetku inicijalizuju i to sa verovatnocom 0.5 za spin up i verovatnocom 0.5 za spin down
- u beskonacnoj petlji se iterira model, tj od trenutnog stanja matrice se pravi sledece stanje na sledeci nacin:
Random se odabere jedna celija u matrici
Izracuna se tzv hipoteticka energija kada se promeni spin u toj celiji
Ako je hipoteticka energija manja od trenutne zadrzi se novo stanje promenjene celije
Inace sa verovatocom koja odgovara Bolcmanovoj raspodeli se promeni spin tog polja (da se ne upadne u ekstrem)

Hipoteticka energija za jednu celiju se racuna na osnovu stanja spinova njenih suseda

I to je cela mudrost...

super, trebalo bi da je tako :)

to sam i prochitao na

http://oscar.cacr.caltech.edu/Hrothgar/Ising/monte.html

na dnu strane, jeste da jednostavno zvuchi al'mislim da je dobra fora

hvala najlepshe na trudu!

sve najbolje