simulated-annealing.hh

Go to the documentation of this file.

#ifndef __MINLCA_UTILS_SIMULATED_ANNEALING_HH
#define __MINLCA_UTILS_SIMULATED_ANNEALING_HH

#include <lemon/random.h>


namespace minlca
{
namespace utils
{

template<typename Node>
class SimulatedAnnealing
{
protected:
  typedef lemon::Random Random;
  Node *_current; 
  Node *_best; 
  int _steps; 
  int _max_steps; 
  int _stiter; 
  int _k; 
  double _lambda; 
  bool _delete_random; 
  Random *_r; 

  inline void runStep()
  {
    if (_current != _best and _current->energy() < 0.5 * _best->energy()) {
      delete _current;
      _current = _best;
    }

    Node *next = _current->randomNeighbour();
    double difEnergy = next->energy() - _current->energy();

#ifdef SA_VERBOSE
    std::string flags = "";
#endif

    if (_r->boolean(std::exp(difEnergy / temperature()))) {
      if (_current != _best) {
        delete _current;
      }

      _current = next;

#ifdef SA_VERBOSE
      flags = flags + " #";
#endif

      if (_current->energy() > _best->energy()) {
        delete _best;
        _best = _current;

#ifdef SA_VERBOSE
        flags = flags + " *";
#endif
      }

#ifdef SA_VERBOSE
      else {
        flags = flags + " ++";
      }

#endif
    }

#ifdef SA_VERBOSE
    std::cerr << "Step " << _steps << ' ' << _current->energy() << flags;
    std::cerr << std::endl;
#endif
  }

public:
  SimulatedAnnealing(
    int steps, 
    int stIter, 
    int k, 
    double lambda, 
    int seed = 0 
  )
    : _current(nullptr), _best(nullptr), _steps(0), _max_steps(steps),
      _stiter(stIter), _k(k), _lambda(lambda), _delete_random(true),
      _r(nullptr)
  {
    _r = new lemon::Random(seed);
  }

  SimulatedAnnealing(
    int maxSteps, 
    int stIter, 
    int k, 
    double lambda, 
    Random &r 
  )
    : _current(nullptr), _best(nullptr), _steps(0), _max_steps(maxSteps),
      _stiter(stIter), _k(k), _lambda(lambda), _delete_random(false), _r(&r)
  {
  }

  ~SimulatedAnnealing()
  {
    if (_current != _best and _current != nullptr) {
      delete _current;
    }

    if (_delete_random) {
      delete _r;
    }
  }

  void init(
    Node *start 
  )
  {
    _current = _best = start;
    _steps = 0;
  }

  virtual inline double temperature() const
  {
    return _k * std::exp(-_lambda * (_steps / _stiter) * _stiter);
  }

  Node *run()
  {
    while (_steps < _max_steps) {
      runStep();
      ++_steps;
    }

#ifdef SA_VERBOSE
    std::cerr << "Finished SA execution" << std::endl;
    std::cerr << std::string(10, '-') << std::endl;
#endif

    if (_current != _best) {
      delete _current;
      _current = nullptr;
    }

    return _best;
  }

  Node *best()
  {
    return _best;
  }
};
}
}

#endif