Heuristic/simulated_anneal.cpp

This file defines the working of the Simulated Annealing heuristic. We do not intend to describe the details here, but simply specify the requirements. First, SimulatedAnneal must be derived from BasicSearch, and consequently define three virtual functions: search() overhead_time(), search_specific_display(). The last one is meant to output information specific to the heuristic at each report, which in this case, is the current temperature.

The time-sensitive aspect of this particular version of the heuristic is shown in the update_temperature() method, when the annealing rate is changed according to how much time is left.

template <class T>
class SimulatedAnneal : public BasicSearch<T> {
public:
  
  SimulatedAnneal(double running_time, double r_interval, 
                  double cp_interval);
  
  //---virtual definition in BasicSearch<T>
  void search();

  void search_specific_display(ostream *out);

  double overhead_time();
};

template<class T>
void SimulatedAnneal<T>::search_specific_display(ostream *out)
{
  *out << "(temperature, "<< temperature << ")\n";
}
	
template<class T>
double SimulatedAnneal<T>::overhead_time()
{
  return MinLength * Global<T>::get_neighbor_creation_time() +
    Global<T>::get_solution_creation_time();
}

template<class T>
void SimulatedAnneal<T>::update_temperature()
{
  current_time = get_remaining_time();
  dtime =  prev_time - current_time;
  prev_time = current_time;

  if(current_time > 0 && dtime > 0){
    expected_trials = current_time/dtime;
    dtemp = pow(low_temperature/temperature, 1.0/expected_trials);
    if(dtemp > 0.9999999) dtemp = 0.9999999;
    if(dtemp < 0.0001) dtemp = 0.0001;
  }

  temperature *= dtemp;

  static int count = 0;
  if(temperature <= low_temperature){
    count++;
    temperature = low_temperature;
  }

  if(count > 2) temperature_saturated = true;
}