source: lemon-0.x/lemon/simann.h @ 2529:93de38566e6c

/* -*- C++ -*-
 *
 * This file is a part of LEMON, a generic C++ optimization library
 *
 * Copyright (C) 2003-2007
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
 *
 * Permission to use, modify and distribute this software is granted
 * provided that this copyright notice appears in all copies. For
 * precise terms see the accompanying LICENSE file.
 *
 * This software is provided "AS IS" with no warranty of any kind,
 * express or implied, and with no claim as to its suitability for any
 * purpose.
 *
 */

#ifndef LEMON_SIMANN_H
#define LEMON_SIMANN_H

/// \ingroup experimental
/// \file
/// \brief Simulated annealing framework.
///
/// \todo A test and some demo should be added
/// \todo Doc should be improved
/// \author Akos Ladanyi

#include <cstdlib>
#include <cmath>
#include <limits>
#include <lemon/time_measure.h>
#include <lemon/random.h>

namespace lemon {

  class SimAnnBase;

  /// \brief A base class for controllers.
  class ControllerBase {
  public:
    friend class SimAnnBase;
    /// \brief Pointer to the simulated annealing base class.
    SimAnnBase *simann;
    /// \brief Initializes the controller.
    virtual void init() {}
    /// \brief This is called by the simulated annealing class when a
    /// neighbouring state gets accepted.
    virtual void acceptEvent() {}
    /// \brief This is called by the simulated annealing class when the
    /// accepted neighbouring state's cost is less than the best found one's.
    virtual void improveEvent() {}
    /// \brief This is called by the simulated annealing class when a
    /// neighbouring state gets rejected.
    virtual void rejectEvent() {}
    /// \brief Decides whether to continue the annealing process or not.
    virtual bool next() = 0;
    /// \brief Decides whether to accept the current solution or not.
    virtual bool accept() = 0;
    /// \brief Destructor.
    virtual ~ControllerBase() {}
  };

  /// \brief Skeleton of an entity class.
  class EntityBase {
  public:
    /// \brief Makes a minor change to the entity.
    /// \return the new cost
    virtual double mutate() = 0;
    /// \brief Restores the entity to its previous state i.e. reverts the
    /// effects of the last mutate().
    virtual void revert() = 0;
    /// \brief Makes a copy of the entity.
    virtual EntityBase* clone() = 0;
    /// \brief Makes a major change to the entity.
    virtual void randomize() = 0;
    /// \brief Destructor.
    virtual ~EntityBase() {}
  };

  /// \brief Simulated annealing abstract base class.
  ///
  /// Can be used to derive a custom simulated annealing class if \ref SimAnn
  /// doesn't fit your needs.
  class SimAnnBase {
  private:
    /// \brief Pointer to the controller.
    ControllerBase *controller;
    /// \brief Cost of the current solution.
    double curr_cost;
    /// \brief Cost of the best solution.
    double best_cost;
    /// \brief Cost of the previous solution.
    double prev_cost;
    /// \brief Cost of the solution preceding the previous one.
    double prev_prev_cost;
    /// \brief Number of iterations.
    long iter;
    /// \brief Number of iterations which did not improve the solution since
    /// the last improvement.
    long last_impr;
  protected:
    /// \brief Step to a neighbouring state.
    virtual double mutate() = 0;
    /// \brief Reverts the last mutate().
    virtual void revert() = 0;
    /// \brief Saves the current solution as the best one.
    virtual void saveAsBest() = 0;
    /// \brief Does initializations before each run.
    virtual void init() {
      controller->init();
      curr_cost = prev_cost = prev_prev_cost = best_cost =
        std::numeric_limits<double>::infinity();
      iter = last_impr = 0;
    }
  public:
    /// \brief Sets the controller class to use.
    void setController(ControllerBase &_controller) {
      controller = &_controller;
      controller->simann = this;
    }
    /// \brief Returns the cost of the current solution.
    double getCurrCost() const { return curr_cost; }
    /// \brief Returns the cost of the previous solution.
    double getPrevCost() const { return prev_cost; }
    /// \brief Returns the cost of the best solution.
    double getBestCost() const { return best_cost; }
    /// \brief Returns the number of iterations done.
    long getIter() const { return iter; }
    /// \brief Returns the ordinal number of the last iteration when the
    /// solution was improved.
    long getLastImpr() const { return last_impr; }
    /// \brief Performs one iteration.
    bool step() {
      iter++;
      prev_prev_cost = prev_cost;
      prev_cost = curr_cost;
      curr_cost = mutate();
      if (controller->accept()) {
        controller->acceptEvent();
        last_impr = iter;
        if (curr_cost < best_cost) {
          best_cost = curr_cost;
          saveAsBest();
          controller->improveEvent();
        }
      }
      else {
        revert();
        curr_cost = prev_cost;
        prev_cost = prev_prev_cost;
        controller->rejectEvent();
      }
      return controller->next();
    }
    /// \brief Performs a given number of iterations.
    /// \param n the number of iterations
    bool step(int n) {
      for(; n > 0 && step(); --n) ;
      return !n;
    }
    /// \brief Starts the annealing process.
    void run() {
      init();
      do { } while (step());
    }
    /// \brief Destructor.
    virtual ~SimAnnBase() {}
  };

