diff options
Diffstat (limited to 'src/vppinfra/anneal.c')
| -rw-r--r-- | src/vppinfra/anneal.c | 172 |
1 files changed, 172 insertions, 0 deletions
diff --git a/src/vppinfra/anneal.c b/src/vppinfra/anneal.c new file mode 100644 index 00000000000..35d10946482 --- /dev/null +++ b/src/vppinfra/anneal.c @@ -0,0 +1,172 @@ +/* + Copyright (c) 2011 Cisco and/or its affiliates. + + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. +*/ + +#include <vppinfra/anneal.h> + +/* + * Optimize an objective function by simulated annealing + * + * Here are a couple of short, easily-understood + * descriptions of simulated annealing: + * + * http://www.cs.sandia.gov/opt/survey/sa.html + * Numerical Recipes in C, 2nd ed., 444ff + * + * The description in the Wikipedia is not helpful. + * + * The algorithm tries to produce a decent answer to combinatorially + * explosive optimization problems by analogy to slow cooling + * of hot metal, aka annealing. + * + * There are (at least) three problem-dependent annealing parameters + * to consider: + * + * t0, the initial "temperature. Should be set so that the probability + * of accepting a transition to a higher cost configuration is + * initially about 0.8. + * + * ntemps, the number of temperatures to use. Each successive temperature + * is some fraction of the previous temperature. + * + * nmoves_per_temp, the number of configurations to try at each temperature + * + * It is a black art to set ntemps, nmoves_per_temp, and the rate + * at which the temperature drops. Go too fast with too few iterations, + * and the computation falls into a local minimum instead of the + * (desired) global minimum. + */ + +void +clib_anneal (clib_anneal_param_t * p) +{ + f64 t; + f64 cost, prev_cost, delta_cost, initial_cost, best_cost; + f64 random_accept, delta_cost_over_t; + f64 total_increase = 0.0, average_increase; + u32 i, j; + u32 number_of_increases = 0; + u32 accepted_this_temperature; + u32 best_saves_this_temperature; + int accept; + + t = p->initial_temperature; + best_cost = initial_cost = prev_cost = p->anneal_metric (p->opaque); + p->anneal_save_best_configuration (p->opaque); + + if (p->flags & CLIB_ANNEAL_VERBOSE) + fformat (stdout, "Initial cost %.2f\n", initial_cost); + + for (i = 0; i < p->number_of_temperatures; i++) + { + accepted_this_temperature = 0; + best_saves_this_temperature = 0; + + p->anneal_restore_best_configuration (p->opaque); + cost = best_cost; + + for (j = 0; j < p->number_of_configurations_per_temperature; j++) + { + p->anneal_new_configuration (p->opaque); + cost = p->anneal_metric (p->opaque); + + delta_cost = cost - prev_cost; + + /* cost function looks better, accept this move */ + if (p->flags & CLIB_ANNEAL_MINIMIZE) + accept = delta_cost < 0.0; + else + accept = delta_cost > 0.0; + + if (accept) + { + if (p->flags & CLIB_ANNEAL_MINIMIZE) + if (cost < best_cost) + { + if (p->flags & CLIB_ANNEAL_VERBOSE) + fformat (stdout, "New best cost %.2f\n", cost); + best_cost = cost; + p->anneal_save_best_configuration (p->opaque); + best_saves_this_temperature++; + } + + accepted_this_temperature++; + prev_cost = cost; + continue; + } + + /* cost function worse, keep stats to suggest t0 */ + total_increase += (p->flags & CLIB_ANNEAL_MINIMIZE) ? + delta_cost : -delta_cost; + + number_of_increases++; + + /* + * Accept a higher cost with Pr { e^(-(delta_cost / T)) }, + * equivalent to rnd[0,1] < e^(-(delta_cost / T)) + * + * AKA, the Boltzmann factor. + */ + random_accept = random_f64 (&p->random_seed); + + delta_cost_over_t = delta_cost / t; + + if (random_accept < exp (-delta_cost_over_t)) + { + accepted_this_temperature++; + prev_cost = cost; + continue; + } + p->anneal_restore_previous_configuration (p->opaque); + } + + if (p->flags & CLIB_ANNEAL_VERBOSE) + { + fformat (stdout, "Temp %.2f, cost %.2f, accepted %d, bests %d\n", t, + prev_cost, accepted_this_temperature, + best_saves_this_temperature); + fformat (stdout, "Improvement %.2f\n", initial_cost - prev_cost); + fformat (stdout, "-------------\n"); + } + + t = t * p->temperature_step; + } + + /* + * Empirically, one wants the probability of accepting a move + * at the initial temperature to be about 0.8. + */ + average_increase = total_increase / (f64) number_of_increases; + p->suggested_initial_temperature = average_increase / 0.22; /* 0.22 = -ln (0.8) */ + + p->final_temperature = t; + p->final_metric = p->anneal_metric (p->opaque); + + if (p->flags & CLIB_ANNEAL_VERBOSE) + { + fformat (stdout, "Average cost increase from a bad move: %.2f\n", + average_increase); + fformat (stdout, "Suggested t0 = %.2f\n", + p->suggested_initial_temperature); + } +} + +/* + * fd.io coding-style-patch-verification: ON + * + * Local Variables: + * eval: (c-set-style "gnu") + * End: + */ |