-
Notifications
You must be signed in to change notification settings - Fork 0
/
vns.py
143 lines (123 loc) · 5.18 KB
/
vns.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
135
136
137
138
139
import copy
import random
from datetime import timedelta
from timeit import default_timer as timer
import tsplib95
import utils
## Reverse path between two random points
def stochastic_two_opt(path):
perm = copy.deepcopy(path)
i = random.randint(0, len(perm) - 1)
j = random.randint(0, len(perm) - 1)
if i > j:
i, j = j, i
perm[i:j + 1] = list(reversed(perm[i:j + 1]))
return perm
## Perform local search on the given problem
## Generate neighbors w.r.t neighborhood
## Update best_path if a neighbor is global best
## Else don't touch best_path
def local_search(problem, best_path , max_no_improv, neighborhood):
count = 0
while count <= max_no_improv:
count += 1
candidate_path = copy.deepcopy(best_path)
for i in range(0, neighborhood): # Generate neighbor, a neighborhood is a permutation that you can access in n number of two-opt's
candidate_path = stochastic_two_opt(candidate_path)
candidate_cost = utils.cost(candidate_path, problem) # Calculate candidate cost after generating neighbour
if candidate_cost < utils.cost(best_path, problem):
count = 0
best_path = candidate_path
return best_path
## Perform VSN on the given problem
## Default values are determined by testing on berlin52 data set
def search(problem, neighborhoods=6, max_no_improv=40, max_no_improv_ls=20, plot_progress = False, plot_end_start = False):
best_path = utils.random_permutation([*range(1, problem.dimension + 1, 1)]) # Create a random solution of problem size(number of cities)
best_cost = utils.cost(best_path, problem)
initial_cost = best_cost
count = 0
if plot_end_start:
title = "Cost: {}, Time: {}, Err: %{:.4f}".format(best_cost, 0.0, utils.error_rate(problem.best_known, best_cost))
utils.plot_tsp(best_path, problem, title)
start = timer()
print("Initial cost: {}".format(best_cost))
print("VNS: ", end="")
while count <= max_no_improv:
count += 1
for i in range(0, neighborhoods): # Generate neighbor, a neighborhood is a permutation that you can access in n number of two-opt's
# Explore best_path's neighbours instead of random candidates neighbours
candidate_path = local_search(problem, best_path, max_no_improv_ls, i)
candidate_cost = utils.cost(candidate_path, problem)
if candidate_cost < best_cost:
print("#", end="") # Search progress
count = 0
best_path = copy.deepcopy(candidate_path)
best_cost = candidate_cost
if plot_progress and i%2==0:
snapshot_timer(best_cost, best_path, problem, start)
break
end = timer()
elapsedTime = timedelta(seconds=end - start)
if plot_end_start:
snapshot_timer(best_cost, best_path, problem, start)
csv_log_str = utils.simple_log(problem, elapsedTime, best_cost, best_path, initial_cost)
return best_path, csv_log_str
def avns(problem, c_divr = 0.4, max_iter=60000, neighborhoods=12, max_no_improv=40, max_no_improv_ls=20, plot_progress = False, plot_end_start = False):
best_path = utils.random_permutation([*range(1, problem.dimension + 1, 1)]) # Create a random solution of problem size(number of cities)
best_cost = utils.cost(best_path, problem)
initial_cost = best_cost
count = 0
m = 0
if plot_end_start:
title = "Cost: {}, Time: {}, Err: %{:.4f}".format(best_cost, 0.0, utils.error_rate(problem.best_known, best_cost))
utils.plot_tsp(best_path, problem, title)
start = timer()
print("Initial cost: {}".format(best_cost))
print("AVNS: ", end="")
while count <= max_no_improv and m < max_iter:
for i in range(0, neighborhoods): # Generate neighbor, a neighborhood is a permutation that you can access in n number of two-opt's
m += max_no_improv_ls
if m <= (int(max_iter*c_divr)):
candidate_path = stochastic_two_opt(best_path)
else:
candidate_path = copy.deepcopy(best_path)
candidate_path = local_search(problem, candidate_path, max_no_improv_ls, i)
candidate_cost = utils.cost(candidate_path, problem)
if candidate_cost < best_cost:
print("#", end="") # Search progress
count = 0
m -= max_no_improv_ls
best_path = copy.deepcopy(candidate_path)
best_cost = candidate_cost
if plot_progress:
snapshot_timer(best_cost, best_path, problem, start)
break
end = timer()
elapsedTime = timedelta(seconds=end - start)
if plot_end_start:
snapshot_timer(best_cost, best_path, problem, start)
csv_log_str = utils.simple_log(problem, elapsedTime, best_cost, best_path, initial_cost)
return best_path, csv_log_str
## pseudo real-time plotting wrapper for search method
def snapshot_timer(best_cost, best_path, problem, start):
end = timer()
elapsedTime = timedelta(seconds=end - start)
title = "Cost: {}, Time: {}, Err: %{:.4f}".format(best_cost, elapsedTime.total_seconds(),
utils.error_rate(problem.best_known, best_cost))
utils.plot_tsp(best_path, problem, title)
if __name__ == '__main__':
problem_berlin52 = tsplib95.load_problem('problems/berlin52.tsp')
problem_berlin52.best_known = 7542
path1 = search(problem_berlin52,
neighborhoods=6,
max_no_improv=40,
max_no_improv_ls=20,
plot_progress=False,
plot_end_start=True)
path2 = avns(problem_berlin52,
c_divr= 0.4,
neighborhoods=6,
max_no_improv=40,
max_no_improv_ls=20,
plot_progress=False,
plot_end_start=True)