Algorithms - Combinatorial (Discrete) Simulated Annealing

The OSTRICH combinatorial simulated annealing optimization algorithm

Initial Publication:

Modified:

The following optional group will configure the combinatorial Simulated Annealing algorithm and will be processed if [ProgramType] is set to “DiscreteSimulatedAnnealing”.

BeginSimulatedAlg
NumInitialTrials       [n_init]
TemperatureScaleFactor [tscale]
OuterIterations        [nouter]
InnerIterations        [ninner]
ConvergenceVal         [conval]
EndSimulatedAlg
BeginSimulatedAlg
NumInitialTrials       100
TemperatureScaleFactor 0.9
OuterIterations        20
InnerIterations        10
ConvergenceVal         1.00E-3
EndSimulatedAlg

Figure 1: General Format (left) and Example (right) of the Discrete Simulated Annealing Group

Where BeginSimulatedAlg and EndSimulatedAlg are parsing tags that wrap a set of algorithm configuration variables. These variables are described below:

  • NumInitialTrials: This is the number of uphill moves that are attempted in the melting process. Larger values will result in more accurate estimates of the initial temperature, but at the expense of additional model runs. The default value is 100.
  • TemperatureScaleFactor: After each (outer) iteration, the temperature is reduced by multiplying by this value. This value should be less than 1.00. The default value is 0.90.
  • OuterIterations: This is the number of iterations in the overall algorithm, where one outer iteration corresponds to one temperature reduction. The default value is 20.
  • InnerIterations: This is the number of iterations in each temperature equilibration, where one inner iteration corresponds to a single transitional move. The default value is 10.
  • ConvergenceVal: This is the convergence value for the algorithm. If the relative difference between the current minimum and the median of the latest series of equilibration moves is less than or equal to this value, the algorithm will halt. The default value is 0.001.