  /// \ingroup metah
  ///
  /// \brief Simulated annealing class.
  class SimAnn : public SimAnnBase {
  private:
    /// \brief Pointer to the current entity.
    EntityBase *curr_ent;
    /// \brief Pointer to the best entity.
    EntityBase *best_ent;
    /// \brief Does initializations before each run.
    void init() {
      SimAnnBase::init();
      if (best_ent) delete best_ent;
      best_ent = NULL;
      curr_ent->randomize();
    }
  public:
    /// \brief Constructor.
    SimAnn() : curr_ent(NULL), best_ent(NULL) {}
    /// \brief Destructor.
    virtual ~SimAnn() {
      if (best_ent) delete best_ent;
    }
    /// \brief Step to a neighbouring state.
    double mutate() {
      return curr_ent->mutate();
    }
    /// \brief Reverts the last mutate().
    void revert() {
      curr_ent->revert();
    }
    /// \brief Saves the current solution as the best one.
    void saveAsBest() { 
      if (best_ent) delete best_ent;
      best_ent = curr_ent->clone();
    }
    /// \brief Sets the current entity.
    void setEntity(EntityBase &_ent) {
      curr_ent = &_ent;
    }
    /// \brief Returns a copy of the best found entity.
    EntityBase* getBestEntity() { return best_ent->clone(); }
  };

  /// \brief A simple controller for the simulated annealing class.
  ///
  /// This controller starts from a given initial temperature and evenly
  /// decreases it.
  class SimpleController : public ControllerBase {
  private:
    /// \brief Maximum number of iterations.
    long max_iter;
    /// \brief Maximum number of iterations which do not improve the
    /// solution.
    long max_no_impr;
    /// \brief Temperature.
    double temp;
    /// \brief Annealing factor.
    double ann_fact;
    /// \brief Constructor.
    /// \param _max_iter maximum number of iterations
    /// \param _max_no_impr maximum number of consecutive iterations which do
    ///        not yield a better solution
    /// \param _temp initial temperature
    /// \param _ann_fact annealing factor
  public:
    SimpleController(long _max_iter = 500000, long _max_no_impr = 20000,
    double _temp = 1000.0, double _ann_fact = 0.9999) : max_iter(_max_iter),
      max_no_impr(_max_no_impr), temp(_temp), ann_fact(_ann_fact)
    {
    }
    /// \brief This is called when a neighbouring state gets accepted.
    void acceptEvent() {}
    /// \brief This is called when the accepted neighbouring state's cost is
    /// less than the best found one's.
    void improveEvent() {}
    /// \brief This is called when a neighbouring state gets rejected.
    void rejectEvent() {}
    /// \brief Decides whether to continue the annealing process or not. Also
    /// decreases the temperature.
    bool next() {
      temp *= ann_fact;
      bool quit = (simann->getIter() > max_iter) ||
        (simann->getIter() - simann->getLastImpr() > max_no_impr);
      return !quit;
    }
    /// \brief Decides whether to accept the current solution or not.
    bool accept() {
      double cost_diff = simann->getCurrCost() - simann->getPrevCost();
      return (rnd() <= exp(-(cost_diff / temp)));
    }
    /// \brief Destructor.
    virtual ~SimpleController() {}
  };

