Simulated annealing: Difference between revisions
→{{header|jq}}
m (grammar) |
|||
Line 2,138:
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</syntaxhighlight>
=={{header|jq}}==
'''Adapted from [[#Wren|Wren]]'''
'''Works with jq, the C implementation of jq'''
'''Works with gojq, the Go implementation of jq'''
This adaptation does not cache the distances
and can be used for any square grid of cities.
Since jq does not include a PRN generator, we assume an
external source of randomness, such as /dev/urandom.
Specifically, the following program assumes an invocation
of jq along the lines of:
<pre>
< /dev/urandom tr -cd '0-9' | fold -w 1 | jq -Rcnr -f sa.jq
</pre>
Since gojq does not include jq's `_nwise/1`, here is a suitable def:
<pre>
# Require $n > 0
def _nwise($n):
def _n: if length <= $n then . else .[:$n] , (.[$n:] | _n) end;
if $n <= 0 then "_nwise: argument should be non-negative" else _n end;
</pre>
<syntaxhighlight lang="jq">
## Pseuo-random numbers and shuffling
# Output: a prn in range(0;$n) where $n is `.`
def prn:
if . == 1 then 0
else . as $n
| ([1, (($n-1)|tostring|length)]|max) as $w
| [limit($w; inputs)] | join("") | tonumber
| if . < $n then . else ($n | prn) end
end;
def randFloat:
(1000|prn) / 1000;
def knuthShuffle:
length as $n
| if $n <= 1 then .
else {i: $n, a: .}
| until(.i == 0;
.i += -1
| (.i + 1 | prn) as $j
| .a[.i] as $t
| .a[.i] = .a[$j]
| .a[$j] = $t)
| .a
end;
## Generic utilities
def divmod($j):
(. % $j) as $mod
| [(. - $mod) / $j, $mod] ;
def hypot($a;$b):
($a*$a) + ($b*$b) | sqrt;
def lpad($len): tostring | ($len - length) as $l | (" " * $l) + .;
def round($ndec): pow(10;$ndec) as $p | . * $p | round / $p;
def sum(s): reduce s as $x (0; . + $x);
def swap($i; $j):
.[$i] as $tmp
| .[$i] = .[$j]
| .[$j] = $tmp;
### The cities
# all 8 neighbors for an $n x $n grid
def neighbors($n): [1, -1, $n, -$n, $n-1, $n+1, -$n-1, $n+1];
# Distance between two cities $x and $y in an .n * .n grid
def dist($x; $y):
.n as $n
| ($x | divmod($n)) as [$xi, $xj]
| ($y | divmod($n)) as [$yi, $yj]
| hypot( $xi-$yi; $xj - $yj );
### Simulated annealing
# The energy of the input state (.s), to be minimized
# Input: {s, n}
def Es:
.s as $path
| sum( range(0; $path|length - 1) as $i
| dist($path[$i]; $path[$i+1]) );
# temperature function, decreases to 0
def T($k; $kmax; $kT):
(1 - ($k / $kmax)) * $kT;
# variation of E, from one state to the next state
# Input: {s, n}
def dE($u; $v):
.s as $s
| $s[$u] as $su
| $s[$v] as $sv
# old
| dist($s[$u-1]; $su) as $a
| dist($s[$u+1]; $su) as $b
| dist($s[$v-1]; $sv) as $c
| dist($s[$v+1]; $sv) as $d
# new
| dist($s[$u-1]; $sv) as $na
| dist($s[$u+1]; $sv) as $nb
| dist($s[$v-1]; $su) as $nc
| dist($s[$v+1]; $su) as $nd
| if ($v == $u+1) then ($na + $nd) - ($a + $d)
elif ($u == $v+1) then ($nc + $nb) - ($c + $b)
else ($na + $nb + $nc + $nd) - ($a + $b + $c + $d)
end;
# probability of moving from one state to another
def P($deltaE; $k; $kmax; $kT):
T($k; $kmax; $kT) as $T
| if $T == 0 then 0
else (-$deltaE / $T) | exp
end;
# Simulated annealing for $n x $n cities
def sa($kmax; $kT; $n):
def format($k; $T; $E):
[ "k:", ($k | lpad(10)),
"T:", ($T | round(2) | lpad(4)),
"Es:", $E ]
| join(" ");
neighbors($n) as $neighbors # potential neighbors
| ($n*$n) as $n2
# random path from 0 to 0
| {s: ([0] + ([ range(1; $n2)] | knuthShuffle) + [0]) }
| .n = $n # for dist/2
| .Emin = Es # E0
| "kT = \($kT)",
"E(s0) \(.Emin)\n",
( foreach range(0; 1+$kmax) as $k (.;
.emit = null
| if ($k % (($kmax/10)|floor)) == 0
then .emit = format($k; T($k; $kmax; $kT); Es)
else .
end
| (($n2-1)|prn + 1) as $u # a random city apart from the starting point
| (.s[$u] + $neighbors[8|prn]) as $cv # a neighboring city, perhaps
| if ($cv <= 0 or $cv >= $n2) # check the city is not bogus
then . # continue
elif dist(.s[$u]; $cv) > 5 # check true neighbor
then . # continue
else .s[$cv] as $v # city index
| dE($u; $v) as $deltae
| if ($deltae < 0 or # always move if negative
P($deltae; $k; $kmax; $kT) >= randFloat)
then .s |= swap($u; $v)
| .Emin += $deltae
end
end;
select(.emit).emit,
(select($k == $kmax)
| "\nE(s_final) \(.Emin)",
"Path:",
# output final state
(.s | map(lpad(3)) | _nwise(10) | join(" ")) ) ));
# Cities on a 10 x 10 grid
sa(1e6; 1; 10)
</syntaxhighlight>
{{output}}
<pre>
kT = 1
E(s0) 511.63434626356127
k: 0 T: 1 Es: 511.63434626356127
k: 100000 T: 0.9 Es: 183.44842684951274
k: 200000 T: 0.8 Es: 173.6522166458839
k: 300000 T: 0.7 Es: 191.88956498870922
k: 400000 T: 0.6 Es: 161.63509965859427
k: 500000 T: 0.5 Es: 173.6829125726551
k: 600000 T: 0.4 Es: 135.5154326151275
k: 700000 T: 0.3 Es: 174.33930236055193
k: 800000 T: 0.2 Es: 141.907500599355
k: 900000 T: 0.1 Es: 141.76740977979034
k: 1000000 T: 0 Es: 148.13930861301918
E(s_final) 148.13930861301935
Path:
0 1 2 11 10 20 21 22 23 24
14 5 4 3 13 12 32 42 33 25
15 16 6 7 8 9 19 29 39 28
18 17 27 26 36 46 35 34 43 52
41 30 31 44 45 55 56 38 37 49
48 47 65 64 54 53 51 72 91 81
80 71 70 61 62 40 50 60 92 82
83 73 63 57 67 66 75 74 84 93
94 95 78 77 68 58 87 76 86 99
89 79 69 59 88 98 97 96 85 90
0
</pre>
=={{header|Julia}}==
| |||