COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/akos/simann.h @ 956:0ff924405d21

Last change on this file since 956:0ff924405d21 was 956:0ff924405d21, checked in by Akos Ladanyi, 16 years ago

Added the SimpleController? class, and removed the first version of SimAnn? in favour of the second.

File size: 2.6 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) { controller = &_controller; }
26    double getBestCost() { return best_cost; }
27    void run() {
28      while (controller->next()) {
29        mutate();
30        if (controller->accept(prev_cost - curr_cost)) {
31          controller->acceptEvent();
32          if (curr_cost < best_cost) {
33            saveAsBest();
34            controller->improveEvent();
35          }
36        }
37        else {
38          revert();
39          controller->rejectEvent();
40        }
41      }
42    }
43
44    class Controller {
45    public:
46      virtual void acceptEvent() {}
47      virtual void improveEvent() {}
48      virtual void rejectEvent() {}
49      virtual bool next() = 0;
50      virtual bool accept(double cost_diff) = 0;
51    };
52  };
53
54  template <typename E>
55  class SimAnn : public SimAnnBase {
56  private:
57    E *curr_ent;
58    E *best_ent;
59  public:
60    SimAnn2() : SimAnnBase() {}
61    void setEntity(E &Ent) {
62      curr_ent = new E(Ent);
63      best_ent = new E(Ent);
64    }
65    E getBestEntity() { return *best_ent; }
66    void mutate() {
67      curr_ent->mutate();
68    }
69    void revert() {
70      curr_ent->revert();
71    }
72    void saveAsBest() {
73      *best_ent = *curr_ent;
74      best_cost = curr_cost;
75    }
76  };
77
78  class EntitySkeleton {
79  public:
80    // returns the new cost
81    double mutate() { return 0.0; }
82    // restores the entity to its previous state i.e. reverts the effects of
83    // the last mutate()
84    void revert() {}
85  };
86
87  class SimpleController : public SimAnnBase::Controller {
88  public:
89    long iter, last_impr, max_iter, max_no_impr;
90    double temp, annealing_factor;
91    MyController() {
92      iter = last_impr = 0;
93      max_iter = 500000;
94      max_no_impr = 20000;
95      annealing_factor = 0.9999;
96      temp = 1000;
97    }
98    void acceptEvent() {
99      iter++;
100    }
101    void improveEvent() {
102      last_impr = iter;
103    }
104    void rejectEvent() {
105      iter++;
106    }
107    bool next() {
108      temp *= annealing_factor;
109      bool quit = (iter > max_iter) || (iter - last_impr > max_no_impr);
110      return !quit;
111    }
112    bool accept(double cost_diff) {
113      return (drand48() <= exp(cost_diff / temp));
114    }
115  };
116
117}
118
119#endif
Note: See TracBrowser for help on using the repository browser.