1.1 --- a/src/work/akos/SimAnn.h Fri Oct 08 13:07:51 2004 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,103 +0,0 @@
1.4 -#ifndef SIMANN_H
1.5 -#define SIMANN_H
1.6 -
1.7 -#ifndef INFTY
1.8 -#define INFTY 1e24
1.9 -#endif
1.10 -
1.11 -#include <iostream>
1.12 -
1.13 -class SimAnnBase {
1.14 -public:
1.15 - friend class Controller;
1.16 - class Controller {
1.17 - public:
1.18 - SimAnnBase *sab;
1.19 - double T;
1.20 - void init(SimAnnBase *_sab) { sab = _sab; }
1.21 - bool next() {}
1.22 - bool accept(double cost) {}
1.23 - };
1.24 -protected:
1.25 - double CurrCost;
1.26 - double PrevCost;
1.27 - double BestCost;
1.28 -
1.29 - long Iter;
1.30 - long LastImpr;
1.31 -
1.32 - //friend class Controller;
1.33 - Controller *Ctrl;
1.34 -public:
1.35 - long getIter() { return Iter; }
1.36 - long getLastImpr() { return LastImpr; }
1.37 - double getBestCost() { return BestCost; }
1.38 - virtual void mutate() = 0;
1.39 - virtual void revert() = 0;
1.40 - virtual void saveAsBest() = 0;
1.41 - virtual void init() = 0;
1.42 -
1.43 - void run() {
1.44 - init();
1.45 - while (Ctrl->next()) {
1.46 - Iter++;
1.47 - std::cout << Iter << std::endl;
1.48 - mutate();
1.49 - if (Ctrl->accept(PrevCost - CurrCost) && (CurrCost < BestCost)) {
1.50 - LastImpr = Iter;
1.51 - saveAsBest();
1.52 - }
1.53 - else {
1.54 - revert();
1.55 - }
1.56 - }
1.57 - }
1.58 -};
1.59 -
1.60 -template <typename E>
1.61 -class SimAnn : public SimAnnBase {
1.62 -private:
1.63 - E *CurrEnt;
1.64 - E *PrevEnt;
1.65 - E *BestEnt;
1.66 -public:
1.67 - SimAnn() {
1.68 - CurrCost = PrevCost = BestCost = INFTY;
1.69 - Iter = LastImpr = 0;
1.70 - }
1.71 - void setController(Controller &_Ctrl) { Ctrl = &_Ctrl; }
1.72 - void setEnt(E &Ent) {
1.73 - CurrEnt = new E(Ent);
1.74 - PrevEnt = new E(Ent);
1.75 - BestEnt = new E(Ent);
1.76 - }
1.77 - E getBestEnt() { return *BestEnt; }
1.78 - void mutate() {
1.79 - *PrevEnt = *CurrEnt;
1.80 - PrevCost = CurrCost;
1.81 - CurrCost = CurrEnt->mutate();
1.82 - }
1.83 - void revert() {
1.84 - E *tmp = CurrEnt;
1.85 - CurrEnt = PrevEnt;
1.86 - PrevEnt = tmp;
1.87 - CurrCost = PrevCost;
1.88 - }
1.89 - void saveAsBest() {
1.90 - *BestEnt = *CurrEnt;
1.91 - BestCost = CurrCost;
1.92 - }
1.93 - void init() {
1.94 - Ctrl->init(this);
1.95 - CurrEnt->init();
1.96 - }
1.97 -};
1.98 -
1.99 -class EntitySkeleton {
1.100 -public:
1.101 - void init() {}
1.102 - // returns the new cost
1.103 - double mutate() { return 0.0; }
1.104 -};
1.105 -
1.106 -#endif
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/src/work/akos/simann.h Mon Oct 11 18:02:48 2004 +0000
2.3 @@ -0,0 +1,126 @@
2.4 +#ifndef LEMON_SIMANN_H
2.5 +#define LEMON_SIMANN_H
2.6 +
2.7 +namespace lemon {
2.8 +
2.9 + const double INFTY = 1e24;
2.10 +
2.11 + class SimAnnBase {
2.12 + public:
2.13 + class Controller;
2.14 + private:
2.15 + Controller *controller;
2.16 + protected:
2.17 + double curr_cost;
2.18 + double prev_cost;
2.19 + double best_cost;
2.20 +
2.21 + virtual void mutate() = 0;
2.22 + virtual void revert() = 0;
2.23 + virtual void saveAsBest() = 0;
2.24 + public:
2.25 + SimAnnBase() {
2.26 + curr_cost = prev_cost = best_cost = INFTY;
2.27 + }
2.28 + void setController(Controller &_controller) { controller = &_controller; }
2.29 + double getBestCost() { return best_cost; }
2.30 + void run() {
2.31 + while (controller->next()) {
2.32 + mutate();
2.33 + if (controller->accept(prev_cost - curr_cost)) {
2.34 + controller->acceptEvent();
2.35 + if (curr_cost < best_cost) {
2.36 + saveAsBest();
2.37 + controller->improveEvent();
2.38 + }
2.39 + }
2.40 + else {
2.41 + revert();
2.42 + controller->rejectEvent();
2.43 + }
2.44 + }
2.45 + }
2.46 +
2.47 + class Controller {
2.48 + public:
2.49 + virtual void acceptEvent() {}
2.50 + virtual void improveEvent() {}
2.51 + virtual void rejectEvent() {}
2.52 + virtual bool next() = 0;
2.53 + virtual bool accept(double cost_diff) = 0;
2.54 + };
2.55 + };
2.56 +
2.57 + template <typename E>
2.58 + class SimAnn : public SimAnnBase {
2.59 + private:
2.60 + E *curr_ent;
2.61 + E *prev_ent;
2.62 + E *best_ent;
2.63 + public:
2.64 + SimAnn() : SimAnnBase() {}
2.65 + void setEntity(E &Ent) {
2.66 + curr_ent = new E(Ent);
2.67 + prev_ent = new E(Ent);
2.68 + best_ent = new E(Ent);
2.69 + }
2.70 + E getBestEntity() { return *best_ent; }
2.71 + void mutate() {
2.72 + *prev_ent = *curr_ent;
2.73 + prev_cost = curr_cost;
2.74 + curr_cost = curr_ent->mutate();
2.75 + }
2.76 + void revert() {
2.77 + E *tmp = curr_ent;
2.78 + curr_ent = prev_ent;
2.79 + prev_ent = tmp;
2.80 + curr_cost = prev_cost;
2.81 + }
2.82 + void saveAsBest() {
2.83 + *best_ent = *curr_ent;
2.84 + best_cost = curr_cost;
2.85 + }
2.86 + };
2.87 +
2.88 + class EntitySkeleton {
2.89 + public:
2.90 + // returns the new cost
2.91 + double mutate() { return 0.0; }
2.92 + };
2.93 +
2.94 + template <typename E>
2.95 + class SimAnn2 : public SimAnnBase {
2.96 + private:
2.97 + E *curr_ent;
2.98 + E *best_ent;
2.99 + public:
2.100 + SimAnn2() : SimAnnBase() {}
2.101 + void setEntity(E &Ent) {
2.102 + curr_ent = new E(Ent);
2.103 + best_ent = new E(Ent);
2.104 + }
2.105 + E getBestEntity() { return *best_ent; }
2.106 + void mutate() {
2.107 + curr_ent->mutate();
2.108 + }
2.109 + void revert() {
2.110 + curr_ent->revert();
2.111 + }
2.112 + void saveAsBest() {
2.113 + *best_ent = *curr_ent;
2.114 + best_cost = curr_cost;
2.115 + }
2.116 + };
2.117 +
2.118 + class EntitySkeleton2 {
2.119 + public:
2.120 + // returns the new cost
2.121 + double mutate() { return 0.0; }
2.122 + // restores the entity to its previous state i.e. reverts the effects of
2.123 + // the last mutate()
2.124 + void revert() {}
2.125 + };
2.126 +
2.127 +}
2.128 +
2.129 +#endif
3.1 --- a/src/work/akos/simann_test.cc Fri Oct 08 13:07:51 2004 +0000
3.2 +++ b/src/work/akos/simann_test.cc Mon Oct 11 18:02:48 2004 +0000
3.3 @@ -1,39 +1,50 @@
3.4 -#include "SimAnn.h"
3.5 +#include "simann.h"
3.6 #include <cstdlib>
3.7 #include <cmath>
3.8 #include <iostream>
3.9
3.10 +using namespace lemon;
3.11 +
3.12 class MyController : public SimAnnBase::Controller {
3.13 public:
3.14 - long MaxIter, MaxNoImpr;
3.15 - double af;
3.16 + long iter, last_impr, max_iter, max_no_impr;
3.17 + double temp, annealing_factor;
3.18 MyController() {
3.19 - MaxIter = 500000;
3.20 - MaxNoImpr = 20000;
3.21 - af = 0.9999;
3.22 - T = 1000;
3.23 + iter = last_impr = 0;
3.24 + max_iter = 500000;
3.25 + max_no_impr = 20000;
3.26 + annealing_factor = 0.9999;
3.27 + temp = 1000;
3.28 + }
3.29 + void acceptEvent() {
3.30 + iter++;
3.31 + }
3.32 + void improveEvent() {
3.33 + last_impr = iter;
3.34 + }
3.35 + void rejectEvent() {
3.36 + iter++;
3.37 }
3.38 bool next() {
3.39 - T *= af;
3.40 - std::cout << T << std::endl;
3.41 - return !((sab->getIter() > MaxIter) || (sab->getIter() - sab->getLastImpr() > MaxNoImpr));
3.42 + temp *= annealing_factor;
3.43 + bool quit = (iter > max_iter) || (iter - last_impr > max_no_impr);
3.44 + return !quit;
3.45 }
3.46 - bool accept(double cost) {
3.47 - return (drand48() <= exp(cost / T));
3.48 + bool accept(double cost_diff) {
3.49 + return (drand48() <= exp(cost_diff / temp));
3.50 }
3.51 };
3.52
3.53 class MyEntity {
3.54 public:
3.55 - void init() {}
3.56 double mutate() { return 10.0; }
3.57 };
3.58
3.59 int main() {
3.60 - SimAnn<MyEntity> sa;
3.61 - MyController c;
3.62 - sa.setController(c);
3.63 + SimAnn<MyEntity> simann;
3.64 + MyController ctrl;
3.65 + simann.setController(ctrl);
3.66 MyEntity ent;
3.67 - sa.setEnt(ent);
3.68 - sa.run();
3.69 + simann.setEntity(ent);
3.70 + simann.run();
3.71 }