The simulated_annealing command attempts to find a point in a search space for which a real-valued cost function is minimized, by using the method of simulated annealing.
Note: this function requires that giac is linked to GNU Scientific Library.
p=e |
|
f(x)=e−(x−1)2sin(8x). |
simulated_annealing(15.5,x->exp(-(x-1)^2)*sin(8x), |
(x,y)->abs(x-y),(x,m)->rand(x-m,x+m), |
[1.0,0.008,1.003,2.0e-6],[20,100],1.0) |
1.36313090008 |
We attempt to find the shortest tour which visits each city exactly once. A tour is represented by a permutation of cities. In total, there are 12!=479001600 possible configurations.
First we need to create a distance matrix which stores the distances between each two cities
because each distance may be called for multiple times.
We do so by applying the function dist_km which computes the shortest distance
(in kilometres) between two cities on a spherical model of Earth of radius R=6375 km.
Input:
dist_km:=proc(latitude1,longitude1,latitude2,longitude2) local R,sla1,cla1,slo1,clo1,sla2,cla2,slo2,clo2,x1,x2,y1,y2,z1,z2,p,a; R:=6375.0; sla1:=sin(latitude1*pi/180); cla1:=cos(latitude1*pi/180); slo1:=sin(longitude1*pi/180); clo1:=cos(longitude1*pi/180); sla2:=sin(latitude2*pi/180); cla2:=cos(latitude2*pi/180); slo2:=sin(longitude2*pi/180); clo2:=cos(longitude2*pi/180); x1:=cla1*clo1; y1:=cla1*slo1; z1:=sla1; x2:=cla2*clo2; y2:=cla2*slo2; z2:=sla2; p:=x1*x2+y1*y2+z1*z2; a:=acos(p); return R*a; end:;
Now we create the distance matrix by using the following commands.
Input:
nc:=length(cities):; |
dist_mat:=matrix(nc,nc, |
(j,k)->dist_km(cities[j,1],cities[j,2],cities[k,1],cities[k,2])):; |
We generate a neighbor of a given tour by exchanging two random consecutive cities. The distance between two tours (configurations) is simply the Hamming distance. The cost of a tour is equal to its length (in kilometres). The three functions we require are thus entered as follows:
distf:=proc(xp,yp) return hamdist(xp,yp); end:;
costf:=proc(xp) local j,d; assume(j,symbol); d:=0; for j from 0 to nc-1 do d+=dist_mat[xp[j],xp[irem(j+1,nc)]]; od; return d; end:;
stepf:=proc(xp) local j,jnext,tmp,xpmod; j:=rand(nc); jnext:=irem(j+1,nc); tmp:=xp[j]; xpmod:=xp; xpmod[j]:=xpmod[jnext]; xpmod[jnext]:=tmp; return xpmod; end:;
The initial tour is a random permutation of cities.
Input:
The best tour may be found by entering the following command (note that we use the default values
of n and N).
Input:
Possible output:
⎡ ⎣ | 7,2,8,6,0,3,5,9,1,11,10,4 | ⎤ ⎦ |
The easiest way to visualize the result is to draw the tour as a directed graph.
Input:
Output:
"a directed unweighted graph with 12 vertices and 12 arcs" |
Input:
Observe that we are swapping latitudes and longitudes to obtain a more appropriate layout.
Output:
(Note: To display city names, set labels to true.)