- Main Page
- Classes
- Files

- File List

# OptFrame/Parallel/OptFrameMapReduce.hpp

    00001 #ifndef OptFrameMapReduce_HPP_
    00002 #define OptFrameMapReduce_HPP_
    00003
    00004 #include "MapReduce++/MaPI/MaPI.h"
    00005
    00006 #include "../Heuristic.hpp"
    00007 #include "../NSEnum.hpp"
    00008 #include "../Evaluator.hpp"
    00009
    00010 // OptFrame MapReduce Types
    00011
    00012 //typedef R KeyA;                               // initial solution // TODO memory for reevaluation
    00013 //typedef (int,(double,double)) A;              // search subspace index (timelimit,target_f)
    00014 //typedef int KeyB;                             // dummy unique key (integer -1)
    00015 //typedef pair<R, double> B;                    // best move in each subspace and its cost // TODO //typedef pair<Move<R, M>*, double> B;       // best move in each subspace and its cost
    00016 //typedef R C;                                  // best solution among all subspaces
    00017
    00018 typedef pair<int,pair<double,double> > RankAndStop; // A -> int double double
    00019
    00020 template<class R, class M>
    00021 class MyMaPISerializer : public MaPI_Serializer<R, RankAndStop, int, pair<R, double> , R>
    00022 {
    00023 public:
    00024
    00025         virtual R KeyA_fromString(string s) = 0;
    00026         virtual string KeyA_toString(R o) = 0;
    00027
    00028         virtual RankAndStop A_fromString(string s) = 0;
    00029         virtual string A_toString(RankAndStop o) = 0;
    00030
    00031         virtual int KeyB_fromString(string s) = 0;
    00032         virtual string KeyB_toString(int o) = 0;
    00033
    00034         virtual pair<R, double> B_fromString(string s) = 0;
    00035         virtual string B_toString(pair<R, double> o) = 0;
    00036
    00037         virtual R C_fromString(string s) = 0;
    00038         virtual string C_toString(R o) = 0;
    00039
    00040 };
    00041
    00042
    00043 template<class R, class M>
    00044 class MyMaPIMapper: public MaPI_Mapper<R, RankAndStop, int, pair<R, double> , R>
    00045 {
    00046 private:
    00047         Evaluator<R, M>& eval;
    00048         Heuristic<R, M>* hmap;
    00049 public:
    00050         MyMaPIMapper(MaPI_MapReduce<R, RankAndStop, int, pair<R, double> , R> * mr, MaPI_Serializer<R, RankAndStop, int, pair<R, double> , R> * s, Evaluator<R, M>& _eval) :
    00051                 MaPI_Mapper<R, RankAndStop, int, pair<R, double> , R> (mr,s), eval(_eval)
    00052         {
    00053         }
    00054
    00055         void setHeuristic(Heuristic<R, M>* h) {hmap = h;}
    00056
    00057         virtual vector<pair<int, pair<R, double> > > map(pair<R, RankAndStop> a) // TODO
    00058         {
    00059                 cout << "[MyMaPIMapper::map] begin " << a.second.first << endl; //exit(1);
    00060                 vector<pair<int, pair<R, double> > > m;
    00061
    00062                 Solution<R> s(a.first);
    00063
    00064                 hmap->exec(s,a.second.second.first,a.second.second.second);
    00065
    00066                 Evaluation<M> e = eval.evaluate(s);
    00067
    00068                 R mapped = R(s.getR());
    00069
    00070                 m.push_back( make_pair(-1, make_pair( mapped , e.evaluation() ) ) );
    00071                 cout << "[MyMaPIMapper::map] end " << a.second << " " << m << endl;
    00072
    00073                 return m;
    00074         }
    00075 };
    00076
    00077 template<class R, class M>
    00078 class MyMaPIReducer: public MaPI_Reducer<R, RankAndStop, int, pair<R, double> , R>
    00079 {
    00080 private:
    00081         Evaluator<R, M>& eval;
    00082         Heuristic<R, M>* hreduce;
    00083 public:
    00084         MyMaPIReducer(MaPI_MapReduce<R, RankAndStop, int, pair<R, double> , R> * mr, MaPI_Serializer<R, RankAndStop, int, pair<R, double> , R> * s,Evaluator<R, M>& _eval) :
    00085                 MaPI_Reducer<R, RankAndStop, int, pair<R, double> , R> (mr,s),eval(_eval),hreduce(NULL)
    00086         {
    00087         }
    00088
    00089         void setHeuristic(Heuristic<R, M>* h) {hreduce = h;}
    00090
    00091         virtual pair<int, R> reduce(pair<int, vector<pair<R, double> > > bs)
    00092         {
    00093                 //cout << "[MyMaPIReducer::reduce] begin " << bs.first << endl;
    00094
    00095                 //
    00096
    00097                 R reduced;
    00098
    00099                 if (hreduce == NULL) { // reduction best solution
    00100
    00101                         int bestIndex = 0;
    00102                         double bestCost = bs.second[bestIndex].second;
    00103
    00104                         for (unsigned i = 0 ; i < bs.second.size() ; i++)
    00105                         {
    00106                                 if ( eval.betterThan(bs.second[i].second,bestCost) )
    00107                                 {
    00108                                         bestIndex = i;
    00109                                         bestCost = bs.second[i].second;
    00110                                 }
    00111                         }
    00112
    00113                         reduced = bs.second[bestIndex].first;
    00114                 }
    00115                 else
    00116                 {
    00117                         // reduction based on a heuristic method
    00118
    00119                         if (bs.second.size() == 0) return pair<int, R> (bs.first, R());
    00120
    00121                         Population<R> pop;
    00122                         for (unsigned i = 0 ; i < bs.second.size() ; i++) pop.push_back( * new TestSolution<R>(bs.second[i].first) );
    00123
    00124                         //Population<R> & popReduced =
    00125                         hreduce->exec(pop, 60, 0); // TODO considerar tempo
    00126
    00127                         if (pop.size() == 0) return pair<int, R> (bs.first, R());
    00128                         if (pop.size() == 1) return pair<int, R> (bs.first, pop.at(0).getR());
    00129
    00130                         Evaluation<M>& ebest = eval.evaluate(pop.at(0));
    00131                         unsigned bestIndex = 0;
    00132
    00133                         for (unsigned i = 0 ; i < pop.size() ; i++) // TODO
    00134                         {
    00135                                 Evaluation<M>& e = eval.evaluate(pop.at(i).getR());
    00136
    00137                                 if ( eval.betterThan(e,ebest) )
    00138                                 {
    00139                                         bestIndex = i;
    00140                                         ebest = e;
    00141                                         delete &e;
    00142                                 }
    00143                         }
    00144
    00145                         reduced = pop.at(bestIndex).getR();
    00146
    00147                         //for (unsigned i = 0 ; i < popReduced.size() ; i++) delete &popReduced.at(i);
    00148                 }
    00149
    00150                 //cout << "[MyMaPIReducer::reduce] end " << bs.first << endl;
    00151
    00152                 return pair<int, R> (bs.first, reduced);
    00153         }
    00154 };
    00155
    00156 template<class R, class M = OPTFRAME_DEFAULT_MEMORY>
    00157 class OptFrameMapReduce: public Heuristic<R, M>
    00158 {
    00159 private:
    00160         Evaluator<R, M>& evaluator;
    00161
    00162         MyMaPISerializer<R, M> &serializer;
    00163         MaPI_MapReduce<R, RankAndStop, int, pair<R, double> , R> &mapReduce;
    00164         MyMaPIMapper<R, M> &mapper;
    00165         MyMaPIReducer<R, M> &reducer;
    00166
    00167 public:
    00168
    00169         using Heuristic<R, M>::exec; // prevents name hiding
    00170
    00171         OptFrameMapReduce(
    00172                         MyMaPISerializer<R, M> &_serializer,
    00173                         MaPI_MapReduce<R, RankAndStop, int, pair<R, double> , R> &_mapReduce,
    00174                         MyMaPIMapper<R, M> &_mapper,
    00175                         MyMaPIReducer<R, M> &_reducer,
    00176                         Evaluator<R, M>& _eval) :
    00177                                 serializer(_serializer),mapReduce(_mapReduce),mapper(_mapper),reducer(_reducer),
    00178                                 evaluator(_eval)
    00179         {
    00180         }
    00181
    00182         virtual void exec(Solution<R>& s, double timelimit, double target_f)
    00183         {
    00184                 Evaluation<M>& e = evaluator.evaluate(s.getR());
    00185                 exec(s, e, timelimit, target_f);
    00186                 delete &e;
    00187         }
    00188
    00189         virtual void exec(Solution<R>& s, Evaluation<M>& e, double timelimit, double target_f)
    00190         {
    00191                 vector< pair<R,RankAndStop> > input;
    00192                 for (int i = 0 ; i < mapReduce.getMPISize()-1 ; i++)
    00193                         input.push_back(make_pair(s.getR(),make_pair(i,make_pair(timelimit,target_f))));
    00194
    00195                 vector< pair<int,R> > output = mapReduce.run(mapper,reducer,input);
    00196
    00197                 Solution<R>& s1 = s.clone();
    00198                 if (output.size()>0)
    00199                         s1.setR(output[0].second);
    00200
    00201                 Evaluation<M>& e1 = evaluator.evaluate(s1);
    00202
    00203                 if(evaluator.betterThan(e1,e))
    00204                 {
    00205                         s = s1;
    00206                         e = e1;
    00207                         e.print();
    00208                 }
    00209
    00210                 delete &s1;
    00211                 delete &e1;
    00212         }
    00213 };
    00214
    00215 #endif /*OptFrameMapReduce_HPP_*/

All Classes Functions