-
Notifications
You must be signed in to change notification settings - Fork 3
/
simulation.py
134 lines (102 loc) · 4.52 KB
/
simulation.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
from network import Network
from heuristic import greedy, two_opt
from mcts import RandomMCTS, GreedyMCTS
from plot import plot_path
from matplotlib import pyplot as plt
import time
import numpy as np
from tqdm import tqdm
from multiprocessing import Pool
from itertools import product
# trail function defined separately for multiprocessing
def run_trail(network):
results = []
### heuristic 1 - greedy
start = time.time()
edges, cost = greedy(network)
run_time = time.time() - start
results.append([cost, run_time])
### heuristic 2 - two opt
start = time.time()
edges, cost = two_opt(network)
run_time = time.time() - start
results.append([cost, run_time])
### mcts 1 - random
start = time.time()
random_mcts = RandomMCTS(network)
edges, cost = random_mcts.run(50, 20, 100)
run_time = time.time() - start
results.append([cost, run_time])
### mcts 2 - greedy
start = time.time()
greedy_mcts = GreedyMCTS(network, 0.2)
edges, cost = greedy_mcts.run(50, 20, 100)
run_time = time.time() - start
results.append([cost, run_time])
return results
# ###### Simulation ######
#
# Run Monte Carlo simulation to get performance report.
#
# Input
# |- num_of_network: number of network to test on
# |- trail_per_network: number of trail to run each method on a network
# |- num_of_node: number of node to visit
# |- side_length: the side length of the 2d square the all the nodes rest on
# └- plot: a boolean telling if to plot a histogram
def simulation(num_of_network, trail_per_network, num_of_node, side_length=100, plot=False):
results = np.array([])
for i in tqdm(range(num_of_network)):
# run trails at the same time using multiprocessing
network = Network(num_of_node, side_length)
networks = [network for _ in range(trail_per_network)]
p = Pool(10)
result = p.map(run_trail, networks)
p.close()
result = np.array(result)
# add to result set
results = np.vstack((results, result)) if results.size else result
h_1 = results[:, 0, :]
h_2 = results[:, 1, :]
t_1 = results[:, 2, :]
t_2 = results[:, 3, :]
print ("greedy has average cost of {:.2f}".format(np.mean(h_1)))
print ("2 opt has average cost of {:.2f}".format(np.mean(h_2)))
print ("random mcts has average cost of {:.2f}".format(np.mean(t_1)))
print ("greedy mcts has average cost of {:.2f}".format(np.mean(t_2)))
if plot == True:
### time vs cost plot
fig, ax = plt.subplots(nrows=1, ncols=1, figsize=(8,8))
ax.plot(h_1[:,1], h_1[:,0], 'r+', label='greedy heuristic')
ax.plot(h_2[:,1], h_2[:,0], 'm+', label='two opt heuristic')
ax.plot(t_1[:,1], t_1[:,0], 'b+', label='random mcts')
ax.plot(t_2[:,1], t_2[:,0], 'c+', label='greedy mcts')
ax.set_xscale('log')
ax.set_xlabel('time (s)')
ax.set_ylabel('cost')
ax.set_title("Time-Cost Performance (num_of_node={:d}, side_length={:d})".format(num_of_node, side_length))
# put legend below current axis
box = ax.get_position()
ax.set_position([box.x0, box.y0 + box.height * 0.1,
box.width, box.height * 0.9])
ax.legend(loc='upper center', bbox_to_anchor=(0.5, -0.1),
fancybox=True, shadow=True, ncol=5)
plt.show()
### cost histogram
bin_start = int(np.amin(results[:, :, 0])/20) * 20
bin_end = int(np.amax(results[:, :, 0])/20) * 20 + 21
fig, ax = plt.subplots(nrows=1, ncols=1, figsize=(8,8))
ax.hist(h_1[:,0], bins=range(bin_start, bin_end, 20), density=True, alpha=0.6, color= 'r', label='greedy heuristic')
ax.hist(h_2[:,0], bins=range(bin_start, bin_end, 20), density=True, alpha=0.6, color= 'm', label='two opt heuristic')
ax.hist(t_1[:,0], bins=range(bin_start, bin_end, 20), density=True, alpha=0.6, color= 'b', label='random mcts')
ax.hist(t_2[:,0], bins=range(bin_start, bin_end, 20), density=True, alpha=0.6, color= 'c', label='greedy mcts')
ax.set_xlabel('cost')
ax.set_ylabel('frequency')
ax.set_title("Cost Histogram (num_of_node={:d}, side_length={:d})".format(num_of_node, side_length))
# put legend below current axis
box = ax.get_position()
ax.set_position([box.x0, box.y0 + box.height * 0.1,
box.width, box.height * 0.9])
ax.legend(loc='upper center', bbox_to_anchor=(0.5, -0.1),
fancybox=True, shadow=True, ncol=5)
plt.show()