무작위 계 컴퓨터시뮬레이션학과 2016년 봄학기 담당교수 : 이형원 E304호,

Presentation on theme: "무작위 계 컴퓨터시뮬레이션학과 2016년 봄학기 담당교수 : 이형원 E304호,"— Presentation transcript:

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

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

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

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

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

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

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

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

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

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

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

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

13 Modelica 소스

14 난수 발생기 사용법

15 C 함수 작성

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

17 실행 결과

18 실행 결과

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

20 Modelica 구현 Motion.y2016.Week10.RandomWalk

21 MoveRandom 함수

22 MoveRandom 함수

23 실행 결과

24 실행 결과

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

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

27 Modelica 구현 Motion.y2016.Week10.RandomWalk2

28 MoveRandomR2 함수

29 MoveRandomR2 함수

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

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

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

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

34 실행 결과

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

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

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

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

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

40 MoveRandomSize 함수

41 MoveRandomSize 함수

42 실행 결과

43

44 실행 결과

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

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

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

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

49 무작위 걸음 𝑥 2

50 결과 해석 걸음 크기를 임의로 하면 확산이 덜 된다. 𝑥 𝑛 = 𝑖=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

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

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

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

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

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

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

57 2차원 결과

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

59 결과

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

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

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

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

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

65 Modelica 클래스 Motion.y2016.Week10.Diffusion1D

66 Diffuse1D 함수

67 Diffuse1D 함수

68 실행결과

69 실행 결과

70 실행 결과

71 실행 결과

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

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

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

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

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

77 Diffuse2D 함수

78 Diffuse2D 함수

79 SaveParticles 함수

80 SetInitial 함수

81 MoveParticle 함수

82 GetEntropy 함수

83 GetEntropy 함수

84 실행결과(엔트로피)

85 실행결과(엔트로피)

86 실행결과(엔트로피)

87 실행결과(엔트로피)

88 오류 발생 re-simulate 다시 simulate

89 정상실행

90 실행결과(입자분포)

91 실행결과(입자분포)

92 실행결과(입자분포)

93 실행결과(입자분포)

94 실행결과(입자분포)

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

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

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

98 Diffuse2DLimit 함수

99 Diffuse2DLimit 함수

100 MoveParticleLimit 함수

101 실행결과(엔트로피)

102 실행결과(엔트로피)

103 실행결과(엔트로피)

104 실행결과(엔트로피)

105 실행결과(입자분포)

106 실행결과(입자분포)

107 실행결과(입자분포)

108 실행결과(입자분포)

109 실행결과(입자분포)

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

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

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

113 Modelica 구현 Motion.y2016.ClusterEden

114 EdenGrowth 함수

115 EdenGrowth 함수

116 SaveCluster 함수

117 InitializeCluster 함수

118 AddParticle 함수

119 IsPerimeter 함수

120 실행 결과

121 실행 결과

122 실행 결과

123 실행 결과

124 실행 결과

125 실행결과

126 실행 결과

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

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

129 DLA 모델

130 얼음 결정 Wikipedia

131 Modelica 구현 Motion.y2016.ClusterDLA

132 DLAGrowth 함수

133 DLAGrowth 함수

134 AddParticleDLA 함수

135 AddParticleDLA 함수

136 AddParticleDLA 함수

137 실행 결과

138 실행 결과

139 실행 결과

140 실행 결과

141 실행 결과

142 실행 결과

143 실행 결과

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

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

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

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

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

149 곡선의 프랙탈 차원 𝐿 𝑒𝑓𝑓 ≡ 𝑁 𝑠 𝐿 𝑠 ~ 𝐿 𝑠 − 𝑑 𝑓 𝐿 𝑠 = 𝐿 𝑠 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− 𝑑 𝑓 𝐿 𝑒𝑓𝑓 𝑘 = 𝑘−1 = 𝑘−1 1− 𝑑 𝑓 𝑘−1 ln 4 − ln 3 =− 𝑘−1 1− 𝑑 𝑓 ln 3 𝑑 𝑓 = ln 4 ln 3 =

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

151 곡선의 프랙탈 차원 Koch 원

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

153 Modelica 구현 Motion.y2016.Week10.Percolation

154 PercolateCluster 함수

155 PercolateCluster 함수

156 실행 결과

157 실행 결과

158

159 실행 결과

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

161 임계 확률

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

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

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

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

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

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