2 %> Algorithm 27.7: simulated annealing
for the knapsack problem. Implementation of algorithm 27.7 of \cite Bier15-book
4 %> @note Tested with \ref run2702simAnn.m
7 %> @author Michel Bierlaire
8 %> @date Sun Apr 19 13:20:29 2015
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.
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") ;
31 error("Infeasible starting point") ;
33 currentLength = u'*current;
34 currentWeight = w'*current ;
35 bestSackUtility = currentLength ;
36 bestSackWeight = currentWeight ;
37 typicalIncrease = 20.0 ;
42 a = (lastTau - firstTau) / nbrcooling ;
43 temp = -typicalIncrease/log(firstTau + a * tt) ;
46 while (iter <= maxiter)
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)
52 l = chosenNeighborhood'*u ;
53 weight = chosenNeighborhood'* w ;
54 delta = l - currentLength ;
57 current = chosenNeighborhood ;
59 currentWeight = current'*w ;
60 if (l > bestSackUtility)
62 bestSackUtility = currentLength ;
63 bestSackWeight = currentWeight ;
67 if r < exp(delta/temp)
68 current = chosenNeighborhood ;
70 currentWeight = current'*w ;
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)
function ksRandomNeighbor(in x0, in s)
function ksSimulatedAnnealing(in u, in w, in c, in x0)