Optimization: principles and algorithms, by Michel Bierlaire
ksSimulatedAnnealing.m
Go to the documentation of this file.
1 %> \file
2 %> Algorithm 27.7: simulated annealing for the knapsack problem. Implementation of algorithm 27.7 of \cite Bier15-book
3 %>
4 %> @note Tested with \ref run2702simAnn.m
5 %> @note Calls \ref ksRandomNeighbor
6 %>
7 %> @author Michel Bierlaire
8 %> @date Sun Apr 19 13:20:29 2015
9 %> @ingroup Algorithms
10 %> @ingroup chap27
11 %>
12 %> Simulated annealing for the knapsack problem
13 %> @param u utility of each item
14 %> @param w weight of each item
15 %> @param c capacity of the knapsack
16 %> @param x0 current solution
17 %> @return bestSack best solution found
18 %> @return bestSackUtility utility of the best solution
19 %> @return bestSackWeight weight of the best solution
20 %> @return The file \c ksSimAnnIters.dat is also created, containing the details of the iterations.
21 function [bestSack, bestSackUtility, bestSackWeight] = ksSimulatedAnnealing(u,w,c,x0)
22  [fff,msg] = fopen("ksSimAnnIters.dat","w")
23  fprintf(fff,"Iter\tTemp\tCurrent_u\tCurrent_w\tBest_u\tBest_w\n") ;
24  printf("Iter\tTemp\tCurrent_u\tCurrent_w\tBest_u\tBest_w\n") ;
25  lastTemp = 0.000001 ;
26  maxiter = 5 ;
27  nbrcooling = 1000 ;
28  current = x0 ;
29  bestSack = x0 ;
30  if (w'*x0 > c)
31  error("Infeasible starting point") ;
32  endif
33  currentLength = u'*current;
34  currentWeight = w'*current ;
35  bestSackUtility = currentLength ;
36  bestSackWeight = currentWeight ;
37  typicalIncrease = 20.0 ;
38  firstTau = 0.999 ;
39  lastTau = 0.00001 ;
40  n = 0 ;
41  for tt =1:nbrcooling
42  a = (lastTau - firstTau) / nbrcooling ;
43  temp = -typicalIncrease/log(firstTau + a * tt) ;
44  k = 1 ;
45  iter = 0 ;
46  while (iter <= maxiter)
47  n += 1 ;
48  fprintf(fff,"%d\t%f\t%f\t%f\t%f\t%f\n",n,temp,currentLength,currentWeight,bestSackUtility,bestSackWeight)
49  printf("%d\t%f\t%f\t%f\t%f\t%f\n",n,temp,currentLength,currentWeight,bestSackUtility,bestSackWeight)
50  iter += 1 ;
51  chosenNeighborhood = ksRandomNeighbor(current,1) ;
52  l = chosenNeighborhood'*u ;
53  weight = chosenNeighborhood'* w ;
54  delta = l - currentLength ;
55  if (weight > c)
56  elseif (delta > 0)
57  current = chosenNeighborhood ;
58  currentLength = l ;
59  currentWeight = current'*w ;
60  if (l > bestSackUtility)
61  bestSack = current ;
62  bestSackUtility = currentLength ;
63  bestSackWeight = currentWeight ;
64  endif
65  else
66  r = rand() ;
67  if r < exp(delta/temp)
68  current = chosenNeighborhood ;
69  currentLength = l ;
70  currentWeight = current'*w ;
71  else
72  endif
73  endif
74  endwhile
75  endfor
76  n += 1 ;
77  fprintf(fff,"%d\t%f\t%f\t%f\t%f\t%f\n",n,temp,currentLength,currentWeight,bestSackUtility,bestSackWeight)
78  printf("%d\t%f\t%f\t%f\t%f\t%f\n",n,temp,currentLength,currentWeight,bestSackUtility,bestSackWeight)
79  fclose(fff) ;
80 endfunction
function ksRandomNeighbor(in x0, in s)
function ksSimulatedAnnealing(in u, in w, in c, in x0)