EasyLocal++ Documentation |
|
EasyLocalTemplates.cppGo 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. |