00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019 #ifndef LEMON_SIMANN_H
00020 #define LEMON_SIMANN_H
00021
00029
00030 #include <cstdlib>
00031 #include <cmath>
00032 #include <limits>
00033 #include <lemon/time_measure.h>
00034
00035 namespace lemon {
00036
00039
00040 class SimAnnBase;
00041
00043 class ControllerBase {
00044 public:
00045 friend class SimAnnBase;
00047 SimAnnBase *simann;
00049 virtual void init() {}
00052 virtual void acceptEvent() {}
00055 virtual void improveEvent() {}
00058 virtual void rejectEvent() {}
00060 virtual bool next() = 0;
00062 virtual bool accept() = 0;
00064 virtual ~ControllerBase() {}
00065 };
00066
00068 class EntityBase {
00069 public:
00072 virtual double mutate() = 0;
00075 virtual void revert() = 0;
00077 virtual EntityBase* clone() = 0;
00079 virtual void randomize() = 0;
00081 virtual ~EntityBase() {}
00082 };
00083
00087 class SimAnnBase {
00088 private:
00090 ControllerBase *controller;
00092 double curr_cost;
00094 double best_cost;
00096 double prev_cost;
00098 double prev_prev_cost;
00100 long iter;
00103 long last_impr;
00104 protected:
00106 virtual double mutate() = 0;
00108 virtual void revert() = 0;
00110 virtual void saveAsBest() = 0;
00112 virtual void init() {
00113 controller->init();
00114 curr_cost = prev_cost = prev_prev_cost = best_cost =
00115 std::numeric_limits<double>::infinity();
00116 iter = last_impr = 0;
00117 }
00118 public:
00120 void setController(ControllerBase &_controller) {
00121 controller = &_controller;
00122 controller->simann = this;
00123 }
00125 double getCurrCost() const { return curr_cost; }
00127 double getPrevCost() const { return prev_cost; }
00129 double getBestCost() const { return best_cost; }
00131 long getIter() const { return iter; }
00134 long getLastImpr() const { return last_impr; }
00136 bool step() {
00137 iter++;
00138 prev_prev_cost = prev_cost;
00139 prev_cost = curr_cost;
00140 curr_cost = mutate();
00141 if (controller->accept()) {
00142 controller->acceptEvent();
00143 last_impr = iter;
00144 if (curr_cost < best_cost) {
00145 best_cost = curr_cost;
00146 saveAsBest();
00147 controller->improveEvent();
00148 }
00149 }
00150 else {
00151 revert();
00152 curr_cost = prev_cost;
00153 prev_cost = prev_prev_cost;
00154 controller->rejectEvent();
00155 }
00156 return controller->next();
00157 }
00160 bool step(int n) {
00161 for(; n > 0 && step(); --n) ;
00162 return !n;
00163 }
00165 void run() {
00166 init();
00167 do { } while (step());
00168 }
00170 virtual ~SimAnnBase() {}
00171 };
00172
00174 class SimAnn : public SimAnnBase {
00175 private:
00177 EntityBase *curr_ent;
00179 EntityBase *best_ent;
00181 void init() {
00182 SimAnnBase::init();
00183 if (best_ent) delete best_ent;
00184 best_ent = NULL;
00185 curr_ent->randomize();
00186 }
00187 public:
00189 SimAnn() : curr_ent(NULL), best_ent(NULL) {}
00191 virtual ~SimAnn() {
00192 if (best_ent) delete best_ent;
00193 }
00195 double mutate() {
00196 return curr_ent->mutate();
00197 }
00199 void revert() {
00200 curr_ent->revert();
00201 }
00203 void saveAsBest() {
00204 if (best_ent) delete best_ent;
00205 best_ent = curr_ent->clone();
00206 }
00208 void setEntity(EntityBase &_ent) {
00209 curr_ent = &_ent;
00210 }
00212 EntityBase* getBestEntity() { return best_ent->clone(); }
00213 };
00214
00218 class SimpleController : public ControllerBase {
00219 private:
00221 long max_iter;
00224 long max_no_impr;
00226 double temp;
00228 double ann_fact;
00235 public:
00236 SimpleController(long _max_iter = 500000, long _max_no_impr = 20000,
00237 double _temp = 1000.0, double _ann_fact = 0.9999) : max_iter(_max_iter),
00238 max_no_impr(_max_no_impr), temp(_temp), ann_fact(_ann_fact)
00239 {
00240 srand48(time(0));
00241 }
00243 void acceptEvent() {}
00246 void improveEvent() {}
00248 void rejectEvent() {}
00251 bool next() {
00252 temp *= ann_fact;
00253 bool quit = (simann->getIter() > max_iter) ||
00254 (simann->getIter() - simann->getLastImpr() > max_no_impr);
00255 return !quit;
00256 }
00258 bool accept() {
00259 double cost_diff = simann->getCurrCost() - simann->getPrevCost();
00260 return (drand48() <= exp(-(cost_diff / temp)));
00261 }
00263 virtual ~SimpleController() {}
00264 };
00265
00277 class AdvancedController : public ControllerBase {
00278 private:
00280 Timer timer;
00283 virtual double threshold(double time) {
00284 return (-1.0) * start_threshold / end_time * time + start_threshold;
00285 }
00287 double alpha;
00289 double beta;
00291 double gamma;
00293 double end_time;
00295 double start_time;
00297 double start_threshold;
00299 double avg_cost;
00301 double temp;
00303 double ann_fact;
00305 double init_ann_fact;
00307 bool start;
00308 public:
00315 AdvancedController(double _end_time, double _alpha = 0.2,
00316 double _beta = 0.9, double _gamma = 1.6, double _ann_fact = 0.9999) :
00317 alpha(_alpha), beta(_beta), gamma(_gamma), end_time(_end_time),
00318 ann_fact(_ann_fact), init_ann_fact(_ann_fact), start(false)
00319 {
00320 srand48(time(0));
00321 }
00323 void init() {
00324 avg_cost = simann->getCurrCost();
00325 }
00327 void acceptEvent() {
00328 avg_cost = alpha * simann->getCurrCost() + (1.0 - alpha) * avg_cost;
00329 if (!start) {
00330 static int cnt = 0;
00331 cnt++;
00332 if (cnt >= 100) {
00333
00334 start_threshold = 5.0 * fabs(simann->getBestCost() - avg_cost);
00335 temp = 10000.0;
00336 start = true;
00337 timer.restart();
00338 }
00339 }
00340 }
00342 bool next() {
00343 if (!start) {
00344 return true;
00345 }
00346 else {
00347 double elapsed_time = timer.realTime();
00348 if (fabs(avg_cost - simann->getBestCost()) > threshold(elapsed_time)) {
00349
00350 ann_fact *= beta;
00351 }
00352 else {
00353
00354 temp *= gamma;
00355
00356 ann_fact = init_ann_fact;
00357 }
00358 temp *= ann_fact;
00359 return elapsed_time < end_time;
00360 }
00361 }
00363 bool accept() {
00364 if (!start) {
00365 return true;
00366 }
00367 else {
00368 double cost_diff = simann->getCurrCost() - simann->getPrevCost();
00369 return (drand48() <= exp(-(cost_diff / temp)));
00370 }
00371 }
00373 virtual ~AdvancedController() {}
00374 };
00375
00377
00378 }
00379
00380 #endif