source: lemon-0.x/src/work/akos/simann.h @ 968:1a7593db0eaa

#ifndef LEMON_SIMANN_H
#define LEMON_SIMANN_H

#include <cstdlib>
#include <cmath>
#include <sys/time.h>

namespace lemon {

  const double INFTY = 1e24;

  class SimAnnBase {
  public:
    class Controller;
  private:
    Controller *controller;
  protected:
    double curr_cost;
    double prev_cost;
    double best_cost;

    virtual void mutate() = 0;
    virtual void revert() = 0;
    virtual void saveAsBest() = 0;
  public:
    SimAnnBase() {
      curr_cost = prev_cost = best_cost = INFTY;
    }
    void setController(Controller &_controller) {
      controller = &_controller;
      controller->setBase(this);
    }
    double getCurrCost() { return curr_cost; }
    double getPrevCost() { return prev_cost; }
    double getBestCost() { return best_cost; }
    void run() {
      controller->init();
      while (controller->next()) {
        mutate();
        if (controller->accept()) {
          controller->acceptEvent();
          if (curr_cost < best_cost) {
            saveAsBest();
            controller->improveEvent();
          }
        }
        else {
          revert();
          controller->rejectEvent();
        }
      }
    }

    class Controller {
    public:
      SimAnnBase *base;
      virtual void init() {}
      virtual void acceptEvent() {}
      virtual void improveEvent() {}
      virtual void rejectEvent() {}
      virtual void setBase(SimAnnBase *_base) { base = _base; }
      virtual bool next() = 0;
      virtual bool accept() = 0;
    };
  };

  template <typename E>
  class SimAnn : public SimAnnBase {
  private:
    E *curr_ent;
    E *best_ent;
  public:
    SimAnn() : SimAnnBase() {}
    void setEntity(E &ent) {
      curr_ent = new E(ent);
      best_ent = new E(ent);
    }
    E getBestEntity() { return *best_ent; }
    void mutate() {
      curr_ent->mutate();
    }
    void revert() {
      curr_ent->revert();
    }
    void saveAsBest() {
      *best_ent = *curr_ent;
      best_cost = curr_cost;
    }
  };

  class EntitySkeleton {
  public:
    /*! \brief Makes a minor change to the entity.
     *  \return the new cost
     */
    double mutate() { return 0.0; }
    /*! \brief Restores the entity to its previous state i.e. reverts the
     *  effects of the last mutate.
     */
    void revert() {}
  };

  /*! \brief A simple controller for the simulated annealing class.
   *  \todo Find a way to set the various parameters.
   */
  class SimpleController : public SimAnnBase::Controller {
  public:
    long iter, last_impr, max_iter, max_no_impr;
    double temp, annealing_factor;
    SimpleController() {
      iter = last_impr = 0;
      max_iter = 500000;
      max_no_impr = 20000;
      annealing_factor = 0.9999;
      temp = 1000;
    }
    void acceptEvent() {
      iter++;
    }
    void improveEvent() {
      last_impr = iter;
    }
    void rejectEvent() {
      iter++;
    }
    bool next() {
      temp *= annealing_factor;
      bool quit = (iter > max_iter) || (iter - last_impr > max_no_impr);
      return !quit;
    }
    bool accept() {
      return (drand48() <= exp(base->getPrevCost() - base->getCurrCost() /
        temp));
    }
  };

  /*! \brief A controller with preset running time for the simulated annealing
   *  class.
   *  \todo Find a better name.
   */
  class AdvancedController : public SimAnnBase::Controller {
  private:
    double threshold() { return 0.0; }
  public:
    double alpha;
    double temp;
    double avg_cost;
    double start_time, end_time;
    void init() {
      timeval tv;
      gettimeofday(&tv, 0);
      start_time = tv.tv_sec + double(tv.tv_usec) / 1e6;
    }
    void acceptEvent() {
      avg_cost = alpha * base->getCurrCost() + (1.0 - alpha) * avg_cost;
    }
    void improveEvent() {
    }
    void rejectEvent() {
    }
    bool next() {
      // abs(avg_cost - base->getBestCost())
      // ha nagy: cooling factor novelese
      // ha kicsi: homerseklet novelese
      // de mennyivel?
      timeval tv;
      gettimeofday(&tv, 0);
      double elapsed_time = tv.tv_sec + double(tv.tv_usec) / 1e6 - start_time;
      return elapsed_time < end_time;
    }
    bool accept() {
      return (drand48() <= exp(base->getPrevCost() - base->getCurrCost() /
        temp));
    }
  };

}

#endif