Simulated annealing: Difference between revisions
Content deleted Content added
m fixed typo |
Added Julia language |
||
Line 259: | Line 259: | ||
1e6 0 101.657 |
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> |
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}}== |
=={{header|zkl}}== |