Monte Carlo Method Homework 9

來自專欄 Monte Carlo Method

Monte Carlo Methods

Homework-9

Exercise：

• Generate 100 cities (points) randomly in the unit space. Find the minimum spanning tree for the 100 cities. Show graphically.
• Run a simulated algorithm to find an optimum path starting from the nominal visiting sequence (1, 2,, 100). Choose a proposal function and state it clearly. Also define your starting temperature and your annealing sequence. Show your optimal path graphically.

Exercise 1

We use the method discusses in the lecture and the result is plotted as shown below.

Exercise 2

We choose a flat proposal function, and the results for 20 cities and 100 cities are plotted as below.

Annealing sequence: 1,2,3,4,5,6,…..,20,21, 22,23, 24,…..100.

Starting temperature: T= (0.1)**12

代碼部分(python 3)：

#9.1#

import numpy as npimport matplotlib.pyplot as pltimport mathimport function#generate 100 points randomly in the unit spacex_list=[]y_list=[]s=100for i in range(s): x_list.append(function.generator.extract()) y_list.append(function.generator.extract())#choose the first point (x[0],y[0]) as the reference pointpoints_xlist=[x_list[0]]points_ylist=[y_list[0]]points=0min_distance=2a=0b=0plotx=[]ploty=[]while points<s: for i in range(len(x_list)): for j in range(len(points_xlist)): distance = math.sqrt((x_list[i] - points_xlist[j]) ** 2 + (y_list[i] -points_ylist[j]) ** 2) if 0<distance<min_distance: min_distance = distance a = i b = j plotx.append([x_list[a],points_xlist[b]]) ploty.append([y_list[a],points_ylist[b]]) points_xlist.append(x_list[a]) points_ylist.append(y_list[a]) del x_list[a] del y_list[a] min_distance = 2 points=points+1#draw the graphplt.figure ()for i in range(len(plotx)): plt.plot(plotx[i],ploty[i],color=r) plt.scatter(plotx[i],ploty[i],color=b)plt.show()

#9.2#

import numpy as npimport matplotlib.pyplot as pltimport mathimport function#generate 100 points randomly in the unit spacex_list=[]y_list=[]s=100T=(0.1)**12iterations=(10)**12for i in range(s): x_list.append(function.generator.extract()) y_list.append(function.generator.extract())#find the optimun pathfor i in range(iterations): k=int(s*function.generator.extract()) if 0<k<s-2: d1=math.sqrt((x_list[k-1]-x_list[k+1])**2+(y_list[k-1]-y_list[k+1])**2) d2=math.sqrt((x_list[k]-x_list[k+2])**2+(y_list[k]-y_list[k+2])**2) d3=math.sqrt((x_list[k-1]-x_list[k])**2+(y_list[k-1]-y_list[k])**2) d4=math.sqrt((x_list[k+2]-x_list[k+1])**2+(y_list[k+2]-y_list[k+1])**2) d=d1+d2-d3-d4 if d < 0: x_list[k], x_list[k + 1] = x_list[k + 1], x_list[k] y_list[k], y_list[k + 1] = y_list[k + 1], y_list[k] if d > 0: u = function.generator.extract() if u < math.exp(-d / T): x_list[k], x_list[k + 1] = x_list[k + 1], x_list[k] y_list[k], y_list[k + 1] = y_list[k + 1], y_list[k] if k<1: d1 = math.sqrt((x_list[1] - x_list[s-1]) ** 2 + (y_list[1] - y_list[s-1]) ** 2) d2 = math.sqrt((x_list[0] - x_list[2]) ** 2 + (y_list[0] - y_list[2]) ** 2) d3 = math.sqrt((x_list[0] - x_list[s-1]) ** 2 + (y_list[0] - y_list[s-1]) ** 2) d4 = math.sqrt((x_list[1] - x_list[2]) ** 2 + (y_list[1] - y_list[2]) ** 2) d=d1+d2-d3-d4 if d < 0: x_list[k], x_list[k + 1] = x_list[k + 1], x_list[k] y_list[k], y_list[k + 1] = y_list[k + 1], y_list[k] if d > 0: u = function.generator.extract() if u < math.exp(-d / T): x_list[k], x_list[k + 1] = x_list[k + 1], x_list[k] y_list[k], y_list[k + 1] = y_list[k + 1], y_list[k] if k>s-2: d1 = math.sqrt((x_list[1] - x_list[s - 1]) ** 2 + (y_list[1] - y_list[s - 1]) ** 2) d2 = math.sqrt((x_list[0] - x_list[s-2]) ** 2 + (y_list[0] - y_list[s-2]) ** 2) d3 = math.sqrt((x_list[0] - x_list[1]) ** 2 + (y_list[0] - y_list[1]) ** 2) d4 = math.sqrt((x_list[s-1] - x_list[s-2]) ** 2 + (y_list[s-1] - y_list[s-2]) ** 2) d = d1 + d2 - d3 - d4 if d < 0: x_list[k], x_list[0] = x_list[0], x_list[k] y_list[k], y_list[0] = y_list[0], y_list[k] if d > 0: u = function.generator.extract() if u < math.exp(-d / T): x_list[k], x_list[0] = x_list[0], x_list[k] y_list[k], y_list[0] = y_list[0], y_list[k] if s-3<k<s-1: d1 = math.sqrt((x_list[s-2] - x_list[0]) ** 2 + (y_list[s-2] - y_list[0]) ** 2) d2 = math.sqrt((x_list[s-1] - x_list[s - 3]) ** 2 + (y_list[s-1] - y_list[s-3]) ** 2) d3 = math.sqrt((x_list[s-2] - x_list[s-3]) ** 2 + (y_list[s-2] - y_list[s-3]) ** 2) d4 = math.sqrt((x_list[s - 1] - x_list[0]) ** 2 + (y_list[s - 1] - y_list[0]) ** 2) d = d1 + d2 - d3 - d4 if d < 0: x_list[k], x_list[k+1] = x_list[k+1], x_list[k] y_list[k], y_list[k+1] = y_list[k+1], y_list[k] if d > 0: u = function.generator.extract() if u < math.exp(-d / T): x_list[k], x_list[k+1] = x_list[k+1], x_list[k] y_list[k], y_list[k+1] = y_list[k+1], y_list[k]#plot the resultx_list.append(x_list[0])y_list.append(y_list[0])plt.figure()plt.scatter(x_list,y_list,color=b)plt.plot(x_list,y_list,color=r)plt.show()

推薦閱讀：