Simulated annealing: Difference between revisions

=={{header|Nim}}==

<lang Nim>import math, random, sugar, strformat

from times import cpuTime

const

kT = 1

kMax = 1_000_000

proc randomNeighbor(x: int): int =

case x

of 0:

rand([1, 10, 11])

of 9:

rand([8, 18, 19])

of 90:

rand([80, 81, 91])

of 99:

rand([88, 89, 98])

elif x > 0 and x < 9: # top ceiling

rand [x-1, x+1, x+9, x+10, x+11]

elif x > 90 and x < 99: # bottom floor

rand [x-11, x-10, x-9, x-1, x+1]

elif x mod 10 == 0: # left wall

rand([x-10, x-9, x+1, x+10, x+11])

elif (x+1) mod 10 == 0: # right wall

rand([x-11, x-10, x-1, x+9, x+10])

else: # center

rand([x-11, x-10, x-9, x-1, x+1, x+9, x+10, x+11])

proc neighbor(s: seq[int]): seq[int] =

result = s

var city = rand s

var cityNeighbor = city.randomNeighbor

while cityNeighbor == 0 or city == 0:

city = rand s

cityNeighbor = city.randomNeighbor

result[s.find city].swap result[s.find cityNeighbor]

func distNeighbor(a, b: int): float =

template divmod(a: int): (int, int) = (a div 10, a mod 10)

let

(diva, moda) = a.divmod

(divb, modb) = b.divmod

hypot((diva-divb).float, (moda-modb).float)

func temperature(k, kmax: float): float =

kT * (1 - (k / kmax))

func pdelta(eDelta, temp: float): float =

if eDelta < 0: 1.0

else: exp(-eDelta / temp)

func energy(path: seq[int]): float =

var sum = 0.distNeighbor path[0]

for i in 1 ..< path.len:

sum += path[i-1].distNeighbor(path[i])

sum + path[^1].distNeighbor 0

proc main =

randomize()

var

s = block:

var x = lc[x | (x <- 0 .. 99), int]

template shuffler: int = rand(1 .. x.len-1)

for i in 1 .. x.len-1:

x[i].swap x[shuffler()]

x

let startTime = cpuTime()

echo fmt"E(s0): {energy s:6.4f}"

for k in 0 .. kMax:

var

temp = temperature(float k, float kMax)

lastenergy = energy s

newneighbor = s.neighbor

newenergy = newneighbor.energy

if k mod (kMax div 10) == 0:

echo fmt"k: {k:7} T: {temp:6.2f} Es: {lastenergy:6.4f}"

var deltaEnergy = newenergy - lastenergy

if pDelta(deltaEnergy, temp) >= rand(1.0):

s = newneighbor

s.add 0

echo fmt"E(sFinal): {energy s:6.4f}"

echo fmt"path: {s}"

#echo fmt"ended after: {cpuTime() - startTime}"

main()</lang>

Compile and run: <pre>nim c -r -d:release --opt:speed travel_sa.nim</pre>

{{out}}

Sample run:

<pre>

E(s0): 505.1591

k: 0 T: 1.00 Es: 505.1591

k: 100000 T: 0.90 Es: 196.5216

k: 200000 T: 0.80 Es: 165.6735

k: 300000 T: 0.70 Es: 159.3411

k: 400000 T: 0.60 Es: 144.8330

k: 500000 T: 0.50 Es: 131.7888

k: 600000 T: 0.40 Es: 127.6914

k: 700000 T: 0.30 Es: 113.9280

k: 800000 T: 0.20 Es: 104.7279

k: 900000 T: 0.10 Es: 103.3137

k: 1000000 T: 0.00 Es: 103.3137

E(sFinal): 103.3137

path: @[0, 10, 11, 22, 21, 20, 30, 31, 41, 40, 50, 51, 61, 60, 70, 71, 81, 80, 90, 91, 92, 93, 82, 83, 73, 72, 62, 63, 53, 52, 42, 32, 33, 23, 13, 14, 24, 34, 35, 25, 15, 16, 26, 36, 47, 48, 38, 39, 49, 59, 58, 57, 68, 69, 79, 89, 99, 98, 97, 96, 95, 94, 84, 74, 75, 85, 86, 87, 88, 78, 77, 67, 76, 66, 65, 64, 54, 43, 44, 45, 55, 56, 46, 37, 27, 28, 29, 19, 9, 8, 18, 17, 7, 6, 5, 4, 3, 2, 12, 1, 0]

</pre>