COIN-OR::LEMON - Graph Library

Changeset 942:75fdd0c6866d in lemon-0.x


Ignore:
Timestamp:
10/11/04 20:02:48 (19 years ago)
Author:
Akos Ladanyi
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1285
Message:

Naming and coding style fixes and various other changes.

Location:
src/work/akos
Files:
1 edited
1 moved

Legend:

Unmodified
Added
Removed
  • src/work/akos/simann.h

    r918 r942  
    1 #ifndef SIMANN_H
    2 #define SIMANN_H
     1#ifndef LEMON_SIMANN_H
     2#define LEMON_SIMANN_H
    33
    4 #ifndef INFTY
    5 #define INFTY 1e24
    6 #endif
     4namespace lemon {
    75
    8 #include <iostream>
     6  const double INFTY = 1e24;
    97
    10 class SimAnnBase {
    11 public:
    12   friend class Controller;
    13   class Controller {
     8  class SimAnnBase {
    149  public:
    15     SimAnnBase *sab;
    16     double T;
    17     void init(SimAnnBase *_sab) { sab = _sab; }
    18     bool next() {}
    19     bool accept(double cost) {}
    20   };
    21 protected:
    22   double CurrCost;
    23   double PrevCost;
    24   double BestCost;
     10    class Controller;
     11  private:
     12    Controller *controller;
     13  protected:
     14    double curr_cost;
     15    double prev_cost;
     16    double best_cost;
    2517
    26   long Iter;
    27   long LastImpr;
    28 
    29   //friend class Controller;
    30   Controller *Ctrl;
    31 public:
    32   long getIter() { return Iter; }
    33   long getLastImpr() { return LastImpr; }
    34   double getBestCost() { return BestCost; }
    35   virtual void mutate() = 0;
    36   virtual void revert() = 0;
    37   virtual void saveAsBest() = 0;
    38   virtual void init() = 0;
    39 
    40   void run() {
    41     init();
    42     while (Ctrl->next()) {
    43       Iter++;
    44       std::cout << Iter << std::endl;
    45       mutate();
    46       if (Ctrl->accept(PrevCost - CurrCost) && (CurrCost < BestCost)) {
    47         LastImpr = Iter;
    48         saveAsBest();
    49       }
    50       else {
    51         revert();
     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        }
    5241      }
    5342    }
    54   }
    55 };
    5643
    57 template <typename E>
    58 class SimAnn : public SimAnnBase {
    59 private:
    60   E *CurrEnt;
    61   E *PrevEnt;
    62   E *BestEnt;
    63 public:
    64   SimAnn() {
    65     CurrCost = PrevCost = BestCost = INFTY;
    66     Iter = LastImpr = 0;
    67   }
    68   void setController(Controller &_Ctrl) { Ctrl = &_Ctrl; }
    69   void setEnt(E &Ent) {
    70     CurrEnt = new E(Ent);
    71     PrevEnt = new E(Ent);
    72     BestEnt = new E(Ent);
    73   }
    74   E getBestEnt() { return *BestEnt; }
    75   void mutate() {
    76     *PrevEnt = *CurrEnt;
    77     PrevCost = CurrCost;
    78     CurrCost = CurrEnt->mutate();
    79   }
    80   void revert() {
    81     E *tmp = CurrEnt;
    82     CurrEnt = PrevEnt;
    83     PrevEnt = tmp;
    84     CurrCost = PrevCost;
    85   }
    86   void saveAsBest() {
    87     *BestEnt = *CurrEnt;
    88     BestCost = CurrCost;
    89   }
    90   void init() {
    91     Ctrl->init(this);
    92     CurrEnt->init();
    93   }
    94 };
     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  };
    9553
    96 class EntitySkeleton {
    97 public:
    98   void init() {}
    99   // returns the new cost
    100   double mutate() { return 0.0; }
    101 };
     54  template <typename E>
     55  class SimAnn : public SimAnnBase {
     56  private:
     57    E *curr_ent;
     58    E *prev_ent;
     59    E *best_ent;
     60  public:
     61    SimAnn() : SimAnnBase() {}
     62    void setEntity(E &Ent) {
     63      curr_ent = new E(Ent);
     64      prev_ent = new E(Ent);
     65      best_ent = new E(Ent);
     66    }
     67    E getBestEntity() { return *best_ent; }
     68    void mutate() {
     69      *prev_ent = *curr_ent;
     70      prev_cost = curr_cost;
     71      curr_cost = curr_ent->mutate();
     72    }
     73    void revert() {
     74      E *tmp = curr_ent;
     75      curr_ent = prev_ent;
     76      prev_ent = tmp;
     77      curr_cost = prev_cost;
     78    }
     79    void saveAsBest() {
     80      *best_ent = *curr_ent;
     81      best_cost = curr_cost;
     82    }
     83  };
     84
     85  class EntitySkeleton {
     86  public:
     87    // returns the new cost
     88    double mutate() { return 0.0; }
     89  };
     90
     91  template <typename E>
     92  class SimAnn2 : public SimAnnBase {
     93  private:
     94    E *curr_ent;
     95    E *best_ent;
     96  public:
     97    SimAnn2() : SimAnnBase() {}
     98    void setEntity(E &Ent) {
     99      curr_ent = new E(Ent);
     100      best_ent = new E(Ent);
     101    }
     102    E getBestEntity() { return *best_ent; }
     103    void mutate() {
     104      curr_ent->mutate();
     105    }
     106    void revert() {
     107      curr_ent->revert();
     108    }
     109    void saveAsBest() {
     110      *best_ent = *curr_ent;
     111      best_cost = curr_cost;
     112    }
     113  };
     114
     115  class EntitySkeleton2 {
     116  public:
     117    // returns the new cost
     118    double mutate() { return 0.0; }
     119    // restores the entity to its previous state i.e. reverts the effects of
     120    // the last mutate()
     121    void revert() {}
     122  };
     123
     124}
    102125
    103126#endif
  • src/work/akos/simann_test.cc

    r918 r942  
    1 #include "SimAnn.h"
     1#include "simann.h"
    22#include <cstdlib>
    33#include <cmath>
    44#include <iostream>
    55
     6using namespace lemon;
     7
    68class MyController : public SimAnnBase::Controller {
    79public:
    8   long MaxIter, MaxNoImpr;
    9   double af;
     10  long iter, last_impr, max_iter, max_no_impr;
     11  double temp, annealing_factor;
    1012  MyController() {
    11     MaxIter = 500000;
    12     MaxNoImpr = 20000;
    13     af = 0.9999;
    14     T = 1000;
     13    iter = last_impr = 0;
     14    max_iter = 500000;
     15    max_no_impr = 20000;
     16    annealing_factor = 0.9999;
     17    temp = 1000;
     18  }
     19  void acceptEvent() {
     20    iter++;
     21  }
     22  void improveEvent() {
     23    last_impr = iter;
     24  }
     25  void rejectEvent() {
     26    iter++;
    1527  }
    1628  bool next() {
    17     T *= af;
    18     std::cout << T << std::endl;
    19     return !((sab->getIter() > MaxIter) || (sab->getIter() - sab->getLastImpr() > MaxNoImpr));
     29    temp *= annealing_factor;
     30    bool quit = (iter > max_iter) || (iter - last_impr > max_no_impr);
     31    return !quit;
    2032  }
    21   bool accept(double cost) {
    22     return (drand48() <= exp(cost / T));
     33  bool accept(double cost_diff) {
     34    return (drand48() <= exp(cost_diff / temp));
    2335  }
    2436};
     
    2638class MyEntity {
    2739public:
    28   void init() {}
    2940  double mutate() { return 10.0; }
    3041};
    3142
    3243int main() {
    33   SimAnn<MyEntity> sa;
    34   MyController c;
    35   sa.setController(c);
     44  SimAnn<MyEntity> simann;
     45  MyController ctrl;
     46  simann.setController(ctrl);
    3647  MyEntity ent;
    37   sa.setEnt(ent);
    38   sa.run();
     48  simann.setEntity(ent);
     49  simann.run();
    3950}
Note: See TracChangeset for help on using the changeset viewer.