무작위 계 컴퓨터시뮬레이션학과 2016년 봄학기 담당교수 : 이형원 E304호, hwlee@inje.ac.kr 운동시뮬레이션 제10주 무작위 계 컴퓨터시뮬레이션학과 2016년 봄학기 담당교수 : 이형원 E304호, hwlee@inje.ac.kr

여러분들의 질문 지난 주 실습하는 과정에서의 질문

토론을 위한 질문 초기값 문제의 미분방정식을 해결하는 것을 통틀어서 무엇이라고 하는가? 1차원 Random Walk에서 좌우로 움직일 확률은 각각 얼마인가? 시간이 지남에 따라 1차원 Random Walker의 위치는 어떻게 되는가?

토론을 위한 질문 3차원 공간에서 한 순간에 한 위치에 물체가 존재할 확률은 이전 순간의 확률로 어떻게 표시 되는가? 확산 방정식의 안정조건은 어떻게 되는가? Flory exponent 란 무엇인가?

책 읽기 퀴즈 무작위성(randomness)이 중요한 역할을 하는 시스템을 ( )이라고 한다. 난수를 활용하여 시뮬레이션 하는 이유는 입자의 수가 ( ) 때문이다. 1차원 Random Walker의 위치의 제곱의 평균은 시간이 지남에 따라 ( )한다. 확산방정식의 안전 조건은 ( )방정식에서의 안정 조건과 유사하다. 스토캐스틱 많기 증가 파동

단어 퀴즈 Stochastic Randomness Random walk Cream particles Diffusion Self-avoiding walks Entropy

다음주 과제 실습해오기 제 8 장 읽어오기 숙제 제출하기

내용 왜 무작위 과정을 시뮬레이션 하는가? 무작위 걸음 재방문 불허 걸음 무작위 걸음과 확산 확산, 엔트로피 그리고 시간의 화살 군락 증가 모델 곡선의 프랙탈 차원 침습 프랙탈에서의 확산

왜 무작위 과정을 시뮬레이션 하는가? 결정론적(deterministic) 계 무작위 또는 확률적인(stochastic ) 계 주어진 경계조건을 만족하는 미분 방정식 무작위 또는 확률적인(stochastic ) 계 매우 많은 자유도 상호작용이 통계적(열적) 대표적 확률적인 계 확산

확산 약 10 23 개의 입자에 대한 미분방정식 비현실적 개개 입자의 운동이 물리적 과정을 이해 하는 데 도움이 안 된다.

무작위 걸음 알고리즘 걸음 수에 따른 확산 𝑥 2 =2𝐷𝑡 Generate random #r [0:1] r>0.5 ? 걸음 수에 따른 확산 𝑥 2 =2𝐷𝑡 Generate random #r [0:1] r>0.5 ? Move left Move right 아니오 예

난수 발생기 𝑋 𝑛+1 = 𝑎 𝑋 𝑛 +𝑐 mod 𝑚 : 기본 난수 발생기 추가한 난수 발생기 𝑎 1 =171, 𝑎 2 =172, 𝑎 3 =170 𝑚 1 =30269, 𝑚 2 =30307, 𝑚 3 =30323

Modelica 소스

난수 발생기 사용법

C 함수 작성

난수발생 예제 Motion.y2016.Week10.RandTest

실행 결과

실행 결과

RandomWalk 프로그램의 동작 주어진 수 만큼의 Walker에 대하여 각각 주어진 수 만큼의 걸음 수만큼 0부터 시작하여 걸음을 걷고 그 값을 기록한다. 각 걸음 수에 대하여 각 Walker의 위치 값을 파일에 저장한다. 저장된 파일의 내용을 gnuplot 으로 그림을 그린다.

Modelica 구현 Motion.y2016.Week10.RandomWalk

MoveRandom 함수

MoveRandom 함수

실행 결과

실행 결과

