Anonymous user
Simulated annealing: Difference between revisions
Added Julia language
m (fixed typo) |
(Added Julia language) |
||
Line 259:
1e6 0 101.657
0 1 2 3 4 13 23 24 34 44 43 33 32 31 41 42 52 51 61 62 53 54 64 65 55 45 35 25 15 14 5 6 7 17 16 26 27 37 36 46 47 48 38 28 18 8 9 19 29 39 49 59 69 79 78 68 58 57 56 66 67 77 76 75 85 86 87 88 89 99 98 97 96 95 94 84 74 73 63 72 82 83 93 92 91 90 80 81 71 70 60 50 40 30 20 21 22 12 11 10 0</lang>
=={{header|Julia}}==
{{trans|EchoLisp}}
'''Module''':
<lang julia>module TravelingSalesman
using Random, Printf
# Eₛ: length(path)
Eₛ(distances, path) = sum(distances[ci, cj] for (ci, cj) in zip(path, Iterators.drop(path, 1)))
# T: temperature
T(k, kmax, kT) = kT * (1 - k / kmax)
# Alternative temperature:
#T(k, kmax, kT) = kT * (1 - sin(π / 2 * k / kmax))
# ΔE = Eₛ_new - Eₛ_old > 0
# Prob. to move if ΔE > 0, → 0 when T → 0 (fronzen state)
P(ΔE, k, kmax, kT) = exp(-ΔE / T(k, kmax, kT))
# ∆E from path ( .. a u b .. c v d ..) to (.. a v b ... c u d ..)
# ∆E before swapping (u,v)
# Quicker than Eₛ(s_next) - Eₛ(path)
function dE(distances, path, u, v)
a = distances[path[u - 1], path[u]]
b = distances[path[u + 1], path[u]]
c = distances[path[v - 1], path[v]]
d = distances[path[v + 1], path[v]]
na = distances[path[u - 1], path[v]]
nb = distances[path[u + 1], path[v]]
nc = distances[path[v - 1], path[u]]
nd = distances[path[v + 1], path[u]]
if v == u + 1
return (na + nd) - (a + d)
elseif u == v + 1
return (nc + nb) - (c + b)
else
return (na + nb + nc + nd) - (a + b + c + d)
end
end
const dirs = [1, -1, 10, -10, 9, 11, -11, -9]
function findpath(distances, kmax, kT)
n = size(distances, 1)
path = vcat(1, shuffle(2:n), 1)
Emin = Eₛ(distances, path)
@printf("E(s₀) = %10.2f\n", Emin)
println("Random path: ", join(path, ", "))
for k in Base.OneTo(kmax)
if iszero(k % (kmax ÷ 10))
@printf("k: %10d | T: %8.4f | Eₛ: %8.4f\n", k, T(k, kmax, kT), Eₛ(distances, path))
end
u = rand(2:n)
v = path[u] + rand(dirs)
v ∈ 2:n || continue
δE = dE(distances, path, u, v)
if δE < 0 || P(δE, k, kmax, kT) ≥ rand()
path[u], path[v] = path[v], path[u]
Emin += δE
end
end
@printf("k: %10d | T: %8.4f | Eₛ: %8.4f\n", kmax, T(kmax, kmax, kT), Eₛ(distances, path))
println("Found path: ", join(path, ", "))
return path
end
end # module TravelingSalesman</lang>
'''Main''':
<lang julia>distance(a, b) = isqrt(sum((a .- b) .^ 2))
const _citydist = collect(distance((ci % 10, ci ÷ 10), (cj % 10, ci ÷ 10)) for ci in 1:100, cj in 1:100)
TravelingSalesman.findpath(citydist, 100000, 100)</lang>
{{out}}
<pre>Random path: 1, 11, 4, 3, 5, 8, 10, 9, 17, 2, 7, 13, 15, 12, 6, 16, 14, 1
k: 10000 | T: 90.0000 | Eₛ: 4278.0000
k: 20000 | T: 80.0000 | Eₛ: 4401.0000
k: 30000 | T: 70.0000 | Eₛ: 4633.0000
k: 40000 | T: 60.0000 | Eₛ: 4557.0000
k: 50000 | T: 50.0000 | Eₛ: 4564.0000
k: 60000 | T: 40.0000 | Eₛ: 4552.0000
k: 70000 | T: 30.0000 | Eₛ: 4443.0000
k: 80000 | T: 20.0000 | Eₛ: 4400.0000
k: 90000 | T: 10.0000 | Eₛ: 4400.0000
k: 100000 | T: 0.0000 | Eₛ: 4400.0000
k: 100000 | T: 0.0000 | Eₛ: 4400.0000
Found path: 1, 11, 4, 9, 15, 2, 16, 17, 8, 10, 13, 3, 12, 5, 14, 6, 7, 1</pre>
=={{header|zkl}}==
| |||