[알고리즘] 몬테카를로 알고리즘

출처: http://www.aistudy.co.kr/physics/monte_carlo_method.htm

Monte Carlo mothod

 

Monte Carlo method 는 임의의 수 (random number 또는 pseudo-random number) 를 사용하여 다양한 계산문제를 푸는 알고리즘 으로서 결정적 알고리즘 (deterministic algorithm) 의 반대되는 개념이다. 전산물리 (computational physics) 와 관련 응용분야에서 매우 중요한 방법이며 esoteric quantum chromodynamics calculations 로부터 heat shields and aerodynamic forms 설계 까지 다양한 응용을 갖는다. 이 방법은 radiance field 를 정의하는 적분-미분 방정식들을 푸는데 효율적인 것으로 증명되었고, 따라서 photorealistic images of virtual 3D models 를 만드는 global illumination computations 에 사용되어 왔으며, 비디오게임, 건축, 설계, 컴퓨터제작 필름, 영화의 특수효과, 경영, 경제 등등의 여러분야에 응용되었다.

흥미롭게도 Monte Carlo method 은 진짜 임의의 수를 사용할 필요는 없다. 대부분의 유용한 기술은 deterministic, pseudo-random sequences 를 사용하며 test and re-run simulations 를 쉽게 만든다. 좋은 시뮬레이션을 만드는데 필요한 진짜 중요한 것은 pseudo-random sequence 가 "충분히 임의적인 것으로 (random enough)" 보이게 하는 것이다. 즉 충분히 많은 수의 요소들의 순서가 고려될때 균일 분포 (uniformly distributed) 하거나 다른 바람직한 분포를 따라야 한다는 것이다.

알고리즘의 반복과 많은 수의 계산이 포함되기때문에, Monte Carlo 는 컴퓨터를 사용하여 계산하기에 적당한 방법이며, 컴퓨터 시뮬레이션의 많은 기술을 사용하기에 적당한 방법이다.

Monte Carlo algorithm 은 쉽게 풀리지 않는 수학문제 (많은 변수를 가지는 문제, 예를들면 integral calculus 같은) 의 해를 찾는데 사용하는 numerical Monte Carlo method 를 말한다. 문제의 차원 (dimension) 이 증가할때에 다른 수치적 방법들에 비교해서 Monte Carlo algorithm 의 효율성이 더 증가한다. ............. (Wikipedia : Monte Carlo mothod)

몬테칼로 기법이라 하면 뭐 대단히 어려운 전산과학의 기법인양 생각하게 쉬운데 사실은 간단한 보기를 통하여 그 핵심은 설명할 수 있다.   전산물리라 하면 몬테칼로 기법을 가지고 물리 문제를 푸는 것이라 해도 과언이 아닐 정도로 몬테칼로 기법은 전산물리의 중요 중심과제다.  

