EasyLocal++ Documentation


 
Main Page   Modules   Namespace List   Class Hierarchy   Alphabetical List   Compound List   File List   Namespace Members   Compound Members   File Members   Related Pages  

EasyLocalTemplates.cpp

Go to the documentation of this file.
00001 
00017 namespace easylocal {
00018 
00019   // State Manager functions
00020 
00028   template <class Input, class State>
00029   fvalue StateManager<Input,State>::SampleState(State &st, int samples)
00030   { 
00031     int s = 1;
00032     RandomState(st);
00033     fvalue cost = CostFunction(st);
00034     State best_state = st;
00035     fvalue best_cost = cost;
00036     while (s < samples)
00037       { 
00038         RandomState(st);
00039         cost = CostFunction(st);
00040         if (cost < best_cost)
00041           { 
00042             best_state = st;
00043             best_cost = cost;
00044           }
00045         s++;
00046       }
00047     st = best_state;
00048     return best_cost;
00049   }
00050 
00060   template <class Input, class State>
00061   fvalue StateManager<Input,State>::ImprovedSampleState(State &st, int samples, Runner<Input,State>* r)
00062   { // same of SampleState, except that each sample is let run using r
00063     // before comparing its value
00064     int s = 1;
00065     RandomState(st);
00066     r->SetCurrentState(st);
00067     r->Go();
00068     st = r->GetCurrentState();
00069     fvalue cost = CostFunction(st);
00070     State best_state = st;
00071     fvalue best_cost = cost;
00072     do 
00073       { 
00074         cost = CostFunction(st);
00075         if (cost < best_cost)
00076           { 
00077             best_state = st;
00078             best_cost = cost;
00079           }
00080         RandomState(st);
00081         r->SetCurrentState(st);
00082         r->Go();
00083         st = r->GetCurrentState();
00084         s++;
00085       }
00086     while (s <= samples);
00087     st = best_state;
00088     return best_cost;
00089   }
00090 
00098   template <class Input, class State>
00099   fvalue StateManager<Input,State>::CostFunction(const State& st) const 
00100   { return HARD_WEIGHT * Violations(st) + Objective(st); } 
00101 
00107   template <class Input, class State>
00108   void StateManager<Input,State>::PrintState(const State& st) const
00109   {
00110     std::cout << st << std::endl;
00111     std::cout << "Total cost : " << CostFunction(st) << std::endl;
00112     std::cout << "    Violations : " << Violations(st) << std::endl;
00113     std::cout << "    Objective : " << Objective(st) << std::endl;
00114   }
00115 
00123   template <class Input, class State>  
00124   fvalue StateManager<Input,State>::Violations(const State& st) const
00125   { 
00126     std::cout << "Warning: violations function not implemented yet!" << std::endl;
00127     return 0; 
00128   }
00129 
00137   template <class Input, class State>  
00138   fvalue StateManager<Input,State>::Objective(const State& st) const
00139   { 
00140     std::cout << "Warning: violations function not implemented yet!" << std::endl;
00141     return 0; 
00142   }
00143  
00149   template <class Input, class State>  
00150   void StateManager<Input,State>::SetInput(Input* in) 
00151   { p_in = in; }
00152 
00158   template <class Input, class State>  
00159   Input* StateManager<Input,State>::GetInput() 
00160   { return p_in; }
00161 
00166   template <class Input, class State>  
00167   void StateManager<Input,State>::Check() const
00168   { assert(p_in != NULL); }
00169 
00175   template <class Input, class State>  
00176   StateManager<Input,State>::StateManager(Input* in) 
00177     : p_in(in)  
00178   {}
00179 
00180   // Output Manager functions
00181 
00182 
00189   template <class Input, class Output, class State>
00190   void OutputManager<Input,Output,State>::ReadState(State &st, std::istream &is) const
00191   {
00192     Output out(p_in);
00193     is >> out;
00194     InputState(st,out);
00195   }
00196 
00203   template <class Input, class Output, class State>
00204   void OutputManager<Input,Output,State>::WriteState(const State &st, std::ostream &os) const
00205   {
00206     Output out(p_in);
00207     OutputState(st,out);  
00208     os << out;
00209   }
00210 
00216   template <class Input, class Output, class State>
00217   void OutputManager<Input,Output,State>::SetInput(Input* in) 
00218   { p_in = in; }
00219 
00225   template <class Input, class Output, class State>
00226   Input* OutputManager<Input,Output,State>::GetInput() 
00227   { return p_in; }
00228   
00233   template <class Input, class Output, class State>  
00234   void OutputManager<Input,Output,State>::Check() const
00235   { 
00236     assert(p_in != NULL && p_sm->GetInput() == p_in); 
00237   }
00238 
00239   // Prohibition Manager functions
00240   // up to now, the only actual prohibition manager is the tabu list manager
00241 
00249   template <class Move>
00250   TabuListManager<Move>::TabuListManager(int min, int max)
00251     : min_tenure(min), max_tenure(max), iter(0)
00252   { }
00253 
00254   
00262   template <class Move>
00263   void TabuListManager<Move>::InsertMove(const Move& mv, fvalue mv_cost, fvalue curr, fvalue best)
00264   { 
00265     InsertIntoList(mv); 
00266     UpdateAspirationFunction(mv_cost,curr,best); 
00267   }
00268 
00278   template <class Move>
00279   bool TabuListManager<Move>::ProhibitedMove(const Move& mv, fvalue mv_cost, fvalue curr, fvalue best) const
00280   { return ListMember(mv) && !Aspiration(mv,mv_cost,curr,best); }
00281 
00285   template <class Move>
00286   void TabuListManager<Move>::Clean()
00287   { tlist.clear(); }
00288 
00296   template <class Move>
00297   bool TabuListManager<Move>::ListMember(const Move& mv) const
00298   {
00299     std::list<ListItem<Move> >::const_iterator p = tlist.begin();
00300     while (p != tlist.end())
00301       {
00302         if (Inverse(mv,p->elem))
00303           return true;
00304         else
00305           p++;
00306       }
00307     return false;
00308   }
00309 
00316   template <class Move>
00317   std::ostream& operator<<(std::ostream& os, const TabuListManager<Move>& tl)
00318   {
00319     std::list<ListItem<Move> >::const_iterator p = tl.tlist.begin();
00320     while (p != tl.tlist.end())
00321       {
00322         os << p->elem << " (" << p->out_iter - tl.iter << ")" << std::endl;
00323         p++;
00324       }
00325     return os;
00326   }
00327 
00339   template <class Move>
00340   bool TabuListManager<Move>::Aspiration(const Move& mv, fvalue mv_cost, fvalue curr, fvalue best) const 
00341   { return curr + mv_cost < best; }
00342 
00349   template <class Move>
00350   void TabuListManager<Move>::InsertIntoList(const Move& mv)
00351   {
00352     int tenure = Random(min_tenure,max_tenure);
00353     ListItem<Move> li(mv, iter+tenure);
00354     tlist.push_front(li);
00355         
00356     std::list<ListItem<Move> >::iterator p = tlist.begin();
00357     while (p != tlist.end())
00358       if (p->out_iter == iter)
00359         p = tlist.erase(p);
00360       else
00361         p++;
00362     iter++;
00363   }
00364 
00365   // Neighborhood explorer functions
00366 
00374   template <class Input, class State, class Move>  
00375   NeighborhoodExplorer<Input,State,Move>::NeighborhoodExplorer(StateManager<Input,State>* sm, Input* in) 
00376     :  p_sm(sm), p_in(in), p_pm(NULL)
00377   {}
00378 
00388   template <class Input, class State, class Move>  
00389   NeighborhoodExplorer<Input,State,Move>::NeighborhoodExplorer(StateManager<Input,State>* sm, ProhibitionManager<Move>* pm, Input* in) 
00390     :  p_sm(sm), p_in(in), p_pm(pm)
00391   {}
00392 
00403   template <class Input, class State, class Move>  
00404   fvalue NeighborhoodExplorer<Input,State,Move>::DeltaCostFunction(const State& st, const Move & mv)
00405   { return HARD_WEIGHT * DeltaViolations(st,mv) + DeltaObjective(st,mv); }
00406 
00412   template <class Input, class State, class Move>  
00413   void NeighborhoodExplorer<Input,State,Move>::SetProhibitionManager(ProhibitionManager<Move>* pm) 
00414   { p_pm = pm; }
00415 
00416 
00426   template <class Input, class State, class Move>  
00427   fvalue NeighborhoodExplorer<Input,State,Move>::BestMove(const State &st, Move& mv)
00428   {  
00429     FirstMove(st,mv); 
00430     fvalue mv_cost = DeltaCostFunction(st,mv);
00431     best_move = mv; 
00432     fvalue best_delta = mv_cost;
00433     do // look for the best move
00434       { 
00435         mv_cost = DeltaCostFunction(st,mv);
00436 #ifdef COST_DEBUG
00437         std::cerr << mv << ' ' << mv_cost << std::endl;
00438 #endif
00439         if (mv_cost < best_delta) 
00440           { 
00441             best_move = mv;
00442             best_delta = mv_cost;
00443           }
00444         NextMove(st,mv);
00445       }
00446     while (!LastMoveDone(mv));
00447     mv = best_move;
00448     return best_delta;
00449   }
00450 
00458   template <class Input, class State, class Move>  
00459   void NeighborhoodExplorer<Input,State,Move>::NeighborhoodStatistics(const State &st)
00460   {  
00461     unsigned int neighbors = 0, improving_neighbors = 0, 
00462       worsening_neighbors = 0, non_improving_neighbors = 0;
00463     Move mv;
00464     fvalue mv_cost;
00465 
00466     FirstMove(st,mv);
00467     do 
00468       {         
00469         neighbors++;
00470         mv_cost = DeltaCostFunction(st,mv);
00471         if (mv_cost < 0)
00472           improving_neighbors++;
00473         else if (mv_cost > 0)
00474           worsening_neighbors++;
00475         else
00476           non_improving_neighbors++;
00477         NextMove(st,mv);
00478       }
00479     while (!LastMoveDone(mv));
00480     std::cout << "Neighborhood size: " <<  neighbors << std::endl
00481               << "   improving moves: " << improving_neighbors << " ("
00482               << (100.0*improving_neighbors)/neighbors << "\%)" << std::endl
00483               << "   worsening moves: " << worsening_neighbors << " ("
00484               << (100.0*worsening_neighbors)/neighbors << "\%)" << std::endl
00485               << "   non-improving moves: " << non_improving_neighbors << " ("
00486               << (100.0*non_improving_neighbors)/neighbors << "\%)" << std::endl;
00487   }
00488 
00497   template <class Input, class State, class Move>
00498   void NeighborhoodExplorer<Input,State,Move>::FirstMove(const State& st, Move& mv) 
00499   { 
00500     RandomMove(st,mv); 
00501     start_move = mv;
00502   }
00503 
00513   template <class Input, class State, class Move>  
00514   fvalue NeighborhoodExplorer<Input,State,Move>::SampleMove(const State &st, Move& mv, int samples)
00515   {  
00516     int s = 1;
00517     RandomMove(st,mv);
00518     fvalue mv_cost = DeltaCostFunction(st,mv);
00519     best_move = mv;
00520     fvalue best_delta = mv_cost;
00521     do // look for the best sampled move
00522       { 
00523         mv_cost = DeltaCostFunction(st,mv);
00524         if (mv_cost < best_delta)
00525           { 
00526             best_move = mv;
00527             best_delta = mv_cost;
00528           }
00529         RandomMove(st,mv);
00530         s++;
00531       }
00532     while (s < samples);
00533     mv = best_move;
00534     return best_delta;
00535   }
00536 
00546   template <class Input, class State, class Move>  
00547   fvalue NeighborhoodExplorer<Input,State,Move>::BestNonProhibitedMove(const State &st, Move& mv, fvalue curr, fvalue best) 
00548   {
00549     register fvalue mv_cost;
00550     bool tabu_move;
00551     bool all_moves_tabu = true;
00552         
00553     FirstMove(st,mv); 
00554     mv_cost = DeltaCostFunction(st,mv);
00555     best_move = mv;
00556     fvalue best_delta = mv_cost;
00557     do  // look for the best non prohibited move 
00558       { // (if all moves are prohibited, then get the best)
00559         tabu_move = p_pm->ProhibitedMove(mv,mv_cost,curr,best);      
00560         if (   (mv_cost < best_delta && !tabu_move)
00561                || (mv_cost < best_delta && all_moves_tabu)
00562                || (all_moves_tabu && !tabu_move))
00563           { 
00564             best_move = mv;
00565             best_delta = mv_cost;
00566           }
00567         if (!tabu_move) 
00568           all_moves_tabu = false;
00569         NextMove(st,mv);
00570         mv_cost = DeltaCostFunction(st,mv);
00571       }
00572     while (!LastMoveDone(mv));
00573     mv = best_move;
00574     return best_delta;
00575   } 
00576 
00577   
00589   template <class Input, class State, class Move>  
00590   fvalue NeighborhoodExplorer<Input,State,Move>::SampleNonProhibitedMove(const State &st, Move& mv, int samples, fvalue curr, fvalue best)
00591   {  
00592     int s = 1;
00593     fvalue mv_cost;
00594     bool tabu_move;
00595     bool all_moves_tabu = true;
00596         
00597     RandomMove(st,mv);
00598     mv_cost = DeltaCostFunction(st,mv);
00599     best_move = mv;
00600     fvalue best_delta = mv_cost;
00601     do 
00602       { 
00603         tabu_move = p_pm->ProhibitedMove(mv,mv_cost,curr,best);      
00604         if (   (mv_cost < best_delta && !tabu_move)
00605                || (mv_cost < best_delta && all_moves_tabu)
00606                || (all_moves_tabu && !tabu_move))
00607           { 
00608             best_move = mv;
00609             best_delta = mv_cost;
00610           }
00611         if (!tabu_move) 
00612           all_moves_tabu = false;
00613         RandomMove(st,mv);
00614         mv_cost = DeltaCostFunction(st,mv);
00615         s++;
00616       }
00617     while (s < samples);
00618     mv = best_move;
00619     return best_delta;
00620   }
00621 
00622 
00630   template <class Input, class State, class Move>  
00631   void NeighborhoodExplorer<Input,State,Move>::PrintMoveInfo(const State &st, const Move& mv, std::ostream& os)
00632   {
00633     os << "Move : " << mv << std::endl;
00634     os << "Start state cost : " << p_sm->CostFunction(st) << std::endl;
00635     os << "\tViolations : " << p_sm->Violations(st) << std::endl;
00636     os << "\tObjective  : " << p_sm->Objective(st) << std::endl;
00637         
00638     os << "Move cost : " << DeltaCostFunction(st,mv) << std::endl;
00639     os << "\tViolations : " << DeltaViolations(st,mv) << std::endl;
00640     os << "\tObjective  : " << DeltaObjective(st,mv) << std::endl;
00641         
00642     State st1 = st;
00643     MakeMove(st1,mv);
00644     os << "Final state cost : " << p_sm->CostFunction(st1) << std::endl;  
00645     os << "\tViolations : " << p_sm->Violations(st1) << std::endl;
00646     os << "\tObjective  : " << p_sm->Objective(st1) << std::endl;
00647         
00648     os << "Error : " << p_sm->CostFunction(st1) - DeltaCostFunction(st,mv) - p_sm->CostFunction(st) << std::endl;
00649   }
00650 
00656   template <class Input, class State, class Move>
00657   void NeighborhoodExplorer<Input,State,Move>::SetInput(Input* in) 
00658   { p_in = in; }
00659 
00665   template <class Input, class State, class Move>
00666   Input* NeighborhoodExplorer<Input,State,Move>::GetInput() 
00667   { return p_in; }
00668 
00673   template <class Input, class State, class Move>  
00674   void NeighborhoodExplorer<Input,State,Move>::Check()
00675   { assert(p_in != NULL && p_in == p_sm->GetInput()); }
00676 
00688   template <class Input, class State, class Move>  
00689   fvalue NeighborhoodExplorer<Input,State,Move>::DeltaViolations(const State& st, const Move & mv)
00690   {
00691     State st1 = st;
00692     MakeMove(st1,mv);
00693     return p_sm->Violations(st1) - p_sm->Violations(st);
00694   }
00695 
00707   template <class Input, class State, class Move>  
00708   fvalue NeighborhoodExplorer<Input,State,Move>::DeltaObjective(const State& st, const Move & mv)
00709   {
00710     State st1 = st;
00711     MakeMove(st1,mv);
00712     return p_sm->Objective(st1) - p_sm->Objective(st);
00713   }
00714 
00723   template <class Input, class State, class Move>  
00724   bool NeighborhoodExplorer<Input,State,Move>::LastMoveDone(const Move &mv) 
00725   { return mv == start_move; } 
00726 
00727   // Runner functions
00728 
00735   template <class Input, class State>
00736   Runner<Input,State>::Runner(std::string s, std::string t)
00737     : name(s), type(t) 
00738   {}
00739 
00745   template <class Input, class State>
00746   std::string Runner<Input,State>::Name() 
00747   { return name; }
00748 
00754   template <class Input, class State>
00755   std::string Runner<Input,State>::Type()
00756   { return type; }
00757 
00763   template <class Input, class State>
00764   void Runner<Input,State>::SetName(std::string s) 
00765   { name = s; } 
00766 
00778   template <class Input, class State, class Move>
00779   MoveRunner<Input,State,Move>::MoveRunner(StateManager<Input,State>* sm, NeighborhoodExplorer<Input,State,Move>* ne, Input* in, std::string name, std::string type)
00780     : Runner<Input,State>(name,type), p_in(in), p_sm(sm), p_nhe(ne)
00781   { 
00782     if (in != NULL)
00783       current_state.SetInput(in);
00784     number_of_iterations = 0;
00785     max_iteration = ULONG_MAX;
00786     current_state_set = false; 
00787   }
00788 
00794   template <class Input, class State, class Move>
00795   void MoveRunner<Input,State,Move>::SetInput(Input* in) 
00796   { 
00797     p_in = in; 
00798     current_state.SetInput(in);
00799     current_state_set = false;
00800     p_nhe->SetInput(in);
00801   }
00802 
00808   template <class Input, class State, class Move>
00809   Input* MoveRunner<Input,State,Move>::GetInput() 
00810   { return p_in; }
00811 
00817   template <class Input, class State, class Move>
00818   void MoveRunner<Input,State,Move>::Print(std::ostream& os) const
00819   { os << name << " : " << type << std::endl; }
00820 
00825   template <class Input, class State, class Move>
00826   void MoveRunner<Input,State,Move>::Check() 
00827   { 
00828     assert(p_in != NULL);
00829     assert(p_in == p_sm->GetInput());  
00830     assert(p_in == p_nhe->GetInput());
00831   }
00832 
00833 
00839   template <class Input, class State, class Move>
00840   void MoveRunner<Input,State,Move>::SetCurrentState(const State& s) 
00841   { 
00842     current_state = s; 
00843     current_state_set = true; 
00844     current_state_cost = p_sm->CostFunction(current_state); 
00845   }
00846 
00852   template <class Input, class State, class Move>
00853   State MoveRunner<Input,State,Move>::GetCurrentState() 
00854   { return current_state; }
00855 
00861   template <class Input, class State, class Move>
00862   fvalue MoveRunner<Input,State,Move>::CurrentStateCost() 
00863   { return current_state_cost; }
00864 
00870   template <class Input, class State, class Move>
00871   State MoveRunner<Input,State,Move>::GetBestState() 
00872   { return best_state; }
00873 
00879   template <class Input, class State, class Move>
00880   fvalue MoveRunner<Input,State,Move>::BestStateCost() 
00881   { return best_state_cost; }
00882 
00887   template <class Input, class State, class Move>
00888   void MoveRunner<Input,State,Move>::ComputeCost()  
00889   { current_state_cost = p_sm->CostFunction(current_state); }
00890 
00896   template <class Input, class State, class Move>
00897   bool MoveRunner<Input,State,Move>::LowerBoundReached() 
00898   { return current_state_cost == 0; }
00899 
00905   template <class Input, class State, class Move>
00906   unsigned long MoveRunner<Input,State,Move>::NumberOfIterations() const 
00907   { return number_of_iterations; }
00908 
00914   template <class Input, class State, class Move>
00915   unsigned long MoveRunner<Input,State,Move>::MaxIteration() const 
00916   { return max_iteration; }
00917 
00922   template <class Input, class State, class Move>
00923   void MoveRunner<Input,State,Move>::SetMaxIteration(unsigned long max)  
00924   { max_iteration = max; }
00925 
00931   template <class Input, class State, class Move>
00932   void MoveRunner<Input,State,Move>::SetParameters(const ParameterBox& pb)
00933   {   
00934     pb.Get("max idle iteration",max_idle_iteration);
00935     pb.Get("max iteration", max_iteration);
00936   }
00937 
00941   template <class Input, class State, class Move>
00942   void MoveRunner<Input,State,Move>::Go()
00943   { 
00944     assert(current_state_set);
00945     InitializeRun();
00946     while (!MaxIterationExpired() && !StopCriterion() && !LowerBoundReached())
00947       { 
00948         UpdateIterationCounter();
00949         SelectMove();
00950 #ifdef TRACE_MOVES
00951         Print(); std::cerr << "press any key ... "; std::cin.get();
00952 #endif
00953         if (AcceptableMove())
00954           { 
00955             MakeMove();
00956             UpdateStateCost();
00957             StoreMove();
00958           }
00959       }
00960     TerminateRun();
00961   }
00962 
00966   template <class Input, class State, class Move>
00967   void MoveRunner<Input,State,Move>::MakeMove() 
00968   { 
00969 #ifdef TRACE_MOVES
00970     p_nhe->PrintMoveInfo(current_state,current_move,std::cerr);
00971 #endif
00972 #ifdef COST_DEBUG
00973     fvalue ocost = current_state_cost;
00974     State previous_state = current_state;
00975 #endif
00976     p_nhe->MakeMove(current_state,current_move); 
00977 #ifdef COST_DEBUG
00978     fvalue ncost = p_sm->CostFunction(current_state);
00979     if (distance(ncost,(ocost+current_move_cost)) > EPS)
00980       {
00981         std::cerr << "Error in computing delta_cost: " 
00982                   << ncost-(ocost+current_move_cost) << std::endl;
00983         std::cerr << "Current iteration : " << number_of_iterations << std::endl;
00984         std::cerr << "Previous state : " << std::endl;
00985         std::cerr << previous_state << std::endl;
00986         std::cerr << "Current state : " << std::endl;
00987         std::cerr << current_state << std::endl;
00988         p_nhe->PrintMoveInfo(previous_state,current_move,std::cerr);
00989         char s[3];
00990         std::cout << "Press enter to continue...";
00991         std::cin.getline(s,3);
00992       }
00993 #endif
00994 #ifdef PLOT_DATA
00995     assert(pos); // the plot output stream must be set
00996     *pos << number_of_iterations << "\t" << current_state_cost << std::endl;
00997 #endif
00998   }
00999 
01005   template <class Input, class State, class Move>
01006   void MoveRunner<Input,State,Move>::Step(unsigned int n)
01007   { 
01008     assert(current_state_set);
01009     for (unsigned int i = 0; i < n; i++) 
01010       { 
01011         UpdateIterationCounter();
01012         SelectMove();
01013         if (AcceptableMove())
01014           { MakeMove();
01015           UpdateStateCost();
01016           StoreMove();
01017           if (LowerBoundReached())
01018             break;
01019           }
01020       }
01021   }
01022 
01027   template <class Input, class State, class Move>
01028   void MoveRunner<Input,State,Move>::ComputeMoveCost() 
01029   { current_move_cost = p_nhe->DeltaCostFunction(current_state,current_move); }
01030 
01034   template <class Input, class State, class Move>
01035   void MoveRunner<Input,State,Move>::UpdateIterationCounter() 
01036   { number_of_iterations++; }
01037 
01045   template <class Input, class State, class Move>
01046   bool MoveRunner<Input,State,Move>::MaxIterationExpired() 
01047   { return number_of_iterations > max_iteration; }
01048 
01053   template <class Input, class State, class Move>
01054   bool MoveRunner<Input,State,Move>::AcceptableMove() 
01055   { return true; }
01056 
01060   template <class Input, class State, class Move>
01061   void MoveRunner<Input,State,Move>::UpdateStateCost() 
01062   { current_state_cost += current_move_cost; }
01063 
01067   template <class Input, class State, class Move>
01068   void MoveRunner<Input,State,Move>::InitializeRun()
01069   {
01070     number_of_iterations = 0;
01071     iteration_of_best = 0;
01072     ComputeCost();
01073     best_state = current_state;
01074     best_state_cost = current_state_cost;
01075   }
01076 
01077   // Actual Runners
01078 
01079 
01080   // Hill Climbing
01081   
01082 
01091   template <class Input, class State, class Move>
01092   HillClimbing<Input,State,Move>::HillClimbing(StateManager<Input,State>* s, NeighborhoodExplorer<Input,State,Move>* ne, Input* in)
01093     : MoveRunner<Input,State,Move>(s, ne, in, "Runner name", "Hill Climbing")
01094   { 
01095     //  max_idle_iteration = 0; 
01096   }
01097 
01101   template <class Input, class State, class Move>   
01102   void HillClimbing<Input,State,Move>::ReadParameters() 
01103   { 
01104     std::cout << "HILL CLIMBING -- INPUT PARAMETERS" << std::endl;
01105     std::cout << "Number of idle iterations: ";
01106     std::cin >> max_idle_iteration;
01107   }
01108   
01113   template <class Input, class State, class Move>   
01114   void HillClimbing<Input,State,Move>::SelectMove() 
01115   { 
01116     p_nhe->RandomMove(current_state,current_move); 
01117     ComputeMoveCost();
01118   }
01119 
01124   template <class Input, class State, class Move>
01125   void HillClimbing<Input,State,Move>::InitializeRun()
01126   { 
01127     MoveRunner<Input,State,Move>::InitializeRun(); 
01128     assert(max_idle_iteration > 0);
01129   }
01130 
01135   template <class Input, class State, class Move>
01136   void HillClimbing<Input,State,Move>::TerminateRun()
01137   { 
01138     best_state = current_state;
01139     best_state_cost = current_state_cost;
01140   }
01141 
01146   template <class Input, class State, class Move>
01147   bool HillClimbing<Input,State,Move>::StopCriterion()
01148   { return number_of_iterations - iteration_of_best >= max_idle_iteration; }
01149 
01154   template <class Input, class State, class Move>
01155   bool HillClimbing<Input,State,Move>::AcceptableMove()
01156   { return current_move_cost <= 0; }
01157 
01162   template <class Input, class State, class Move>
01163   void HillClimbing<Input,State,Move>::StoreMove()
01164   { 
01165     if (fabs(current_move_cost) < EPS)
01166       {
01167         iteration_of_best = number_of_iterations;
01168       }
01169   }
01170 
01176   template <class Input, class State, class Move>
01177   void HillClimbing<Input,State,Move>::Print(std::ostream & os) const
01178   { 
01179     MoveRunner<Input,State,Move>::Print(os);
01180     os << "PATAMETERS: " << std::endl;
01181     os << "  Max idle iteration : " << max_idle_iteration << std::endl;
01182     os << "  Max iteration : " << max_iteration << std::endl;
01183     os << "RESULTS : " << std::endl;
01184     os << "  Number of iterations : " << number_of_iterations << std::endl;
01185     os << "  Iteration of best : " << iteration_of_best << std::endl;
01186     os << "  Current state [cost: " 
01187        << current_state_cost << "] " << std::endl;
01188     os << current_state << std::endl;
01189     os << std::endl;
01190   }
01191 
01192   // Steepest Descent
01193 
01202   template <class Input, class State, class Move>
01203   SteepestDescent<Input,State,Move>::SteepestDescent(StateManager<Input,State>* s, NeighborhoodExplorer<Input,State,Move>* ne, Input* in)
01204     : MoveRunner<Input,State,Move>(s, ne, in, "Runner name", "Steepest Descent")
01205   {}
01206 
01210   template <class Input, class State, class Move>   
01211   void SteepestDescent<Input,State,Move>::SelectMove() 
01212   { current_move_cost = p_nhe->BestMove(current_state,current_move); }
01213 
01218   template <class Input, class State, class Move>
01219   void SteepestDescent<Input,State,Move>::InitializeRun()
01220   { 
01221     MoveRunner<Input,State,Move>::InitializeRun(); 
01222     current_move_cost = -1; // needed for passing the first time 
01223                             // the StopCriterion test
01224   }
01225 
01229   template <class Input, class State, class Move>
01230   bool SteepestDescent<Input,State,Move>::StopCriterion()
01231   { return current_move_cost >= 0; }
01232 
01236   template <class Input, class State, class Move>
01237   bool SteepestDescent<Input,State,Move>::AcceptableMove()
01238   { return current_move_cost < 0; }
01239 
01244   template <class Input, class State, class Move>
01245   void SteepestDescent<Input,State,Move>::TerminateRun()
01246   { 
01247     best_state = current_state;
01248     best_state_cost = current_state_cost;
01249   }
01250   
01256   template <class Input, class State, class Move>
01257   void SteepestDescent<Input,State,Move>::Print(std::ostream & os) const
01258   {  
01259     MoveRunner<Input,State,Move>::Print(os);
01260     os << "PATAMETERS: " << std::endl;
01261     os << "  Max iteration : " << max_iteration << std::endl;
01262     os << "RESULTS : " << std::endl;
01263     os << "  Number of iterations : " << number_of_iterations << std::endl;
01264     os << "  Current state [cost: " 
01265        << current_state_cost << "] " << std::endl;
01266     os << current_state << std::endl;
01267     os << std::endl;
01268   }
01269 
01270   // Tabu Search
01271   
01281   template <class Input, class State, class Move>
01282   TabuSearch<Input,State,Move>::TabuSearch(StateManager<Input,State>* s, NeighborhoodExplorer<Input,State,Move>* ne, TabuListManager<Move>* tlm, Input* in)
01283     : MoveRunner<Input,State,Move>(s, ne, in, "Runner name", "Tabu Search")
01284   { 
01285     if (in != NULL)
01286       best_state.SetInput(in);
01287         
01288     SetTabuListManager(tlm); 
01289     p_pm = tlm;
01290     p_nhe->SetProhibitionManager(p_pm);
01291   }
01292 
01298   template <class Input, class State, class Move>
01299   void TabuSearch<Input,State,Move>::SetInput(Input* in) 
01300   { 
01301     MoveRunner<Input,State,Move>::SetInput(in);
01302     best_state.SetInput(in); 
01303   }
01304 
01308   template <class Input, class State, class Move>
01309   void TabuSearch<Input,State,Move>::ReadParameters()
01310   {
01311     int min_tabu, max_tabu;
01312     std::cout << "TABU SEARCH -- INPUT PARAMETERS" << std::endl;
01313     std::cout << "Length of the tabu list (min,max): ";
01314     std::cin >> min_tabu >> max_tabu;
01315     p_pm->SetLength(min_tabu,max_tabu);
01316     std::cout << "Number of idle iterations: ";
01317     std::cin >> max_idle_iteration;
01318   }
01319 
01327   template <class Input, class State, class Move>
01328   void TabuSearch<Input,State,Move>::SetTabuListManager(TabuListManager<Move>* tlm, int min_tabu, int max_tabu)
01329   { 
01330     p_pm = tlm;
01331     if (max_tabu != 0) // if min_tabu and max_tabu are properly set
01332       p_pm->SetLength(min_tabu,max_tabu);
01333     p_nhe->SetProhibitionManager(p_pm);
01334   }
01335 
01336 
01341   template <class Input, class State, class Move>
01342   void TabuSearch<Input,State,Move>::InitializeRun()
01343   {
01344     MoveRunner<Input,State,Move>::InitializeRun(); 
01345     assert(max_idle_iteration > 0);
01346     p_pm->Clean();
01347   }
01348 
01353   template <class Input, class State, class Move>
01354   void TabuSearch<Input,State,Move>::SelectMove() 
01355   { current_move_cost = p_nhe->BestNonProhibitedMove(current_state, current_move, current_state_cost, best_state_cost); }
01356 
01361   template <class Input, class State, class Move>  
01362   bool TabuSearch<Input,State,Move>::StopCriterion()
01363   { return number_of_iterations - iteration_of_best >= max_idle_iteration; }
01364 
01370   template <class Input, class State, class Move>  
01371   bool TabuSearch<Input,State,Move>::AcceptableMove() { return true; }
01372 
01373   
01379   template <class Input, class State, class Move>  
01380   void TabuSearch<Input,State,Move>::SetParameters(const ParameterBox& pb)
01381   {
01382     unsigned int min_tabu, max_tabu;
01383     MoveRunner<Input,State,Move>::SetParameters(pb);
01384     pb.Get("min tenure", min_tabu);
01385     pb.Get("max tenure", max_tabu);
01386     p_pm->SetLength(min_tabu,max_tabu);
01387   }
01388 
01393   template <class Input, class State, class Move>  
01394   void TabuSearch<Input,State,Move>::StoreMove()
01395   {
01396     p_pm->InsertMove(current_move, current_move_cost, current_state_cost, best_state_cost);
01397     if (current_state_cost + EPS < best_state_cost)
01398       { 
01399         iteration_of_best = number_of_iterations;
01400         best_state = current_state;
01401         best_state_cost = current_state_cost;
01402       }
01403   }
01404 
01410   template <class Input, class State, class Move>
01411   void TabuSearch<Input,State,Move>::Print(std::ostream & os) const
01412   {  
01413     MoveRunner<Input,State,Move>::Print(os);
01414     os << "PATAMETERS: " << std::endl;
01415     os << "  Max idle iteration : " << max_idle_iteration << std::endl;
01416     os << "  Max iteration : " << max_iteration << std::endl;
01417     os << "  Tenure : " << p_pm->MinTenure() << '-' << p_pm->MaxTenure() << std::endl;
01418     os << "RESULTS : " << std::endl;
01419     os << "  Number of iterations : " << number_of_iterations << std::endl;
01420     os << "  Iteration of best : " << iteration_of_best << std::endl;
01421     os << "  Current state [cost: " 
01422        << current_state_cost << "] " << std::endl
01423        << current_state << std::endl;
01424     os << "  Best State    [cost: " 
01425        << best_state_cost << "] " << std::endl
01426        << best_state << std::endl << std::endl;
01427     os << "Tabu list : " << std::endl;
01428     os << *p_pm; 
01429     os << std::endl << std::endl;
01430   }
01431 
01432   // Simulated Annealing
01433 
01442   template <class Input, class State, class Move>
01443   SimulatedAnnealing<Input,State,Move>::SimulatedAnnealing(StateManager<Input,State>* s, NeighborhoodExplorer<Input,State,Move>* ne, Input* in)
01444     : MoveRunner<Input,State,Move>(s, ne, in, "Runner name", "Simulated Annealing")
01445   { 
01446     min_temperature = 0.0001;
01447   }
01448 
01452   template <class Input, class State, class Move>
01453   void SimulatedAnnealing<Input,State,Move>::ReadParameters()
01454   {
01455     std::cout << "SIMULATED ANNEALING -- INPUT PARAMETERS" << std::endl;
01456     std::cout << "Start temperature: ";
01457     std::cin >> start_temperature;
01458     std::cout << "Cooling rate: ";
01459     std::cin >> cooling_rate;
01460     std::cout << "Neighbors sampled at each temperature : ";
01461     std::cin >> neighbor_sample;
01462   }
01463 
01468   template <class Input, class State, class Move>
01469   void SimulatedAnnealing<Input,State,Move>::InitializeRun()
01470   {
01471     MoveRunner<Input,State,Move>::InitializeRun(); 
01472     assert(start_temperature > 0 && cooling_rate > 0 && neighbor_sample > 0);
01473     temperature = start_temperature;
01474   }
01475 
01479   template <class Input, class State, class Move>
01480   void SimulatedAnnealing<Input,State,Move>::TerminateRun()
01481   { 
01482     best_state = current_state;
01483     best_state_cost = current_state_cost;
01484   }
01485 
01489   template <class Input, class State, class Move>
01490   void SimulatedAnnealing<Input,State,Move>::SelectMove() 
01491   { 
01492     p_nhe->RandomMove(current_state, current_move); 
01493     ComputeMoveCost(); 
01494   }
01495 
01501   template <class Input, class State, class Move>
01502   void SimulatedAnnealing<Input,State,Move>::SetParameters(const ParameterBox& pb)
01503   {
01504     pb.Get("start temperature", start_temperature);
01505     pb.Get("cooling rate", cooling_rate);
01506     pb.Get("neighbors sampled", neighbor_sample);
01507     pb.Get("max iteration", max_iteration);
01508   }
01509 
01515   template <class Input, class State, class Move>
01516   void SimulatedAnnealing<Input,State,Move>::Print(std::ostream & os) const
01517   {
01518     MoveRunner<Input,State,Move>::Print(os);
01519     os << "PATAMETERS: " << std::endl;
01520     os << "  Start temperature : " << start_temperature << std::endl;
01521     os << "  Cooling rate : " << cooling_rate << std::endl;
01522     os << "  Neighbor sample : " << neighbor_sample << std::endl;
01523     os << "  Max iteration : " << max_iteration << std::endl;
01524     os << "RESULTS : " << std::endl;
01525     os << "  Number of iterations : " << number_of_iterations << std::endl;
01526     os << "  Current state [cost: " 
01527        << current_state_cost << "] " << std::endl
01528        << current_state << std::endl;
01529   }
01530 
01534   template <class Input, class State, class Move>
01535   bool SimulatedAnnealing<Input,State,Move>::StopCriterion()
01536   { return temperature <= min_temperature; }
01537 
01542   template <class Input, class State, class Move>
01543   void SimulatedAnnealing<Input,State,Move>::UpdateIterationCounter() 
01544   { number_of_iterations++; 
01545   if (number_of_iterations % neighbor_sample == 0)
01546     temperature *= cooling_rate;
01547   }
01548 
01553   template <class Input, class State, class Move>
01554   bool SimulatedAnnealing<Input,State,Move>::AcceptableMove()
01555   { return (current_move_cost <= 0)
01556       || (rand() < exp(-current_move_cost/temperature)); }
01557 
01563   template <class Input, class Output>
01564   void Solver<Input,Output>::SetInput(Input* in) 
01565   { p_in = in; }
01566 
01572   template <class Input, class Output>
01573   void Solver<Input,Output>::SetOutput(Output* out) 
01574   { p_out = out; }
01575 
01582   template <class Input, class Output>
01583   Solver<Input,Output>::Solver(Input* in, Output* out)
01584     : p_in(in), p_out(out) 
01585   {}
01586 
01592   template <class Input, class Output>
01593   Input* Solver<Input,Output>::GetInput()
01594   { return p_in; }
01595 
01601   template <class Input, class Output>
01602   Output* Solver<Input,Output>::GetOutput()
01603   { return p_out; }
01604 
01609   template <class Input, class Output, class State>
01610   void LocalSearchSolver<Input,Output,State>::SetInitTrials(int t) 
01611   { number_of_init_trials = t; }
01612 
01618   template <class Input, class Output, class State>
01619   void LocalSearchSolver<Input,Output,State>::SetInput(Input* in) 
01620   { 
01621     p_in = in;
01622     internal_state.SetInput(in); 
01623   }
01624 
01630   template <class Input, class Output, class State>
01631   fvalue LocalSearchSolver<Input,Output,State>::InternalStateCost() 
01632   { return internal_state_cost; }
01633 
01643   template <class Input, class Output, class State>
01644   LocalSearchSolver<Input,Output,State>::LocalSearchSolver(StateManager<Input,State>* sm, OutputManager<Input,Output,State>* om, Input* in, Output* out) 
01645     : Solver<Input, Output>(in,out), p_sm(sm),  p_om(om), 
01646     number_of_init_trials(1)
01647   {
01648     if (in != NULL)
01649       internal_state.SetInput(in); 
01650   }
01651 
01656   template <class Input, class Output, class State>
01657   void LocalSearchSolver<Input,Output,State>::DeliverOutput() 
01658   { p_om->OutputState(internal_state,*p_out); }
01659 
01664   template <class Input, class Output, class State>
01665   void LocalSearchSolver<Input,Output,State>::FindInitialState() 
01666   { internal_state_cost = p_sm->SampleState(internal_state,number_of_init_trials); }
01667 
01671   template <class Input, class Output, class State>
01672   void LocalSearchSolver<Input,Output,State>::ComputeCost() 
01673   { internal_state_cost = p_sm->CostFunction(internal_state); }
01674 
01675 
01680   template <class Input, class Output, class State>
01681   void LocalSearchSolver<Input,Output,State>::Check()
01682   {
01683     assert(p_in != NULL);
01684     assert(p_in == p_sm->GetInput());
01685     assert(p_in == p_om->GetInput());
01686   }
01687 
01694   template <class Input, class Output, class State>
01695   void SimpleLocalSearch<Input,Output,State>::SetRunner(Runner<Input,State> *r) 
01696   { p_runner = r; }
01697 
01698 
01710   template <class Input, class Output, class State>
01711   SimpleLocalSearch<Input,Output,State>::SimpleLocalSearch(StateManager<Input,State>* sm, OutputManager<Input,Output,State>* om, Runner<Input,State>* r, Input* in, Output* out)
01712     : LocalSearchSolver<Input,Output,State>(sm,om,in,out) 
01713   { p_runner = r; }
01714 
01715 
01725   template <class Input, class Output, class State>
01726   SimpleLocalSearch<Input,Output,State>::SimpleLocalSearch(StateManager<Input,State>* sm, OutputManager<Input,Output,State>* om, Input* in, Output* out)
01727     : LocalSearchSolver<Input,Output,State>(sm,om,in,out) 
01728   { p_runner = NULL; }
01729 
01730 
01736   template <class Input, class Output, class State>
01737   unsigned long SimpleLocalSearch<Input,Output,State>::NumberOfIterations() const 
01738   { return p_runner->NumberOfIterations(); }
01739 
01743   template <class Input, class Output, class State>
01744   void SimpleLocalSearch<Input,Output,State>::Run()
01745   {
01746     p_runner->SetCurrentState(internal_state);
01747     p_runner->Go();
01748     internal_state = p_runner->GetBestState();
01749     internal_state_cost = p_runner->BestStateCost();
01750   }
01751 
01756   template <class Input, class Output, class State>
01757   void LocalSearchSolver<Input,Output,State>::Solve()
01758   {
01759     FindInitialState();
01760     Run();
01761     DeliverOutput();
01762   }
01763   
01768   template <class Input, class Output, class State>
01769   void LocalSearchSolver<Input,Output,State>::ReSolve()
01770   {
01771     Run();
01772     DeliverOutput();
01773   }
01774 
01781   template <class Input, class Output, class State>
01782   void LocalSearchSolver<Input,Output,State>::MultiStartSolve(unsigned int n)
01783   { 
01784     State best_state;
01785     fvalue best_state_cost = 0; // we assign it a value only to prevent
01786                                 // warnings from "smart" compilers
01787     for (unsigned int i = 0; i < n; i++)
01788       { 
01789         FindInitialState();
01790         Run();
01791         if (i == 0 || internal_state_cost < best_state_cost)
01792           { 
01793             best_state = internal_state;
01794             best_state_cost = internal_state_cost;
01795           }
01796       }
01797     internal_state = best_state;
01798     internal_state_cost = best_state_cost;
01799     DeliverOutput();
01800   }
01801 
01806   template <class Input, class Output, class State>
01807   unsigned long MultiRunnerSolver<Input,Output,State>::NumberOfIterations() const 
01808   { return total_iterations; }
01809 
01810 
01820   template <class Input, class Output, class State>
01821   MultiRunnerSolver<Input,Output,State>::MultiRunnerSolver(StateManager<Input,State>* sm, OutputManager<Input,Output,State>* om, Input* in, Output* out)
01822     : LocalSearchSolver<Input,Output,State>(sm,om,in,out), 
01823     total_iterations(0)
01824   { runners.clear(); }
01825 
01832   template <class Input, class Output, class State>
01833   void MultiRunnerSolver<Input,Output,State>::SetRunner(Runner<Input,State> *r, unsigned int i) 
01834   { 
01835     assert(i < runners.size());
01836     runners[i] = r; 
01837   }
01838 
01844   template <class Input, class Output, class State>
01845   void MultiRunnerSolver<Input,Output,State>::AddRunner(Runner<Input,State> *r)
01846   { runners.push_back(r); }
01847 
01851   template <class Input, class Output, class State>
01852   void MultiRunnerSolver<Input,Output,State>::ClearRunners()
01853   { runners.clear(); }
01854 
01859   template <class Input, class Output, class State>
01860   void ComparativeSolver<Input,Output,State>::Run()
01861   { 
01862     int i;
01863     start_state = internal_state;
01864     runners[0]->SetCurrentState(start_state);
01865     runners[0]->Go();
01866     runners[0]->ComputeCost();
01867     internal_state = runners[0]->GetBestState();
01868     internal_state_cost = runners[0]->BestStateCost();
01869         
01870     for (i = 1; i < runners.size(); i++)
01871       {
01872         runners[i]->SetCurrentState(start_state);
01873         runners[i]->Go();
01874         runners[i]->ComputeCost();
01875         total_iterations += runners[i]->NumberOfIterations();
01876         if (runners[i]->BestStateCost() < internal_state_cost)
01877           {
01878             internal_state = runners[i]->GetBestState();
01879             internal_state_cost = runners[i]->BestStateCost();
01880           }
01881       }
01882   }
01883 
01889   template <class Input, class Output, class State>
01890   void TokenRingSolver<Input,Output,State>::SetRounds(unsigned int r) 
01891   { max_idle_rounds = r; }
01892 
01898   template <class Input, class Output, class State>
01899   void TokenRingSolver<Input,Output,State>::SetStartRunner(unsigned int i)
01900   { start_runner = i; }
01901 
01902 
01912   template <class Input, class Output, class State>
01913   TokenRingSolver<Input,Output,State>::TokenRingSolver(StateManager<Input,State>* sm, OutputManager<Input,Output,State>* om, Input* in, Output* out) 
01914     : MultiRunnerSolver<Input,Output,State>(sm,om,in,out), 
01915     max_idle_rounds(1) 
01916   {}
01917 
01922   template <class Input, class Output, class State>
01923   void TokenRingSolver<Input,Output,State>::Check()
01924   {
01925     LocalSearchSolver<Input,Output,State>::Check();
01926     for (unsigned int i = 0; i < runners.size(); i++)
01927       {
01928         runners[i]->Check();
01929         assert(runners[i]->GetInput() == p_in);
01930       }
01931   }
01932 
01938   template <class Input, class Output, class State>
01939   void TokenRingSolver<Input,Output,State>::Print(std::ostream& os) const
01940   {
01941     os << "Solver State" << std::endl;
01942     for (unsigned int i = 0; i < runners.size(); i++)
01943       {
01944         os << "Runner " << i << std::endl;
01945         runners[i]->Print(os);
01946       }
01947   }
01948 
01953   template <class Input, class Output, class State>
01954   void TokenRingSolver<Input,Output,State>::Run()
01955   {
01956     assert(start_runner < runners.size());
01957         
01958     // i is the current runner, j is the previous one;
01959     unsigned int i = start_runner, j = (start_runner >= 1) ?
01960       (start_runner - 1) : runners.size() - 1;
01961     int idle_rounds = 0;
01962     bool interrupt_search = false;
01963     bool improvement_found = false;
01964         
01965     ComputeCost(); // Set internal_state_cost
01966     // internal_state_cost is used to check
01967     // whether a full round has produces improvements or not
01968     runners[i]->SetCurrentState(internal_state);
01969         
01970     while (idle_rounds < max_idle_rounds && !interrupt_search)
01971       { 
01972         do
01973           {
01974             runners[i]->Go();
01975             if (runners[i]->BestStateCost() < internal_state_cost) 
01976               { 
01977                 internal_state = runners[i]->GetBestState(); 
01978                 internal_state_cost = runners[i]->BestStateCost(); 
01979                 improvement_found = true;
01980               } 
01981             total_iterations += runners[i]->NumberOfIterations();
01982             if (runners[i]->LowerBoundReached() || runners.size() == 1)
01983               {
01984                 interrupt_search = true;
01985                 break;
01986               }
01987             j = i;
01988             i = (i + 1) % runners.size();
01989             runners[i]->SetCurrentState(runners[j]->GetBestState());
01990           }
01991         while (i != start_runner);
01992                 
01993         if (!interrupt_search)
01994           {
01995             if (improvement_found)
01996               idle_rounds = 0;
01997             else
01998               idle_rounds++;
01999             improvement_found = false;
02000           }
02001       }
02002   }
02003 
02004   // Abstract Move Tester
02005 
02011   template <class Input, class Output, class State>
02012   AbstractMoveTester<Input,Output,State>::AbstractMoveTester(std::string s) 
02013   { name = s; }
02014 
02019   template <class Input, class Output, class State>
02020   std::string AbstractMoveTester<Input,Output,State>::Name() 
02021   { return name; }
02022 
02023   // Move Tester
02024 
02036   template <class Input, class Output, class State, class Move>
02037   MoveTester<Input,Output,State,Move>::MoveTester(StateManager<Input,State>* sm, OutputManager<Input,Output,State>* om, NeighborhoodExplorer<Input,State,Move>* ne, std::string nm, Input* in)
02038     : AbstractMoveTester<Input,Output,State>(nm)
02039   { 
02040     if (in != NULL)
02041       out.SetInput(in);
02042     p_in = in; 
02043     p_sm = sm; 
02044     p_om = om;
02045     p_nhe = ne; 
02046   }  
02047 
02053   template <class Input, class Output, class State, class Move>
02054   void MoveTester<Input,Output,State,Move>::SetInput(Input* in)
02055   {
02056     p_in = in;
02057     out.SetInput(in);
02058     p_nhe->SetInput(in);
02059   }
02060 
02066   template <class Input, class Output, class State, class Move>
02067   void MoveTester<Input,Output,State,Move>::RunTestMenu(State& st)
02068   {
02069     do
02070       {
02071         ShowMenu();
02072         if (choice != 0)
02073           {
02074             clock_t start_t = clock();
02075             ExecuteChoice(st);
02076             clock_t end_t = clock();
02077             double eltime = (end_t - start_t)/(double)CLOCKS_PER_SEC;
02078             p_om->OutputState(st,out);
02079             std::cout << "CURRENT SOLUTION " << std::endl << out << std::endl;
02080             std::cout << "CURRENT COST : " << p_sm->CostFunction(st) << std::endl;
02081             std::cout << "ELAPSED TIME : " << eltime << "s" << std::endl;
02082           }
02083       }
02084     while (choice != 0);
02085     std::cout << "Leaving move menu" << std::endl;
02086   }
02087 
02091   template <class Input, class Output, class State, class Move>
02092   void MoveTester<Input,Output,State,Move>::ShowMenu()
02093   { 
02094     std::cout << "Move Menu: " << std::endl
02095               << "     (1)  Best" << std::endl     
02096               << "     (2)  Random" << std::endl
02097               << "     (3)  Input" << std::endl
02098               << "     (4)  Print Neighborhood statistics" << std::endl
02099               << "     (5)  Check Move Info" << std::endl
02100               << "     (0)  Return to Main Menu" << std::endl
02101               << " Your choice: ";
02102     std::cin >> choice;
02103   }
02104 
02110   template <class Input, class Output, class State, class Move>
02111   void MoveTester<Input,Output,State,Move>::ExecuteChoice(State& st)
02112   {
02113     Move mv;
02114     switch(choice)
02115       { 
02116       case 1: 
02117         p_nhe->BestMove(st,mv);
02118         break;
02119       case 2: 
02120         p_nhe->RandomMove(st,mv);
02121         break;
02122       case 3:      
02123         std::cout << "Input move : ";
02124         std::cin >> mv;
02125         break;
02126       case 4: 
02127         p_nhe->NeighborhoodStatistics(st);
02128         break;
02129       case 5: 
02130         {
02131           char ch;
02132           std::cout << "Random move (y/n)? ";
02133           std::cin >> ch;
02134           if (ch == 'y' || ch == 'Y')
02135             p_nhe->RandomMove(st,mv);
02136           else
02137             {
02138               std::cout << "Input move : ";
02139               std::cin >> mv;
02140             }
02141           std::cout << "Move info" << std::endl;
02142           p_nhe->PrintMoveInfo(st,mv,std::cout);
02143           break;
02144         }
02145       default:
02146         std::cout << "Invalid choice" << std::endl;
02147       }
02148     if (choice == 1 || choice == 2 || choice == 3)
02149       {
02150         std::cout << "Move : " << mv << std::endl;
02151         if (p_nhe->FeasibleMove(st,mv))
02152           p_nhe->MakeMove(st,mv);
02153         else
02154           std::cout << "Infeasible move!" << std::endl;
02155       }
02156   }
02157 
02158   // State Tester
02159 
02168   template <class Input, class Output, class State>
02169   StateTester<Input,Output,State>::StateTester(StateManager<Input,State>* s, OutputManager<Input,Output,State>* o, Input* in)
02170     : p_sm(s), p_om(o), p_in(in)
02171   {
02172     if (in != NULL)
02173       out.SetInput(in); 
02174   }
02175 
02181   template <class Input, class Output, class State>
02182   void StateTester<Input,Output,State>::SetInput(Input* in)
02183   {
02184     p_in = in;
02185     out.SetInput(in);
02186   }
02187 
02193   template <class Input, class Output, class State>
02194   void StateTester<Input,Output,State>::RunTestMenu(State& st)
02195   {
02196     ShowMenu();    
02197     clock_t start_t = clock();
02198     ExecuteChoice(st);
02199     clock_t end_t = clock();
02200     double eltime = (end_t - start_t)/(double)CLOCKS_PER_SEC;
02201     if (choice != 4 && choice != 5 && choice != 6 && choice != 7) // choices 4-7 do not change the state
02202       {
02203         p_om->OutputState(st,out);
02204         std::cout << "CURRENT SOLUTION " << std::endl << out << std::endl;
02205         std::cout << "CURRENT COST : " << p_sm->CostFunction(st) << std::endl;
02206         std::cout << "ELAPSED TIME : " << eltime << "s" << std::endl;
02207       }
02208   }
02209 
02213   template <class Input, class Output, class State>
02214   void StateTester<Input,Output,State>::RunInputMenu(State& st)
02215   {
02216     ShowReducedMenu();
02217     clock_t start_t = clock();
02218     ExecuteChoice(st);
02219     clock_t end_t = clock();
02220     double eltime = (end_t - start_t)/(double)CLOCKS_PER_SEC;
02221     p_om->OutputState(st,out);
02222     std::cout << "INITIAL SOLUTION " << std::endl << out << std::endl;
02223     std::cout << "INITIAL COST : " << p_sm->CostFunction(st) << std::endl;
02224     std::cout << "ELAPSED TIME : " << eltime << "s" << std::endl;
02225   }
02226 
02230   template <class Input, class Output, class State>
02231   void StateTester<Input,Output,State>::ShowMenu()
02232   {
02233     std::cout << "State Menu: " << std::endl
02234               << "    (1) Random state " << std::endl
02235               << "    (2) Sample state" << std::endl
02236               << "    (3) Read from file" << std::endl
02237               << "    (4) Write to file" << std::endl
02238               << "    (5) Show state" << std::endl
02239               << "    (6) Show input" << std::endl
02240               << "    (7) Show cost function components" << std::endl
02241               << "Your choice : ";
02242     std::cin >> choice;
02243   }
02244 
02248   template <class Input, class Output, class State>
02249   void StateTester<Input,Output,State>::ShowReducedMenu()
02250   {
02251     std::cout << "Initial State Menu: " << std::endl
02252               << "    (1) Random state " << std::endl
02253               << "    (2) Sample state" << std::endl
02254               << "    (3) Read from file" << std::endl
02255               << "Your choice : ";
02256     std::cin >> choice;
02257     if (choice == 4 || choice == 5 || choice == 6) choice = -1; // choices 4 and 5 do not belong to the reduces menu
02258   }
02259 
02265   template <class Input, class Output, class State>
02266   void StateTester<Input,Output,State>::ExecuteChoice(State& st)
02267   {
02268     unsigned long start_t, end_t;
02269     start_t = end_t = 0;
02270     switch(choice)
02271       {
02272       case 1: 
02273         start_t = clock();
02274         p_sm->RandomState(st);
02275         end_t = clock();
02276         break;
02277       case 2: 
02278         {
02279           int samples;
02280           std::cout << "How many samples : ";
02281           std::cin >> samples;
02282           start_t = clock();
02283           p_sm->SampleState(st,samples);
02284           end_t = clock();
02285           break;
02286         }
02287       case 3:
02288         {
02289           std::string file_name;
02290           std::cout << "File name : ";
02291           std::cin >> file_name;
02292           std::ifstream is(file_name.c_str());
02293           p_om->ReadState(st,is);
02294           break;
02295         }
02296       case 4:
02297         {
02298           std::string file_name;
02299           std::cout << "File name : ";
02300           std::cin >> file_name;
02301           std::ofstream os(file_name.c_str());
02302           p_om->WriteState(st,os);
02303           break;
02304         }
02305       case 5:
02306         {
02307           p_sm->PrintState(st); 
02308           break;
02309         }
02310       case 6:
02311         {
02312           std::cout << *p_in;
02313           break;
02314         }
02315       case 7:
02316         {
02317           std::cout << std::endl << "Violations: " << std::endl;
02318           p_sm->Violations(st);
02319           std::cout << std::endl << "Objective: " << std::endl;
02320           p_sm->Objective(st);
02321           break;
02322         }
02323       default:
02324         std::cout << "Invalid choice" << std::endl;
02325       }
02326     if (choice == 1 || choice == 2)
02327       std::cout << "Time: " << (end_t - start_t)/(float)CLOCKS_PER_SEC << " secs" << std::endl;
02328   }
02329 
02330   // Tester
02331 
02338   template <class Input, class Output, class State>  
02339   void Tester<Input, Output, State>::SetMoveTester(AbstractMoveTester<Input,Output,State>* p_amt, int i)
02340   { assert(i < move_testers.size()); move_testers[i] = p_amt; }
02341 
02347   template <class Input, class Output, class State>  
02348   void Tester<Input, Output, State>::AddMoveTester(AbstractMoveTester<Input,Output,State>* p_amt)
02349   { move_testers.push_back(p_amt); }
02350 
02354   template <class Input, class Output, class State>  
02355   void Tester<Input, Output, State>::CleanMoveTesters()
02356   { move_testers.clear(); }
02357 
02363   template <class Input, class Output, class State>  
02364   void Tester<Input, Output, State>::SetStateTester(StateTester<Input,Output,State>* p_st)
02365   { state_tester = p_st; }
02366 
02375   template <class Input, class Output, class State>
02376   Tester<Input, Output, State>::Tester(StateManager<Input,State>* sm, 
02377                                        OutputManager<Input,Output,State>* om,
02378                                        Input *in)
02379     : move_testers(0), runners(0), p_in(in)
02380   {
02381     if (in != NULL)
02382       {
02383         test_state.SetInput(in); 
02384         out.SetInput(in);  
02385       }
02386     p_sm = sm;
02387     p_om = om;
02388     state_tester = NULL;
02389     solver = NULL;
02390     logstream = &std::cerr;
02391     output_file_prefix = "";
02392     plot_file_prefix = "";
02393   }
02394 
02400   template <class Input, class Output, class State>
02401   void Tester<Input,Output,State>::SetInput(Input* in)
02402   {
02403     unsigned int i;
02404 
02405     p_in = in; 
02406     p_sm->SetInput(in);
02407     p_om->SetInput(in);
02408     test_state.SetInput(in);
02409     state_tester->SetInput(in);
02410     out.SetInput(in);
02411     if (solver != NULL) 
02412       solver->SetInput(in);
02413     for (i = 0; i < runners.size(); i++)
02414       if (runners[i] != NULL) 
02415         runners[i]->SetInput(in);
02416     for (i = 0; i < move_testers.size(); i++)
02417       move_testers[i]->SetInput(in);
02418   }
02419 
02424   template <class Input, class Output, class State>
02425   void  Tester<Input,Output,State>::Check()
02426   {
02427     assert(p_sm->GetInput() == p_in);
02428     assert(p_om->GetInput() == p_in);
02429     solver->Check();
02430     assert(solver->GetInput() == p_in);
02431     for (unsigned int i = 0; i < runners.size(); i++)
02432       {
02433         runners[i]->Check();
02434         assert(runners[i]->GetInput() == p_in);
02435       }
02436   }
02437 
02443   template <class Input, class Output, class State>
02444   void  Tester<Input,Output,State>::Print(std::ostream& os) const
02445   {
02446     os << "Tester State" << std::endl;
02447     for (unsigned int i = 0; i < runners.size(); i++)
02448       {
02449         os << "Runner " << i << std::endl;
02450         runners[i]->Print(os);
02451       }
02452     solver->Print(os);
02453   }
02454 
02460   template <class Input, class Output, class State>
02461   void Tester<Input, Output, State>::SetSolver(TokenRingSolver<Input,Output,State>* p_so)
02462   { 
02463     solver = p_so; 
02464     if (p_in != NULL && p_in != solver->GetInput())
02465       solver->SetInput(p_in);
02466     if (&out != solver->GetOutput())
02467       solver->SetOutput(&out);
02468   }
02469 
02476   template <class Input, class Output, class State>
02477   void Tester<Input, Output, State>::SetSolverParameters(unsigned int rounds, unsigned int start_runner) 
02478   {
02479     assert(solver != NULL);
02480     solver->SetRounds(rounds);
02481     solver->SetStartRunner(start_runner);
02482   }  
02483 
02487   template <class Input, class Output, class State>
02488   void Tester<Input, Output, State>::CleanRunners()
02489   { 
02490     runners.clear();
02491   }
02492 
02500   template <class Input, class Output, class State>
02501   void Tester<Input, Output, State>::SetRunner(Runner<Input,State>* p_ru, unsigned int i)
02502   { 
02503     runners[i] = p_ru; 
02504     if (p_in != NULL)
02505       runners[i]->SetInput(p_in);
02506   }
02507 
02513   template <class Input, class Output, class State>
02514   void Tester<Input, Output, State>::AddRunner(Runner<Input,State>* p_ru)
02515   { 
02516     assert(p_ru != NULL);
02517     if (p_in != p_ru->GetInput())
02518       p_ru->SetInput(p_in);
02519     runners.push_back(p_ru);
02520   }
02521 
02525   template <class Input, class Output, class State>
02526   void Tester<Input, Output, State>::CleanSolver() 
02527   { 
02528     assert(solver != NULL); 
02529     solver->ClearRunners(); 
02530   }
02531 
02539   template <class Input, class Output, class State>
02540   int Tester<Input, Output, State>::AddRunnerToSolver(std::string name, std::string type)
02541   {
02542     assert(solver != NULL);
02543     bool found = false, type_mismatch;
02544     for (unsigned int i = 0; i < runners.size(); i++)
02545       if (name == runners[i]->Name())
02546         {
02547           found = true;
02548           if (type == runners[i]->Type()) 
02549             {
02550               type_mismatch = false;
02551               solver->AddRunner(runners[i]);      
02552             }
02553           else
02554             type_mismatch = true;
02555           break;
02556         }
02557     if (found)
02558       if (!type_mismatch)
02559         return 0;
02560       else
02561         return RUNNER_TYPE_MISMATCH;
02562     else
02563       return RUNNER_NOT_FOUND;
02564   }
02565 
02574   template <class Input, class Output, class State>
02575   void Tester<Input, Output, State>::SetRunningParameters(std::string name, std::string type, const ParameterBox& pb)
02576   {
02577     bool found = false;
02578     for (unsigned int i = 0; i < runners.size(); i++) 
02579       if (name == runners[i]->Name()) 
02580         {
02581           runners[i]->SetParameters(pb);
02582           found = true;
02583           break;
02584         }
02585     assert(found);
02586   }
02587   
02591   template <class Input, class Output, class State>
02592   void Tester<Input, Output, State>::StartSolver()
02593   { 
02594     double avgtime = 0;
02595     fvalue avgcost = 0, avgviol = 0, avgobj = 0;
02596     assert(solver != NULL);
02597     *logstream << "Run\t" << "elapsed time\t" << "cost \t" << "violations\t" << "objective\t" << std::endl;
02598     *logstream << "--------------------------------------------------------------------------" << std::endl;
02599     for (unsigned int i = 1; i <= trials; i++)
02600       {
02601         unsigned long start_t = clock();
02602         solver->Solve();
02603         unsigned long end_t = clock();      
02604         double eltime = (end_t - start_t)/(double)CLOCKS_PER_SEC;
02605         p_om->InputState(test_state,out);
02606         // writing the output in a output file
02607         if (output_file_prefix != "")
02608           {
02609             std::string fn(output_file_prefix);
02610             char* trial = new char[(int)ceil(log10(i))+1];
02611             sprintf(trial,"%d",i);
02612             fn += '-' + std::string(trial) + std::string(".out");
02613             std::ofstream os(fn.c_str(),std::ios::out);
02614             os << out;
02615             delete trial;
02616           }      
02617         fvalue cost = p_sm->CostFunction(test_state);
02618         fvalue viol = p_sm->Violations(test_state);
02619         fvalue obj = p_sm->Objective(test_state);
02620         *logstream << i << "\t" << eltime << "\t\t" 
02621                    << cost << "\t" << viol << "\t\t" << obj << std::endl;      
02622         avgtime += eltime;
02623         avgcost += cost;
02624         avgviol += viol;
02625         avgobj += obj;
02626       }
02627         
02628     avgtime /= trials; avgcost /= trials; avgviol /= trials; avgobj /= trials;
02629     *logstream << "--------------------------------------------------------------------------" << std::endl;
02630     *logstream << "Avg:\t" << avgtime << "\t\t" << avgcost << "\t" << avgviol << "\t\t" << avgobj << std::endl;
02631   }
02632 
02638   template <class Input, class Output, class State>
02639   void Tester<Input, Output, State>::LoadInstance(std::string id) 
02640   {
02641     *logstream << "Instance: " << id << std::endl;
02642     CleanSolver();  
02643     p_in->Load(id);
02644     SetInput(p_in);
02645   }
02646 
02652   template <class Input, class Output, class State>
02653   void Tester<Input, Output, State>::ProcessBatch(std::string filename) 
02654   { 
02655     if (yyin = fopen(filename.c_str(), "r"))
02656       {
02657         yyout = stdout;
02658         yyparse();
02659         fclose(yyin);
02660       }
02661     else
02662       std::cerr << "Error: " << filename << " file not found" << std::endl;
02663   }
02664 
02665   
02670   template <class Input, class Output, class State>
02671   void Tester<Input, Output, State>::RunMainMenu()
02672   {
02673     unsigned int i;
02674     assert(state_tester != NULL);
02675     for (i = 0; i < move_testers.size(); i++)
02676       assert(move_testers[i] != NULL);
02677     for (i = 0; i < runners.size(); i++)
02678       assert(runners[i] != NULL);
02679         
02680     state_tester->RunInputMenu(test_state);
02681         
02682     do
02683       {
02684         ShowMainMenu();
02685         if (choice != 0)
02686           ExecuteMainChoice();
02687       }
02688     while (choice != 0);
02689     std::cout << "Bye bye..." << std::endl;
02690   }
02691 
02695   template <class Input, class Output, class State>
02696   void Tester<Input,Output, State>::ShowMainMenu()
02697   {
02698     std::cout << "MAIN MENU:" << std::endl
02699               << "   (1) Move menu" << std::endl
02700               << "   (2) Run menu" << std::endl
02701               << "   (3) State menu" << std::endl
02702               << "   (4) Process batch file" << std::endl
02703               << "   (5) Debugging" << std::endl
02704               << "   (0) Exit" << std::endl
02705               << " Your choice: ";
02706     std::cin >> choice;
02707   }
02708 
02712   template <class Input, class Output, class State>
02713   void Tester<Input,Output, State>::ShowDebuggingMenu()
02714   {
02715     std::cout << "DEBUGGING MENU:" << std::endl
02716               << "   (1) Print tester status" << std::endl
02717               << "   (2) Check tester status" << std::endl
02718               << " Your choice: ";
02719     std::cin >> choice;
02720   }
02721 
02725   template <class Input, class Output, class State>
02726   void Tester<Input, Output,State>::ExecuteDebuggingMenu()
02727   {
02728     switch(choice)
02729       {
02730       case 1: 
02731         Print();
02732         Check();
02733         break;
02734       case 2: 
02735         Check();
02736         break;
02737       default:
02738         std::cout << "Invalid choice" << std::endl;
02739       }
02740   }
02741 
02745   template <class Input, class Output, class State>
02746   void Tester<Input, Output,State>::ExecuteMainChoice()
02747   {
02748     switch(choice)
02749       {
02750       case 1: 
02751         ShowMovesMenu();
02752         ExecuteMovesChoice();
02753         break;
02754       case 2: 
02755         ShowRunMenu();
02756         ExecuteRunChoice();
02757         break;
02758       case 3: 
02759         state_tester->RunTestMenu(test_state);
02760         break;
02761       case 4:
02762         {
02763           std::string file_name;
02764           std::cout << "Insert Batch File name : ";
02765           std::cin >> file_name;
02766           ProcessBatch(file_name);
02767           break;
02768         }
02769       case 5:
02770         ShowDebuggingMenu();
02771         ExecuteDebuggingMenu(); 
02772       case 0:
02773         break;
02774       default:
02775         std::cout << "Invalid choice" << std::endl;
02776       }
02777   }
02778 
02782   template <class Input, class Output, class State>
02783   void Tester<Input, Output,State>::ShowMovesMenu()
02784   {
02785     unsigned int i;
02786     std::cout << "MOVES MENU: " << std::endl;
02787     for (i = 0; i < move_testers.size(); i++)
02788       std::cout << "   (" << i+1 << ") " << move_testers[i]->Name() << std::endl;
02789     std::cout << "   (0) Return to Main Menu" << std::endl;
02790     std::cout << " Your choice: ";
02791     std::cin >> sub_choice;
02792   }
02793 
02797   template <class Input, class Output, class State>
02798   void Tester<Input,Output, State>::ShowRunMenu()
02799   {
02800     unsigned int i;
02801     std::cout << "RUN MENU: " << std::endl;
02802     for (i = 0; i < runners.size(); i++)
02803       std::cout << "   (" << i+1 << ") " << runners[i]->Name() << " [" << runners[i]->Type() << "]" << std::endl;
02804     std::cout << "   (0) Return to Main Menu" << std::endl;
02805     std::cout << " Your choice: ";
02806     std::cin >> sub_choice;
02807   }
02808 
02812   template <class Input, class Output, class State>
02813   void Tester<Input,Output, State>::ExecuteMovesChoice()
02814   {
02815     if (sub_choice > 0)
02816       move_testers[sub_choice-1]->RunTestMenu(test_state);
02817   }
02818 
02822   template <class Input, class Output, class State>
02823   void Tester<Input,Output, State>::ExecuteRunChoice()
02824   {
02825     if (sub_choice > 0)
02826       {
02827         runners[sub_choice-1]->ReadParameters();
02828         runners[sub_choice-1]->SetCurrentState(test_state);
02829         clock_t start_t = clock();
02830         runners[sub_choice-1]->Go();
02831         clock_t end_t = clock();
02832         double eltime = (end_t - start_t)/(double)CLOCKS_PER_SEC;
02833         test_state = runners[sub_choice-1]->GetBestState();
02834         p_om->OutputState(test_state,out);
02835         std::cout << "CURRENT SOLUTION " << std::endl << out << std::endl;
02836         std::cout << "CURRENT COST : " << runners[sub_choice-1]->BestStateCost() << std::endl;
02837         std::cout << "ELAPSED TIME : " << eltime << "s" << std::endl;
02838       }
02839   }
02840 } // end of namespace easylocal
 
Go to: the Main Page of the documentation.