Repository navigation
Expand file tree
/
Copy pathTabuSearch.py
More file actions
140 lines (113 loc) 路 4.42 KB
/
Copy pathTabuSearch.py
File metadata and controls
140 lines (113 loc) 路 4.42 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
from abc import ABCMeta, abstractmethod
from copy import deepcopy
from collections import deque
from numpy import argmax
class TabuSearch:
"""
Conducts tabu search
"""
__metaclass__ = ABCMeta
cur_steps = None
tabu_size = None
tabu_list = None
initial_state = None
current = None
best = None
max_steps = None
max_score = None
def __init__(self, initial_state, tabu_size, max_steps, max_score=None):
"""
:param initial_state: initial state, should implement __eq__ or __cmp__
:param tabu_size: number of states to keep in tabu list
:param max_steps: maximum number of steps to run algorithm for
:param max_score: score to stop algorithm once reached
"""
self.initial_state = initial_state
if isinstance(tabu_size, int) and tabu_size > 0:
self.tabu_size = tabu_size
else:
raise TypeError('Tabu size must be a positive integer')
if isinstance(max_steps, int) and max_steps > 0:
self.max_steps = max_steps
else:
raise TypeError('Maximum steps must be a positive integer')
if max_score is not None:
if isinstance(max_score, (int, float)):
self.max_score = float(max_score)
else:
raise TypeError('Maximum score must be a numeric type')
def __str__(self):
return ('TABU SEARCH: \n' +
'CURRENT STEPS: %d \n' +
'BEST SCORE: %f \n' +
'BEST MEMBER: %s \n\n') % \
(self.cur_steps, self._score(self.best), str(self.best))
def __repr__(self):
return self.__str__()
def _clear(self):
"""
Resets the variables that are altered on a per-run basis of the algorithm
:return: None
"""
self.cur_steps = 0
self.tabu_list = deque(maxlen=self.tabu_size)
self.current = self.initial_state
self.best = self.initial_state
@abstractmethod
def _score(self, state):
"""
Returns objective function value of a state
:param state: a state
:return: objective function value of state
"""
pass
@abstractmethod
def _neighborhood(self):
"""
Returns list of all members of neighborhood of current state, given self.current
:return: list of members of neighborhood
"""
pass
def _best(self, neighborhood):
"""
Finds the best member of a neighborhood
:param neighborhood: a neighborhood
:return: best member of neighborhood
"""
return neighborhood[argmax([self._score(x) for x in neighborhood])]
def run(self, verbose=True):
"""
Conducts tabu search
:param verbose: indicates whether or not to print progress regularly
:return: best state and objective function value of best state
"""
self._clear()
for i in range(self.max_steps):
self.cur_steps += 1
if ((i + 1) % 100 == 0) and verbose:
print(self)
neighborhood = self._neighborhood()
neighborhood_best = self._best(neighborhood)
while True:
if all([x in self.tabu_list for x in neighborhood]):
print("TERMINATING - NO SUITABLE NEIGHBORS")
return self.best, self._score(self.best)
if neighborhood_best in self.tabu_list:
if self._score(neighborhood_best) > self._score(self.best):
self.tabu_list.append(neighborhood_best)
self.best = deepcopy(neighborhood_best)
break
else:
neighborhood.remove(neighborhood_best)
neighborhood_best = self._best(neighborhood)
else:
self.tabu_list.append(neighborhood_best)
self.current = neighborhood_best
if self._score(self.current) > self._score(self.best):
self.best = deepcopy(self.current)
break
if self.max_score is not None and self._score(self.best) > self.max_score:
print("TERMINATING - REACHED MAXIMUM SCORE")
return self.best, self._score(self.best)
print("TERMINATING - REACHED MAXIMUM STEPS")
return self.best, self._score(self.best)