COIN-OR::LEMON - Graph Library

Changeset 1918:09415ae11103 in lemon-0.x


Ignore:
Timestamp:
01/29/06 23:06:10 (14 years ago)
Author:
Akos Ladanyi
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2493
Message:

more doc

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/simann.h

    r1847 r1918  
    1212#include <cstdlib>
    1313#include <cmath>
     14#include <limits>
    1415#include <lemon/time_measure.h>
    1516
     
    1920/// @{
    2021
    21   /*! \brief A base class for controllers. */
     22  /// \brief A base class for controllers.
    2223  class ControllerBase {
     24  public:
    2325    friend class SimAnnBase;
    24   public:
    25     /*! \brief Pointer to the simulated annealing base class. */
     26    /// \brief Pointer to the simulated annealing base class.
    2627    SimAnnBase *simann;
    27     /*! \brief Initializes the controller. */
     28    /// \brief Initializes the controller.
    2829    virtual void init() {}
    29     /*! \brief This is called when a neighbouring state gets accepted. */
     30    /// \brief This is called by the simulated annealing class when a
     31    /// neighbouring state gets accepted.
    3032    virtual void acceptEvent() {}
    31     /*! \brief This is called when the accepted neighbouring state's cost is
    32      *  less than the best found one's.
    33      */
     33    /// \brief This is called by the simulated annealing class when the
     34    /// accepted neighbouring state's cost is less than the best found one's.
    3435    virtual void improveEvent() {}
    35     /*! \brief This is called when a neighbouring state gets rejected. */
     36    /// \brief This is called by the simulated annealing class when a
     37    /// neighbouring state gets rejected.
    3638    virtual void rejectEvent() {}
    37     /*! \brief Decides whether to continue the annealing process or not. */
     39    /// \brief Decides whether to continue the annealing process or not.
    3840    virtual bool next() = 0;
    39     /*! \brief Decides whether to accept the current solution or not. */
     41    /// \brief Decides whether to accept the current solution or not.
    4042    virtual bool accept() = 0;
    41   };
    42 
    43   /*! \brief Skeleton of an entity class. */
     43    /// \brief Destructor.
     44    virtual ~ControllerBase() {}
     45  };
     46
     47  /// \brief Skeleton of an entity class.
    4448  class EntityBase {
    4549  public:
    46     /*! \brief Makes a minor change to the entity.
    47      *  \return the new cost
    48      */
     50    /// \brief Makes a minor change to the entity.
     51    /// \return the new cost
    4952    virtual double mutate() = 0;
    50     /*! \brief Restores the entity to its previous state i.e. reverts the
    51      *  effects of the last mutate().
    52      */
     53    /// \brief Restores the entity to its previous state i.e. reverts the
     54    /// effects of the last mutate().
    5355    virtual void revert() = 0;
    54     /*! \brief Makes a copy of the entity. */
     56    /// \brief Makes a copy of the entity.
    5557    virtual EntityBase* clone() = 0;
    56     /*! \brief Makes a major change to the entity. */
     58    /// \brief Makes a major change to the entity.
    5759    virtual void randomize() = 0;
    58   };
    59 
    60   /*! \brief Simulated annealing base class. */
     60    /// \brief Destructor.
     61    virtual ~EntityBase() {}
     62  };
     63
     64  /// \brief Simulated annealing abstract base class.
     65  /// Can be used to derive a custom simulated annealing class if \ref SimAnn
     66  /// doesn't fit your needs.
    6167  class SimAnnBase {
    6268  private:
    63     /*! Pointer to the controller. */
     69    /// \brief Pointer to the controller.
    6470    ControllerBase *controller;
    65     /*! \brief Cost of the current solution. */
     71    /// \brief Cost of the current solution.
    6672    double curr_cost;
    67     /*! \brief Cost of the best solution. */
     73    /// \brief Cost of the best solution.
    6874    double best_cost;
    69     /*! \brief Cost of the previous solution. */
     75    /// \brief Cost of the previous solution.
    7076    double prev_cost;
    71     /*! \brief Cost of the solution preceding the previous one. */
     77    /// \brief Cost of the solution preceding the previous one.
    7278    double prev_prev_cost;
    73     /*! \brief Number of iterations. */
     79    /// \brief Number of iterations.
    7480    long iter;
    75     /*! \brief Number of iterations which did not improve the solution since
    76      *  the last improvement. */
     81    /// \brief Number of iterations which did not improve the solution since
     82    /// the last improvement.
    7783    long last_impr;
    7884  protected:
    79     /*! \brief Step to a neighbouring state. */
     85    /// \brief Step to a neighbouring state.
    8086    virtual double mutate() = 0;
    81     /*! \brief Reverts the last mutate(). */
     87    /// \brief Reverts the last mutate().
    8288    virtual void revert() = 0;
    83     /*! \brief Saves the current solution as the best one. */
     89    /// \brief Saves the current solution as the best one.
    8490    virtual void saveAsBest() = 0;
    85     /*! \brief Does initializations before each run. */
     91    /// \brief Does initializations before each run.
    8692    virtual void init() {
    8793      controller->init();
     
    9197    }
    9298  public:
    93     /*! \brief Sets the controller class to use. */
     99    /// \brief Sets the controller class to use.
    94100    void setController(ControllerBase &_controller) {
    95101      controller = &_controller;
    96102      controller->simann = this;
    97103    }
    98     /*! \brief Returns the cost of the current solution. */
     104    /// \brief Returns the cost of the current solution.
    99105    double getCurrCost() const { return curr_cost; }
    100     /*! \brief Returns the cost of the previous solution. */
     106    /// \brief Returns the cost of the previous solution.
    101107    double getPrevCost() const { return prev_cost; }
    102     /*! \brief Returns the cost of the best solution. */
     108    /// \brief Returns the cost of the best solution.
    103109    double getBestCost() const { return best_cost; }
    104     /*! \brief Returns the number of iterations. */
     110    /// \brief Returns the number of iterations done.
    105111    long getIter() const { return iter; }
    106     /*! \brief Returns the number of the last iteration when the solution was
    107      *  improved.
    108      */
     112    /// \brief Returns the ordinal number of the last iteration when the
     113    /// solution was improved.
    109114    long getLastImpr() const { return last_impr; }
    110     /*! \brief Performs one iteration. */
     115    /// \brief Performs one iteration.
    111116    bool step() {
    112117      iter++;
     
    131136      return controller->next();
    132137    }
    133     /*! \brief Performs a given number of iterations.
    134      *  \param n the number of iterations
    135      */
     138    /// \brief Performs a given number of iterations.
     139    /// \param n the number of iterations
    136140    bool step(int n) {
    137141      for(; n > 0 && step(); --n) ;
    138142      return !n;
    139143    }
    140     /*! \brief Starts the annealing process. */
     144    /// \brief Starts the annealing process.
    141145    void run() {
    142146      init();
    143147      do { } while (step());
    144148    }
    145   };
    146 
    147   /*! \brief Simulated annealing class. */
     149    /// \brief Destructor.
     150    virtual ~SimAnnBase() {}
     151  };
     152
     153  /// \brief Simulated annealing class.
    148154  class SimAnn : public SimAnnBase {
    149155  private:
    150     /*! \brief Pointer to the current entity. */
     156    /// \brief Pointer to the current entity.
    151157    EntityBase *curr_ent;
    152     /*! \brief Pointer to the best entity. */
     158    /// \brief Pointer to the best entity.
    153159    EntityBase *best_ent;
    154     /*! \brief Does initializations before each run. */
     160    /// \brief Does initializations before each run.
    155161    void init() {
    156162      SimAnnBase::init();
     
    160166    }
    161167  public:
    162     /*! \brief Constructor. */
     168    /// \brief Constructor.
    163169    SimAnn() : curr_ent(NULL), best_ent(NULL) {}
    164     /*! \brief Destructor. */
     170    /// \brief Destructor.
    165171    virtual ~SimAnn() {
    166172      if (best_ent) delete best_ent;
    167173    }
    168     /*! \brief Step to a neighbouring state. */
     174    /// \brief Step to a neighbouring state.
    169175    double mutate() {
    170176      return curr_ent->mutate();
    171177    }
    172     /*! \brief Reverts the last mutate(). */
     178    /// \brief Reverts the last mutate().
    173179    void revert() {
    174180      curr_ent->revert();
    175181    }
    176     /*! \brief Saves the current solution as the best one. */
     182    /// \brief Saves the current solution as the best one.
    177183    void saveAsBest() {
    178184      if (best_ent) delete best_ent;
    179185      best_ent = curr_ent->clone();
    180186    }
    181     /*! \brief Sets the current entity. */
     187    /// \brief Sets the current entity.
    182188    void setEntity(EntityBase &_ent) {
    183189      curr_ent = &_ent;
    184190    }
    185     /*! \brief Returns a copy of the best found entity. */
     191    /// \brief Returns a copy of the best found entity.
    186192    EntityBase* getBestEntity() { return best_ent->clone(); }
    187193  };
    188194
    189   /*! \brief A simple controller for the simulated annealing class. */
     195  /// \brief A simple controller for the simulated annealing class.
     196  /// This controller starts from a given initial temperature and evenly
     197  /// decreases it.
    190198  class SimpleController : public ControllerBase {
    191   public:
    192     /*! \brief Maximum number of iterations. */
     199  private:
     200    /// \brief Maximum number of iterations.
    193201    long max_iter;
    194     /*! \brief Maximum number of iterations which do not improve the
    195      *  solution. */
     202    /// \brief Maximum number of iterations which do not improve the
     203    /// solution.
    196204    long max_no_impr;
    197     /*! \brief Temperature. */
     205    /// \brief Temperature.
    198206    double temp;
    199     /*! \brief Annealing factor. */
     207    /// \brief Annealing factor.
    200208    double ann_fact;
    201     /*! \brief Constructor.
    202      * \param _max_iter maximum number of iterations
    203      * \param _max_no_impr maximum number of consecutive iterations which do
    204      *         not yield a better solution
    205      * \param _temp initial temperature
    206      * \param _ann_fact annealing factor
    207      */
     209    /// \brief Constructor.
     210    /// \param _max_iter maximum number of iterations
     211    /// \param _max_no_impr maximum number of consecutive iterations which do
     212    ///        not yield a better solution
     213    /// \param _temp initial temperature
     214    /// \param _ann_fact annealing factor
     215  public:
    208216    SimpleController(long _max_iter = 500000, long _max_no_impr = 20000,
    209217    double _temp = 1000.0, double _ann_fact = 0.9999) : max_iter(_max_iter),
     
    212220      srand48(time(0));
    213221    }
    214     /*! \brief This is called when a neighbouring state gets accepted. */
     222    /// \brief This is called when a neighbouring state gets accepted.
    215223    void acceptEvent() {}
    216     /*! \brief This is called when the accepted neighbouring state's cost is
    217      *  less than the best found one's.
    218      */
     224    /// \brief This is called when the accepted neighbouring state's cost is
     225    /// less than the best found one's.
    219226    void improveEvent() {}
    220     /*! \brief This is called when a neighbouring state gets rejected. */
     227    /// \brief This is called when a neighbouring state gets rejected.
    221228    void rejectEvent() {}
    222     /*! \brief Decides whether to continue the annealing process or not. Also
    223      *  decreases the temperature. */
     229    /// \brief Decides whether to continue the annealing process or not. Also
     230    /// decreases the temperature.
    224231    bool next() {
    225232      temp *= ann_fact;
     
    228235      return !quit;
    229236    }
    230     /*! \brief Decides whether to accept the current solution or not. */
     237    /// \brief Decides whether to accept the current solution or not.
    231238    bool accept() {
    232       double cost_diff = simann->getPrevCost() - simann->getCurrCost();
    233       return (drand48() <= exp(cost_diff / temp));
    234     }
    235   };
    236 
    237   /*! \brief A controller with preset running time for the simulated annealing
    238    *  class.
    239    *
    240    *  With this controller you can set the running time of the annealing
    241    *  process in advance. It works the following way: the controller measures
    242    *  a kind of divergence. The divergence is the difference of the average
    243    *  cost of the recently found solutions the cost of the best found one. In
    244    *  case this divergence is greater than a given threshold, then we decrease
    245    *  the annealing factor, that is we cool the system faster. In case the
    246    *  divergence is lower than the threshold, then we increase the temperature.
    247    *  The threshold is a function of the elapsed time which reaches zero at the
    248    *  desired end time.
    249    */
     239      double cost_diff = simann->getCurrCost() - simann->getPrevCost();
     240      return (drand48() <= exp(-(cost_diff / temp)));
     241    }
     242    /// \brief Destructor.
     243    virtual ~SimpleController() {}
     244  };
     245
     246  /// \brief A controller with preset running time for the simulated annealing
     247  /// class.
     248  /// With this controller you can set the running time of the annealing
     249  /// process in advance. It works the following way: the controller measures
     250  /// a kind of divergence. The divergence is the difference of the average
     251  /// cost of the recently found solutions the cost of the best found one. In
     252  /// case this divergence is greater than a given threshold, then we decrease
     253  /// the annealing factor, that is we cool the system faster. In case the
     254  /// divergence is lower than the threshold, then we increase the temperature.
     255  /// The threshold is a function of the elapsed time which reaches zero at the
     256  /// desired end time.
    250257  class AdvancedController : public ControllerBase {
    251258  private:
     259    /// \brief Timer class to measure the elapsed time.
    252260    Timer timer;
    253     /*! \param time the elapsed time in seconds */
     261    /// \brief Calculates the threshold value.
     262    /// \param time the elapsed time in seconds
    254263    virtual double threshold(double time) {
    255264      return (-1.0) * start_threshold / end_time * time + start_threshold;
    256265    }
    257   public:
     266    /// \brief Parameter used to calculate the running average.
    258267    double alpha;
     268    /// \brief Parameter used to decrease the annealing factor.
    259269    double beta;
     270    /// \brief Parameter used to increase the temperature.
    260271    double gamma;
    261     /*! \brief The time at the end of the algorithm. */
     272    /// \brief The time at the end of the algorithm.
    262273    double end_time;
    263     /*! \brief The time at the start of the algorithm. */
     274    /// \brief The time at the start of the algorithm.
    264275    double start_time;
    265     /*! \brief Starting threshold. */
     276    /// \brief Starting threshold.
    266277    double start_threshold;
    267     /*! \brief Average cost of recent solutions. */
     278    /// \brief Average cost of recent solutions.
    268279    double avg_cost;
    269     /*! \brief Temperature. */
     280    /// \brief Temperature.
    270281    double temp;
    271     /*! \brief Annealing factor. */
     282    /// \brief Annealing factor.
    272283    double ann_fact;
    273     /*! \brief Initial annealing factor. */
     284    /// \brief Initial annealing factor.
    274285    double init_ann_fact;
    275     bool warmup;
    276     /*! \brief Constructor.
    277      *  \param _end_time running time in seconds
    278      *  \param _alpha parameter used to calculate the running average
    279      *  \param _beta parameter used to decrease the annealing factor
    280      *  \param _gamma parameter used to increase the temperature
    281      *  \param _ann_fact initial annealing factor
    282      */
     286    /// \brief True when the annealing process has been started.
     287    bool start;
     288  public:
     289    /// \brief Constructor.
     290    /// \param _end_time running time in seconds
     291    /// \param _alpha parameter used to calculate the running average
     292    /// \param _beta parameter used to decrease the annealing factor
     293    /// \param _gamma parameter used to increase the temperature
     294    /// \param _ann_fact initial annealing factor
    283295    AdvancedController(double _end_time, double _alpha = 0.2,
    284296    double _beta = 0.9, double _gamma = 1.6, double _ann_fact = 0.9999) :
    285297    alpha(_alpha), beta(_beta), gamma(_gamma), end_time(_end_time),
    286     ann_fact(_ann_fact), init_ann_fact(_ann_fact), warmup(true)
     298    ann_fact(_ann_fact), init_ann_fact(_ann_fact), start(false)
    287299    {
    288300      srand48(time(0));
    289301    }
     302    /// \brief Does initializations before each run.
    290303    void init() {
    291304      avg_cost = simann->getCurrCost();
    292305    }
    293     /*! \brief This is called when a neighbouring state gets accepted. */
     306    /// \brief This is called when a neighbouring state gets accepted.
    294307    void acceptEvent() {
    295308      avg_cost = alpha * simann->getCurrCost() + (1.0 - alpha) * avg_cost;
    296       if (warmup) {
     309      if (!start) {
    297310        static int cnt = 0;
    298311        cnt++;
     
    301314          start_threshold = 5.0 * fabs(simann->getBestCost() - avg_cost);
    302315          temp = 10000.0;
    303           warmup = false;
     316          start = true;
    304317          timer.restart();
    305318        }
    306319      }
    307320    }
    308     /*! \brief Decides whether to continue the annealing process or not. */
     321    /// \brief Decides whether to continue the annealing process or not.
    309322    bool next() {
    310       if (warmup) {
     323      if (!start) {
    311324        return true;
    312325      }
    313326      else {
    314         double elapsed_time = timer.getRealTime();
     327        double elapsed_time = timer.realTime();
    315328        if (fabs(avg_cost - simann->getBestCost()) > threshold(elapsed_time)) {
    316329          // decrease the annealing factor
     
    327340      }
    328341    }
    329     /*! \brief Decides whether to accept the current solution or not. */
     342    /// \brief Decides whether to accept the current solution or not.
    330343    bool accept() {
    331       if (warmup) {
    332         // we accept eveything during the "warm up" phase
     344      if (!start) {
    333345        return true;
    334346      }
    335347      else {
    336         double cost_diff = simann->getPrevCost() - simann->getCurrCost();
    337         if (cost_diff < 0.0) {
    338           return (drand48() <= exp(cost_diff / temp));
    339         }
    340         else {
    341           return true;
    342         }
    343       }
    344     }
     348        double cost_diff = simann->getCurrCost() - simann->getPrevCost();
     349        return (drand48() <= exp(-(cost_diff / temp)));
     350      }
     351    }
     352    /// \brief Destructor.
     353    virtual ~AdvancedController() {}
    345354  };
    346355
Note: See TracChangeset for help on using the changeset viewer.