lemon-0.x: src/work/akos/simann.h@5e865c5c8a87

     1 #ifndef LEMON_SIMANN_H

     2 #define LEMON_SIMANN_H

     4 #include <cstdlib>

     5 #include <cmath>

     6 #include <sys/time.h>

     8 namespace lemon {

    10   const double INFTY = 1e24;

    12   class SimAnnBase {

    13   public:

    14     class Controller;

    15   private:

    16     Controller *controller;

    17   protected:

    18     double curr_cost;

    19     double prev_cost;

    20     double best_cost;

    22     virtual void mutate() = 0;

    23     virtual void revert() = 0;

    24     virtual void saveAsBest() = 0;

    25   public:

    26     SimAnnBase() {

    27       curr_cost = prev_cost = best_cost = INFTY;

    28     }

    29     void setController(Controller &_controller) {

    30       controller = &_controller;

    31       controller->setBase(this);

    32     }

    33     double getCurrCost() { return curr_cost; }

    34     double getPrevCost() { return prev_cost; }

    35     double getBestCost() { return best_cost; }

    36     void run() {

    37       controller->init();

    38       while (controller->next()) {

    39         mutate();

    40         if (controller->accept()) {

    41           controller->acceptEvent();

    42           if (curr_cost < best_cost) {

    43             saveAsBest();

    44             controller->improveEvent();

    45           }

    46         }

    47         else {

    48           revert();

    49           controller->rejectEvent();

    50         }

    51       }

    52     }

    54     class Controller {

    55     public:

    56       SimAnnBase *base;

    57       virtual void init() {}

    58       virtual void acceptEvent() {}

    59       virtual void improveEvent() {}

    60       virtual void rejectEvent() {}

    61       virtual void setBase(SimAnnBase *_base) { base = _base; }

    62       virtual bool next() = 0;

    63       virtual bool accept() = 0;

    64     };

    65   };

    67   template <typename E>

    68   class SimAnn : public SimAnnBase {

    69   private:

    70     E *curr_ent;

    71     E *best_ent;

    72   public:

    73     SimAnn() : SimAnnBase() {}

    74     void setEntity(E &ent) {

    75       curr_ent = new E(ent);

    76       best_ent = new E(ent);

    77     }

    78     E getBestEntity() { return *best_ent; }

    79     void mutate() {

    80       curr_ent->mutate();

    81     }

    82     void revert() {

    83       curr_ent->revert();

    84     }

    85     void saveAsBest() {

    86       *best_ent = *curr_ent;

    87       best_cost = curr_cost;

    88     }

    89   };

    91   class EntitySkeleton {

    92   public:

    93     /*! \brief Makes a minor change to the entity.

    94      *  \return the new cost

    95      */

    96     double mutate() { return 0.0; }

    97     /*! \brief Restores the entity to its previous state i.e. reverts the

    98      *  effects of the last mutate.

    99      */

   100     void revert() {}

   101   };

   103   /*! \brief A simple controller for the simulated annealing class.

   104    *  \todo Find a way to set the various parameters.

   105    */

   106   class SimpleController : public SimAnnBase::Controller {

   107   public:

   108     long iter, last_impr, max_iter, max_no_impr;

   109     double temp, annealing_factor;

   110     SimpleController() {

   111       iter = last_impr = 0;

   112       max_iter = 500000;

   113       max_no_impr = 20000;

   114       annealing_factor = 0.9999;

   115       temp = 1000;

   116     }

   117     void acceptEvent() {

   118       iter++;

   119     }

   120     void improveEvent() {

   121       last_impr = iter;

   122     }

   123     void rejectEvent() {

   124       iter++;

   125     }

   126     bool next() {

   127       temp *= annealing_factor;

   128       bool quit = (iter > max_iter) || (iter - last_impr > max_no_impr);

   129       return !quit;

   130     }

   131     bool accept() {

   132       return (drand48() <= exp(base->getPrevCost() - base->getCurrCost() /

   133         temp));

   134     }

   135   };

   137   /*! \brief A controller with preset running time for the simulated annealing

   138    *  class.

   139    *  \todo Find a better name.

   140    */

   141   class AdvancedController : public SimAnnBase::Controller {

   142   private:

   143     double threshold() { return 0.0; }

   144   public:

   145     double alpha;

   146     double temp;

   147     double avg_cost;

   148     double start_time, end_time;

   149     void init() {

   150       timeval tv;

   151       gettimeofday(&tv, 0);

   152       start_time = tv.tv_sec + double(tv.tv_usec) / 1e6;

   153     }

   154     void acceptEvent() {

   155       avg_cost = alpha * base->getCurrCost() + (1.0 - alpha) * avg_cost;

   156     }

   157     void improveEvent() {

   158     }

   159     void rejectEvent() {

   160     }

   161     bool next() {

   162       // abs(avg_cost - base->getBestCost())

   163       // ha nagy: cooling factor novelese

   164       // ha kicsi: homerseklet novelese

   165       // de mennyivel?

   166       timeval tv;

   167       gettimeofday(&tv, 0);

   168       double elapsed_time = tv.tv_sec + double(tv.tv_usec) / 1e6 - start_time;

   169       return elapsed_time < end_time;

   170     }

   171     bool accept() {

   172       return (drand48() <= exp(base->getPrevCost() - base->getCurrCost() /

   173         temp));

   174     }

   175   };

   177 }

   179 #endif

author	ladanyi
	Mon, 08 Nov 2004 08:40:37 +0000
changeset 966	5e865c5c8a87
parent 957	4dd4eaee28e7
child 1000	7f4d07047ed8
permissions	-rw-r--r--