COIN-OR::LEMON - Graph Library

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

Last change on this file since 966:5e865c5c8a87 was 966:5e865c5c8a87, checked in by Akos Ladanyi, 16 years ago

Added an init method to the controller, and started writing a second controller.

File size: 4.2 KB
Line 
1#ifndef LEMON_SIMANN_H
2#define LEMON_SIMANN_H
3
4#include <cstdlib>
5#include <cmath>
6#include <sys/time.h>
7
8namespace lemon {
9
10  const double INFTY = 1e24;
11
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;
21
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    }
53
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  };
66
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  };
90
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  };
102
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  };
136
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  };
176
177}
178
179#endif
Note: See TracBrowser for help on using the repository browser.