- Main Page
- Classes
- Files

- File List

# OptFrame/Heuristic/IntensifiedIteratedLocalSearch.hpp

    00001 #ifndef OPTFRAME_IILS_HPP_
    00002 #define OPTFRAME_IILS_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 IntensifiedIteratedLocalSearch: 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         IntensifiedIteratedLocalSearch(Evaluator<R, M>& _evaluator) :
    00021                 evaluator(_evaluator)
    00022         {
    00023         }
    00024
    00025         Evaluator<R, M>& getEvaluator()
    00026         {
    00027                 return evaluator;
    00028         }
    00029
    00030         virtual H& initializeHistory() = 0;
    00031
    00032         virtual void localSearch(Solution<R>& s, Evaluation<M>& e, double timelimit, double target_f) = 0;
    00033
    00034         virtual void intensification(Solution<R>& s, Evaluation<M>& e, double timelimit, double target_f, H& history) = 0;
    00035
    00036         virtual void perturbation(Solution<R>& s, Evaluation<M>& e, double timelimit, double target_f, H& history) = 0;
    00037
    00038         virtual Solution<R>& acceptanceCriterion(const Solution<R>& s1, const Solution<R>& s2, H& history) = 0;
    00039
    00040         virtual bool terminationCondition(H& history) = 0;
    00041
    00042         void exec(Solution<R>& s, double timelimit, double target_f)
    00043         {
    00044                 Evaluation<M>& e = evaluator.evaluate(s.getR());
    00045                 exec(s, e, timelimit, target_f);
    00046                 delete &e;
    00047         }
    00048
    00049         void exec(Solution<R>& s, Evaluation<M>& e, double timelimit, double target_f)
    00050         {
    00051                 cout << "ILS exec(" << target_f << "," << timelimit << ")" << endl;
    00052
    00053                 Timer tnow;
    00054
    00055                 H* history = &initializeHistory();
    00056
    00057                 // 's0' <- GenerateSolution
    00058                 // 's*' <- localSearch 's'
    00059
    00060
    00061                 localSearch(s, e, (timelimit - (tnow.now())), target_f);
    00062
    00063                 Solution<R>* sStar = &s.clone();
    00064                 Evaluation<M>* eStar = &e.clone();
    00065
    00066                 cout << "ILS starts: ";
    00067                 e.print();
    00068
    00069                 do
    00070                 {
    00071                         Solution<R>* s1 = &sStar->clone();
    00072                         Evaluation<M>* e1 = &eStar->clone();
    00073
    00074                         perturbation(*s1, *e1, (timelimit - (tnow.now())), target_f, *history);
    00075
    00076                         localSearch(*s1, *e1, (timelimit - (tnow.now())), target_f);
    00077
    00078                         intensification(*s1, *e1, (timelimit - (tnow.now())), target_f, *history);
    00079
    00080                         Solution<R>* s2 = s1;
    00081                         Evaluation<M>* e2 = e1;
    00082
    00083                         Solution<R>* sStar1 = &acceptanceCriterion(*sStar, *s2, *history);
    00084
    00085                         delete sStar;
    00086                         delete eStar;
    00087                         delete s2;
    00088                         delete e2;
    00089
    00090                         sStar = sStar1;
    00091                         eStar = &evaluator.evaluate(*sStar);
    00092
    00093                 } while (evaluator.betterThan(target_f, eStar->evaluation()) && !terminationCondition(*history) && ((tnow.now()) < timelimit));
    00094
    00095                 e = *eStar;
    00096                 s = *sStar;
    00097
    00098                 delete eStar;
    00099                 delete sStar;
    00100
    00101                 delete history;
    00102         }
    00103 };
    00104
    00105 #endif /*OPTFRAME_IILS_HPP_*/

All Classes Functions