-
Notifications
You must be signed in to change notification settings - Fork 27
/
anneal.go
61 lines (58 loc) · 1.35 KB
/
anneal.go
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
package rush
import (
"fmt"
"math"
"math/rand"
"time"
)
func anneal(state *Board, maxTemp, minTemp float64, steps int) *Board {
start := time.Now()
factor := -math.Log(maxTemp / minTemp)
state = state.Copy()
bestState := state.Copy()
bestEnergy := state.Energy()
bestTime := start
previousEnergy := bestEnergy
rate := steps / 1000
for step := 0; step < steps; step++ {
pct := float64(step) / float64(steps-1)
temp := maxTemp * math.Exp(factor*pct)
if step%rate == 0 {
showAnnealProgress(
step, steps, temp, bestEnergy, time.Since(start).Seconds())
}
undo := state.Mutate()
energy := state.Energy()
change := energy - previousEnergy
if change > 0 && math.Exp(-change/temp) < rand.Float64() {
undo()
} else {
previousEnergy = energy
if energy < bestEnergy {
bestEnergy = energy
bestState = state.Copy()
bestTime = time.Now()
}
}
if time.Since(bestTime).Seconds() > 15 {
fmt.Println()
return bestState
}
}
showAnnealProgress(
steps, steps, minTemp, bestEnergy, time.Since(start).Seconds())
fmt.Println()
return bestState
}
func showAnnealProgress(i, n int, t, e, d float64) {
pct := int(100 * float64(i) / float64(n))
fmt.Printf(" %3d%% [", pct)
for p := 0; p < 100; p += 3 {
if pct > p {
fmt.Print("=")
} else {
fmt.Print(" ")
}
}
fmt.Printf("] %.1f %.2f %.3fs \r", t, e, d)
}