- Main Page
- Classes
- Files

- File List

# OptFrame/Heuristic/PathRelinking.hpp

    00001 #ifndef OPTFRAME_PATHRELINKING_HPP_
    00002 #define OPTFRAME_PATHRELINKING_HPP_
    00003
    00004 #include "../Heuristic.hpp"
    00005
    00006 template<class R, class M = OPTFRAME_DEFAULT_MEMORY>
    00007 class PathRelinking: public Heuristic<R, M>
    00008 {
    00009         typedef vector<Evaluation<M>*> FitnessValues;
    00010         typedef const vector<const Evaluation<M>*> ConstFitnessValues;
    00011
    00012 protected:
    00013         Evaluator<R, M>& evaluator;
    00014         unsigned int k;
    00015         bool forward;
    00016         Heuristic<R, M>& localSearch;
    00017
    00018 public:
    00019
    00020         using Heuristic<R, M>::exec; // prevents name hiding
    00021
    00022         PathRelinking(Heuristic<R, M>& localSearch, Evaluator<R, M>& evaluator, int k = 1, bool forward = false) :
    00023                 localSearch(localSearch), evaluator(evaluator), k(k), forward(forward)
    00024         {
    00025         }
    00026
    00027         virtual ~PathRelinking()
    00028         {
    00029         }
    00030
    00031         virtual vector<pair<Move<R, M>*, double> >& symmetric_difference(Solution<R>& x, Evaluation<M>& e_x, const Solution<R>& xt,
    00032                         const Evaluation<M>& e_xt) = 0;
    00033
    00034         virtual void update_delta(vector<pair<Move<R, M>*, double> >& delta, int index_best, Solution<R>& x, Evaluation<M>& e_x, const Solution<R>& xt,
    00035                         const Evaluation<M>& e_xt)
    00036         {
    00037                 delta.erase(delta.begin() + index_best);
    00038         }
    00039
    00040         // path-relinking from starting solution 'xs' to target solution 'xt'
    00041         virtual pair<Solution<R>&, Evaluation<M>&>& path_relinking(const Solution<R>& xs, const Evaluation<M>& e_xs, const Solution<R>& xt,
    00042                         const Evaluation<M>& e_xt, double timelimit, double target_f)
    00043         {
    00044                 cout << "path_relinking " << (forward ? "forward" : "backward") << endl;
    00045                 cout << "from: ";
    00046                 e_xs.print();
    00047                 cout << "to: ";
    00048                 e_xt.print();
    00049
    00050                 Solution<R>& x = xs.clone();
    00051                 Evaluation<M>& e_x = e_xs.clone();
    00052
    00053                 // compute the symmetric difference 'delta' between xs and xt
    00054                 vector<pair<Move<R, M>*, double> >& delta = symmetric_difference(x, e_x, xt, e_xt);
    00055
    00056                 // compute f*
    00057                 Solution<R>* s_star;
    00058                 Evaluation<M>* e_star;
    00059
    00060                 if (evaluator.betterThan(e_xs, e_xt))
    00061                 {
    00062                         e_star = &e_xs.clone();
    00063                         s_star = &xs.clone();
    00064                 }
    00065                 else
    00066                 {
    00067                         e_star = &e_xt.clone();
    00068                         s_star = &xt.clone();
    00069                 }
    00070
    00071                 // while 'delta' > 0, i.e., 'xs' are 'xt' are different
    00072                 while (delta.size() > 0)
    00073                 {
    00074                         /*
    00075                          cout << "\nNOVA ITERACAO = |delta| = " << delta.size() << endl;
    00076                          cout << "waiting...";
    00077                          getchar();
    00078                          */
    00079
    00080                         //1. find best move
    00081                         unsigned index_best = 0;
    00082
    00083                         for (unsigned i = 1; i < delta.size(); i++)
    00084                                 if (evaluator.betterThan(delta[i].second, delta[index_best].second))
    00085                                         index_best = i;
    00086
    00087                         Move<R, M>* m_star = delta[index_best].first;
    00088                         double f_m_star = delta[index_best].second;
    00089
    00090                         //2. update 'x' and 'e_x'
    00091                         m_star->apply(e_x, x);
    00092                         //m_star->print();
    00093                         //cout << "FO ATUAL ANTES BUSCA= " << evaluator.evaluate(x).evaluation() << endl;
    00094                         localSearch.exec(x, e_x, timelimit, target_f);
    00095                         //cout << "FO ATUAL= " << evaluator.evaluate(x).evaluation() << endl;
    00096
    00097                         evaluator.evaluate(e_x, x);
    00098
    00099                         //3. update 'delta'
    00100                         update_delta(delta, index_best, x, e_x, xt, e_xt);
    00101                         //delta.erase(delta.begin() + index_best);
    00102
    00103                         //4. compare with 'x*'
    00104                         if (evaluator.betterThan(e_x, *e_star))
    00105                         {
    00106                                 delete e_star;
    00107                                 delete s_star;
    00108
    00109                                 e_star = &e_x.clone();
    00110                                 s_star = &x.clone();
    00111                         }
    00112                 }
    00113
    00114                 delete &x;
    00115                 delete &e_x;
    00116
    00117                 pair<Solution<R>&, Evaluation<M>&>& r = *new pair<Solution<R>&, Evaluation<M>&> (*s_star, *e_star);
    00118                 cout << "best path_relinking: ";
    00119                 e_star->print();
    00120                 //getchar();
    00121                 return r;
    00122         }
    00123
    00124         // rewritting search method for efficiency purposes!
    00125         // safe use of const_cast
    00126         Population<R>& search(const Population<R>& p, double timelimit = 100000000, double target_f = 0)
    00127         {
    00128                 int p_size = p.size();
    00129
    00130                 Population<R>* v = new Population<R> ;
    00131
    00132                 for (unsigned i = 0; i < p.size(); i++)
    00133                         v->push_back(const_cast<Solution<R>&> (p.at(i)));
    00134
    00135                 exec(*v, timelimit, target_f);
    00136
    00137                 for (int i = 0; i < p_size; i++)
    00138                         v->remove(0);
    00139
    00140                 return *v;
    00141         }
    00142
    00143         void exec(Population<R>& p, double timelimit, double target_f)
    00144         {
    00145                 vector<Evaluation<M>*>& ev = *new vector<Evaluation<M>*> ;
    00146                 for (int i = 0; i < p.size(); i++)
    00147                         ev.push_back(&evaluator.evaluate(p.at(i)));
    00148
    00149                 exec(p, ev, timelimit, target_f);
    00150
    00151                 for (int i = 0; i < ev.size(); i++)
    00152                         delete ev[i];
    00153                 delete &ev;
    00154         }
    00155
    00156         // rewritting search method for efficiency purposes!
    00157         // safe use of const_cast
    00158         pair<Population<R>&, FitnessValues&>& search(const Population<R>& p, ConstFitnessValues& ev, double timelimit = 100000000, double target_f = 0)
    00159         {
    00160                 Population<R>* p2 = new Population<R> ;
    00161                 for (unsigned i = 0; i < p.size(); i++)
    00162                         p2->push_back(const_cast<Solution<R>&> (p.at(i)));
    00163
    00164                 vector<Evaluation<M>*>* ev2 = new vector<Evaluation<M>*> ;
    00165                 for (unsigned i = 0; i < p.size(); i++)
    00166                         ev2->push_back(const_cast<Evaluation<M>*> (ev[i]));
    00167
    00168                 exec(*p2, *ev2, timelimit, target_f);
    00169
    00170                 // update and return correct values
    00171
    00172                 return *new pair<Population<R>&, FitnessValues&> (*p2, *ev2);
    00173         }
    00174
    00175         void exec(Population<R>& p, vector<Evaluation<M>*>& ev, double timelimit, double target_f)
    00176         {
    00177                 if (p.size() <= 1)
    00178                 {
    00179                         cout << "Path Relinking exec(p&,e&) warning: empty or only one solution in the pool!" << endl;
    00180                         return;
    00181                 }
    00182
    00183                 long tini = time(NULL);
    00184
    00185                 cout << "Path Relinking starts!" << endl;
    00186
    00187                 vector<Solution<R>*> new_s;
    00188                 vector<Evaluation<M>*> new_e;
    00189
    00190                 int iter = 0;
    00191
    00192                 long tnow = time(NULL);
    00193
    00194                 while (iter < k && ((tnow - tini) < timelimit))
    00195                 {
    00196                         int x1 = rand() % p.size();
    00197                         // different values of x, for efficiency purposes
    00198                         int x2 = x1;
    00199                         while (x2 == x1)
    00200                                 x2 = rand() % p.size();
    00201
    00202                         if (forward && evaluator.betterThan(ev[x1]->evaluation(), ev[x2]->evaluation()))
    00203                         {
    00204                                 int aux = x1;
    00205                                 x1 = x2;
    00206                                 x2 = aux;
    00207                         }
    00208
    00209                         if ((!forward) && evaluator.betterThan(ev[x2]->evaluation(), ev[x1]->evaluation()))
    00210                         {
    00211                                 int aux = x1;
    00212                                 x1 = x2;
    00213                                 x2 = aux;
    00214                         }
    00215
    00216                         pair<Solution<R> &, Evaluation<M>&>& ret_path = path_relinking(p.at(x1), *ev[x1], p.at(x2), *ev[x2], timelimit, target_f);
    00217
    00218                         new_s.push_back(&ret_path.first);
    00219                         new_e.push_back(&ret_path.second);
    00220
    00221                         delete &ret_path;
    00222
    00223                         tnow = time(NULL);
    00224                         iter++;
    00225                 }
    00226
    00227                 for(int i=0;i<new_s.size();i++)
    00228                         p.push_back(*new_s[i]);
    00229
    00230                 new_s.clear();
    00231                 ev.insert(ev.end(), new_e.begin(), new_e.end());
    00232                 new_e.clear();
    00233         }
    00234
    00235 };
    00236
    00237 #endif /*OPTFRAME_PATHRELINKING_HPP_*/

All Classes Functions