결과 해석 같은 곳에서 출발했다 하더라도 시뮬레이션할 때 마다 다른 결과를 준다. 평균적으로 시작 위치에서 걸음을 걸을 수록 멀어진다.

분산결과 확인 RandomWalk에서 𝑥 2 의 평균을 구하여 확인 Random walk에서 𝑥 2 =2𝐷𝑡 로 주어진다. 제곱의 평균을 계산하여 출력한다.

Modelica 구현 Motion.y2016.Week10.RandomWalk2

MoveRandomR2 함수

MoveRandomR2 함수

실행 결과 한 개의 무작위 걸음

실행결과 5 개의 무작위 걸음

실행 결과 50 개의 무작위 걸음

실행 결과 500 개의 무작위 걸음

실행 결과

결과 해석 여러 무작위 걸음의 위치의 제곱의 평균은 스텝 수에 비례해서 증가한다. 무작위 걸음의 확산 계수는 𝑥 2 ≈𝑛=𝑡 이므로 𝐷=1/2 이다.

이론적 설명 𝑛 걸음 후의 위치 𝑥 𝑛 은 𝑥 𝑛 = 𝑖=1 𝑛 𝑠 𝑖 , 𝑠 𝑖 =±1 로 주어진다. 𝑛 걸음 후의 위치 𝑥 𝑛 은 𝑥 𝑛 = 𝑖=1 𝑛 𝑠 𝑖 , 𝑠 𝑖 =±1 로 주어진다. 𝑥 𝑛 2 = 𝑖=1 𝑛 𝑠 𝑖 𝑗=1 𝑛 𝑠 𝑗 = 𝑖=1 𝑛 𝑗=1 𝑛 𝑠 𝑖 𝑠 𝑗 𝑠 𝑖 𝑠 𝑗 =±1, 𝑖≠𝑗, 𝑠 𝑖 𝑠 𝑗 =1, 𝑖=𝑗 𝑥 𝑛 2 = 𝑖=1 𝑛 𝑠 𝑖 2 =𝑛 𝑥 2 =2𝐷𝑡

𝑥 𝑛 2 의 분산 𝑥 𝑛 2 − 𝑥 𝑛 2 2 = 𝑥 𝑛 4 − 𝑥 𝑛 2 2 𝑥 𝑛 4 = 𝑖,𝑗,𝑘,𝑙=1 𝑛 𝑠 𝑖 𝑠 𝑗 𝑠 𝑘 𝑠 𝑙 𝑖=𝑗=𝑘=𝑙 , 𝑖=𝑗, 𝑘=𝑙 , 𝑖=𝑘, 𝑗=𝑙 𝑖=𝑘, 𝑗=𝑙 , 𝑖=𝑙, 𝑗=𝑘 𝑥 𝑛 4 = 𝑖=1 𝑛 𝑠 𝑖 4 +3 𝑖=1 𝑛 𝑠 𝑖 2 𝑗≠𝑖 𝑠 𝑗 2 =𝑛+3 𝑖=1 𝑛 𝑛−1 =𝑛+3𝑛 𝑛−1 =3 𝑛 2 −2𝑛 𝑥 𝑛 2 − 𝑥 𝑛 2 2 = 2 𝑛 2 −2𝑛 ≈ 2 𝑛

일반화 무작위 걸음 크기 : 걸음의 크기를 임의로 한다. 3차원 걸음 : 걸음을 임의 방향으로 한다.

무작위 걸음 크기 구현 Modelica.y2016.Week10.RandomWalkSize

MoveRandomSize 함수

MoveRandomSize 함수

실행 결과

실행 결과

실행 결과 1 개의 무작위 걸음 𝑥 2

실행 결과 5 개의 무작위 걸음 𝑥 2

실행 결과 50 개의 무작위 걸음 𝑥 2

실행 결과 500 개의 무작위 걸음 𝑥 2

무작위 걸음 𝑥 2

