-
Notifications
You must be signed in to change notification settings - Fork 0
/
simulated_annealing.py
113 lines (96 loc) · 2.36 KB
/
simulated_annealing.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
"""
Simulated Annealing
===================
Best Result so far:
[21, 4, 10, 11, 15, 20, 19, 27, 32, 1, 12, 34, 26, 18, 29, 13, 6, 3, 16, 7, 17, 24, 9, 8, 30, 23, 14, 25, 31, 33, 2, 0, 22, 28, 5]
0 Biel
34 Neuchatel
83 Bern
116 Fribourg
253 Genf
317 Lausanne
348 Montreux
390 Martigny
422 Sion
502 Zermatt
626 Andermatt
726 Glarus
795 Zug
822 Schwyz
859 Luzern
951 Thun
981 Interlaken
1094 Brig
1222 Bellinzona
1240 Locarno
1306 Chiasso
1333 Lugano
1459 St. Moritz
1527 Davos
1585 Chur
1625 Vaduz
1691 St. Gallen
1731 Kreuzlingen
1776 Schaffhausen
1804 Winterthur
1829 Zürich
1912 Basel
1977 Aarau
1990 Olten
2028 Solothurn
2052 Biel
Distance: 2052
"""
from math import exp
from random import random, sample
from copy import copy
import simulated_annealing_data as data
from simulated_annealing_data import path_length as length
from simulated_annealing_data import path_print
#BOLTZMANN = 1.3808 * 10 ** (-23)
BOLTZMANN = 1
def metropolis(E1, E0, T):
"""Metropolis Verteilung
"""
return exp((E0 - E1) / (T * BOLTZMANN)) if E0 < E1 else 1
def two_opt(path0):
path1 = copy(path0)
# generate non-neighbouring permutation
x = True
while x:
p = sample(range(len(p2)), 4)
x = abs(p[0]-p[1]) == 1 or abs(p[2]-p[3]) == 1
path1[p[0]], p2[p[1]] = path1[p[1]], p2[p[0]]
path1[p[2]], p2[p[3]] = path1[p[3]], p2[p[2]]
return p2
def main():
# initial solution
path = [i for i in range(len(data.CITIES))]
path_len = length(path)
shortest = path
shortest_len = path_len
# initial temperature
T = 3000
# annealing
for _ in range(200):
# search for solutions at constant temperature
for _ in range(200):
path_new = two_opt(path)
path_new_len = length(path_new)
# continue with new path in case it is shorter
# or with metropolis likelihood, depending on temperature
# -> high temperature is more likely to take new path
if path_new_len < path_len \
or metropolis(path_len, path_new_len, T) < random():
path = path_new
path_len = path_new_len
if path_len < shortest_len:
shortest_len = path_len
shortest = path
# decrease temperature
T = 0.8 * T
# show result
path_print(shortest)
print('\nDistance: ', shortest_len)
if __name__ == '__main__':
main()