TheAlgorithms-Python

1
"""
2
This is pure Python implementation of Tabu search algorithm for a Travelling Salesman
3
Problem, that the distances between the cities are symmetric (the distance between city
4
'a' and city 'b' is the same between city 'b' and city 'a').
5
The TSP can be represented into a graph. The cities are represented by nodes and the
6
distance between them is represented by the weight of the ark between the nodes.
7

8
The .txt file with the graph has the form:
9

10
node1 node2 distance_between_node1_and_node2
11
node1 node3 distance_between_node1_and_node3
12
...
13

14
Be careful node1, node2 and the distance between them, must exist only once. This means
15
in the .txt file should not exist:
16
node1 node2 distance_between_node1_and_node2
17
node2 node1 distance_between_node2_and_node1
18

19
For pytests run following command:
20
pytest
21

22
For manual testing run:
23
python tabu_search.py -f your_file_name.txt -number_of_iterations_of_tabu_search \
24
    -s size_of_tabu_search
25
e.g. python tabu_search.py -f tabudata2.txt -i 4 -s 3
26
"""
27

28
import argparse
29
import copy
30

31

32
def generate_neighbours(path):
33
    """
34
    Pure implementation of generating a dictionary of neighbors and the cost with each
35
    neighbor, given a path file that includes a graph.
36

37
    :param path: The path to the .txt file that includes the graph (e.g.tabudata2.txt)
38
    :return dict_of_neighbours: Dictionary with key each node and value a list of lists
39
        with the neighbors of the node and the cost (distance) for each neighbor.
40

41
    Example of dict_of_neighbours:
42
    >>) dict_of_neighbours[a]
43
    [[b,20],[c,18],[d,22],[e,26]]
44

45
    This indicates the neighbors of node (city) 'a', which has neighbor the node 'b'
46
    with distance 20, the node 'c' with distance 18, the node 'd' with distance 22 and
47
    the node 'e' with distance 26.
48
    """
49

50
    dict_of_neighbours = {}
51

52
    with open(path) as f:
53
        for line in f:
54
            if line.split()[0] not in dict_of_neighbours:
55
                _list = []
56
                _list.append([line.split()[1], line.split()[2]])
57
                dict_of_neighbours[line.split()[0]] = _list
58
            else:
59
                dict_of_neighbours[line.split()[0]].append(
60
                    [line.split()[1], line.split()[2]]
61
                )
62
            if line.split()[1] not in dict_of_neighbours:
63
                _list = []
64
                _list.append([line.split()[0], line.split()[2]])
65
                dict_of_neighbours[line.split()[1]] = _list
66
            else:
67
                dict_of_neighbours[line.split()[1]].append(
68
                    [line.split()[0], line.split()[2]]
69
                )
70

71
    return dict_of_neighbours
72

73

74
def generate_first_solution(path, dict_of_neighbours):
75
    """
76
    Pure implementation of generating the first solution for the Tabu search to start,
77
    with the redundant resolution strategy. That means that we start from the starting
78
    node (e.g. node 'a'), then we go to the city nearest (lowest distance) to this node
79
    (let's assume is node 'c'), then we go to the nearest city of the node 'c', etc.
80
    till we have visited all cities and return to the starting node.
81

82
    :param path: The path to the .txt file that includes the graph (e.g.tabudata2.txt)
83
    :param dict_of_neighbours: Dictionary with key each node and value a list of lists
84
        with the neighbors of the node and the cost (distance) for each neighbor.
85
    :return first_solution: The solution for the first iteration of Tabu search using
86
        the redundant resolution strategy in a list.
87
    :return distance_of_first_solution: The total distance that Travelling Salesman
88
        will travel, if he follows the path in first_solution.
89
    """
90

91
    with open(path) as f:
92
        start_node = f.read(1)
93
    end_node = start_node
94

95
    first_solution = []
96

97
    visiting = start_node
98

99
    distance_of_first_solution = 0
100
    while visiting not in first_solution:
101
        minim = 10000
102
        for k in dict_of_neighbours[visiting]:
103
            if int(k[1]) < int(minim) and k[0] not in first_solution:
104
                minim = k[1]
105
                best_node = k[0]
106

107
        first_solution.append(visiting)
108
        distance_of_first_solution = distance_of_first_solution + int(minim)
109
        visiting = best_node
110

111
    first_solution.append(end_node)
112

113
    position = 0
114
    for k in dict_of_neighbours[first_solution[-2]]:
115
        if k[0] == start_node:
116
            break
117
        position += 1
118

119
    distance_of_first_solution = (
120
        distance_of_first_solution
121
        + int(dict_of_neighbours[first_solution[-2]][position][1])
122
        - 10000
123
    )
124
    return first_solution, distance_of_first_solution
125

126

