FD.io VPP  v18.07-34-g55fbdb9
Vector Packet Processing
anneal.c
Go to the documentation of this file.
1 /*
2  Copyright (c) 2011 Cisco and/or its affiliates.
3 
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at:
7  *
8  * http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15 */
16 
17 #include <vppinfra/anneal.h>
18 
19 /*
20  * Optimize an objective function by simulated annealing
21  *
22  * Here are a couple of short, easily-understood
23  * descriptions of simulated annealing:
24  *
25  * http://www.cs.sandia.gov/opt/survey/sa.html
26  * Numerical Recipes in C, 2nd ed., 444ff
27  *
28  * The description in the Wikipedia is not helpful.
29  *
30  * The algorithm tries to produce a decent answer to combinatorially
31  * explosive optimization problems by analogy to slow cooling
32  * of hot metal, aka annealing.
33  *
34  * There are (at least) three problem-dependent annealing parameters
35  * to consider:
36  *
37  * t0, the initial "temperature. Should be set so that the probability
38  * of accepting a transition to a higher cost configuration is
39  * initially about 0.8.
40  *
41  * ntemps, the number of temperatures to use. Each successive temperature
42  * is some fraction of the previous temperature.
43  *
44  * nmoves_per_temp, the number of configurations to try at each temperature
45  *
46  * It is a black art to set ntemps, nmoves_per_temp, and the rate
47  * at which the temperature drops. Go too fast with too few iterations,
48  * and the computation falls into a local minimum instead of the
49  * (desired) global minimum.
50  */
51 
52 void
54 {
55  f64 t;
56  f64 cost, prev_cost, delta_cost, initial_cost, best_cost;
57  f64 random_accept, delta_cost_over_t;
58  f64 total_increase = 0.0, average_increase;
59  u32 i, j;
60  u32 number_of_increases = 0;
61  u32 accepted_this_temperature;
62  u32 best_saves_this_temperature;
63  int accept;
64 
65  t = p->initial_temperature;
66  best_cost = initial_cost = prev_cost = p->anneal_metric (p->opaque);
68 
69  if (p->flags & CLIB_ANNEAL_VERBOSE)
70  fformat (stdout, "Initial cost %.2f\n", initial_cost);
71 
72  for (i = 0; i < p->number_of_temperatures; i++)
73  {
74  accepted_this_temperature = 0;
75  best_saves_this_temperature = 0;
76 
78  cost = best_cost;
79 
80  for (j = 0; j < p->number_of_configurations_per_temperature; j++)
81  {
83  cost = p->anneal_metric (p->opaque);
84 
85  delta_cost = cost - prev_cost;
86 
87  /* cost function looks better, accept this move */
88  if (p->flags & CLIB_ANNEAL_MINIMIZE)
89  accept = delta_cost < 0.0;
90  else
91  accept = delta_cost > 0.0;
92 
93  if (accept)
94  {
95  if (p->flags & CLIB_ANNEAL_MINIMIZE)
96  if (cost < best_cost)
97  {
98  if (p->flags & CLIB_ANNEAL_VERBOSE)
99  fformat (stdout, "New best cost %.2f\n", cost);
100  best_cost = cost;
102  best_saves_this_temperature++;
103  }
104 
105  accepted_this_temperature++;
106  prev_cost = cost;
107  continue;
108  }
109 
110  /* cost function worse, keep stats to suggest t0 */
111  total_increase += (p->flags & CLIB_ANNEAL_MINIMIZE) ?
112  delta_cost : -delta_cost;
113 
114  number_of_increases++;
115 
116  /*
117  * Accept a higher cost with Pr { e^(-(delta_cost / T)) },
118  * equivalent to rnd[0,1] < e^(-(delta_cost / T))
119  *
120  * AKA, the Boltzmann factor.
121  */
122  random_accept = random_f64 (&p->random_seed);
123 
124  delta_cost_over_t = delta_cost / t;
125 
126  if (random_accept < exp (-delta_cost_over_t))
127  {
128  accepted_this_temperature++;
129  prev_cost = cost;
130  continue;
131  }
133  }
134 
135  if (p->flags & CLIB_ANNEAL_VERBOSE)
136  {
137  fformat (stdout, "Temp %.2f, cost %.2f, accepted %d, bests %d\n", t,
138  prev_cost, accepted_this_temperature,
139  best_saves_this_temperature);
140  fformat (stdout, "Improvement %.2f\n", initial_cost - prev_cost);
141  fformat (stdout, "-------------\n");
142  }
143 
144  t = t * p->temperature_step;
145  }
146 
147  /*
148  * Empirically, one wants the probability of accepting a move
149  * at the initial temperature to be about 0.8.
150  */
151  average_increase = total_increase / (f64) number_of_increases;
152  p->suggested_initial_temperature = average_increase / 0.22; /* 0.22 = -ln (0.8) */
153 
154  p->final_temperature = t;
155  p->final_metric = p->anneal_metric (p->opaque);
156 
157  if (p->flags & CLIB_ANNEAL_VERBOSE)
158  {
159  fformat (stdout, "Average cost increase from a bad move: %.2f\n",
160  average_increase);
161  fformat (stdout, "Suggested t0 = %.2f\n",
163  }
164 }
165 
166 /*
167  * fd.io coding-style-patch-verification: ON
168  *
169  * Local Variables:
170  * eval: (c-set-style "gnu")
171  * End:
172  */
u32 number_of_configurations_per_temperature
Definition: anneal.h:37
int i
u32 number_of_temperatures
Definition: anneal.h:34
double f64
Definition: types.h:142
f64 temperature_step
Definition: anneal.h:31
unsigned int u32
Definition: types.h:88
void(* anneal_restore_best_configuration)(void *opaque)
Definition: anneal.h:75
f64 final_temperature
Definition: anneal.h:51
void(* anneal_new_configuration)(void *opaque)
Definition: anneal.h:66
word fformat(FILE *f, char *fmt,...)
Definition: format.c:453
f64 initial_temperature
Definition: anneal.h:28
#define CLIB_ANNEAL_MINIMIZE
Definition: anneal.h:41
#define CLIB_ANNEAL_VERBOSE
Definition: anneal.h:40
f64 suggested_initial_temperature
Definition: anneal.h:57
void clib_anneal(clib_anneal_param_t *p)
Definition: anneal.c:53
static f64 random_f64(u32 *seed)
Generate f64 random number in the interval [0,1].
Definition: random.h:145
f64(* anneal_metric)(void *opaque)
Definition: anneal.h:63
void(* anneal_restore_previous_configuration)(void *opaque)
Definition: anneal.h:69
void(* anneal_save_best_configuration)(void *opaque)
Definition: anneal.h:72