1 | #ifndef LEMON_SIMANN_H |
---|
2 | #define LEMON_SIMANN_H |
---|
3 | |
---|
4 | namespace 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 |
---|