Optimization: principles and algorithms, by Michel Bierlaire
tspSimulatedAnnealing.m
Go to the documentation of this file.
1 %> \file
2 %> Algorithm 27.7: simulated annealing for the TSP. Implementation of algorithm 27.7 of \cite Bier15-book
3 %>
4 %> @note Tested with \ref run2703simAnn.m
5 %> @note Calls \ref tspTourLength
6 %> @note Calls \ref twoOptRandomNeighbor
7 %>
8 %> @author Michel Bierlaire
9 %> @date Sun Apr 19 13:30:57 2015
10 %> @ingroup Algorithms
11 %> @ingroup chap27
12 %>
13 %> Simulated annealing for the TSP
14 %> @param tour initial solution
15 %> @param dist the distance matrix
16 %> @return bestTour best tour found
17 %> @return bestTourLength length of the best tour found
18 %> @return The file \c tspSimAnnIters.dat is also created, containing the details of the iterations.
19 function [bestTour, bestTourLength] = tspSimulatedAnnealing(tour,dist)
20  [fff,msg] = fopen("tspSimAnnIters.dat","w") ;
21  fprintf(fff,"Iter\tTemp\tCurrent\tBest\n") ;
22  printf("Iter\tTemp\tCurrent\tBest\n") ;
23  lastTemp = 0.000001 ;
24  maxiter = 50 ;
25  nbrcooling = 100 ;
26  current = tour ;
27  bestTour = tour ;
28  currentLength = tspTourLength(current,dist) ;
29  bestTourLength = currentLength ;
30  typicalIncrease = 5.0 ;
31  firstTau = 0.999 ;
32  lastTau = 0.00001 ;
33  n = 0 ;
34  for tt =1:nbrcooling
35  a = (lastTau - firstTau) / nbrcooling ;
36  temp = -typicalIncrease/log(firstTau + a * tt) ;
37  k = 1 ;
38  iter = 0 ;
39  while (iter <= maxiter)
40  n += 1 ;
41  fprintf(fff,"%d\t%f\t%f\t%f\n",n,temp,currentLength,bestTourLength)
42  printf("%d\t%f\t%f\t%f\n",n,temp,currentLength,bestTourLength)
43  iter += 1 ;
44  if (mod(iter,10) == 0 )
45  endif
46  chosenNeighborhood = twoOptRandomNeighbor(current) ;
47  l = tspTourLength(chosenNeighborhood,dist) ;
48  delta = l - currentLength ;
49  if (delta < 0)
50  current = chosenNeighborhood ;
51  currentLength = l ;
52  if (l < bestTourLength)
53  bestTour = current ;
54  bestTourLength = currentLength ;
55  endif
56  else
57  r = rand() ;
58  if r < exp(-delta/temp)
59  current = chosenNeighborhood ;
60  currentLength = l ;
61  else
62  endif
63  endif
64  endwhile
65  endfor
66  n += 1 ;
67  fprintf(fff,"%d\t%f\t%f\t%f\n",n,temp,currentLength,bestTourLength)
68  printf("%d\t%f\t%f\t%f\n",n,temp,currentLength,bestTourLength)
69  fclose(fff) ;
70 endfunction
function tspSimulatedAnnealing(in tour, in dist)
function tspTourLength(in tour, in dist)
Calculate the length of a tour for the TSP.
function twoOptRandomNeighbor(in cities)
Generate one random 2-opt neighbor for the TSP.
Copyright 2015-2016 Michel Bierlaire