- Main Page
- Classes
- Files

- File List

# OptFrame/Heuristic/IteratedLocalSearch.hpp

    00001 #ifndef OPTFRAME_ILS_HPP_
    00002 #define OPTFRAME_ILS_HPP_
    00003
    00004 #include <math.h>
    00005 #include <vector>
    00006
    00007 #include "../Heuristic.hpp"
    00008 #include "../Evaluator.hpp"
    00009
    00010 template<class H, class R, class M = OPTFRAME_DEFAULT_MEMORY>
    00011 class IteratedLocalSearch: public Heuristic<R, M>
    00012 {
    00013 protected:
    00014         Evaluator<R, M>& evaluator;
    00015
    00016 public:
    00017
    00018         using Heuristic<R, M>::exec; // prevents name hiding
    00019
    00020         IteratedLocalSearch(Evaluator<R, M>& _evaluator) :
    00021                 evaluator(_evaluator)
    00022         {
    00023         }
    00024
    00025         virtual H& initializeHistory() = 0;
    00026
    00027         virtual void localSearch(Solution<R>& s, Evaluation<M>& e, double timelimit, double target_f) = 0;
    00028
    00029         virtual void perturbation(Solution<R>& s, Evaluation<M>& e, double timelimit, double target_f, H& history) = 0;
    00030
    00031         virtual Solution<R>& acceptanceCriterion(const Solution<R>& s1, const Solution<R>& s2, H& history) = 0;
    00032
    00033         virtual bool terminationCondition(H& history) = 0;
    00034
    00035         void exec(Solution<R>& s, double timelimit, double target_f)
    00036         {
    00037                 Evaluation<M>& e = evaluator.evaluate(s.getR());
    00038                 exec(s, e, timelimit, target_f);
    00039                 delete &e;
    00040         }
    00041
    00042         void exec(Solution<R>& s, Evaluation<M>& e, double timelimit, double target_f)
    00043         {
    00044                 cout << "ILS exec(" << target_f << "," << timelimit << ")" << endl;
    00045
    00046                 Timer tnow;
    00047
    00048                 H* history = &initializeHistory();
    00049
    00050                 // 's0' <- GenerateSolution
    00051                 // 's*' <- localSearch 's'
    00052
    00053
    00054                 localSearch(s, e, (timelimit - (tnow.now())), target_f);
    00055
    00056                 Solution<R>* sStar = &s.clone();
    00057                 Evaluation<M>* eStar = &e.clone();
    00058
    00059                 cout << "ILS starts: ";
    00060                 e.print();
    00061
    00062                 do
    00063                 {
    00064                         Solution<R>* s1 = &sStar->clone();
    00065                         Evaluation<M>* e1 = &eStar->clone();
    00066
    00067                         perturbation(*s1, *e1, (timelimit - (tnow.now())), target_f, *history);
    00068
    00069                         localSearch(*s1, *e1, (timelimit - (tnow.now())), target_f);
    00070
    00071                         Solution<R>* s2 = s1;
    00072                         Evaluation<M>* e2 = e1;
    00073
    00074                         Solution<R>* sStar1 = &acceptanceCriterion(*sStar, *s2, *history);
    00075
    00076                         delete sStar;
    00077                         delete eStar;
    00078                         delete s2;
    00079                         delete e2;
    00080
    00081                         sStar = sStar1;
    00082                         eStar = &evaluator.evaluate(*sStar);
    00083
    00084                 } while (evaluator.betterThan(target_f, eStar->evaluation()) && !terminationCondition(*history) && ((tnow.now()) < timelimit));
    00085
    00086                 e = *eStar;
    00087                 s = *sStar;
    00088
    00089                 delete eStar;
    00090                 delete sStar;
    00091
    00092                 delete history;
    00093         }
    00094 };
    00095
    00096 #endif /*OPTFRAME_ILS_HPP_*/

All Classes Functions