  /// \brief A controller with preset running time for the simulated annealing
  /// class.
  ///
  /// With this controller you can set the running time of the annealing
  /// process in advance. It works the following way: the controller measures
  /// a kind of divergence. The divergence is the difference of the average
  /// cost of the recently found solutions the cost of the best found one. In
  /// case this divergence is greater than a given threshold, then we decrease
  /// the annealing factor, that is we cool the system faster. In case the
  /// divergence is lower than the threshold, then we increase the temperature.
  /// The threshold is a function of the elapsed time which reaches zero at the
  /// desired end time.
  class AdvancedController : public ControllerBase {
  private:
    /// \brief Timer class to measure the elapsed time.
    Timer timer;
    /// \brief Calculates the threshold value.
    /// \param time the elapsed time in seconds
    virtual double threshold(double time) {
      return (-1.0) * start_threshold / end_time * time + start_threshold;
    }
    /// \brief Parameter used to calculate the running average.
    double alpha;
    /// \brief Parameter used to decrease the annealing factor.
    double beta;
    /// \brief Parameter used to increase the temperature.
    double gamma;
    /// \brief The time at the end of the algorithm.
    double end_time;
    /// \brief The time at the start of the algorithm.
    double start_time;
    /// \brief Starting threshold.
    double start_threshold;
    /// \brief Average cost of recent solutions.
    double avg_cost;
    /// \brief Temperature.
    double temp;
    /// \brief Annealing factor.
    double ann_fact;
    /// \brief Initial annealing factor.
    double init_ann_fact;
    /// \brief True when the annealing process has been started.
    bool start;
  public:
    /// \brief Constructor.
    /// \param _end_time running time in seconds
    /// \param _alpha parameter used to calculate the running average
    /// \param _beta parameter used to decrease the annealing factor
    /// \param _gamma parameter used to increase the temperature
    /// \param _ann_fact initial annealing factor
    AdvancedController(double _end_time, double _alpha = 0.2,
    double _beta = 0.9, double _gamma = 1.6, double _ann_fact = 0.9999) :
    alpha(_alpha), beta(_beta), gamma(_gamma), end_time(_end_time),
    ann_fact(_ann_fact), init_ann_fact(_ann_fact), start(false)
    {
    }
    /// \brief Does initializations before each run.
    void init() {
      avg_cost = simann->getCurrCost();
    }
    /// \brief This is called when a neighbouring state gets accepted.
    void acceptEvent() {
      avg_cost = alpha * simann->getCurrCost() + (1.0 - alpha) * avg_cost;
      if (!start) {
        static int cnt = 0;
        cnt++;
        if (cnt >= 100) {
          // calculate starting threshold and starting temperature
          start_threshold = 5.0 * fabs(simann->getBestCost() - avg_cost);
          temp = 10000.0;
          start = true;
          timer.restart();
        }
      }
    }
    /// \brief Decides whether to continue the annealing process or not.
    bool next() {
      if (!start) {
        return true;
      }
      else {
        double elapsed_time = timer.realTime();
        if (fabs(avg_cost - simann->getBestCost()) > threshold(elapsed_time)) {
          // decrease the annealing factor
          ann_fact *= beta;
        }
        else {
          // increase the temperature
          temp *= gamma;
          // reset the annealing factor
          ann_fact = init_ann_fact;
        }
        temp *= ann_fact;
        return elapsed_time < end_time;
      }
    }
    /// \brief Decides whether to accept the current solution or not.
    bool accept() {
      if (!start) {
        return true;
      }
      else {
        double cost_diff = simann->getCurrCost() - simann->getPrevCost();
        return (rnd() <= exp(-(cost_diff / temp)));
      }
    }
    /// \brief Destructor.
    virtual ~AdvancedController() {}
  };

}

#endif