simann.h

Go to the documentation of this file.
00001 /* -*- C++ -*-
00002  *
00003  * This file is a part of LEMON, a generic C++ optimization library
00004  *
00005  * Copyright (C) 2003-2006
00006  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
00007  * (Egervary Research Group on Combinatorial Optimization, EGRES).
00008  *
00009  * Permission to use, modify and distribute this software is granted
00010  * provided that this copyright notice appears in all copies. For
00011  * precise terms see the accompanying LICENSE file.
00012  *
00013  * This software is provided "AS IS" with no warranty of any kind,
00014  * express or implied, and with no claim as to its suitability for any
00015  * purpose.
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           // calculate starting threshold and starting temperature
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           // decrease the annealing factor
00350           ann_fact *= beta;
00351         }
00352         else {
00353           // increase the temperature
00354           temp *= gamma;
00355           // reset the annealing factor
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

Generated on Fri Feb 3 18:39:41 2006 for LEMON by  doxygen 1.4.6