equal
deleted
inserted
replaced
1 #ifndef LEMON_SIMANN_H |
1 #ifndef LEMON_SIMANN_H |
2 #define LEMON_SIMANN_H |
2 #define LEMON_SIMANN_H |
|
3 |
|
4 #include <cstdlib> |
|
5 #include <cmath> |
|
6 #include <sys/time.h> |
3 |
7 |
4 namespace lemon { |
8 namespace lemon { |
5 |
9 |
6 const double INFTY = 1e24; |
10 const double INFTY = 1e24; |
7 |
11 |
28 } |
32 } |
29 double getCurrCost() { return curr_cost; } |
33 double getCurrCost() { return curr_cost; } |
30 double getPrevCost() { return prev_cost; } |
34 double getPrevCost() { return prev_cost; } |
31 double getBestCost() { return best_cost; } |
35 double getBestCost() { return best_cost; } |
32 void run() { |
36 void run() { |
|
37 controller->init(); |
33 while (controller->next()) { |
38 while (controller->next()) { |
34 mutate(); |
39 mutate(); |
35 if (controller->accept()) { |
40 if (controller->accept()) { |
36 controller->acceptEvent(); |
41 controller->acceptEvent(); |
37 if (curr_cost < best_cost) { |
42 if (curr_cost < best_cost) { |
47 } |
52 } |
48 |
53 |
49 class Controller { |
54 class Controller { |
50 public: |
55 public: |
51 SimAnnBase *base; |
56 SimAnnBase *base; |
|
57 virtual void init() {} |
52 virtual void acceptEvent() {} |
58 virtual void acceptEvent() {} |
53 virtual void improveEvent() {} |
59 virtual void improveEvent() {} |
54 virtual void rejectEvent() {} |
60 virtual void rejectEvent() {} |
55 virtual void setBase(SimAnnBase *_base) { base = _base; } |
61 virtual void setBase(SimAnnBase *_base) { base = _base; } |
56 virtual bool next() = 0; |
62 virtual bool next() = 0; |
82 } |
88 } |
83 }; |
89 }; |
84 |
90 |
85 class EntitySkeleton { |
91 class EntitySkeleton { |
86 public: |
92 public: |
87 // returns the new cost |
93 /*! \brief Makes a minor change to the entity. |
|
94 * \return the new cost |
|
95 */ |
88 double mutate() { return 0.0; } |
96 double mutate() { return 0.0; } |
89 // restores the entity to its previous state i.e. reverts the effects of |
97 /*! \brief Restores the entity to its previous state i.e. reverts the |
90 // the last mutate() |
98 * effects of the last mutate. |
|
99 */ |
91 void revert() {} |
100 void revert() {} |
92 }; |
101 }; |
93 |
102 |
|
103 /*! \brief A simple controller for the simulated annealing class. |
|
104 * \todo Find a way to set the various parameters. |
|
105 */ |
94 class SimpleController : public SimAnnBase::Controller { |
106 class SimpleController : public SimAnnBase::Controller { |
95 public: |
107 public: |
96 long iter, last_impr, max_iter, max_no_impr; |
108 long iter, last_impr, max_iter, max_no_impr; |
97 double temp, annealing_factor; |
109 double temp, annealing_factor; |
98 SimpleController() { |
110 SimpleController() { |
115 temp *= annealing_factor; |
127 temp *= annealing_factor; |
116 bool quit = (iter > max_iter) || (iter - last_impr > max_no_impr); |
128 bool quit = (iter > max_iter) || (iter - last_impr > max_no_impr); |
117 return !quit; |
129 return !quit; |
118 } |
130 } |
119 bool accept() { |
131 bool accept() { |
120 return (drand48() <= exp(base->getPrevCost() - base->getCurrCost() / temp)); |
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)); |
121 } |
174 } |
122 }; |
175 }; |
123 |
176 |
124 } |
177 } |
125 |
178 |