COIN-OR::LEMON - Graph Library

Changeset 1142:450f794dca81 in lemon-0.x


Ignore:
Timestamp:
02/08/05 12:27:03 (15 years ago)
Author:
Akos Ladanyi
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1541
Message:

more docs

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/work/akos/simann.h

    r1096 r1142  
    11#ifndef LEMON_SIMANN_H
    22#define LEMON_SIMANN_H
     3
     4/// \ingroup experimental
     5/// \file
     6/// \brief Simulated annealing framework.
     7/// \author Akos Ladanyi
    38
    49#include <cstdlib>
     
    813namespace lemon {
    914
     15/// \addtogroup experimental
     16/// @{
     17
    1018  const double INFTY = 1e24;
    1119
     20  /*! \brief Simulated annealing base class. */
    1221  class SimAnnBase {
    1322  public:
    1423    class Controller;
    1524  private:
     25    /*! Pointer to the controller. */
    1626    Controller *controller;
    1727  protected:
     28    /*! \brief Cost of the current solution. */
    1829    double curr_cost;
     30    /*! \brief Cost of the best solution. */
    1931    double best_cost;
     32    /*! \brief Cost of the previous solution. */
    2033    double prev_cost;
     34    /*! \brief Cost of the solution preceding the previous one. */
    2135    double prev_prev_cost;
    2236
    23     virtual void mutate() = 0;
    24     virtual void revert() = 0;
    25     virtual void saveAsBest() = 0;
    26   public:
     37    /*! \brief Step to a neighbouring state. */
     38    virtual void mutate() {}
     39    /*! \brief Reverts the last mutate(). */
     40    virtual void revert() {}
     41    /*! \brief Saves the current solution as the best one. */
     42    virtual void saveAsBest() {}
     43  public:
     44    /*! \brief Constructor. */
    2745    SimAnnBase() {
    2846      best_cost = prev_cost = prev_prev_cost = INFTY;
    2947    }
     48    /*! \brief Sets the controller class to use. */
    3049    void setController(Controller &_controller) {
    3150      controller = &_controller;
    3251      controller->setBase(this);
    3352    }
     53    /*! \brief Returns the cost of the current solution. */
    3454    double getCurrCost() const { return curr_cost; }
     55    /*! \brief Returns the cost of the previous solution. */
    3556    double getPrevCost() const { return prev_cost; }
     57    /*! \brief Returns the cost of the best solution. */
    3658    double getBestCost() const { return best_cost; }
     59    /*! \brief Starts the annealing process. */
    3760    void run() {
    3861      controller->init();
     
    5679    class Controller {
    5780    public:
     81      /*! \brief Pointer to the simulated annealing base class. */
    5882      SimAnnBase *base;
     83      /*! \brief Initializes the controller. */
    5984      virtual void init() {}
    6085      /*! \brief This is called when a neighbouring state gets accepted. */
     
    6691      /*! \brief This is called when a neighbouring state gets rejected. */
    6792      virtual void rejectEvent() {}
     93      /*! \brief Sets the simulated annealing base class to use. */
    6894      virtual void setBase(SimAnnBase *_base) { base = _base; }
    69       /*! */
     95      /*! \brief Decides whether to continue the annealing process or not. */
    7096      virtual bool next() = 0;
    71       /*! */
     97      /*! \brief Decides whether to accept the current solution or not. */
    7298      virtual bool accept() = 0;
    7399    };
    74100  };
    75101
     102  /*! \brief Simulated annealing class. */
    76103  template <typename E>
    77104  class SimAnn : public SimAnnBase {
    78105  private:
     106    /*! \brief Pointer to the current entity. */
    79107    E *curr_ent;
     108    /*! \brief Pointer to the best entity. */
    80109    E *best_ent;
    81110  public:
     111    /*! \brief Constructor. */
    82112    SimAnn() : SimAnnBase() {}
     113    /*! \brief Sets the initial entity. */
    83114    void setEntity(E &ent) {
    84115      curr_ent = new E(ent);
     
    86117      curr_cost = curr_ent->getCost();
    87118    }
     119    /*! \brief Returns the best found entity. */
    88120    E getBestEntity() { return *best_ent; }
     121    /*! \brief Step to a neighbouring state. */
    89122    void mutate() {
    90123      prev_prev_cost = prev_cost;
     
    93126      curr_cost = curr_ent->getCost();
    94127    }
     128    /*! \brief Reverts the last mutate(). */
    95129    void revert() {
    96130      curr_ent->revert();
     
    98132      prev_cost = prev_prev_cost;
    99133    }
     134    /*! \brief Saves the current solution as the best one. */
    100135    void saveAsBest() {
    101136      delete(best_ent);
     
    105140  };
    106141
     142  /*! \brief Skeleton of an entity class. */
    107143  class EntitySkeleton {
    108144  public:
    109     /*! \return the cost of the entity */
     145    /*! \brief Returns the cost of the entity. */
    110146    double getCost() { return 0.0; }
    111147    /*! \brief Makes a minor change to the entity. */
    112148    void mutate() {}
    113149    /*! \brief Restores the entity to its previous state i.e. reverts the
    114      *  effects of the last mutate.
     150     *  effects of the last mutate().
    115151     */
    116152    void revert() {}
    117153  };
    118154
    119   /*! \brief A simple controller for the simulated annealing class.
    120    *  \todo Find a way to set the various parameters.
    121    */
     155  /*! \brief A simple controller for the simulated annealing class. */
    122156  class SimpleController : public SimAnnBase::Controller {
    123157  public:
    124     long iter, last_impr, max_iter, max_no_impr;
    125     double temp, ann_fact;
    126     /*! \param _max_iter maximum number of iterations
     158    /*! \brief Number of iterations. */
     159    long iter;
     160    /*! \brief Number of iterations which did not improve the solution since
     161     *  the last improvement. */
     162    long last_impr;
     163    /*! \brief Maximum number of iterations. */
     164    long max_iter;
     165    /*! \brief Maximum number of iterations which do not improve the
     166     *  solution. */
     167    long max_no_impr;
     168    /*! \brief Temperature. */
     169    double temp;
     170    /*! \brief Annealing factor. */
     171    double ann_fact;
     172    /*! \brief Constructor.
     173     *  \param _max_iter maximum number of iterations
    127174     *  \param _max_no_impr maximum number of consecutive iterations which do
    128175     *         not yield a better solution
     
    137184      iter++;
    138185    }
     186    /*! \brief This is called when the accepted neighbouring state's cost is
     187     *  less than the best found one's.
     188     */
    139189    void improveEvent() {
    140190      last_impr = iter;
    141191    }
     192    /*! \brief This is called when a neighbouring state gets rejected. */
    142193    void rejectEvent() {
    143194      iter++;
    144195    }
     196    /*! \brief Decides whether to continue the annealing process or not. Also
     197     *  decreases the temperature. */
    145198    bool next() {
    146199      temp *= ann_fact;
     
    148201      return !quit;
    149202    }
     203    /*! \brief Decides whether to accept the current solution or not. */
    150204    bool accept() {
    151205      double cost_diff = base->getPrevCost() - base->getCurrCost();
     
    162216  /*! \brief A controller with preset running time for the simulated annealing
    163217   *  class.
    164    *  \todo Find a better name.
    165218   */
    166219  class AdvancedController : public SimAnnBase::Controller {
     
    169222    /*! \param time the elapsed time in seconds */
    170223    virtual double threshold(double time) {
    171       // 1 / log(x)
    172       /*
    173       static double xm = 5.0 / end_time;
    174       static double ym = start_threshold / (1 / log(1.2) - 1 / log(5.0 + 1.2));
    175       return ym * (1 / log(xm * time + 1.2) - 1 / log(5.0 + 1.2));
    176       */
    177224      return (-1.0) * start_threshold / end_time * time + start_threshold;
    178225    }
    179226  public:
    180     double alpha, beta, gamma;
    181     double end_time, start_time;
     227    double alpha;
     228    double beta;
     229    double gamma;
     230    double end_time;
     231    double start_time;
    182232    double start_threshold;
    183233    double avg_cost;
    184     double temp, ann_fact;
     234    double temp;
     235    double ann_fact;
    185236    bool warmup;
    186     /*! \param _end_time running time in seconds
     237    /*! \brief Constructor.
     238     *  \param _end_time running time in seconds
    187239     *  \param _alpha parameter used to calculate the running average
    188240     *  \param _beta parameter used to decrease the annealing factor
     
    195247      avg_cost = base->getCurrCost();
    196248    }
     249    /*! \brief This is called when a neighbouring state gets accepted. */
    197250    void acceptEvent() {
    198251      avg_cost = alpha * base->getCurrCost() + (1.0 - alpha) * avg_cost;
     
    203256          // calculate starting threshold and starting temperature
    204257          start_threshold = 5.0 * fabs(base->getBestCost() - avg_cost);
    205           //temp = max_cost_diff / log(0.5);
    206258          temp = 10000.0;
    207259          warmup = false;
     
    210262      }
    211263    }
    212     void improveEvent() {
    213     }
    214     void rejectEvent() {
    215     }
     264    /*! \brief Decides whether to continue the annealing process or not. */
    216265    bool next() {
    217266      if (warmup) {
     
    227276          // increase the temperature
    228277          temp *= gamma;
    229           ann_fact = 0.99999999;
     278          ann_fact = 0.99999999; // !!!!!!!!!!!
    230279        }
    231280        temp *= ann_fact;
     
    233282      }
    234283    }
     284    /*! \brief Decides whether to accept the current solution or not. */
    235285    bool accept() {
    236286      if (warmup) {
     
    250300  };
    251301
     302/// @}
     303
    252304}
    253305
Note: See TracChangeset for help on using the changeset viewer.