# HG changeset patch
# User ladanyi
# Date 1138572370 0
# Node ID 09415ae11103d45885cb305db0068986247facf1
# Parent 87d3518d73d8f0c6b7e3d8bdb492bdbe3a6d4be4
more doc
diff -r 87d3518d73d8 -r 09415ae11103 lemon/simann.h
--- a/lemon/simann.h Sun Jan 29 22:04:48 2006 +0000
+++ b/lemon/simann.h Sun Jan 29 22:06:10 2006 +0000
@@ -11,6 +11,7 @@
#include <cstdlib>
#include <cmath>
+#include <limits>
#include <lemon/time_measure.h>
namespace lemon {
@@ -18,71 +19,76 @@
/// \addtogroup experimental
/// @{
- /*! \brief A base class for controllers. */
+ /// \brief A base class for controllers.
class ControllerBase {
+ public:
friend class SimAnnBase;
- public:
- /*! \brief Pointer to the simulated annealing base class. */
+ /// \brief Pointer to the simulated annealing base class.
SimAnnBase *simann;
- /*! \brief Initializes the controller. */
+ /// \brief Initializes the controller.
virtual void init() {}
- /*! \brief This is called when a neighbouring state gets accepted. */
+ /// \brief This is called by the simulated annealing class when a
+ /// neighbouring state gets accepted.
virtual void acceptEvent() {}
- /*! \brief This is called when the accepted neighbouring state's cost is
- * less than the best found one's.
- */
+ /// \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 when a neighbouring state gets rejected. */
+ /// \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. */
+ /// \brief Decides whether to continue the annealing process or not.
virtual bool next() = 0;
- /*! \brief Decides whether to accept the current solution or not. */
+ /// \brief Decides whether to accept the current solution or not.
virtual bool accept() = 0;
+ /// \brief Destructor.
+ virtual ~ControllerBase() {}
};
- /*! \brief Skeleton of an entity class. */
+ /// \brief Skeleton of an entity class.
class EntityBase {
public:
- /*! \brief Makes a minor change to the entity.
- * \return the new cost
- */
+ /// \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().
- */
+ /// \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. */
+ /// \brief Makes a copy of the entity.
virtual EntityBase* clone() = 0;
- /*! \brief Makes a major change to the entity. */
+ /// \brief Makes a major change to the entity.
virtual void randomize() = 0;
+ /// \brief Destructor.
+ virtual ~EntityBase() {}
};
- /*! \brief Simulated annealing base class. */
+ /// \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:
- /*! Pointer to the controller. */
+ /// \brief Pointer to the controller.
ControllerBase *controller;
- /*! \brief Cost of the current solution. */
+ /// \brief Cost of the current solution.
double curr_cost;
- /*! \brief Cost of the best solution. */
+ /// \brief Cost of the best solution.
double best_cost;
- /*! \brief Cost of the previous solution. */
+ /// \brief Cost of the previous solution.
double prev_cost;
- /*! \brief Cost of the solution preceding the previous one. */
+ /// \brief Cost of the solution preceding the previous one.
double prev_prev_cost;
- /*! \brief Number of iterations. */
+ /// \brief Number of iterations.
long iter;
- /*! \brief Number of iterations which did not improve the solution since
- * the last improvement. */
+ /// \brief Number of iterations which did not improve the solution since
+ /// the last improvement.
long last_impr;
protected:
- /*! \brief Step to a neighbouring state. */
+ /// \brief Step to a neighbouring state.
virtual double mutate() = 0;
- /*! \brief Reverts the last mutate(). */
+ /// \brief Reverts the last mutate().
virtual void revert() = 0;
- /*! \brief Saves the current solution as the best one. */
+ /// \brief Saves the current solution as the best one.
virtual void saveAsBest() = 0;
- /*! \brief Does initializations before each run. */
+ /// \brief Does initializations before each run.
virtual void init() {
controller->init();
curr_cost = prev_cost = prev_prev_cost = best_cost =
@@ -90,24 +96,23 @@
iter = last_impr = 0;
}
public:
- /*! \brief Sets the controller class to use. */
+ /// \brief Sets the controller class to use.
void setController(ControllerBase &_controller) {
controller = &_controller;
controller->simann = this;
}
- /*! \brief Returns the cost of the current solution. */
+ /// \brief Returns the cost of the current solution.
double getCurrCost() const { return curr_cost; }
- /*! \brief Returns the cost of the previous solution. */
+ /// \brief Returns the cost of the previous solution.
double getPrevCost() const { return prev_cost; }
- /*! \brief Returns the cost of the best solution. */
+ /// \brief Returns the cost of the best solution.
double getBestCost() const { return best_cost; }
- /*! \brief Returns the number of iterations. */
+ /// \brief Returns the number of iterations done.
long getIter() const { return iter; }
- /*! \brief Returns the number of the last iteration when the solution was
- * improved.
- */
+ /// \brief Returns the ordinal number of the last iteration when the
+ /// solution was improved.
long getLastImpr() const { return last_impr; }
- /*! \brief Performs one iteration. */
+ /// \brief Performs one iteration.
bool step() {
iter++;
prev_prev_cost = prev_cost;
@@ -130,28 +135,29 @@
}
return controller->next();
}
- /*! \brief Performs a given number of iterations.
- * \param n the number of iterations
- */
+ /// \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. */
+ /// \brief Starts the annealing process.
void run() {
init();
do { } while (step());
}
+ /// \brief Destructor.
+ virtual ~SimAnnBase() {}
};
- /*! \brief Simulated annealing class. */
+ /// \brief Simulated annealing class.
class SimAnn : public SimAnnBase {
private:
- /*! \brief Pointer to the current entity. */
+ /// \brief Pointer to the current entity.
EntityBase *curr_ent;
- /*! \brief Pointer to the best entity. */
+ /// \brief Pointer to the best entity.
EntityBase *best_ent;
- /*! \brief Does initializations before each run. */
+ /// \brief Does initializations before each run.
void init() {
SimAnnBase::init();
if (best_ent) delete best_ent;
@@ -159,159 +165,166 @@
curr_ent->randomize();
}
public:
- /*! \brief Constructor. */
+ /// \brief Constructor.
SimAnn() : curr_ent(NULL), best_ent(NULL) {}
- /*! \brief Destructor. */
+ /// \brief Destructor.
virtual ~SimAnn() {
if (best_ent) delete best_ent;
}
- /*! \brief Step to a neighbouring state. */
+ /// \brief Step to a neighbouring state.
double mutate() {
return curr_ent->mutate();
}
- /*! \brief Reverts the last mutate(). */
+ /// \brief Reverts the last mutate().
void revert() {
curr_ent->revert();
}
- /*! \brief Saves the current solution as the best one. */
+ /// \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. */
+ /// \brief Sets the current entity.
void setEntity(EntityBase &_ent) {
curr_ent = &_ent;
}
- /*! \brief Returns a copy of the best found entity. */
+ /// \brief Returns a copy of the best found entity.
EntityBase* getBestEntity() { return best_ent->clone(); }
};
- /*! \brief A simple controller for the simulated annealing class. */
+ /// \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:
- /*! \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
- */
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)
{
srand48(time(0));
}
- /*! \brief This is called when a neighbouring state gets accepted. */
+ /// \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.
- */
+ /// \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. */
+ /// \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. */
+ /// \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. */
+ /// \brief Decides whether to accept the current solution or not.
bool accept() {
- double cost_diff = simann->getPrevCost() - simann->getCurrCost();
- return (drand48() <= exp(cost_diff / temp));
+ double cost_diff = simann->getCurrCost() - simann->getPrevCost();
+ return (drand48() <= 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.
- */
+ /// \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;
- /*! \param time the elapsed time in seconds */
+ /// \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:
- double alpha;
- double beta;
- 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;
- bool warmup;
- /*! \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
- */
+ /// \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), warmup(true)
+ ann_fact(_ann_fact), init_ann_fact(_ann_fact), start(false)
{
srand48(time(0));
}
+ /// \brief Does initializations before each run.
void init() {
avg_cost = simann->getCurrCost();
}
- /*! \brief This is called when a neighbouring state gets accepted. */
+ /// \brief This is called when a neighbouring state gets accepted.
void acceptEvent() {
avg_cost = alpha * simann->getCurrCost() + (1.0 - alpha) * avg_cost;
- if (warmup) {
+ 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;
- warmup = false;
+ start = true;
timer.restart();
}
}
}
- /*! \brief Decides whether to continue the annealing process or not. */
+ /// \brief Decides whether to continue the annealing process or not.
bool next() {
- if (warmup) {
+ if (!start) {
return true;
}
else {
- double elapsed_time = timer.getRealTime();
+ double elapsed_time = timer.realTime();
if (fabs(avg_cost - simann->getBestCost()) > threshold(elapsed_time)) {
// decrease the annealing factor
ann_fact *= beta;
@@ -326,22 +339,18 @@
return elapsed_time < end_time;
}
}
- /*! \brief Decides whether to accept the current solution or not. */
+ /// \brief Decides whether to accept the current solution or not.
bool accept() {
- if (warmup) {
- // we accept eveything during the "warm up" phase
+ if (!start) {
return true;
}
else {
- double cost_diff = simann->getPrevCost() - simann->getCurrCost();
- if (cost_diff < 0.0) {
- return (drand48() <= exp(cost_diff / temp));
- }
- else {
- return true;
- }
+ double cost_diff = simann->getCurrCost() - simann->getPrevCost();
+ return (drand48() <= exp(-(cost_diff / temp)));
}
}
+ /// \brief Destructor.
+ virtual ~AdvancedController() {}
};
/// @}