- Main Page
- Classes
- Files

- File List

# OptFrame/Heuristic/BasicSimulatedAnnealing.hpp

    00001 #ifndef OPTFRAME_BSA_HPP_
    00002 #define OPTFRAME_BSA_HPP_
    00003
    00004 #include "../Heuristic.hpp"
    00005 #include <math.h>
    00006
    00007 template<class R, class M = OPTFRAME_DEFAULT_MEMORY>
    00008 class BasicSimulatedAnnealing: public Heuristic<R, M>
    00009 {
    00010 private:
    00011         Evaluator<R, M>& evaluator;
    00012         vector<NS<R, M>*> neighbors;
    00013         RandGen& rg;
    00014         double alpha;
    00015         int SAmax;
    00016         double Ti;
    00017
    00018 public:
    00019
    00020         using Heuristic<R, M>::exec; // prevents name hiding
    00021
    00022         BasicSimulatedAnnealing(Evaluator<R, M>& _evaluator, vector<NS<R, M>*> _neighbors, double _alpha, int _SAmax, double _Ti, RandGen& _rg) :
    00023                 evaluator(_evaluator), neighbors(_neighbors), rg(_rg)
    00024         {
    00025                 alpha = (_alpha);
    00026                 SAmax = (_SAmax);
    00027                 Ti = (_Ti);
    00028
    00029         }
    00030
    00031         BasicSimulatedAnnealing(Evaluator<R, M>& _evaluator, NS<R, M>* _neighbors, double _alpha, int _SAmax, double _Ti, RandGen& _rg) :
    00032                 evaluator(_evaluator), rg(_rg)
    00033         {
    00034                 neighbors.push_back(_neighbors);
    00035                 alpha = (_alpha);
    00036                 SAmax = (_SAmax);
    00037                 Ti = (_Ti);
    00038         }
    00039
    00040         virtual ~BasicSimulatedAnnealing()
    00041         {
    00042         }
    00043
    00044         void exec(Solution<R>& s, double timelimit, double target_f)
    00045         {
    00046                 Evaluation<M>& e = evaluator.evaluate(s.getR());
    00047                 exec(s, e, timelimit, target_f);
    00048                 delete &e;
    00049         }
    00050
    00051         void exec(Solution<R>& s, Evaluation<M>& e, double timelimit, double target_f)
    00052         {
    00053                 cout << "SA exec(" << target_f << "," << timelimit << ")" << endl;
    00054
    00055                 Timer tnow;
    00056
    00057                 double T = Ti;
    00058                 int iterT = 0;
    00059                 Solution<R>* sStar = &s.clone();
    00060                 Evaluation<M>* eStar = &e.clone();
    00061
    00062                 while ((T > 0) && (tnow.now() < timelimit))
    00063                 {
    00064                         while ((iterT < SAmax) && (tnow.now() < timelimit))
    00065                         {
    00066                                 int n = rg.rand(neighbors.size());
    00067                                 Move<R, M>* move = &(neighbors[n]->move(s));
    00068
    00069                                 while (!(move->canBeApplied(e, s)))
    00070                                 {
    00071                                         delete move;
    00072                                         move = &(neighbors[n]->move(s));
    00073                                 }
    00074
    00075                                 Solution<R>* sCurrent = &s.clone();
    00076                                 Evaluation<M>* eCurrent = &e.clone();
    00077                                 move->apply(*eCurrent, *sCurrent);
    00078                                 evaluator.evaluate(*eCurrent, *sCurrent);
    00079
    00080                                 if (evaluator.betterThan(*eCurrent, e))
    00081                                 {
    00082                                         e = *eCurrent;
    00083                                         s = *sCurrent;
    00084                                         delete sCurrent;
    00085                                         delete eCurrent;
    00086
    00087                                         if (evaluator.betterThan(e, *eStar))
    00088                                         {
    00089                                                 delete sStar;
    00090                                                 sStar = &s.clone();
    00091                                                 delete eStar;
    00092                                                 eStar = &e.clone();
    00093
    00094                                                 cout << "Best fo: " << e.evaluation() << " Found on Iter = " << iterT << " and T = " << T << endl;
    00095                                         }
    00096                                 }
    00097                                 else
    00098                                 {
    00099                                         double x = rg.rand01();
    00100                                         double delta = fabs(eCurrent->evaluation() - e.evaluation());
    00101
    00102                                         if (x < exp(-delta / T))
    00103                                         {
    00104                                                 s = *sCurrent;
    00105                                                 e = *eCurrent;
    00106                                                 delete sCurrent;
    00107                                                 delete eCurrent;
    00108                                         }
    00109                                         else
    00110                                         {
    00111                                                 delete sCurrent;
    00112                                                 delete eCurrent;
    00113                                         }
    00114                                 }
    00115
    00116                                 iterT++;
    00117                         }
    00118                         T = alpha * T;
    00119                         iterT = 0;
    00120                 }
    00121
    00122                 s = *sStar;
    00123                 e = *eStar;
    00124                 delete sStar;
    00125                 delete eStar;
    00126         }
    00127
    00128 };
    00129
    00130 /*
    00131
    00132  Procedure originally proposed by Kirkpatrick et al.
    00133
    00134  S. Kirkpatrick, D.C. Gellat, and M.P. Vecchi. Optimization by Simulated Annealing.
    00135  Science, 220:671–680, 1983.
    00136
    00137  LATEX:
    00138
    00139  */
    00140
    00141 #endif /*OPTFRAME_BSA_HPP_*/

All Classes Functions