lemon-0.x: comparison src/work/akos/simann.h

equal deleted inserted replaced

-:a2a9c298de4a
+:d6928bd4d8b5
 #ifndef LEMON_SIMANN_H
 #define LEMON_SIMANN_H
 #include <cstdlib>
 #include <cmath>
-#include <sys/time.h>
+#include <lemon/time_measure.h>
 namespace lemon {
 const double INFTY = 1e24;
 }
 void setController(Controller &_controller) {
 controller = &_controller;
 controller->setBase(this);
 }
-double getCurrCost() { return curr_cost; }
+double getCurrCost() const { return curr_cost; }
-double getPrevCost() { return prev_cost; }
+double getPrevCost() const { return prev_cost; }
-double getBestCost() { return best_cost; }
+double getBestCost() const { return best_cost; }
 void run() {
 controller->init();
-while (controller->next()) {
+do {
 mutate();
 if (controller->accept()) {
 controller->acceptEvent();
 if (curr_cost < best_cost) {
 saveAsBest();
 }
 else {
 revert();
 controller->rejectEvent();
 }
-}
+} while (controller->next());
 }
 /*! \brief A base class for controllers. */
 class Controller {
 public:
 /*! */
 virtual bool accept() = 0;
 };
 };
+/*! \todo atgondolni mi is ez a prev_cost */
 template <typename E>
 class SimAnn : public SimAnnBase {
 private:
 E *curr_ent;
 E *best_ent;
 curr_ent = new E(ent);
 best_ent = new E(ent);
 }
 E getBestEntity() { return *best_ent; }
 void mutate() {
-curr_ent->mutate();
+prev_cost = curr_cost;
+curr_cost = curr_ent->mutate();
 }
 void revert() {
 curr_ent->revert();
+curr_cost = prev_cost;
 }
 void saveAsBest() {
 *best_ent = *curr_ent;
 best_cost = curr_cost;
 }
 temp *= ann_fact;
 bool quit = (iter > max_iter) || (iter - last_impr > max_no_impr);
 return !quit;
 }
 bool accept() {
-return (drand48() <= exp(base->getPrevCost() - base->getCurrCost() /
+double cost_diff = base->getPrevCost() - base->getCurrCost();
-temp));
+if (cost_diff < 0.0) {
+return (drand48() <= exp(cost_diff / temp));
+}
+else {
+return true;
+}
 }
 };
 /*! \brief A controller with preset running time for the simulated annealing
 *  class.
 *  \todo Find a better name.
 */
 class AdvancedController : public SimAnnBase::Controller {
 private:
+Timer timer;
 /*! \param time the elapsed time in seconds */
-double threshold(double time) { return 0.0; }
+virtual double threshold(double time) {
+// this is the function 1 / log(x) scaled and offset
+static double xm = 5.0 / end_time;
+static double ym = start_threshold / (1 / log(1.2) - 1 / log(5.0 + 1.2));
+return ym * (1 / log(xm * time + 1.2) - 1 / log(5.0 + 1.2));
+}
 public:
 double alpha, beta, gamma;
 double end_time, start_time;
+double start_threshold;
 double avg_cost;
 double temp, ann_fact;
-/*! \param _end_time running_time
+bool warmup;
+long iter;
+/*! \param _end_time running time in seconds
 *  \param _alpha parameter used to calculate the running average
 *  \param _beta parameter used to decrease the annealing factor
 *  \param _gamma parameter used to increase the temperature
 */
 AdvancedController(double _end_time, double _alpha = 0.2,
 double _beta = 0.9, double _gamma = 1.2) : alpha(_alpha), beta(_beta),
-gamma(_gamma), end_time(_end_time) {}
+gamma(_gamma), end_time(_end_time), ann_fact(0.9999), warmup(true),
+iter(0) {}
 void init() {
-timeval tv;
+avg_cost = base->getCurrCost();
-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;
+iter++;
 }
 void improveEvent() {
 }
 void rejectEvent() {
+iter++;
 }
 bool next() {
-timeval tv;
+if (warmup) {
-gettimeofday(&tv, 0);
+static double max_cost_diff = 0.0;
-double elapsed_time = tv.tv_sec + double(tv.tv_usec) / 1e6 - start_time;
+double cost_diff = base->getCurrCost() - base->getPrevCost();
-if (fabs(avg_cost - base->getBestCost()) > threshold(elapsed_time)) {
+// jo ez igy egyaltalan? -> prev_cost
-	// decrease the annealing factor
+if ((cost_diff > 0.0) && (cost_diff > max_cost_diff)) {
-ann_fact *= beta;
+max_cost_diff = cost_diff;
+}
+// How to set the starting temperature when all the 100 first
+// iterations improve the solution?
+if (iter > 100) {
+// calculate starting threshold and starting temperature
+start_threshold = fabs(base->getBestCost() - avg_cost);
+temp = exp(max_cost_diff) / 0.5;
+warmup = false;
+timer.reset();
+}
+return true;
 }
 else {
-// increase the temperature
+double elapsed_time = timer.getRealTime();
-temp *= gamma;
+if (fabs(avg_cost - base->getBestCost()) > threshold(elapsed_time)) {
-}
+// decrease the annealing factor
-temp *= ann_fact;
+ann_fact *= beta;
-return elapsed_time < end_time;
+}
+else {
+// increase the temperature
+temp *= gamma;
+}
+temp *= ann_fact;
+return elapsed_time < end_time;
+}
 }
 bool accept() {
-return (drand48() <= exp(base->getPrevCost() - base->getCurrCost() /
+if (warmup) {
-temp));
+// we accept eveything during the "warm up" phase
+return true;
+}
+else {
+double cost_diff = base->getPrevCost() - base->getCurrCost();
+if (cost_diff < 0.0) {
+return (drand48() <= exp(cost_diff / temp));
+}
+else {
+return true;
+}
+}
 }
 };
 }

changeset 1021	fd1d073b6557
parent 1000	7f4d07047ed8
child 1023	3268fef5d623