I enjoyed writing with a single stroke on the self-avoiding random walk ~ Using python with reference to Computational Physics I (Asakura Shoten) ~
Preface
I have created a self-avoiding random walk program in python that is used for simulating the structure of proteins. I feel like I can make a fundamental rework, but it was fun.
What is a random walk?
A random walk is a movement in which the next point to move is randomly selected, and models based on the random walk are used in various studies. For example, the Brownian motion, which is famous for its research by Einstein, is the irregular movement of fine particles in pollen floating on the surface of the water, which is also one of the movements that can be simulated with a model using a random walk. The topic of this time, self-avoiding random walk, is a random walk that does not take the route that you took again. For example, describe the motion of randomly moving the grid points of a two-dimensional rectangular grid with a single stroke. In practice, self-avoiding random walks are sometimes used to simulate protein structure.
I made a self-avoiding random walk program
Due to the above properties, the self-avoiding random walk program (1) needs to avoid the route once taken, (2) there is no point where it can move from the current position to the next (surrounded by its own route), and the simulation of the random walk. Must end. In addition, (3) the simulation ends even when the boundary of the set area is reached.
The program for self-avoiding random walk on a 2D rectangular grid is as follows. In the self_avoidance_random_walk function that returns the result of the self-avoiding random walk, the surrounding_points_checker that determines whether the points around the current point have already passed and the surrounding_points_checker that determines whether the candidate for the next movement point has already passed and moves if there is no problem. The structure is such that next_point_decisioner that determines is working. (This time, the moving points are stored in the list at any time, so I feel that it is a little roundabout. It may be possible to create a map-like thing and divide it into a piece that moves around on it and a part that records the moving position. )
self_avoidance_random_walk
import numpy as np
import random
random.seed(None)
'''
Maximum value of 2D grid xmax,By giving ymax
A function that returns the result of a self-avoidant random walk
'''
def self_avoidance_random_walk(xmax,ymax):
#Preparation of the initial state.
list_x = np.array([0])
list_y = np.array([0])
#random_walk loop
roop_num = 0
while True:
#Check the situation around your current location and pass points(duplicate_num)Count
duplicate_num = surrounding_points_checker(roop_num,list_x,list_y)
#If there is no point that can be moved, exit the loop
if duplicate_num >= 4:
break
#Candidate for next move point(x_dum, y_dum)To make
else:
D1 = random.randint(0,1)
D2 = random.randint(0,1)
dx_dum = (-1)**D1*D2
dy_dum = (-1)**D1*(1-D2)
x_dum = list_x[roop_num] + dx_dum
y_dum = list_y[roop_num] + dy_dum
#Exit the loop when you reach the boundary
if (abs(x_dum)==xmax or abs(y_dum)==ymax):
list_x = np.append(list_x,x_dum)
list_y = np.append(list_y,y_dum)
break
#Add new points
roop_num,list_x,list_y = next_point_decisioner(roop_num,list_x,list_y,list_mono,x_dum,y_dum)
return list_x, list_y
def surrounding_points_checker(i,list_x,list_y):
#Current position x_cur,y_Store in cur
x_cur = list_x[i]
y_cur = list_y[i]
#X the position around the current position_plus,y_plus,x_minus,y_Show as minus
x_plus = x_cur+1
x_minus = x_cur-1
y_plus = y_cur+1
y_minus = y_cur-1
#Record and return the position that has already passed around
duplicate_num = 0
for j in range(len(list_x)):
if (x_plus == list_x[j] and y_cur == list_y[j]) or (x_minus == list_x[j] and y_cur == list_y[j]):
duplicate_num +=1
elif (x_cur == list_x[j] and y_plus == list_y[j]) or (x_cur == list_x[j] and y_minus == list_y[j]):
duplicate_num +=1
else:
duplicate_num +=0
return duplicate_num
def next_point_decisioner(i,list_x,list_y,list_mono,x_dum,y_dum):
#Candidates for moving points(x_dum, y_dum)Determine if is not a point that has already passed
k = 0
for j in range(len(list_x)):
if (x_dum == list_x[j] and y_dum == list_y[j]):
k +=1
else:
k +=0
#If it has not passed, it will be added to the list, and if it has passed, the candidate will be rejected.
if k == 0:
list_x = np.append(list_x,x_dum)
list_y = np.append(list_y,y_dum)
i+=1
return i,list_x,list_y
if k == 1:
return i,list_x,list_y
Execution example of self-avoiding random walk program
The self-avoiding random walk program is executed as follows, for example. Here, the $ x $ axis of the 2D rectangular grid is $ -11 \ le x \ le 11 $, and the $ y $ axis is $ -11 \ le y \ le 11 $.
import matplotlib.pyplot as plt
x_max = 11
y_max = 11
list_x, list_y = self_avoidance_random_walk(x_max, y_max)
plt.figure(figsize=(6, 6))
plt.plot(list_x, list_y)
plt.grid(True)
plt.xlim(-x_max-1,x_max+1)
plt.ylim(-y_max-1,y_max+1)
plt.show()
Then, you can get the following graph. You can see that the simulation ends when you start from the center point and come to the end or are surrounded by yourself. Also, the result will change randomly with each run.
Summary
This time, I made a self-avoiding random walk program. You can also apply this to specify the type of thing at the position of the grid point and simulate the energy stability of the structure. Also, there seems to be a more efficient program method, so I would like to make it a future issue.
[Reference books / web] R.H.Landau, et al. (2018) "Practical Python Library Computational Physics I-Basics of Numerical Calculation / HPC / Fourier Wavelet Analysis" (Yoshio Koyanagi, et al.) Asakura Shoten
http://www.orsj.or.jp/~wiki/wiki/index.php/%E3%80%8A%E3%83%A9%E3%83%B3%E3%83%80%E3%83%A0%E3%83%BB%E3%82%A6%E3%82%A9%E3%83%BC%E3%82%AF%E3%81%A8%E3%83%96%E3%83%A9%E3%82%A6%E3%83%B3%E9%81%8B%E5%8B%95%E3%80%8B
Recommended Posts