결과 해석 걸음 크기를 임의로 하면 확산이 덜 된다. 𝑥 𝑛 = 𝑖=1 𝑛 𝑟 𝑖 , −1≤ 𝑟 𝑖 ≤1 𝑥 𝑛 = 𝑖=1 𝑛 𝑟 𝑖 , −1≤ 𝑟 𝑖 ≤1 𝑥 𝑛 2 = 𝑖=1 𝑛 𝑗=1 𝑛 𝑟 𝑖 𝑟 𝑗 = 𝑖=1 𝑛 𝑟 𝑖 2 𝑥 𝑛 2 = 𝑖=1 𝑛 𝑟 𝑖 2 = 1 3 𝑛=2𝐷𝑡→𝐷= 1 6 𝑟 2 = 1 2 −1 1 𝑟 2 𝑑𝑟 = 1 3

재방문 불허 걸음(SAW) 긴 단백질 시뮬레이션 𝑟 2 ~𝐴 𝑡 𝜈 𝜈 는 Flory 지수

SAW 생성 (a) 와 (b) 는 같은 확률로 생성되지 않는다.

Flory 지수 𝜈=3/4 2차원 경우 𝜈=3/5 5차원 경우

계수(enumeration) 방법 DFS를 이용하여 주어진 걸음 수에 따른 가능한 모든 SAW를 찾는다. 각 걸음 수에 따른 𝑟 𝑛 2 을 계산한다. 𝑛→∞ 보내어 근사를 구한다.

깊이 우선 탐색(DFS) 임의의 위치에서 출발하여 주어진 걸음 만큼 갈 수 있을 만큼 이동한 모든 경로를 찾는다.

깊이 우선 탐색(depth first search : DFS) 순회 방법 시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해 가다가 더 이상 갈 곳이 없게 되면, 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아와서 다른 방향의 간선으로 탐색을 계속 반복하여 결국 모든 정점을 방문하는 순회방법 가장 마지막에 만났던 갈림길 간선의 정점으로 가장 먼저 되돌아가서 다시 깊이 우선 탐색을 반복해야 하므로 후입선출 구조의 스택 사용 깊이 우선 탐색의 수행 순서 ⑴ 시작 정점 v를 결정하여 방문한다. ⑵ 정점 v에 인접한 정점 중에서 방문하지 않은 정점 w가 있으면, 정점 v를 스택에 push하고 w를 방문한다. 그리고 w를 v로 하여 다시 ⑵를 반복한다. 방문하지 않은 정점이 없으면, 탐색의 방향을 바꾸기 위해서 스택을 pop하여 받은 가장 마지막 방문 정점을 v로 하여 다시 ⑵를 수행한다. ⑶ 스택이 공백이 될 때까지 ⑵를 반복한다.

2차원 결과

결과 𝑟 𝑛 2 ~ 𝐴 2 𝑛 2𝜈 𝑟 𝑛+1 2 𝑟 𝑛 2 ~ 𝐴 2 𝑛+1 2𝜈 𝐴 2 𝑛 2𝜈 ~ 1+ 1 𝑛 2𝜈 ~1+ 2𝜈 𝑛

결과

무작위 걸음과 확산 Coarse graining method 입자밀도의 시간변화

𝑃(𝑖,𝑗,𝑘,𝑛) : Probability to find the particle at site (i,j,k) at time n. 𝑃 𝑖,𝑗,𝑘,𝑛 = 1 6 𝑃 𝑖+1,𝑗,𝑘,𝑛−1 +𝑃 𝑖−1,𝑗,𝑘,𝑛−1 + 𝑃 𝑖,𝑗+1,𝑘,𝑛−1 +𝑃 𝑖,𝑗−1,𝑘,𝑛−1 + 𝑃 𝑖,𝑗,𝑘+1,𝑛−1 +𝑃(𝑖,𝑗,𝑘−1,𝑛−1) 𝜕𝑃(𝑥,𝑦,𝑧,𝑡) 𝜕𝑡 =𝐷 𝛻 2 𝑃 𝑥,𝑦,𝑧,𝑡 𝜕𝜌 𝜕𝑡 =𝐷 𝛻 2 𝜌→𝜌 𝑥,𝑡 = 1 𝜎 𝑒 − 𝑥 2 𝜎 2 , 𝜎= 2𝐷𝑡

