Changeset 942:75fdd0c6866d in lemon-0.x for src/work/akos

Timestamp:

10/11/04 20:02:48 (20 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:

• simann.h (moved) (moved from src/work/akos/SimAnn.h) (1 diff)
• simann_test.cc (modified) (2 diffs)

src/work/akos/simann.h

@@ -1 @@
-#ifndef SIMANN_H
-#define SIMANN_H
+#ifndef LEMON_SIMANN_H
+#define LEMON_SIMANN_H
 
-#ifndef INFTY
-#define INFTY 1e24
-#endif
+namespace lemon {
 
-#include <iostream>
+  const double INFTY = 1e24;
 
-class SimAnnBase {
-public:
-  friend class Controller;
-  class Controller {
+  class SimAnnBase {
   public:
-    SimAnnBase *sab;
-    double T;
-    void init(SimAnnBase *_sab) { sab = _sab; }
-    bool next() {}
-    bool accept(double cost) {}
-  };
-protected:
-  double CurrCost;
-  double PrevCost;
-  double BestCost;
+    class Controller;
+  private:
+    Controller *controller;
+  protected:
+    double curr_cost;
+    double prev_cost;
+    double best_cost;
 
-  long Iter;
-  long LastImpr;
-
-  //friend class Controller;
-  Controller *Ctrl;
-public:
-  long getIter() { return Iter; }
-  long getLastImpr() { return LastImpr; }
-  double getBestCost() { return BestCost; }
-  virtual void mutate() = 0;
-  virtual void revert() = 0;
-  virtual void saveAsBest() = 0;
-  virtual void init() = 0;
-
-  void run() {
-    init();
-    while (Ctrl->next()) {
-      Iter++;
-      std::cout << Iter << std::endl;
-      mutate();
-      if (Ctrl->accept(PrevCost - CurrCost) && (CurrCost < BestCost)) {
-        LastImpr = Iter;
-        saveAsBest();
-      }
-      else {
-        revert();
+    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; }
+    double getBestCost() { return best_cost; }
+    void run() {
+      while (controller->next()) {
+        mutate();
+        if (controller->accept(prev_cost - curr_cost)) {
+          controller->acceptEvent();
+          if (curr_cost < best_cost) {
+            saveAsBest();
+            controller->improveEvent();
+          }
+        }
+        else {
+          revert();
+          controller->rejectEvent();
+        }
       }
     }
-  }
-};
 
-template <typename E>
-class SimAnn : public SimAnnBase {
-private:
-  E *CurrEnt;
-  E *PrevEnt;
-  E *BestEnt;
-public:
-  SimAnn() {
-    CurrCost = PrevCost = BestCost = INFTY;
-    Iter = LastImpr = 0;
-  }
-  void setController(Controller &_Ctrl) { Ctrl = &_Ctrl; }
-  void setEnt(E &Ent) {
-    CurrEnt = new E(Ent);
-    PrevEnt = new E(Ent);
-    BestEnt = new E(Ent);
-  }
-  E getBestEnt() { return *BestEnt; }
-  void mutate() {
-    *PrevEnt = *CurrEnt;
-    PrevCost = CurrCost;
-    CurrCost = CurrEnt->mutate();
-  }
-  void revert() {
-    E *tmp = CurrEnt;
-    CurrEnt = PrevEnt;
-    PrevEnt = tmp;
-    CurrCost = PrevCost;
-  }
-  void saveAsBest() {
-    *BestEnt = *CurrEnt;
-    BestCost = CurrCost;
-  }
-  void init() {
-    Ctrl->init(this);
-    CurrEnt->init();
-  }
-};
+    class Controller {
+    public:
+      virtual void acceptEvent() {}
+      virtual void improveEvent() {}
+      virtual void rejectEvent() {}
+      virtual bool next() = 0;
+      virtual bool accept(double cost_diff) = 0;
+    };
+  };
 
-class EntitySkeleton {
-public:
-  void init() {}
-  // returns the new cost
-  double mutate() { return 0.0; }
-};
+  template <typename E>
+  class SimAnn : public SimAnnBase {
+  private:
+    E *curr_ent;
+    E *prev_ent;
+    E *best_ent;
+  public:
+    SimAnn() : SimAnnBase() {}
+    void setEntity(E &Ent) {
+      curr_ent = new E(Ent);
+      prev_ent = new E(Ent);
+      best_ent = new E(Ent);
+    }
+    E getBestEntity() { return *best_ent; }
+    void mutate() {
+      *prev_ent = *curr_ent;
+      prev_cost = curr_cost;
+      curr_cost = curr_ent->mutate();
+    }
+    void revert() {
+      E *tmp = curr_ent;
+      curr_ent = prev_ent;
+      prev_ent = tmp;
+      curr_cost = prev_cost;
+    }
+    void saveAsBest() {
+      *best_ent = *curr_ent;
+      best_cost = curr_cost;
+    }
+  };
+
+  class EntitySkeleton {
+  public:
+    // returns the new cost
+    double mutate() { return 0.0; }
+  };
+
+  template <typename E>
+  class SimAnn2 : public SimAnnBase {
+  private:
+    E *curr_ent;
+    E *best_ent;
+  public:
+    SimAnn2() : 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 EntitySkeleton2 {
+  public:
+    // returns the new cost
+    double mutate() { return 0.0; }
+    // restores the entity to its previous state i.e. reverts the effects of
+    // the last mutate()
+    void revert() {}
+  };
+
+}
 
 #endif

src/work/akos/simann_test.cc

@@ -1 @@
-#include "SimAnn.h"
+#include "simann.h"
 #include <cstdlib>
 #include <cmath>
 #include <iostream>
 
+using namespace lemon;
+
 class MyController : public SimAnnBase::Controller {
 public:
-  long MaxIter, MaxNoImpr;
-  double af;
+  long iter, last_impr, max_iter, max_no_impr;
+  double temp, annealing_factor;
   MyController() {
-    MaxIter = 500000;
-    MaxNoImpr = 20000;
-    af = 0.9999;
-    T = 1000;
+    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() {
-    T *= af;
-    std::cout << T << std::endl;
-    return !((sab->getIter() > MaxIter) || (sab->getIter() - sab->getLastImpr() > MaxNoImpr));
+    temp *= annealing_factor;
+    bool quit = (iter > max_iter) || (iter - last_impr > max_no_impr);
+    return !quit;
   }
-  bool accept(double cost) {
-    return (drand48() <= exp(cost / T));
+  bool accept(double cost_diff) {
+    return (drand48() <= exp(cost_diff / temp));
   }
 };
@@ -26 +38 @@
 class MyEntity {
 public:
-  void init() {}
   double mutate() { return 10.0; }
 };
 
 int main() {
-  SimAnn<MyEntity> sa;
-  MyController c;
-  sa.setController(c);
+  SimAnn<MyEntity> simann;
+  MyController ctrl;
+  simann.setController(ctrl);
   MyEntity ent;
-  sa.setEnt(ent);
-  sa.run();
+  simann.setEntity(ent);
+  simann.run();
 }