/*
* Optimize an objective function by simulated annealing
- *
+ *
* Here are a couple of short, easily-understood
* descriptions of simulated annealing:
*
* 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
* (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:
+ */
Code Review / vpp.git / blobdiff