Simulated annealing: Difference between revisions
Added Go
(Added Go) |
|||
Line 199:
34 33 32 43 42 52 51 41 31 21 11 12 22 23 13 14 15 16 17 26 27 37 38
39 29 28 18 19 9 8 7 6 5 4 3 2 1 0)
</pre>
=={{header|Go}}==
{{trans|zkl}}
<lang go>package main
import (
"fmt"
"math"
"math/rand"
"time"
)
var (
dists = calcDists()
dirs = [8]int{1, -1, 10, -10, 9, 11, -11, -9} // all 8 neighbors
)
// distances
func calcDists() []float64 {
dists := make([]float64, 10000)
for i := 0; i < 10000; i++ {
ab, cd := math.Floor(float64(i)/100), float64(i%100)
a, b := math.Floor(ab/10), float64(int(ab)%10)
c, d := math.Floor(cd/10), float64(int(cd)%10)
dists[i] = math.Hypot(a-c, b-d)
}
return dists
}
// index into lookup table of float64s
func dist(ci, cj int) float64 {
return dists[cj*100+ci]
}
// energy at s, to be minimized
func Es(path []int) float64 {
d := 0.0
for i := 0; i < len(path)-1; i++ {
d += dist(path[i], path[i+1])
}
return d
}
// temperature function, decreases to 0
func T(k, kmax, kT int) float64 {
return (1 - float64(k)/float64(kmax)) * float64(kT)
}
// variation of E, from state s to state s_next
func dE(s []int, u, v int) float64 {
su, sv := s[u], s[v]
// old
a, b, c, d := dist(s[u-1], su), dist(s[u+1], su), dist(s[v-1], sv), dist(s[v+1], sv)
// new
na, nb, nc, nd := dist(s[u-1], sv), dist(s[u+1], sv), dist(s[v-1], su), dist(s[v+1], su)
if v == u+1 {
return (na + nd) - (a + d)
} else if u == v+1 {
return (nc + nb) - (c + b)
} else {
return (na + nb + nc + nd) - (a + b + c + d)
}
}
// probability to move from s to s_next
func P(deltaE float64, k, kmax, kT int) float64 {
return math.Exp(-deltaE / T(k, kmax, kT))
}
func sa(kmax, kT int) {
rand.Seed(time.Now().UnixNano())
temp := make([]int, 99)
for i := 0; i < 99; i++ {
temp[i] = i + 1
}
rand.Shuffle(len(temp), func(i, j int) {
temp[i], temp[j] = temp[j], temp[i]
})
s := make([]int, 101) // all 0 by default
copy(s[1:], temp) // random path from 0 to 0
fmt.Println("kT =", kT)
fmt.Printf("E(s0) %f\n\n", Es(s)) // random starter
Emin := Es(s) // E0
for k := 0; k <= kmax; k++ {
if k%(kmax/10) == 0 {
fmt.Printf("k:%10d T: %8.4f Es: %8.4f\n", k, T(k, kmax, kT), Es(s))
}
u := 1 + rand.Intn(99) // city index 1 to 99
cv := s[u] + dirs[rand.Intn(8)] // city number
if cv <= 0 || cv >= 100 { // bogus city
continue
}
if dist(s[u], cv) > 5 { // check true neighbor (eg 0 9)
continue
}
v := s[cv] // city index
deltae := dE(s, u, v)
if deltae < 0 || // always move if negative
P(deltae, k, kmax, kT) >= rand.Float64() {
s[u], s[v] = s[v], s[u]
Emin += deltae
}
}
fmt.Printf("\nE(s_final) %f\n", Emin)
fmt.Println("Path:")
// output final state
for i := 0; i < len(s); i++ {
if i > 0 && i%10 == 0 {
fmt.Println()
}
fmt.Printf("%4d", s[i])
}
fmt.Println()
}
func main() {
sa(1e6, 1)
}</lang>
{{out}}
Sample run:
<pre>
kT = 1
E(s0) 520.932463
k: 0 T: 1.0000 Es: 520.9325
k: 100000 T: 0.9000 Es: 185.1279
k: 200000 T: 0.8000 Es: 167.7657
k: 300000 T: 0.7000 Es: 158.6923
k: 400000 T: 0.6000 Es: 151.6564
k: 500000 T: 0.5000 Es: 139.9185
k: 600000 T: 0.4000 Es: 132.9964
k: 700000 T: 0.3000 Es: 121.8962
k: 800000 T: 0.2000 Es: 120.0445
k: 900000 T: 0.1000 Es: 116.8476
k: 1000000 T: 0.0000 Es: 116.5565
E(s_final) 116.556509
Path:
0 11 21 31 41 51 52 61 62 72
82 73 74 64 44 45 55 54 63 53
42 32 43 33 35 34 24 23 22 13
12 2 3 4 14 25 26 7 6 16
15 5 17 27 36 46 56 66 65 75
77 78 68 69 59 49 39 38 37 28
29 19 9 8 18 47 48 58 57 67
76 86 85 95 96 97 87 88 79 89
99 98 84 94 83 93 92 91 90 80
81 71 70 60 50 40 30 20 10 1
0
</pre>
| |||