src/vppinfra/anneal.c

   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
  53 clib_anneal (clib_anneal_param_t * p)
  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);
  67   p->anneal_save_best_configuration (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
  77       p->anneal_restore_best_configuration (p->opaque);
  78       cost = best_cost;
  79
  80       for (j = 0; j < p->number_of_configurations_per_temperature; j++)
  81         {
  82           p->anneal_new_configuration (p->opaque);
  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;
 101                     p->anneal_save_best_configuration (p->opaque);
 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             }
 132           p->anneal_restore_previous_configuration (p->opaque);
 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",
 162                p->suggested_initial_temperature);
 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  */