-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathhill-climbing.py
139 lines (114 loc) · 4.36 KB
/
hill-climbing.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
# Adaptative Cognitive Agentes - Activite of Optimization (Hill-Climbing)
# Hill Climbing Algoritmh
# - Choose best child always, if no best child stops.
#
# Developed by Lucas Cavalcanti
from joblib import Parallel, delayed
import tsplib95
import random
import time
from solution import Solution
# Repetitions ->
# - Repeates the algorithm with random starting solution
repeate = 10
# Branch Factor ->
# - Number of childrens generated at each interation.
# - If #brach == #cities, permutes first city with all remaining.
branch_factor = 38
# Swaps ->
# - Number of nodes to randomly swap in child generation
swaps = 1
filePath = "./dj38.tsp"
result_file = open("./results/"+ filePath[:-4] + "_rand_" + (("swap_" + str(swaps)) if swaps >= 0 else "shuffle") + "_" + str(branch_factor) + "_x_" + str(repeate) + ".txt",'w')
def f_n(nodes, cities, n_nodes):
dist = 0
for i in range(n_nodes-1):
edge = nodes[i], nodes[i+1]
dist += cities.get_weight(*edge)
return dist
def swap_random(nodes, cities, n_nodes, i):
temp_nodes = nodes.copy()
swap_place = random.randint(int((i - 1) * (n_nodes / branch_factor)), int(i * (n_nodes / branch_factor) - 1))
if swap_place == 0:
return ([], float('inf'))
temp_nodes[0], temp_nodes[swap_place] = temp_nodes[swap_place], temp_nodes[0]
temp_value = f_n(temp_nodes, cities, n_nodes)
return (temp_nodes, temp_value)
def swap_n_random(nodes, cities, n_nodes, i):
temp_nodes = nodes.copy()
random_idx = list(range(n_nodes))
random.shuffle(random_idx)
for s in range(swaps):
temp_nodes[random_idx[0]], temp_nodes[random_idx[1]] = temp_nodes[random_idx[1]], temp_nodes[random_idx[0]]
random_idx = random_idx[2:]
if len(random_idx) < 4:
random_idx = list(range(n_nodes))
random.shuffle(random_idx)
temp_value = f_n(temp_nodes, cities, n_nodes)
return (temp_nodes, temp_value)
def shuffle_random(nodes, cities, n_nodes, i):
temp_nodes = nodes.copy()
random.shuffle(temp_nodes)
temp_value = f_n(temp_nodes, cities, n_nodes)
return (temp_nodes, temp_value)
def operate(nodes, cities, n_nodes):
b_nodes = []
b_value = 0
function = None
if swaps == 0:
function = swap_random
elif swaps > 0:
function = swap_n_random
else:
function = shuffle_random
childrens = Parallel(n_jobs=8)(delayed(function)(nodes, cities, n_nodes, i) for i in range(1, branch_factor+1))
for c, v in childrens:
# Best child remain
if(b_value == 0 or v < b_value):
b_nodes = c
b_value = v
return b_nodes, b_value
def main():
cities = tsplib95.load(filePath)
n_nodes = len(list(cities.get_nodes()))
solutions = []
best_round_value = (0, 0)
for i in range(repeate):
nodes = list(range(1, n_nodes + 1))
random.shuffle(nodes)
value = f_n(nodes, cities, n_nodes)
iterations = 0
result = Solution(i)
result_file.write("########### Round: " + str(i+1) + " ###########\n")
start_t = time.time()
iterations_t = []
while(True):
iterations += 1
# Operate -> Find best children
child_nodes, child_value = operate(nodes, cities, n_nodes)
result_file.write("#### "+ str(iterations) + " iteration -> f(n): " + str(value) + "\n")
# Success reduces distance value?
if child_value <= value and iterations <= 300:
value = child_value
nodes = child_nodes
else: # end
result.set(nodes, value, iterations)
solutions.append(result)
result_file.write("\n#### Best Solution -> " + str(iterations) + " iterations: f(n): " + str(value))
result_file.write("\n#### - Elapsed time: " + str(sum(iterations_t)) + " | time / iterations: " + str(sum(iterations_t)/iterations) + "\n\n\n")
if best_round_value[0] == 0 or value < best_round_value[0]:
best_round_value = (value, i+1)
with open(result_file.name[:-4] + "_nodes.txt",'w',encoding = 'utf-8') as f:
f.write("##### Best Solution found, in round: " + str(i+1) + " -> f(n): " + str(best_round_value[0]) + " ######\n")
f.write("#### - Elapsed time: " + str(sum(iterations_t)) + " | time / iterations: " + str(sum(iterations_t)/iterations) + "\n")
f.write("Order to visit cities: ")
for n in nodes:
f.write(str(n) + ", ")
if i == repeate-1:
result_file.write("Over all Best Solution: " + str(best_round_value[1]) + " round -> f(n): " + str(best_round_value[0]))
break
iterations_t.append(time.time() - start_t)
start_t = time.time()
result_file.close()
if __name__ == '__main__':
main()