COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/akos/simann.h @ 965:1e16b8dac159

Last change on this file since 965:1e16b8dac159 was 957:4dd4eaee28e7, checked in by Akos Ladanyi, 19 years ago

Now the controller asks SimAnnBase? for the various costs.

File size: 2.8 KB
RevLine 
[942]1#ifndef LEMON_SIMANN_H
2#define LEMON_SIMANN_H
[918]3
[942]4namespace lemon {
[918]5
[942]6  const double INFTY = 1e24;
[918]7
[942]8  class SimAnnBase {
[918]9  public:
[942]10    class Controller;
11  private:
12    Controller *controller;
13  protected:
14    double curr_cost;
15    double prev_cost;
16    double best_cost;
[918]17
[942]18    virtual void mutate() = 0;
19    virtual void revert() = 0;
20    virtual void saveAsBest() = 0;
21  public:
22    SimAnnBase() {
23      curr_cost = prev_cost = best_cost = INFTY;
24    }
[957]25    void setController(Controller &_controller) {
26      controller = &_controller;
27      controller->setBase(this);
28    }
29    double getCurrCost() { return curr_cost; }
30    double getPrevCost() { return prev_cost; }
[942]31    double getBestCost() { return best_cost; }
32    void run() {
33      while (controller->next()) {
34        mutate();
[957]35        if (controller->accept()) {
[942]36          controller->acceptEvent();
37          if (curr_cost < best_cost) {
38            saveAsBest();
39            controller->improveEvent();
40          }
41        }
42        else {
43          revert();
44          controller->rejectEvent();
45        }
[918]46      }
47    }
48
[942]49    class Controller {
50    public:
[957]51      SimAnnBase *base;
[942]52      virtual void acceptEvent() {}
53      virtual void improveEvent() {}
54      virtual void rejectEvent() {}
[957]55      virtual void setBase(SimAnnBase *_base) { base = _base; }
[942]56      virtual bool next() = 0;
[957]57      virtual bool accept() = 0;
[942]58    };
59  };
[918]60
[942]61  template <typename E>
62  class SimAnn : public SimAnnBase {
63  private:
64    E *curr_ent;
65    E *best_ent;
66  public:
[957]67    SimAnn() : SimAnnBase() {}
68    void setEntity(E &ent) {
69      curr_ent = new E(ent);
70      best_ent = new E(ent);
[942]71    }
72    E getBestEntity() { return *best_ent; }
73    void mutate() {
74      curr_ent->mutate();
75    }
76    void revert() {
77      curr_ent->revert();
78    }
79    void saveAsBest() {
80      *best_ent = *curr_ent;
81      best_cost = curr_cost;
82    }
83  };
84
[956]85  class EntitySkeleton {
[942]86  public:
87    // returns the new cost
88    double mutate() { return 0.0; }
89    // restores the entity to its previous state i.e. reverts the effects of
90    // the last mutate()
91    void revert() {}
92  };
93
[956]94  class SimpleController : public SimAnnBase::Controller {
95  public:
96    long iter, last_impr, max_iter, max_no_impr;
97    double temp, annealing_factor;
[957]98    SimpleController() {
[956]99      iter = last_impr = 0;
100      max_iter = 500000;
101      max_no_impr = 20000;
102      annealing_factor = 0.9999;
103      temp = 1000;
104    }
105    void acceptEvent() {
106      iter++;
107    }
108    void improveEvent() {
109      last_impr = iter;
110    }
111    void rejectEvent() {
112      iter++;
113    }
114    bool next() {
115      temp *= annealing_factor;
116      bool quit = (iter > max_iter) || (iter - last_impr > max_no_impr);
117      return !quit;
118    }
[957]119    bool accept() {
120      return (drand48() <= exp(base->getPrevCost() - base->getCurrCost() / temp));
[956]121    }
122  };
123
[942]124}
[918]125
126#endif
Note: See TracBrowser for help on using the repository browser.