Repository navigation
Expand file tree
/
Copy pathVNS.py
More file actions
176 lines (114 loc) · 7.77 KB
/
Copy pathVNS.py
File metadata and controls
176 lines (114 loc) · 7.77 KB
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
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
import nbr_hood as nbr
import random
import pandas as pd
import numpy as np
#create class for hill climb algorithms
class VNS(nbr.nbrHood):
def __init__(self,df,numGroups,nbrhoodsize):
super().__init__(df,numGroups)
self.nbrhoodsize = nbrhoodsize
#when a new global minimum is found, expand search to 2 swap, maybe even 3 swap?
def runVNS(self,VNS_type,restarts,aggMethod,distMetric,startMetric=1,randStart='Y',expandFactor=2,nSwaps=2):
#VNS_type has 3 options -- EXPAND, 2SWAP, 3SWAP. EXPAND increases nbrhood size by a specified factor when a minimum is found,
#2SWAP changes nbrhood to 2 swap when min is found
#3SWAP changes nbrhood to 3 swap when min is found
obs = 0
startSolution = self.startSol(randStart=randStart,startMetric=startMetric)
#conditionally execute hill climb with EXPAND
if VNS_type == 'EXPAND':
globalBestNbr = startSolution
globalBestDist = self.totalDist(self.groupMetrics(startSolution,aggMethod),distMetric)
for j in range(0,restarts):
#do a random start if it is not the first iteration
if j == 0:
currentSolution = startSolution
else:
currentSolution = self.startSol(randStart=randStart,startMetric=startMetric)
done = 0
while done == 0:
bestNbr = currentSolution
bestDist = self.totalDist(self.groupMetrics(currentSolution,aggMethod),distMetric)
for i in self.createNbrhood(currentSolution,self.nbrhoodsize):
obs = obs + 1
if self.totalDist(self.groupMetrics(i,aggMethod),distMetric) < self.totalDist(self.groupMetrics(bestNbr,aggMethod),distMetric):
bestNbr = i
bestDist = self.totalDist(self.groupMetrics(i,aggMethod),distMetric)
print(bestDist)
if currentSolution == bestNbr:
done = 1
else:
currentSolution = bestNbr
print("restart")
if bestDist < globalBestDist:
globalBestNbr = bestNbr
globalBestDist = self.totalDist(self.groupMetrics(bestNbr,aggMethod),distMetric)
print("New Global Best = %s" % globalBestDist)
print("Start Expanded Search")
best_nbr = 0
while best_nbr == 0:
bestNbr = currentSolution
bestDist = self.totalDist(self.groupMetrics(currentSolution,aggMethod),distMetric)
for i in self.createNbrhood(currentSolution,int(round(self.nbrhoodsize*expandFactor,0))):
obs = obs + 1
if self.totalDist(self.groupMetrics(i,aggMethod),distMetric) < self.totalDist(self.groupMetrics(bestNbr,aggMethod),distMetric):
bestNbr = i
bestDist = self.totalDist(self.groupMetrics(i,aggMethod),distMetric)
if currentSolution == bestNbr:
best_nbr = 1
globalBestNbr = bestNbr
print("Global Best = %s" % globalBestDist)
else:
currentSolution = bestNbr
print("End expanded search")
obs_statement = ("%s Solutions Examined" % obs)
print("done")
#conditionally execute hill climb with EXPAND
elif VNS_type == 'NSWAP':
globalBestNbr = startSolution
globalBestDist = self.totalDist(self.groupMetrics(startSolution,aggMethod),distMetric)
for j in range(0,restarts):
#do a random start if it is not the first iteration
if j == 0:
currentSolution = startSolution
else:
currentSolution = self.startSol(randStart=randStart,startMetric=startMetric)
done = 0
while done == 0:
bestNbr = currentSolution
bestDist = self.totalDist(self.groupMetrics(currentSolution,aggMethod),distMetric)
for i in self.createNbrhood(currentSolution,self.nbrhoodsize):
obs = obs + 1
if self.totalDist(self.groupMetrics(i,aggMethod),distMetric) < self.totalDist(self.groupMetrics(bestNbr,aggMethod),distMetric):
bestNbr = i
bestDist = self.totalDist(self.groupMetrics(i,aggMethod),distMetric)
print(bestDist)
if currentSolution == bestNbr:
done = 1
else:
currentSolution = bestNbr
print("restart")
if bestDist < globalBestDist:
globalBestNbr = bestNbr
globalBestDist = self.totalDist(self.groupMetrics(bestNbr,aggMethod),distMetric)
print("New Global Best = %s" % globalBestDist)
print("Start %s Swap Search" % nSwaps)
best_nbr = 0
while best_nbr == 0:
bestNbr = currentSolution
bestDist = self.totalDist(self.groupMetrics(currentSolution,aggMethod),distMetric)
for i in self.createNbrhood(currentSolution,self.nbrhoodsize,numSwaps=nSwaps):
obs = obs + 1
if self.totalDist(self.groupMetrics(i,aggMethod),distMetric) < self.totalDist(self.groupMetrics(bestNbr,aggMethod),distMetric):
bestNbr = i
bestDist = self.totalDist(self.groupMetrics(i,aggMethod),distMetric)
if currentSolution == bestNbr:
best_nbr = 1
globalBestNbr = bestNbr
print("Global Best = %s" % globalBestDist)
else:
currentSolution = bestNbr
print("End expanded search")
obs_statement = ("%s Solutions Examined" % obs)
print("done")
#return solution metric and solution
return [self.groupMetrics(globalBestNbr,aggMethod),globalBestNbr,globalBestDist,obs_statement]