양변에서 𝑃 𝑖,𝑗,𝑘,𝑛−1 를 빼면 다음 식을 얻는다. 𝑃 𝑖,𝑗,𝑘,𝑛 −𝑃 𝑖,𝑗,𝑘,𝑛−1 = 1 6 𝑃 𝑖+1,𝑗,𝑘,𝑛−1 +𝑃 𝑖−1,𝑗,𝑘,𝑛−1 −2𝑃(𝑖,𝑗,𝑘,𝑛−1)+ 𝑃 𝑖,𝑗+1,𝑘,𝑛−1 +𝑃 𝑖,𝑗−1,𝑘,𝑛−1 −2𝑃(𝑖,𝑗,𝑘,𝑛−1)+ 𝑃 𝑖,𝑗,𝑘+1,𝑛−1 +𝑃 𝑖,𝑗,𝑘−1,𝑛−1 −2𝑃(𝑖,𝑗,𝑘,𝑛−1)

1차원 시뮬레이션 𝜌 𝑖,𝑛+1 =𝜌 𝑖,𝑛 + 𝐷∆𝑡 ∆𝑥 2 𝜌 𝑖+1,𝑛 +𝜌 𝑖−1,𝑛 −2𝜌(𝑖,𝑛) 𝜌 𝑖+1,𝑛 +𝜌 𝑖−1,𝑛 −2𝜌(𝑖,𝑛) 안정 조건 ∆𝑡≤ ∆𝑥 2 / 2𝐷 ← 𝑥 2 ~2𝐷𝑡 𝑟≡ 𝐷∆𝑡 ∆𝑥 2 < 1 2

Diffusion1D 1차 미분 방정식인 Diffusion 방정식을 계산한다. 파동과 유사하게 시간에 따라 밀도 값을 출력한다.

Modelica 클래스 Motion.y2016.Week10.Diffusion1D

Diffuse1D 함수

Diffuse1D 함수

실행결과

실행 결과

실행 결과

실행 결과

결과 해석 밀도의 확산은 시간에 따라 가우스 형태로 변화되어 가는 것을 알 수 있다. 값이 0이 되는 점이 나타나는 것은 초기 밀도가 한 점에서만 존재하는 것으로 주었기 때문이다.

확산, 엔트로피 그리고 시간의 화살 무작위 걸음으로 확산현상 시뮬레이션 엔트로피 변화 관찰 정한 구역 내의 입자의 존재 확률 계산 엔트로피 접근 𝑆=− 𝑖 𝑃 𝑖 ln 𝑃 𝑖

에르고딕 가설(ergodic hypothesis) 모든 닫힌 계에서는 시간이 오래 지나면 모든 가능한 계의 상태가 같은 확률로 존재할 수 있다. 기본 원리로부터 유도 되는 것이 아님.

어느 것이 정렬이 잘 되어 있는가? 열린계

Modelica 클래스 Motion.y2016.Week10.Diffusion2D 입자가 위치할 수 있는 범위에 제한을 두지 않는 경우 : 열린 계

Diffuse2D 함수

Diffuse2D 함수

SaveParticles 함수

SetInitial 함수

MoveParticle 함수

GetEntropy 함수

GetEntropy 함수

실행결과(엔트로피)

실행결과(엔트로피)

실행결과(엔트로피)

실행결과(엔트로피)

오류 발생 re-simulate 다시 simulate

정상실행

실행결과(입자분포)

실행결과(입자분포)

실행결과(입자분포)

실행결과(입자분포)

실행결과(입자분포)

