2 Copyright (c) 2011 Cisco and/or its affiliates.
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:
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
17 #include <vppinfra/anneal.h>
20 * Optimize an objective function by simulated annealing
22 * Here are a couple of short, easily-understood
23 * descriptions of simulated annealing:
25 * http://www.cs.sandia.gov/opt/survey/sa.html
26 * Numerical Recipes in C, 2nd ed., 444ff
28 * The description in the Wikipedia is not helpful.
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.
34 * There are (at least) three problem-dependent annealing parameters
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.
41 * ntemps, the number of temperatures to use. Each successive temperature
42 * is some fraction of the previous temperature.
44 * nmoves_per_temp, the number of configurations to try at each temperature
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.
53 clib_anneal (clib_anneal_param_t * p)
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;
60 u32 number_of_increases = 0;
61 u32 accepted_this_temperature;
62 u32 best_saves_this_temperature;
65 t = p->initial_temperature;
66 best_cost = initial_cost = prev_cost = p->anneal_metric (p->opaque);
67 p->anneal_save_best_configuration (p->opaque);
69 if (p->flags & CLIB_ANNEAL_VERBOSE)
70 fformat (stdout, "Initial cost %.2f\n", initial_cost);
72 for (i = 0; i < p->number_of_temperatures; i++)
74 accepted_this_temperature = 0;
75 best_saves_this_temperature = 0;
77 p->anneal_restore_best_configuration (p->opaque);
80 for (j = 0; j < p->number_of_configurations_per_temperature; j++)
82 p->anneal_new_configuration (p->opaque);
83 cost = p->anneal_metric (p->opaque);
85 delta_cost = cost - prev_cost;
87 /* cost function looks better, accept this move */
88 if (p->flags & CLIB_ANNEAL_MINIMIZE)
89 accept = delta_cost < 0.0;
91 accept = delta_cost > 0.0;
95 if (p->flags & CLIB_ANNEAL_MINIMIZE)
98 if (p->flags & CLIB_ANNEAL_VERBOSE)
99 fformat (stdout, "New best cost %.2f\n", cost);
101 p->anneal_save_best_configuration (p->opaque);
102 best_saves_this_temperature++;
105 accepted_this_temperature++;
110 /* cost function worse, keep stats to suggest t0 */
111 total_increase += (p->flags & CLIB_ANNEAL_MINIMIZE) ?
112 delta_cost : -delta_cost;
114 number_of_increases++;
117 * Accept a higher cost with Pr { e^(-(delta_cost / T)) },
118 * equivalent to rnd[0,1] < e^(-(delta_cost / T))
120 * AKA, the Boltzmann factor.
122 random_accept = random_f64 (&p->random_seed);
124 delta_cost_over_t = delta_cost / t;
126 if (random_accept < exp (-delta_cost_over_t))
128 accepted_this_temperature++;
132 p->anneal_restore_previous_configuration (p->opaque);
135 if (p->flags & CLIB_ANNEAL_VERBOSE)
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");
144 t = t * p->temperature_step;
148 * Empirically, one wants the probability of accepting a move
149 * at the initial temperature to be about 0.8.
151 average_increase = total_increase / (f64) number_of_increases;
152 p->suggested_initial_temperature = average_increase / 0.22; /* 0.22 = -ln (0.8) */
154 p->final_temperature = t;
155 p->final_metric = p->anneal_metric (p->opaque);
157 if (p->flags & CLIB_ANNEAL_VERBOSE)
159 fformat (stdout, "Average cost increase from a bad move: %.2f\n",
161 fformat (stdout, "Suggested t0 = %.2f\n",
162 p->suggested_initial_temperature);
167 * fd.io coding-style-patch-verification: ON
170 * eval: (c-set-style "gnu")