- Main Page
- Classes
- Files

- File List

# OptFrame/Heuristic/RVND.hpp

    00001 #ifndef RVND_HPP_
    00002 #define RVND_HPP_
    00003
    00004 #include <algorithm>
    00005
    00006 #include "../Heuristic.hpp"
    00007 #include "../Evaluator.hpp"
    00008 #include "../RandGen.hpp"
    00009
    00010 template<class R, class M = OPTFRAME_DEFAULT_MEMORY>
    00011 class RVND: public Heuristic<R, M>
    00012 {
    00013 public:
    00014         using Heuristic<R, M>::exec; // prevents name hiding
    00015
    00016         RVND(Evaluator<R, M>& _ev, vector<Heuristic<R, M>*> _neighbors, RandGen& _rg) :
    00017                 ev(_ev), neighbors(_neighbors), rg(_rg)
    00018         {
    00019         }
    00020
    00021         virtual void exec(Solution<R>& s, double timelimit, double target_f)
    00022         {
    00023                 Evaluation<M>& e = ev.evaluate(s.getR());
    00024                 exec(s, e, timelimit, target_f);
    00025                 delete &e;
    00026         }
    00027
    00028         virtual void exec(Solution<R>& s, Evaluation<M>& e, double timelimit,
    00029                         double target_f)
    00030         {
    00031
    00032                 long tini = time(NULL);
    00033
    00034                 rg.shuffle(neighbors); // shuffle elements
    00035
    00036                 int r = neighbors.size();
    00037
    00038                 int k = 1;
    00039
    00040                 long tnow = time(NULL);
    00041                 while (ev.betterThan(target_f, e.evaluation()) && (k <= r) && ((tnow - tini) < timelimit))
    00042                 {
    00043                         Solution<R>* s0 = &s.clone();
    00044                         Evaluation<M>* e0 = &e.clone();
    00045
    00046                         neighbors[k - 1]->exec(*s0, *e0, timelimit, target_f);
    00047                         if (ev.betterThan(*s0, s))
    00048                         {
    00049                                 s = *s0;
    00050                                 e = *e0;
    00051                                 delete s0;
    00052                                 delete e0;
    00053                                 k = 1;
    00054                         }
    00055                         else
    00056                         {
    00057                                 delete s0;
    00058                                 delete e0;
    00059                                 k = k + 1;
    00060                         }
    00061                         ev.evaluate(e, s);
    00062
    00063                         tnow = time(NULL);
    00064                 }
    00065
    00066         }
    00067
    00068 private:
    00069         vector<Heuristic<R, M>*> neighbors;
    00070         Evaluator<R, M>& ev;
    00071         RandGen& rg;
    00072 };
    00073
    00074 #endif /*RVND_HPP_*/

All Classes Functions