Simulated annealing: Difference between revisions
Content deleted Content added
Line 1,716:
0
</pre>
=={{header|Icon}}==
<lang icon>link printf
link random
procedure main ()
local initial_path
local final_path
local kT, kmax
randomize()
kT := 1.0
kmax := 1000000
write()
write(" kT: ", kT)
write(" kmax: ", kmax)
write()
write(" k T E(s)")
write(" --------------------------")
initial_path := randomize_path_vector()
final_path := simulate_annealing (kT, kmax, initial_path)
write()
display_path (final_path)
write()
write()
printf("Final E(s): %.2r\n", path_length(final_path))
write()
end
procedure randomize_path_vector ()
local path
local i, j
path := []
every put (path, 0 to 99)
# Shuffle elements 2 to 0.
every i := 1 to 98 do {
j := ?(99 - i) + i + 1
path[i + 1] :=: path[j + 1]
}
return path
end
procedure distance (loc1, loc2)
local i1, j1
local i2, j2
local di, dj
i1 := loc1 / 10
j1 := loc1 % 10
i2 := loc2 / 10
j2 := loc2 % 10
di := i1 - i2
dj := j1 - j2
return sqrt ((di * di) + (dj * dj))
end
procedure path_length (path)
local i
local len
len := distance(path[1], path[100])
every i := 1 to 99 do len +:= distance(path[i], path[i + 1])
return len
end
procedure find_neighbors (loc)
local c1, c2, c3, c4, c5, c6, c7, c8
local i, j
local neighbors
c1 := c2 := c3 := c4 := c5 := c6 := c7 := c8 := 0
i := loc / 10
j := loc % 10
if (i < 9) then {
c1 := (10 * (i + 1)) + j
if (j < 9) then c2 := (10 * (i + 1)) + (j + 1)
if (0 < j) then c3 := (10 * (i + 1)) + (j - 1)
}
if (0 < i) then {
c4 := (10 * (i - 1)) + j
if (j < 9) then c5 := (10 * (i - 1)) + (j + 1)
if (0 < j) then c6 := (10 * (i - 1)) + (j - 1)
}
if (j < 9) then c7 := (10 * i) + (j + 1)
if (0 < j) then c8 := (10 * i) + (j - 1)
neighbors := []
every put(neighbors, 0 ~= (c1 | c2 | c3 | c4 | c5 | c6 | c7 | c8))
return neighbors
end
procedure make_neighbor_path (path)
local neighbor_path
local u, v, iu, iv, j
local neighbors
neighbor_path := copy(path)
u := ?99
neighbors := find_neighbors(u)
v := neighbors[?(*neighbors)]
j := 2
iu := 0
iv := 0
while iu = 0 | iv = 0 do {
if neighbor_path[j] = u then {
iu := j
} else if neighbor_path[j] = v then {
iv := j
}
j +:= 1
}
neighbor_path[iu] := v
neighbor_path[iv] := u
return neighbor_path
end
procedure temperature (kT, kmax, k)
return kT * (1.0 - (real(k) / real(kmax)))
end
procedure my_exp (x)
# Icon's exp() might bail out with an underflow error, if we are not
# careful.
return (if x < -50 then 0.0 else exp(x))
end
procedure probability (delta_E, T)
return (if T = 0.0 then 0.0 else my_exp(-(delta_E / T)))
end
procedure show (k, T, E)
printf(" %7d %7.1r %10.2r\n", k, T, E)
return
end
procedure display_path (path)
local i
every i := 1 to 100 do {
printf("%2d ->", path[i])
if ((i - 1) % 8) = 7 then {
write()
} else {
writes(" ")
}
}
printf("%2d", path[1])
return
end
procedure simulate_annealing (kT, kmax, path)
local kshow
local k
local E, E_trial, T
local trial
kshow := kmax / 10
E := path_length(path)
every k := 0 to kmax do {
T := temperature(kT, kmax, k)
if (k % kshow) = 0 then show(k, T, E)
trial := make_neighbor_path(path)
E_trial := path_length(trial)
if E_trial <= E | ?0 <= probability (E_trial - E, T) then {
path := trial
E := E_trial
}
}
return path
end</lang>
{{out}}
An example run:
<pre>$ icont -s -u simanneal-in-Icon.icn && ./simanneal-in-Icon
kT: 1.0
kmax: 1000000
k T E(s)
--------------------------
0 1.0 511.67
100000 0.9 206.16
200000 0.8 186.68
300000 0.7 165.92
400000 0.6 158.49
500000 0.5 141.76
600000 0.4 122.53
700000 0.3 119.47
800000 0.2 107.56
900000 0.1 102.89
1000000 0.0 102.24
0 -> 10 -> 20 -> 30 -> 31 -> 41 -> 40 -> 50 ->
60 -> 70 -> 71 -> 72 -> 62 -> 61 -> 51 -> 52 ->
53 -> 63 -> 54 -> 44 -> 45 -> 35 -> 34 -> 24 ->
25 -> 26 -> 27 -> 17 -> 7 -> 8 -> 9 -> 19 ->
29 -> 39 -> 49 -> 59 -> 69 -> 79 -> 89 -> 99 ->
98 -> 97 -> 96 -> 86 -> 76 -> 75 -> 84 -> 85 ->
95 -> 94 -> 93 -> 92 -> 91 -> 90 -> 80 -> 81 ->
82 -> 83 -> 73 -> 74 -> 64 -> 55 -> 65 -> 66 ->
56 -> 46 -> 36 -> 37 -> 47 -> 57 -> 67 -> 77 ->
87 -> 88 -> 78 -> 68 -> 58 -> 48 -> 38 -> 28 ->
18 -> 16 -> 6 -> 5 -> 15 -> 14 -> 4 -> 3 ->
2 -> 12 -> 13 -> 23 -> 33 -> 43 -> 42 -> 32 ->
22 -> 21 -> 11 -> 1 -> 0
Final E(s): 102.24
</pre>
=={{header|J}}==
|