diff options
Diffstat (limited to 'vppinfra/vppinfra/anneal.c')
| -rw-r--r-- | vppinfra/vppinfra/anneal.c | 166 |
1 files changed, 87 insertions, 79 deletions
diff --git a/vppinfra/vppinfra/anneal.c b/vppinfra/vppinfra/anneal.c index 9b3a5fe8f94..35d10946482 100644 --- a/vppinfra/vppinfra/anneal.c +++ b/vppinfra/vppinfra/anneal.c @@ -18,7 +18,7 @@ /* * Optimize an objective function by simulated annealing - * + * * Here are a couple of short, easily-understood * descriptions of simulated annealing: * @@ -32,10 +32,10 @@ * of hot metal, aka annealing. * * There are (at least) three problem-dependent annealing parameters - * to consider: + * to consider: * * t0, the initial "temperature. Should be set so that the probability - * of accepting a transition to a higher cost configuration is + * of accepting a transition to a higher cost configuration is * initially about 0.8. * * ntemps, the number of temperatures to use. Each successive temperature @@ -49,116 +49,124 @@ * (desired) global minimum. */ -void clib_anneal (clib_anneal_param_t * p) +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; + 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); + fformat (stdout, "Initial cost %.2f\n", initial_cost); - for (i = 0; i < p->number_of_temperatures; i++) + 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); - } + 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"); - } - + { + 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->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); + 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: + */ |