결과 해석 무작위 걸음에 의하여 확산 현상을 시뮬레이션 한다. 입자 위치에 제한을 두지 않았기 때문에 열린 계를 시뮬레이션 한다. 시간이 오래 지나도 평형에 도착하지 않는다. 즉 엔트로피가 계속해서 줄고 있다.

어느 것이 정렬이 잘 되어 있는가? 닫힌계

Modelica 클래스 Motion.y2016.Week10.Diffusion2DLimit 입자가 위치할 수 있는 범위에 제한을 두는 경우 : 닫힌 계

Diffuse2DLimit 함수

Diffuse2DLimit 함수

MoveParticleLimit 함수

실행결과(엔트로피)

실행결과(엔트로피)

실행결과(엔트로피)

실행결과(엔트로피)

실행결과(입자분포)

실행결과(입자분포)

실행결과(입자분포)

실행결과(입자분포)

실행결과(입자분포)

결과 해석 무작위 걸음에 의하여 확산 현상을 시뮬레이션 한다. 입자 주어진 상자 내에만 움직이게 하여 닫힌 계를 시뮬레이션 한다. 시간이 오래 지나면 평형에 도착한다. 즉 엔트로피가 일정한 값(최대값)으로 유지 된다.

군락 증가 모델 결정이나 물질이 어떻게 크기가 증가 하는가?

에덴(Eden) 모델 현 군락의 외곽에 있는 위치 중에 임으로 선택하여 입자를 추가한다. “cancer” model 중심으로부터 퍼져 나가는 모양 추가된 입자 외곽 위치

Modelica 구현 Motion.y2016.ClusterEden

EdenGrowth 함수

EdenGrowth 함수

SaveCluster 함수

InitializeCluster 함수

AddParticle 함수

IsPerimeter 함수

실행 결과

실행 결과

실행 결과

실행 결과

실행 결과

실행결과

실행 결과

결과 해석 에덴모델은 군락의 증가가 거의 원형으로 증가한다. 군락의 내부에는 거의 빈 곳이 발생하지 않는다. 군락의 프랙탈 차원이 2 와 거의 같다.

DLA 모델 DLA : Diffusion-limited aggregation 확산 제한 성장 모델 임의의 위치에서 입자가 무작윈 걸음을 시작하여 군락의 외곽에 도착하면 입자를 추가한다. 여러 가지가 있는 모양 수용액 내에서의 결정의 성장

DLA 모델

얼음 결정 Wikipedia

Modelica 구현 Motion.y2016.ClusterDLA

DLAGrowth 함수

DLAGrowth 함수

AddParticleDLA 함수

AddParticleDLA 함수

AddParticleDLA 함수

실행 결과

실행 결과

실행 결과

실행 결과

실행 결과

실행 결과

실행 결과

결과해석 군락의 증가가 가지처럼 진행된다. 군락에 빈 부분이 많음을 알 수 있다. 군락의 프랙탈 차원이 2 보다 훨씬 작다.

프랙탈 차원 반경 r 내의 물질의 양 직선의 경우 일반 적인 경우 𝑚 𝑟 =𝜎𝜋 𝑟 2 직선의 경우 𝑚 𝑟 =𝜆𝑟 일반 적인 경우 𝑚 𝑟 ~ 𝑟 𝑑 𝑓 일정한 비율로 빈공간이 있으면 프랙탈 차원은 정수 이다. 빈공간의 크기가 거리에 따라 증가해야 한다.

군락의 프랙탈 차원 log 𝑚 𝑟 ~ 𝑑 𝑓 log 𝑟

곡선의 프랙탈 차원 4차 Koch 곡선 3차 Koch 곡선 2차 Koch 곡선 1차 Koch 곡선

곡선의 프랙탈 차원 𝐿 𝑒𝑓𝑓 ≡ 𝑁 𝑠 𝐿 𝑠 ~ 𝐿 𝑠 − 𝑑 𝑓 𝐿 𝑠 = 𝐿 𝑠 1− 𝑑 𝑓