내가 내 생애의 절반 이상을  컴퓨터를 써서 이 몬테칼로 방법을 연구하고 개발하고 그 방법을 써서 물질의 상전이와 고비현상을 연구하였다.  그래서 내 논문중 여러개가 이와 관련되어 있다.  대표적인 것으로  Journal of Physics 에 발표한  "A New Efficient Monte Carlo Technique",  "A Rejection free Monte Carlo Technique" 라든가  또 물리학계에선 세계에서 가장 권위 있는 학술지인 Physical Review Letters 에 실린 논문도 "Monte Carlo Technique for Universal Finite Scaling Funtions..." 이다.  그래서 지금도 컴퓨터와 몬테칼로 기법을 이렇게 이야기하면서 써 내려가면 내 정열을 바쳤던 옛 추억에 내 가슴에는 잔잔한 흥분이 인다.  그 때가 세벽 3시였다.  새로운 효율적 몬테칼로 기법을 생각해 내고 그 방법을 연구하고 있을 때였다.  훨씬 좋은결과가 나와야 했다. 정확한 풀이가 알려진 상태함수를 새로 개발한 기법을 써서 셈한 다음 그 결과를 곡선으로 그려 정확한 곡선과 비교해 보는데 그 차이가   너무 컸다.  나는 좌절감 때문에 맥이 빠져 있었다.  아무래도 풀그림에 문제가 있다고 생각되었다.  아직 랩톱이 없을 때였고 집에 PC를 하나 놓을 만한 사치를 부릴 수 있는 때가 아니었다. 그래서 Televideo 라는 천근은 되는 휴대용(?) PC(IBM-XT 호환기종)를 학교와 집사이를 가지고 다니고 있었다. 나는 다시 컴퓨터를 켜고 풀그림을 자세히 하나 하나 점검해 갔다.  한군데 루프 변수 "i" 가 찍혀 있을 곳에  상수 "l" 이 찍혀 있었다.  그래서 그 버그를 수정하고 다시 풀그림을 돌려 보니 곡선이 하나가 사라졌다.  나는 착시현상을 일으켰거나 풀그림에 문제가 생긴줄 알았다.  나중에 알고 보니 몬테칼로 셈이 너무 잘 맞아서 정확한 풀이 곡선을 덮어 그렸던 것이다.   그 때 그 흥분과 감동은 아직도 어제 일인양 생생하다.   컴퓨팅의 맛이란 바로 그런 것이다. ......

몬테칼로 기법이란 막수 (random number) 만을 생성해서 수치셈 (computation) 을 하는 것이라 말할 수 있다 ......... (source 이구철)

먼저 몬테 칼로라는 이름의 유래에 대해서 말하지요.  프랑스의 남쪽 지중해를 마주 보는 이태리와의 국경지대에 모나코라는 작은 나라가 있습니다. 한 40 년쯤 전에 미국에서 한참 잘 나가던 여배우 그래이스 케리가  이 나라 왕과 결혼하는 사건이 있어 이 작은 나라는 세상을 떠들썩하게 했습니다.  이 나라의 서울의 이름이 몬테 칼로인데 이 곳은 카지노라는 도박장으로 유명합니다. 바티칸 다음으로 작은 독립국으로 국가 재정은 이 카지노 영업에서 생기는 수입으로 꾸려 나가고 있습니다.   도박을 즐기는 세계의 노름꾼들이 자신의 도박 운을 주사위에 걸기 위해 몰려 듭니다. 1942년 2 차 세계대전의 폭연이 막 피어 오르던 때 미국 서부지역에 있던 로스 알라모스의 비밀 연구소에서는 세계의 초 일류 두뇌들이 모여서 원자탄 개발을 서두르고 있었습니다.  이 지음 제 1 세대의 컴퓨터가 이곳에서 그 모습을 들어 내기도 했지요.  이곳에 연구하던 Stanisław Ulam 이라는 수학자가 Enrico Fermi, John von Neumann, Nicholas Metropolis 등등의 수학, 물리학자와 함께 수치 셈을 하는 한 방편으로 확률적 방법을 생각 해 내었습니다.  이 생각을 처음 한 유램이 제안한 이름이 몬테 칼로 방법입니다.  모나코의 카지노를 떠 올리고 지은 이름이 아닌가 생각합니다.  카지노나 수치적분이나 모두 주사위를 던져서 그 목적을 달성한다는 점에서 같은 동아리에 속한다고 볼 수 있기 때문입니다. ............... (source  이구철)

term :

계산 (Computation)   모의 담금질 (Simulated Annealing)   최적화 (Optimization)   순회판매원 문제 (Travelling Salesman Problem)    유전알고리즘 (Genetic Algorithm)   몬테칼로 기법 (Monte Carlo method)   

site :

• 뷔퐁의 바늘- 몬테칼로 기법의 원조 : 이구철
• 몬테칼로 기법이란 : 이구철
• 몬테칼로 시뮬레이션 (Monte Carlo Simulation)