aboutsummaryrefslogtreecommitdiffstats
path: root/tests/nsh_sfc
diff options
context:
space:
mode:
Diffstat (limited to 'tests/nsh_sfc')
0 files changed, 0 insertions, 0 deletions
hlight .mo { color: #ae81ff } /* Literal.Number.Oct */ .highlight .sa { color: #e6db74 } /* Literal.String.Affix */ .highlight .sb { color: #e6db74 } /* Literal.String.Backtick */ .highlight .sc { color: #e6db74 } /* Literal.String.Char */ .highlight .dl { color: #e6db74 } /* Literal.String.Delimiter */ .highlight .sd { color: #e6db74 } /* Literal.String.Doc */ .highlight .s2 { color: #e6db74 } /* Literal.String.Double */ .highlight .se { color: #ae81ff } /* Literal.String.Escape */ .highlight .sh { color: #e6db74 } /* Literal.String.Heredoc */ .highlight .si { color: #e6db74 } /* Literal.String.Interpol */ .highlight .sx { color: #e6db74 } /* Literal.String.Other */ .highlight .sr { color: #e6db74 } /* Literal.String.Regex */ .highlight .s1 { color: #e6db74 } /* Literal.String.Single */ .highlight .ss { color: #e6db74 } /* Literal.String.Symbol */ .highlight .bp { color: #f8f8f2 } /* Name.Builtin.Pseudo */ .highlight .fm { color: #a6e22e } /* Name.Function.Magic */ .highlight .vc { color: #f8f8f2 } /* Name.Variable.Class */ .highlight .vg { color: #f8f8f2 } /* Name.Variable.Global */ .highlight .vi { color: #f8f8f2 } /* Name.Variable.Instance */ .highlight .vm { color: #f8f8f2 } /* Name.Variable.Magic */ .highlight .il { color: #ae81ff } /* Literal.Number.Integer.Long */ } @media (prefers-color-scheme: light) { .highlight .hll { background-color: #ffffcc } .highlight .c { color: #888888 } /* Comment */ .highlight .err { color: #a61717; background-color: #e3d2d2 } /* Error */ .highlight .k { color: #008800; font-weight: bold } /* Keyword */ .highlight .ch { color: #888888 } /* Comment.Hashbang */ .highlight .cm { color: #888888 } /* Comment.Multiline */ .highlight .cp { color: #cc0000; font-weight: bold } /* Comment.Preproc */ .highlight .cpf { color: #888888 } /* Comment.PreprocFile */ .highlight .c1 { color: #888888 } /* Comment.Single */ .highlight .cs { color: #cc0000; font-weight: bold; background-color: #fff0f0 } /* Comment.Special */ .highlight .gd { color: #000000; background-color: #ffdddd } /* Generic.Deleted */ .highlight .ge { font-style: italic } /* Generic.Emph */ .highlight .gr { color: #aa0000 } /* Generic.Error */ .highlight .gh { color: #333333 } /* Generic.Heading */ .highlight .gi { color: #000000; background-color: #ddffdd } /* Generic.Inserted */ .highlight .go { color: #888888 } /* Generic.Output */ .highlight .gp { color: #555555 } /* Generic.Prompt */ .highlight .gs { font-weight: bold } /* Generic.Strong */ .highlight .gu { color: #666666 } /* Generic.Subheading */ .highlight .gt { color: #aa0000 } /* Generic.Traceback */ .highlight .kc { color: #008800; font-weight: bold } /* Keyword.Constant */ .highlight .kd { color: #008800; font-weight: bold } /* Keyword.Declaration */ .highlight .kn { color: #008800; font-weight: bold } /* Keyword.Namespace */ .highlight .kp { color: #008800 } /* Keyword.Pseudo */ .highlight .kr { color: #008800; font-weight: bold } /* Keyword.Reserved */ .highlight .kt { color: #888888; font-weight: bold } /* Keyword.Type */ .highlight .m { color: #0000DD; font-weight: bold } /* Literal.Number */ .highlight .s { color: #dd2200; background-color: #fff0f0 } /* Literal.String */ .highlight .na { color: #336699 } /* Name.Attribute */ .highlight .nb { color: #003388 } /* Name.Builtin */ .highlight .nc { color: #bb0066; font-weight: bold } /* Name.Class */ .highlight .no { color: #003366; font-weight: bold } /* Name.Constant */ .highlight .nd { color: #555555 } /* Name.Decorator */ .highlight .ne { color: #bb0066; font-weight: bold } /* Name.Exception */ .highlight .nf { color: #0066bb; font-weight: bold } /* Name.Function */ .highlight .nl { color: #336699; font-style: italic } /* Name.Label */ .highlight .nn { color: #bb0066; font-weight: bold } /* Name.Namespace */ .highlight .py { color: #336699; font-weight: bold } /* Name.Property */ .highlight .nt { color: #bb0066; font-weight: bold } /* Name.Tag */ .highlight .nv { color: #336699 } /* Name.Variable */ .highlight .ow { color: #008800 } /* Operator.Word */ .highlight .w { color: #bbbbbb } /* Text.Whitespace */ .highlight .mb { color: #0000DD; font-weight: bold } /* Literal.Number.Bin */ .highlight .mf { color: #0000DD; font-weight: bold } /* Literal.Number.Float */ .highlight .mh { color: #0000DD; font-weight: bold } /* Literal.Number.Hex */ .highlight .mi { color: #0000DD; font-weight: bold } /* Literal.Number.Integer */ .highlight .mo { color: #0000DD; font-weight: bold } /* Literal.Number.Oct */ .highlight .sa { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Affix */ .highlight .sb { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Backtick */ .highlight .sc { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Char */ .highlight .dl { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Delimiter */ .highlight .sd { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Doc */ .highlight .s2 { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Double */ .highlight .se { color: #0044dd; background-color: #fff0f0 } /* Literal.String.Escape */ .highlight .sh { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Heredoc */ .highlight .si { color: #3333bb; background-color: #fff0f0 } /* Literal.String.Interpol */ .highlight .sx { color: #22bb22; background-color: #f0fff0 } /* Literal.String.Other */ .highlight .sr { color: #008800; background-color: #fff0ff } /* Literal.String.Regex */ .highlight .s1 { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Single */ .highlight .ss { color: #aa6600; background-color: #fff0f0 } /* Literal.String.Symbol */ .highlight .bp { color: #003388 } /* Name.Builtin.Pseudo */ .highlight .fm { color: #0066bb; font-weight: bold } /* Name.Function.Magic */ .highlight .vc { color: #336699 } /* Name.Variable.Class */ .highlight .vg { color: #dd7700 } /* Name.Variable.Global */ .highlight .vi { color: #3333bb } /* Name.Variable.Instance */ .highlight .vm { color: #336699 } /* Name.Variable.Magic */ .highlight .il { color: #0000DD; font-weight: bold } /* Literal.Number.Integer.Long */ } 
/*
  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:
 */