곡선의 프랙탈 차원 𝐿 𝑒𝑓𝑓 ≡ 𝑁 𝑠 𝐿 𝑠 ~ 𝐿 𝑠 − 𝑑 𝑓 𝐿 𝑠 = 𝐿 𝑠 1− 𝑑 𝑓 차수 𝑵 𝒔 𝑳 𝒔 𝑳 𝒆𝒇𝒇 1 4 0 1/ 3 0 4 0 / 3 0 2 4 1 1/ 3 1 4 1 / 3 1 3 4 2 1/ 3 2 4 2 / 3 2 4 4 3 1/ 3 3 4 3 / 3 3 5 4 4 1/ 3 4 4 4 / 3 4 6 4 5 1/ 3 5 4 5 / 3 5 𝐿 𝑒𝑓𝑓 ≡ 𝑁 𝑠 𝐿 𝑠 ~ 𝐿 𝑠 − 𝑑 𝑓 𝐿 𝑠 = 𝐿 𝑠 1− 𝑑 𝑓 𝐿 𝑒𝑓𝑓 𝑘 = 4 3 𝑘−1 = 1 3 𝑘−1 1− 𝑑 𝑓 𝑘−1 ln 4 − ln 3 =− 𝑘−1 1− 𝑑 𝑓 ln 3 𝑑 𝑓 = ln 4 ln 3 =1.26186

무작위 Koch 곡선 𝐿 𝑒𝑓𝑓 ≡ 𝑁 𝑠 𝐿 𝑠 ~ 𝐿 𝑠 − 𝑑 𝑓 𝐿 𝑠 = 𝐿 𝑠 1− 𝑑 𝑓

곡선의 프랙탈 차원 Koch 원

침습 땅에 물이 스며드는 현상 바위에 기름이 스며드는 현상 Spanning Cluster : 전체를 다 연결하는 군락->침습, 투과 (Percolation)

Modelica 구현 Motion.y2016.Week10.Percolation

PercolateCluster 함수

PercolateCluster 함수

실행 결과

실행 결과

실행 결과

결과 해석 확률이 커질 수록 큰 군락이 형성된 것을 알 수 있다. 임계 확률은 0.593 이다.

임계 확률

점유율 𝐹= 𝐹 0 𝑝− 𝑝 𝑐 𝛽 𝛽=5/36

BFS 탐색 Spanning 군락 형성 Breath First Search(BFS) 탐색 알고리즘

프랙탈에서의 확산 프랙탈 구조에서의 무작위 걸음

프랙탈에서의 확산 확산 계수 시작점으로 돌아올 확률 관계식 𝑟 𝑡 2 ~ 𝑡 2/ 𝑑 𝜔 , 𝑑 𝜔 >2(sub-diffusive) 시작점으로 돌아올 확률 𝑃 0 𝑡 ~ 𝑡 − 𝑑 𝑠 /2 관계식 𝑑 𝑠 =2 𝑑 𝑓 / 𝑑 𝜔 ℓ~ 𝑡 1/ 𝑑 𝜔

관계식 유도 군락의 크기 가능한 점의 개수 원 점으로 돌아올 확률 ℓ~ 𝑡 1/ 𝑑 𝜔 𝑁~ ℓ 𝑑 𝑓 ~ 𝑡 𝑑 𝑓 / 𝑑 𝜔 원 점으로 돌아올 확률 𝑃 0 ~ 1 𝑁 ~ 𝑡 − 𝑑 𝑓 / 𝑑 𝜔 = 𝑡 −𝑑 𝑠 /2 𝑑 𝑠 =2 𝑑 𝑓 / 𝑑 𝜔

눈먼 개미 모형 마르코프(Markov) 행렬 𝑊= 1 2 1 4 1 4 1 4 3 4 0 1 4 0 3 4 , 𝑊 𝑖𝑗 j에서 i로 갈 확률 1 3 2