Anonymous user
Simulated annealing: Difference between revisions
→{{header|J}}: added zkl
m (→{{header|J}}) |
(→{{header|J}}: added zkl) |
||
Line 257:
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</lang>
=={{header|zkl}}==
{{trans|EchoLisp}}
<lang zkl>var [const] _dists=(0d10_000).pump(List,fcn(abcd){ // two points (a,b) & (c,d), calc distance
ab,cd,a,b,c,d:=abcd/100, abcd%100, ab/10,ab%10, cd/10,cd%10;
(a-c).toFloat().hypot(b-d)
});
fcn dist(ci,cj){ _dists[cj*100 + ci] } // index into lookup table of floats
fcn Es(path) // E(s) = length(path): E(a,b,c)--> dist(a,b) + dist(b,c)
{ d:=Ref(0.0); path.reduce('wrap(a,b){ d.apply('+,dist(a,b)); b }); d.value }
// temperature() function
fcn T(k,kmax,kT){ (1.0 - k.toFloat()/kmax)*kT }
// deltaE = Es_new - Es_old > 0
// probability to move if deltaE > 0, -->0 when T --> 0 (frozen state)
fcn P(deltaE,k,kmax,kT){ (-deltaE/T(k,kmax,kT)).exp() } //-->Float
// deltaE from path ( .. a u b .. c v d ..) to (.. a v b ... c u d ..)
// deltaE before swapping (u,v)
fcn dE(s,u,v){ su,sv:=s[u],s[v]; //-->Float
// 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) (na+nd) - (a+d);
else if(u==v+1) (nc+nb) - (c+b);
else (na+nb+nc+nd) - (a+b+c+d);
}
// all 8 neighbours
var [const] dirs=ROList(1, -1, 10, -10, 9, 11, -11, -9),
fmt="k:%10,d T: %8.4f Es: %8.4f".fmt; // since we use it twice
fcn sa(kmax,kT=10){
s:=List(0, [1..99].walk().shuffle().xplode(), 0); // random path from 0 to 0
println("E(s0) %f".fmt(Es(s))); // random starter
Emin:=Es(s); // E0
foreach k in (kmax){
if(0==k%(kmax/10)) println(fmt(k,T(k,kmax,kT),Es(s)));
u:=(1).random(100); // city index 1 99
cv:=s[u] + dirs[(0).random(8)]; // city number
if(not (0<cv<100)) continue; // bogus city
if(dist(s[u],cv)>5) continue; // check true neighbour (eg 0 9)
v:=s.index(cv,1); // city index
deltae:=dE(s,u,v);
if(deltae<0 or // always move if negative
P(deltae,k,kmax,kT)>=(0.0).random(1)){
s.swap(u,v);
Emin+=deltae;
}
// (assert (= (round Emin) (round (Es s))))
}//foreach
println(fmt(kmax,T(kmax-1,kmax,kT),Es(s)));
println("E(s_final) %f".fmt(Emin));
println("Path: ",s.toString(*));
}</lang>
<lang zkl>sa(0d1_000_000,1);</lang>
{{out}}
<pre>
E(s0) 540.897080
k: 0 T: 1.0000 Es: 540.8971
k: 100,000 T: 0.9000 Es: 181.5102
k: 200,000 T: 0.8000 Es: 167.1944
k: 300,000 T: 0.7000 Es: 159.0975
k: 400,000 T: 0.6000 Es: 170.2344
k: 500,000 T: 0.5000 Es: 130.9919
k: 600,000 T: 0.4000 Es: 115.3422
k: 700,000 T: 0.3000 Es: 113.9280
k: 800,000 T: 0.2000 Es: 106.7924
k: 900,000 T: 0.1000 Es: 103.7213
k: 1,000,000 T: 0.0000 Es: 103.7213
E(s_final) 103.721349
Path: L(0,10,11,21,20,30,40,50,60,70,80,81,71,72,73,63,52,62,61,51,41,31,32,22,12,13,14,15,25,16,17,18,28,27,26,36,35,45,34,24,23,33,42,43,44,54,53,64,74,84,83,82,90,91,92,93,94,95,85,86,96,97,87,88,98,99,89,79,69,68,78,77,67,66,76,75,65,55,56,46,37,38,48,47,57,58,59,49,39,29,19,9,8,7,6,5,4,3,2,1,0)
</pre>
| |||