COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/akos/simann.h @ 963:5a7556e9e340

Last change on this file since 963:5a7556e9e340 was 957:4dd4eaee28e7, checked in by Akos Ladanyi, 20 years ago

Now the controller asks SimAnnBase? for the various costs.

File size: 2.8 KB
Line 
1#ifndef LEMON_SIMANN_H
2#define LEMON_SIMANN_H
3
4namespace lemon {
5
6  const double INFTY = 1e24;
7
8  class SimAnnBase {
9  public:
10    class Controller;
11  private:
12    Controller *controller;
13  protected:
14    double curr_cost;
15    double prev_cost;
16    double best_cost;
17
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    }
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; }
31    double getBestCost() { return best_cost; }
32    void run() {
33      while (controller->next()) {
34        mutate();
35        if (controller->accept()) {
36          controller->acceptEvent();
37          if (curr_cost < best_cost) {
38            saveAsBest();
39            controller->improveEvent();
40          }
41        }
42        else {
43          revert();
44          controller->rejectEvent();
45        }
46      }
47    }
48
49    class Controller {
50    public:
51      SimAnnBase *base;
52      virtual void acceptEvent() {}
53      virtual void improveEvent() {}
54      virtual void rejectEvent() {}
55      virtual void setBase(SimAnnBase *_base) { base = _base; }
56      virtual bool next() = 0;
57      virtual bool accept() = 0;
58    };
59  };
60
61  template <typename E>
62  class SimAnn : public SimAnnBase {
63  private:
64    E *curr_ent;
65    E *best_ent;
66  public:
67    SimAnn() : SimAnnBase() {}
68    void setEntity(E &ent) {
69      curr_ent = new E(ent);
70      best_ent = new E(ent);
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
85  class EntitySkeleton {
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
94  class SimpleController : public SimAnnBase::Controller {
95  public:
96    long iter, last_impr, max_iter, max_no_impr;
97    double temp, annealing_factor;
98    SimpleController() {
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    }
119    bool accept() {
120      return (drand48() <= exp(base->getPrevCost() - base->getCurrCost() / temp));
121    }
122  };
123
124}
125
126#endif
Note: See TracBrowser for help on using the repository browser.