alpar@1956: /* -*- C++ -*-
alpar@1956: *
alpar@1956: * This file is a part of LEMON, a generic C++ optimization library
alpar@1956: *
alpar@1956: * Copyright (C) 2003-2006
alpar@1956: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@1956: * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@1956: *
alpar@1956: * Permission to use, modify and distribute this software is granted
alpar@1956: * provided that this copyright notice appears in all copies. For
alpar@1956: * precise terms see the accompanying LICENSE file.
alpar@1956: *
alpar@1956: * This software is provided "AS IS" with no warranty of any kind,
alpar@1956: * express or implied, and with no claim as to its suitability for any
alpar@1956: * purpose.
alpar@1956: *
alpar@1956: */
alpar@1956:
alpar@1633: #ifndef LEMON_SIMANN_H
alpar@1633: #define LEMON_SIMANN_H
alpar@1633:
alpar@1633: /// \ingroup experimental
alpar@1633: /// \file
alpar@1633: /// \brief Simulated annealing framework.
alpar@1847: ///
alpar@1847: /// \todo A test and some demo should be added
alpar@1847: /// \todo Doc should be improved
alpar@1633: /// \author Akos Ladanyi
alpar@1633:
alpar@1633: #include <cstdlib>
alpar@1633: #include <cmath>
ladanyi@1918: #include <limits>
alpar@1633: #include <lemon/time_measure.h>
deba@2229: #include <lemon/random.h>
deba@2035:
alpar@1633: namespace lemon {
alpar@1633:
alpar@1633: /// \addtogroup experimental
alpar@1633: /// @{
alpar@1633:
deba@1932: class SimAnnBase;
deba@1932:
ladanyi@1918: /// \brief A base class for controllers.
alpar@1633: class ControllerBase {
ladanyi@1918: public:
alpar@1633: friend class SimAnnBase;
ladanyi@1918: /// \brief Pointer to the simulated annealing base class.
alpar@1633: SimAnnBase *simann;
ladanyi@1918: /// \brief Initializes the controller.
alpar@1633: virtual void init() {}
ladanyi@1918: /// \brief This is called by the simulated annealing class when a
ladanyi@1918: /// neighbouring state gets accepted.
alpar@1633: virtual void acceptEvent() {}
ladanyi@1918: /// \brief This is called by the simulated annealing class when the
ladanyi@1918: /// accepted neighbouring state's cost is less than the best found one's.
alpar@1633: virtual void improveEvent() {}
ladanyi@1918: /// \brief This is called by the simulated annealing class when a
ladanyi@1918: /// neighbouring state gets rejected.
alpar@1633: virtual void rejectEvent() {}
ladanyi@1918: /// \brief Decides whether to continue the annealing process or not.
alpar@1633: virtual bool next() = 0;
ladanyi@1918: /// \brief Decides whether to accept the current solution or not.
alpar@1633: virtual bool accept() = 0;
ladanyi@1918: /// \brief Destructor.
ladanyi@1918: virtual ~ControllerBase() {}
alpar@1633: };
alpar@1633:
ladanyi@1918: /// \brief Skeleton of an entity class.
alpar@1633: class EntityBase {
alpar@1633: public:
ladanyi@1918: /// \brief Makes a minor change to the entity.
ladanyi@1918: /// \return the new cost
alpar@1633: virtual double mutate() = 0;
ladanyi@1918: /// \brief Restores the entity to its previous state i.e. reverts the
ladanyi@1918: /// effects of the last mutate().
alpar@1633: virtual void revert() = 0;
ladanyi@1918: /// \brief Makes a copy of the entity.
alpar@1633: virtual EntityBase* clone() = 0;
ladanyi@1918: /// \brief Makes a major change to the entity.
alpar@1633: virtual void randomize() = 0;
ladanyi@1918: /// \brief Destructor.
ladanyi@1918: virtual ~EntityBase() {}
alpar@1633: };
alpar@1633:
ladanyi@1918: /// \brief Simulated annealing abstract base class.
ladanyi@1918: /// Can be used to derive a custom simulated annealing class if \ref SimAnn
ladanyi@1918: /// doesn't fit your needs.
alpar@1633: class SimAnnBase {
alpar@1633: private:
ladanyi@1918: /// \brief Pointer to the controller.
alpar@1633: ControllerBase *controller;
ladanyi@1918: /// \brief Cost of the current solution.
alpar@1633: double curr_cost;
ladanyi@1918: /// \brief Cost of the best solution.
alpar@1633: double best_cost;
ladanyi@1918: /// \brief Cost of the previous solution.
alpar@1633: double prev_cost;
ladanyi@1918: /// \brief Cost of the solution preceding the previous one.
alpar@1633: double prev_prev_cost;
ladanyi@1918: /// \brief Number of iterations.
alpar@1633: long iter;
ladanyi@1918: /// \brief Number of iterations which did not improve the solution since
ladanyi@1918: /// the last improvement.
alpar@1633: long last_impr;
alpar@1633: protected:
ladanyi@1918: /// \brief Step to a neighbouring state.
alpar@1633: virtual double mutate() = 0;
ladanyi@1918: /// \brief Reverts the last mutate().
alpar@1633: virtual void revert() = 0;
ladanyi@1918: /// \brief Saves the current solution as the best one.
alpar@1633: virtual void saveAsBest() = 0;
ladanyi@1918: /// \brief Does initializations before each run.
alpar@1633: virtual void init() {
alpar@1633: controller->init();
alpar@1633: curr_cost = prev_cost = prev_prev_cost = best_cost =
alpar@1633: std::numeric_limits<double>::infinity();
alpar@1633: iter = last_impr = 0;
alpar@1633: }
alpar@1633: public:
ladanyi@1918: /// \brief Sets the controller class to use.
alpar@1633: void setController(ControllerBase &_controller) {
alpar@1633: controller = &_controller;
alpar@1633: controller->simann = this;
alpar@1633: }
ladanyi@1918: /// \brief Returns the cost of the current solution.
alpar@1633: double getCurrCost() const { return curr_cost; }
ladanyi@1918: /// \brief Returns the cost of the previous solution.
alpar@1633: double getPrevCost() const { return prev_cost; }
ladanyi@1918: /// \brief Returns the cost of the best solution.
alpar@1633: double getBestCost() const { return best_cost; }
ladanyi@1918: /// \brief Returns the number of iterations done.
alpar@1633: long getIter() const { return iter; }
ladanyi@1918: /// \brief Returns the ordinal number of the last iteration when the
ladanyi@1918: /// solution was improved.
alpar@1633: long getLastImpr() const { return last_impr; }
ladanyi@1918: /// \brief Performs one iteration.
alpar@1633: bool step() {
alpar@1633: iter++;
alpar@1633: prev_prev_cost = prev_cost;
alpar@1633: prev_cost = curr_cost;
alpar@1633: curr_cost = mutate();
alpar@1633: if (controller->accept()) {
alpar@1633: controller->acceptEvent();
alpar@1633: last_impr = iter;
alpar@1633: if (curr_cost < best_cost) {
alpar@1633: best_cost = curr_cost;
alpar@1633: saveAsBest();
alpar@1633: controller->improveEvent();
alpar@1633: }
alpar@1633: }
alpar@1633: else {
alpar@1633: revert();
alpar@1633: curr_cost = prev_cost;
alpar@1633: prev_cost = prev_prev_cost;
alpar@1633: controller->rejectEvent();
alpar@1633: }
alpar@1633: return controller->next();
alpar@1633: }
ladanyi@1918: /// \brief Performs a given number of iterations.
ladanyi@1918: /// \param n the number of iterations
alpar@1633: bool step(int n) {
alpar@1633: for(; n > 0 && step(); --n) ;
alpar@1633: return !n;
alpar@1633: }
ladanyi@1918: /// \brief Starts the annealing process.
alpar@1633: void run() {
alpar@1633: init();
alpar@1633: do { } while (step());
alpar@1633: }
ladanyi@1918: /// \brief Destructor.
ladanyi@1918: virtual ~SimAnnBase() {}
alpar@1633: };
alpar@1633:
ladanyi@1918: /// \brief Simulated annealing class.
alpar@1633: class SimAnn : public SimAnnBase {
alpar@1633: private:
ladanyi@1918: /// \brief Pointer to the current entity.
alpar@1633: EntityBase *curr_ent;
ladanyi@1918: /// \brief Pointer to the best entity.
alpar@1633: EntityBase *best_ent;
ladanyi@1918: /// \brief Does initializations before each run.
alpar@1633: void init() {
alpar@1633: SimAnnBase::init();
alpar@1633: if (best_ent) delete best_ent;
alpar@1633: best_ent = NULL;
alpar@1633: curr_ent->randomize();
alpar@1633: }
alpar@1633: public:
ladanyi@1918: /// \brief Constructor.
alpar@1633: SimAnn() : curr_ent(NULL), best_ent(NULL) {}
ladanyi@1918: /// \brief Destructor.
alpar@1633: virtual ~SimAnn() {
alpar@1633: if (best_ent) delete best_ent;
alpar@1633: }
ladanyi@1918: /// \brief Step to a neighbouring state.
alpar@1633: double mutate() {
alpar@1633: return curr_ent->mutate();
alpar@1633: }
ladanyi@1918: /// \brief Reverts the last mutate().
alpar@1633: void revert() {
alpar@1633: curr_ent->revert();
alpar@1633: }
ladanyi@1918: /// \brief Saves the current solution as the best one.
alpar@1633: void saveAsBest() {
alpar@1633: if (best_ent) delete best_ent;
alpar@1633: best_ent = curr_ent->clone();
alpar@1633: }
ladanyi@1918: /// \brief Sets the current entity.
alpar@1633: void setEntity(EntityBase &_ent) {
alpar@1633: curr_ent = &_ent;
alpar@1633: }
ladanyi@1918: /// \brief Returns a copy of the best found entity.
alpar@1633: EntityBase* getBestEntity() { return best_ent->clone(); }
alpar@1633: };
alpar@1633:
ladanyi@1918: /// \brief A simple controller for the simulated annealing class.
ladanyi@1918: /// This controller starts from a given initial temperature and evenly
ladanyi@1918: /// decreases it.
alpar@1633: class SimpleController : public ControllerBase {
ladanyi@1918: private:
ladanyi@1918: /// \brief Maximum number of iterations.
ladanyi@1918: long max_iter;
ladanyi@1918: /// \brief Maximum number of iterations which do not improve the
ladanyi@1918: /// solution.
ladanyi@1918: long max_no_impr;
ladanyi@1918: /// \brief Temperature.
ladanyi@1918: double temp;
ladanyi@1918: /// \brief Annealing factor.
ladanyi@1918: double ann_fact;
ladanyi@1918: /// \brief Constructor.
ladanyi@1918: /// \param _max_iter maximum number of iterations
ladanyi@1918: /// \param _max_no_impr maximum number of consecutive iterations which do
ladanyi@1918: /// not yield a better solution
ladanyi@1918: /// \param _temp initial temperature
ladanyi@1918: /// \param _ann_fact annealing factor
alpar@1633: public:
alpar@1633: SimpleController(long _max_iter = 500000, long _max_no_impr = 20000,
alpar@1633: double _temp = 1000.0, double _ann_fact = 0.9999) : max_iter(_max_iter),
alpar@1633: max_no_impr(_max_no_impr), temp(_temp), ann_fact(_ann_fact)
alpar@1633: {
alpar@1633: }
ladanyi@1918: /// \brief This is called when a neighbouring state gets accepted.
alpar@1633: void acceptEvent() {}
ladanyi@1918: /// \brief This is called when the accepted neighbouring state's cost is
ladanyi@1918: /// less than the best found one's.
alpar@1633: void improveEvent() {}
ladanyi@1918: /// \brief This is called when a neighbouring state gets rejected.
alpar@1633: void rejectEvent() {}
ladanyi@1918: /// \brief Decides whether to continue the annealing process or not. Also
ladanyi@1918: /// decreases the temperature.
alpar@1633: bool next() {
alpar@1633: temp *= ann_fact;
alpar@1633: bool quit = (simann->getIter() > max_iter) ||
alpar@1633: (simann->getIter() - simann->getLastImpr() > max_no_impr);
alpar@1633: return !quit;
alpar@1633: }
ladanyi@1918: /// \brief Decides whether to accept the current solution or not.
alpar@1633: bool accept() {
ladanyi@1918: double cost_diff = simann->getCurrCost() - simann->getPrevCost();
deba@2242: return (rnd() <= exp(-(cost_diff / temp)));
alpar@1633: }
ladanyi@1918: /// \brief Destructor.
ladanyi@1918: virtual ~SimpleController() {}
alpar@1633: };
alpar@1633:
ladanyi@1918: /// \brief A controller with preset running time for the simulated annealing
ladanyi@1918: /// class.
ladanyi@1918: /// With this controller you can set the running time of the annealing
ladanyi@1918: /// process in advance. It works the following way: the controller measures
ladanyi@1918: /// a kind of divergence. The divergence is the difference of the average
ladanyi@1918: /// cost of the recently found solutions the cost of the best found one. In
ladanyi@1918: /// case this divergence is greater than a given threshold, then we decrease
ladanyi@1918: /// the annealing factor, that is we cool the system faster. In case the
ladanyi@1918: /// divergence is lower than the threshold, then we increase the temperature.
ladanyi@1918: /// The threshold is a function of the elapsed time which reaches zero at the
ladanyi@1918: /// desired end time.
alpar@1633: class AdvancedController : public ControllerBase {
alpar@1633: private:
ladanyi@1918: /// \brief Timer class to measure the elapsed time.
alpar@1633: Timer timer;
ladanyi@1918: /// \brief Calculates the threshold value.
ladanyi@1918: /// \param time the elapsed time in seconds
alpar@1633: virtual double threshold(double time) {
alpar@1633: return (-1.0) * start_threshold / end_time * time + start_threshold;
alpar@1633: }
ladanyi@1918: /// \brief Parameter used to calculate the running average.
ladanyi@1918: double alpha;
ladanyi@1918: /// \brief Parameter used to decrease the annealing factor.
ladanyi@1918: double beta;
ladanyi@1918: /// \brief Parameter used to increase the temperature.
ladanyi@1918: double gamma;
ladanyi@1918: /// \brief The time at the end of the algorithm.
ladanyi@1918: double end_time;
ladanyi@1918: /// \brief The time at the start of the algorithm.
ladanyi@1918: double start_time;
ladanyi@1918: /// \brief Starting threshold.
ladanyi@1918: double start_threshold;
ladanyi@1918: /// \brief Average cost of recent solutions.
ladanyi@1918: double avg_cost;
ladanyi@1918: /// \brief Temperature.
ladanyi@1918: double temp;
ladanyi@1918: /// \brief Annealing factor.
ladanyi@1918: double ann_fact;
ladanyi@1918: /// \brief Initial annealing factor.
ladanyi@1918: double init_ann_fact;
ladanyi@1918: /// \brief True when the annealing process has been started.
ladanyi@1918: bool start;
alpar@1633: public:
ladanyi@1918: /// \brief Constructor.
ladanyi@1918: /// \param _end_time running time in seconds
ladanyi@1918: /// \param _alpha parameter used to calculate the running average
ladanyi@1918: /// \param _beta parameter used to decrease the annealing factor
ladanyi@1918: /// \param _gamma parameter used to increase the temperature
ladanyi@1918: /// \param _ann_fact initial annealing factor
alpar@1633: AdvancedController(double _end_time, double _alpha = 0.2,
alpar@1633: double _beta = 0.9, double _gamma = 1.6, double _ann_fact = 0.9999) :
alpar@1633: alpha(_alpha), beta(_beta), gamma(_gamma), end_time(_end_time),
ladanyi@1918: ann_fact(_ann_fact), init_ann_fact(_ann_fact), start(false)
alpar@1633: {
alpar@1633: }
ladanyi@1918: /// \brief Does initializations before each run.
alpar@1633: void init() {
alpar@1633: avg_cost = simann->getCurrCost();
alpar@1633: }
ladanyi@1918: /// \brief This is called when a neighbouring state gets accepted.
alpar@1633: void acceptEvent() {
alpar@1633: avg_cost = alpha * simann->getCurrCost() + (1.0 - alpha) * avg_cost;
ladanyi@1918: if (!start) {
alpar@1633: static int cnt = 0;
alpar@1633: cnt++;
alpar@1633: if (cnt >= 100) {
alpar@1633: // calculate starting threshold and starting temperature
alpar@1633: start_threshold = 5.0 * fabs(simann->getBestCost() - avg_cost);
alpar@1633: temp = 10000.0;
ladanyi@1918: start = true;
alpar@1847: timer.restart();
alpar@1633: }
alpar@1633: }
alpar@1633: }
ladanyi@1918: /// \brief Decides whether to continue the annealing process or not.
alpar@1633: bool next() {
ladanyi@1918: if (!start) {
alpar@1633: return true;
alpar@1633: }
alpar@1633: else {
ladanyi@1918: double elapsed_time = timer.realTime();
alpar@1633: if (fabs(avg_cost - simann->getBestCost()) > threshold(elapsed_time)) {
alpar@1633: // decrease the annealing factor
alpar@1633: ann_fact *= beta;
alpar@1633: }
alpar@1633: else {
alpar@1633: // increase the temperature
alpar@1633: temp *= gamma;
alpar@1633: // reset the annealing factor
alpar@1633: ann_fact = init_ann_fact;
alpar@1633: }
alpar@1633: temp *= ann_fact;
alpar@1633: return elapsed_time < end_time;
alpar@1633: }
alpar@1633: }
ladanyi@1918: /// \brief Decides whether to accept the current solution or not.
alpar@1633: bool accept() {
ladanyi@1918: if (!start) {
alpar@1633: return true;
alpar@1633: }
alpar@1633: else {
ladanyi@1918: double cost_diff = simann->getCurrCost() - simann->getPrevCost();
deba@2242: return (rnd() <= exp(-(cost_diff / temp)));
alpar@1633: }
alpar@1633: }
ladanyi@1918: /// \brief Destructor.
ladanyi@1918: virtual ~AdvancedController() {}
alpar@1633: };
alpar@1633:
alpar@1633: /// @}
alpar@1633:
alpar@1633: }
alpar@1633:
alpar@1633: #endif