127
def find_neighborhood(solution, dict_of_neighbours):
128
    """
129
    Pure implementation of generating the neighborhood (sorted by total distance of
130
    each solution from lowest to highest) of a solution with 1-1 exchange method, that
131
    means we exchange each node in a solution with each other node and generating a
132
    number of solution named neighborhood.
133

134
    :param solution: The solution in which we want to find the neighborhood.
135
    :param dict_of_neighbours: Dictionary with key each node and value a list of lists
136
        with the neighbors of the node and the cost (distance) for each neighbor.
137
    :return neighborhood_of_solution: A list that includes the solutions and the total
138
        distance of each solution (in form of list) that are produced with 1-1 exchange
139
        from the solution that the method took as an input
140

141
    Example:
142
    >>> find_neighborhood(['a', 'c', 'b', 'd', 'e', 'a'],
143
    ...                   {'a': [['b', '20'], ['c', '18'], ['d', '22'], ['e', '26']],
144
    ...                    'c': [['a', '18'], ['b', '10'], ['d', '23'], ['e', '24']],
145
    ...                    'b': [['a', '20'], ['c', '10'], ['d', '11'], ['e', '12']],
146
    ...                    'e': [['a', '26'], ['b', '12'], ['c', '24'], ['d', '40']],
147
    ...                    'd': [['a', '22'], ['b', '11'], ['c', '23'], ['e', '40']]}
148
    ...                   )  # doctest: +NORMALIZE_WHITESPACE
149
    [['a', 'e', 'b', 'd', 'c', 'a', 90],
150
     ['a', 'c', 'd', 'b', 'e', 'a', 90],
151
     ['a', 'd', 'b', 'c', 'e', 'a', 93],
152
     ['a', 'c', 'b', 'e', 'd', 'a', 102],
153
     ['a', 'c', 'e', 'd', 'b', 'a', 113],
154
     ['a', 'b', 'c', 'd', 'e', 'a', 119]]
155
    """
156

157
    neighborhood_of_solution = []
158

159
    for n in solution[1:-1]:
160
        idx1 = solution.index(n)
161
        for kn in solution[1:-1]:
162
            idx2 = solution.index(kn)
163
            if n == kn:
164
                continue
165

166
            _tmp = copy.deepcopy(solution)
167
            _tmp[idx1] = kn
168
            _tmp[idx2] = n
169

170
            distance = 0
171

172
            for k in _tmp[:-1]:
173
                next_node = _tmp[_tmp.index(k) + 1]
174
                for i in dict_of_neighbours[k]:
175
                    if i[0] == next_node:
176
                        distance = distance + int(i[1])
177
            _tmp.append(distance)
178

179
            if _tmp not in neighborhood_of_solution:
180
                neighborhood_of_solution.append(_tmp)
181

182
    index_of_last_item_in_the_list = len(neighborhood_of_solution[0]) - 1
183

184
    neighborhood_of_solution.sort(key=lambda x: x[index_of_last_item_in_the_list])
185
    return neighborhood_of_solution
186

187

188
def tabu_search(
189
    first_solution, distance_of_first_solution, dict_of_neighbours, iters, size
190
):
191
    """
192
    Pure implementation of Tabu search algorithm for a Travelling Salesman Problem in
193
    Python.
194

195
    :param first_solution: The solution for the first iteration of Tabu search using
196
        the redundant resolution strategy in a list.
197
    :param distance_of_first_solution: The total distance that Travelling Salesman will
198
        travel, if he follows the path in first_solution.
199
    :param dict_of_neighbours: Dictionary with key each node and value a list of lists
200
        with the neighbors of the node and the cost (distance) for each neighbor.
201
    :param iters: The number of iterations that Tabu search will execute.
202
    :param size: The size of Tabu List.
203
    :return best_solution_ever: The solution with the lowest distance that occurred
204
        during the execution of Tabu search.
205
    :return best_cost: The total distance that Travelling Salesman will travel, if he
206
        follows the path in best_solution ever.
207
    """
208
    count = 1
209
    solution = first_solution
210
    tabu_list = []
211
    best_cost = distance_of_first_solution
212
    best_solution_ever = solution
213

214
    while count <= iters:
215
        neighborhood = find_neighborhood(solution, dict_of_neighbours)
216
        index_of_best_solution = 0
217
        best_solution = neighborhood[index_of_best_solution]
218
        best_cost_index = len(best_solution) - 1
219

220
        found = False
221
        while not found:
222
            i = 0
223
            while i < len(best_solution):
224
                if best_solution[i] != solution[i]:
225
                    first_exchange_node = best_solution[i]
226
                    second_exchange_node = solution[i]
227
                    break
228
                i = i + 1
229

230
            if [first_exchange_node, second_exchange_node] not in tabu_list and [
231
                second_exchange_node,
232
                first_exchange_node,
233
            ] not in tabu_list:
234
                tabu_list.append([first_exchange_node, second_exchange_node])
235
                found = True
236
                solution = best_solution[:-1]
237
                cost = neighborhood[index_of_best_solution][best_cost_index]
238
                if cost < best_cost:
239
                    best_cost = cost
240
                    best_solution_ever = solution
241
            else:
242
                index_of_best_solution = index_of_best_solution + 1
243
                best_solution = neighborhood[index_of_best_solution]
244

245
        if len(tabu_list) >= size:
246
            tabu_list.pop(0)
247

248
        count = count + 1
249

250
    return best_solution_ever, best_cost
251

252

253
def main(args=None):
254
    dict_of_neighbours = generate_neighbours(args.File)
255

256
    first_solution, distance_of_first_solution = generate_first_solution(
257
        args.File, dict_of_neighbours
258
    )
259

260
    best_sol, best_cost = tabu_search(
261
        first_solution,
262
        distance_of_first_solution,
263
        dict_of_neighbours,
264
        args.Iterations,
265
        args.Size,
266
    )
267

268
    print(f"Best solution: {best_sol}, with total distance: {best_cost}.")
269

270

271
if __name__ == "__main__":
272
    parser = argparse.ArgumentParser(description="Tabu Search")
273
    parser.add_argument(
274
        "-f",
275
        "--File",
276
        type=str,
277
        help="Path to the file containing the data",
278
        required=True,
279
    )
280
    parser.add_argument(
281
        "-i",
282
        "--Iterations",
283
        type=int,
284
        help="How many iterations the algorithm should perform",
285
        required=True,
286
    )
287
    parser.add_argument(
288
        "-s", "--Size", type=int, help="Size of the tabu list", required=True
289
    )
290

291
    # Pass the arguments to main method
292
    main(parser.parse_args())
293