EasyLocal++ Documentation |
|
EasyLocal.hGo to the documentation of this file.00001 00016 #ifndef __EASYLOCAL_H 00017 #define __EASYLOCAL_H 00018 00019 #include <iostream> 00020 #include <fstream> 00021 #include <vector> 00022 #include <string> 00023 #include <list> 00024 #include <cmath> 00025 #include <cassert> 00026 #include <ctime> 00027 #include <cstdio> 00028 00031 extern "C++" int yyparse(); 00032 00034 extern FILE *yyin; 00036 extern FILE *yyout; 00037 00039 namespace easylocal { 00046 int Random(int a, int b); 00047 00055 #ifndef HARD_WEIGHT 00056 #define HARD_WEIGHT 1000 00057 #endif 00058 00061 const int RUNNER_NOT_FOUND = 1, RUNNER_TYPE_MISMATCH = 2; 00062 00070 #ifndef fvalue 00071 #define fvalue double 00072 #endif 00073 00077 const double EPS = 1.0E-6; 00078 00086 inline double distance(fvalue x, fvalue y); 00087 00107 // forward class tag declaration 00108 template <class Input, class State> class Runner; 00109 00116 template <class Input, class State> 00117 class StateManager 00118 { 00119 public: 00123 virtual void RandomState(State &st) = 0; 00128 virtual void UpdateRedundantStateData(State &st) 00129 {} 00130 virtual fvalue SampleState(State &st, int samples); 00131 virtual fvalue ImprovedSampleState(State &st, int samples, Runner<Input,State>* r); 00132 00133 // State Evaluation functions 00134 virtual fvalue CostFunction(const State& st) const; 00135 virtual fvalue Objective(const State& st) const; 00136 virtual fvalue Violations(const State& st) const; 00137 00138 // debug functions 00139 virtual void PrintState(const State& st) const; 00140 virtual void Check() const; 00141 00142 void SetInput(Input* in); 00143 Input* GetInput(); 00144 protected: 00145 StateManager(Input* in = NULL); 00146 Input* p_in; 00147 }; 00148 00158 template <class Input, class Output, class State> 00159 class OutputManager 00160 { 00161 public: 00165 virtual void OutputState(const State &st, Output& out) const = 0; 00169 virtual void InputState(State &st, const Output& out) const = 0; 00170 virtual void ReadState(State &st, std::istream &is) const; 00171 virtual void WriteState(const State &st, std::ostream &os) const; 00172 00173 virtual void Check() const; 00174 void SetInput(Input* in); 00175 Input* GetInput(); 00176 protected: 00181 OutputManager(StateManager<Input,State>* sm, Input* in = NULL) 00182 : p_sm(sm), p_in(in) {} 00183 StateManager<Input,State>* p_sm; 00185 Input* p_in; 00186 }; 00187 00188 00197 template <class Move> 00198 class ProhibitionManager 00199 { 00200 public: 00207 virtual void InsertMove(const Move& mv, fvalue mv_cost, fvalue curr, fvalue best) = 0; 00215 virtual bool ProhibitedMove(const Move& mv, fvalue mv_cost, fvalue curr, fvalue best) const = 0; 00217 virtual void Clean() = 0; 00220 virtual void Check() {} 00221 }; 00222 00223 // forward class tag declaration 00224 template <class Move> class ListItem; 00225 00234 template <class Move> 00235 class TabuListManager : public ProhibitionManager<Move> 00236 { 00237 #ifndef __GNUC_MINOR__ 00238 friend std::ostream& operator<<(std::ostream&, const TabuListManager<Move>&); 00239 #elif __GNUC_MINOR__ > 7 00240 friend std::ostream& operator<< <>(std::ostream&, const TabuListManager<Move>&); 00241 #else 00242 friend std::ostream& operator<<(std::ostream&, const TabuListManager<Move>&); 00243 #endif 00244 public: 00245 void InsertMove(const Move& mv, fvalue mv_cost, fvalue curr, fvalue best); 00246 bool ProhibitedMove(const Move& mv, fvalue mv_cost, fvalue curr, 00247 fvalue best) const; 00252 void SetLength(unsigned int min, unsigned int max) 00253 { min_tenure = min; max_tenure = max; } 00254 void Clean(); 00257 unsigned int MinTenure() const 00258 { return min_tenure; } 00261 unsigned int MaxTenure() const 00262 { return max_tenure; } 00269 virtual bool Inverse(const Move& mv1, const Move& mv2) const = 0; 00270 protected: 00271 TabuListManager(int min = 0, int max = 0); 00273 virtual ~TabuListManager() {} 00274 virtual bool Aspiration(const Move&, fvalue mv_cost, fvalue curr, fvalue best) const; 00275 void InsertIntoList(const Move& mv); 00281 void UpdateAspirationFunction(fvalue mv_cost, fvalue curr_cost, fvalue best_cost) 00282 {} 00283 bool ListMember(const Move&) const; 00284 00285 unsigned int min_tenure, 00286 max_tenure; 00287 unsigned long iter; 00288 std::list<ListItem<Move> > tlist; 00289 }; 00290 00295 template <class Move> 00296 class ListItem 00297 { 00298 friend class TabuListManager<Move>; 00299 #ifndef __GNUC_MINOR__ 00300 friend std::ostream& operator<<(std::ostream&, const TabuListManager<Move>&); 00301 #elif __GNUC_MINOR__ > 7 00302 friend std::ostream& operator<< <>(std::ostream&, const TabuListManager<Move>&); 00303 #else 00304 friend std::ostream& operator<<(std::ostream&, const TabuListManager<Move>&); 00305 #endif 00306 public: 00312 ListItem(Move mv, unsigned long out) 00313 : out_iter(out) { elem = mv; } 00314 protected: 00315 Move elem; 00316 unsigned long out_iter; 00318 }; 00319 00321 template <class Move> 00322 std::ostream& operator<<(std::ostream&, const TabuListManager<Move>&); 00323 00324 00331 template <class Input, class State, class Move> 00332 class NeighborhoodExplorer 00333 { 00334 public: 00336 virtual ~NeighborhoodExplorer() {} 00337 00338 // move generating functions 00339 virtual void FirstMove(const State& st, Move& mv); 00348 virtual void NextMove(const State &st, Move& mv) = 0; 00355 virtual void RandomMove(const State &st, Move& mv) = 0; 00356 virtual fvalue BestMove(const State &st, Move& mv); 00357 virtual fvalue SampleMove(const State &st, Move& mv, int samples); 00358 virtual fvalue BestNonProhibitedMove(const State &st, Move& mv, fvalue curr, fvalue best); 00359 virtual fvalue SampleNonProhibitedMove(const State &st, Move& mv, int samples, fvalue curr, fvalue best); 00360 // end of exploration detection 00361 virtual bool LastMoveDone(const Move &mv); 00362 00371 virtual bool FeasibleMove(const State &st, const Move mv) 00372 { return true; } 00373 00374 virtual void SetProhibitionManager(ProhibitionManager<Move> *pm); 00375 00383 virtual void MakeMove(State &st, const Move& mv) = 0; 00384 00385 // evaluation function 00386 virtual fvalue DeltaCostFunction(const State& st, const Move & mv); 00387 00388 // debugging/statistic functions 00389 virtual void NeighborhoodStatistics(const State &st); 00390 void PrintMoveInfo(const State &st, const Move& mv, std::ostream& os = std::cout); 00391 00399 virtual void InputMove(const State &st, Move& mv, std::istream& is = std::cin) const {} 00400 00401 void SetInput(Input* in); 00402 Input* GetInput(); 00403 void Check(); 00404 protected: 00405 NeighborhoodExplorer(StateManager<Input,State>* sm, Input* in = NULL); 00406 NeighborhoodExplorer(StateManager<Input,State>* sm, ProhibitionManager<Move>* pm, Input* in = NULL); 00407 00408 StateManager<Input,State>* p_sm; 00410 Input* p_in; 00411 virtual fvalue DeltaObjective(const State& st, const Move & mv); 00412 virtual fvalue DeltaViolations(const State& st, const Move & mv); 00413 00414 00415 Move best_move; 00419 Move start_move; 00421 // the prohibition manager used with memory based strategies 00422 ProhibitionManager<Move>* p_pm; 00425 }; 00426 00437 union ValueType { 00438 unsigned long natural; 00439 unsigned int short_natural; 00440 double real; 00441 }; 00442 00447 class ParameterData { 00448 std::string name; 00449 std::string type; 00450 ValueType value; 00451 public: 00452 ParameterData(std::string,std::string,ValueType); 00453 std::string Name() const; 00454 std::string Type() const; 00455 ValueType Value() const; 00456 }; 00457 00462 class ParameterBox 00463 { 00464 public: 00465 void Put(std::string name, std::string type, ValueType value); 00466 void Put(std::string name, unsigned long value); 00467 void Put(std::string name, unsigned int value); 00468 void Put(std::string name, double value); 00469 void Get(std::string name, std::string type, ValueType& value) const; 00470 void Get(std::string name, unsigned long& value) const; 00471 void Get(std::string name, unsigned int& value) const; 00472 void Get(std::string name, double& value) const; 00473 void Clear(); 00474 protected: 00475 std::list<ParameterData> parameters; 00477 }; 00478 00494 template <class Input, class State> 00495 class Runner 00496 { 00497 public: 00499 virtual ~Runner() {} 00500 Runner(std::string s = "Runner name", std::string t = "Runner type"); 00502 virtual void Go() = 0; 00505 virtual void Step(unsigned int n) = 0; 00509 virtual void Print(std::ostream& os = std::cout) const = 0; 00512 virtual void SetCurrentState(const State& st) = 0; 00515 virtual State GetCurrentState() = 0; 00518 virtual fvalue CurrentStateCost() = 0; 00521 virtual State GetBestState() = 0; 00524 virtual fvalue BestStateCost() = 0; 00526 virtual void ComputeCost() = 0; 00531 virtual bool LowerBoundReached() = 0; 00534 virtual unsigned long NumberOfIterations() const = 0; 00536 virtual void ReadParameters() = 0; 00537 std::string Name(); 00538 std::string Type(); 00539 void SetName(std::string s); 00542 virtual void SetInput(Input* in) = 0; 00545 virtual Input* GetInput() = 0; 00548 virtual void Check() = 0; 00552 virtual void SetParameters(const ParameterBox& pb) = 0; 00553 protected: 00554 std::string name, 00555 type; 00556 }; 00557 00563 template <class Input, class State, class Move> 00564 class MoveRunner : public Runner<Input,State> 00565 { 00566 public: 00568 virtual ~MoveRunner() {}; 00569 void Go(); 00570 void Step(unsigned int n); 00571 void SetCurrentState(const State& s); 00572 State GetCurrentState(); 00573 fvalue CurrentStateCost(); 00574 State GetBestState(); 00575 fvalue BestStateCost(); 00576 void ComputeCost(); 00577 bool LowerBoundReached(); 00578 unsigned long NumberOfIterations() const; 00579 unsigned long MaxIteration() const; 00580 void SetMaxIteration(unsigned long max); 00581 void SetInput(Input* in); 00582 Input* GetInput(); 00583 void Print(std::ostream& os = std::cout) const; 00584 void SetParameters(const ParameterBox& pb); 00589 void SetPlotStream(std::ostream* os = &std::cerr) 00590 { pos = os; } 00591 void Check(); 00592 protected: 00593 MoveRunner(StateManager<Input,State>* s, 00594 NeighborhoodExplorer<Input,State,Move>* ne, Input* in = NULL, 00595 std::string name = "Runner name", std::string type = "Move Runner"); 00596 virtual void InitializeRun(); 00598 virtual void TerminateRun() {}; 00599 virtual void ComputeMoveCost(); 00600 virtual void UpdateIterationCounter(); 00601 bool MaxIterationExpired(); 00603 virtual bool StopCriterion() = 0; 00605 virtual void SelectMove() = 0; 00606 virtual bool AcceptableMove(); 00607 virtual void MakeMove(); 00609 virtual void StoreMove() {} 00610 virtual void UpdateStateCost(); 00611 00612 // input 00613 Input* p_in; 00615 // helpers 00616 StateManager<Input,State>* p_sm; 00618 NeighborhoodExplorer<Input,State,Move>* p_nhe; 00622 // state data 00623 State current_state; 00624 fvalue current_state_cost; 00625 bool current_state_set; 00627 Move current_move; 00628 fvalue current_move_cost; 00630 State best_state; 00631 fvalue best_state_cost; 00633 unsigned long iteration_of_best; 00635 unsigned long max_idle_iteration; 00639 unsigned long number_of_iterations; 00641 unsigned long max_iteration; 00644 std::ostream* pos; 00645 }; 00646 00654 template <class Input, class State, class Move> 00655 class SteepestDescent : public MoveRunner<Input,State,Move> 00656 { 00657 public: 00658 void Print(std::ostream& os = std::cout) const; 00659 void ReadParameters() {} 00660 protected: 00661 SteepestDescent(StateManager<Input,State>* s, 00662 NeighborhoodExplorer<Input,State,Move>* ne, 00663 Input* in = NULL); 00664 void InitializeRun(); 00665 void TerminateRun(); 00666 bool StopCriterion(); 00667 bool AcceptableMove(); 00668 void SelectMove(); 00669 }; 00670 00676 template <class Input, class State, class Move> 00677 class HillClimbing : public MoveRunner<Input,State,Move> 00678 {public: 00679 void Print(std::ostream& os = std::cout) const; 00680 void ReadParameters(); 00681 protected: 00682 HillClimbing(StateManager<Input,State>* s, 00683 NeighborhoodExplorer<Input,State,Move>* ne, Input* in = NULL); 00684 void InitializeRun(); 00685 void TerminateRun(); 00686 bool StopCriterion(); 00687 bool AcceptableMove(); 00688 void StoreMove(); 00689 void SelectMove(); 00690 }; 00691 00706 template <class Input, class State, class Move> 00707 class TabuSearch : public MoveRunner<Input,State, Move> 00708 {public: 00709 void ReadParameters(); 00710 void Print(std::ostream& os = std::cout) const; 00711 void SetInput(Input* in); 00712 void SetParameters(const ParameterBox& pb); 00713 protected: 00714 TabuSearch(StateManager<Input,State>* s, 00715 NeighborhoodExplorer<Input,State,Move>* ne, 00716 TabuListManager<Move>* tlm, Input* in = NULL); 00717 void SetTabuListManager(TabuListManager<Move>* tlm, 00718 int min_tabu = 0, int max_tabu = 0); 00719 void InitializeRun(); 00720 bool StopCriterion(); 00721 void SelectMove(); 00722 bool AcceptableMove(); 00723 void StoreMove(); 00724 TabuListManager<Move>* p_pm; 00725 }; 00726 00738 template <class Input, class State, class Move> 00739 class SimulatedAnnealing : public MoveRunner<Input,State,Move> 00740 { 00741 public: 00742 void ReadParameters(); 00743 void SetParameters(const ParameterBox& pb); 00744 void Print(std::ostream& os = std::cout) const; 00745 protected: 00746 SimulatedAnnealing(StateManager<Input,State>* s, 00747 NeighborhoodExplorer<Input,State,Move>* ne, Input* in = NULL); 00748 void InitializeRun(); 00749 void TerminateRun(); 00750 bool StopCriterion(); 00751 void UpdateIterationCounter(); 00752 void SelectMove(); 00753 bool AcceptableMove(); 00754 protected: 00755 double temperature; 00756 double start_temperature; 00757 double min_temperature; 00759 double cooling_rate; 00762 unsigned int neighbor_sample; 00764 }; 00765 00781 class AbstractSolver 00782 { 00783 public: 00785 virtual ~AbstractSolver() {} 00788 virtual void Solve() = 0; 00791 virtual void ReSolve() = 0; 00795 virtual void MultiStartSolve(unsigned int n) = 0; 00796 }; 00797 00803 template <class Input, class Output> 00804 class Solver : public AbstractSolver 00805 { 00806 public: 00807 virtual void Solve() = 0; 00808 virtual void SetInput(Input* in); 00809 Input* GetInput(); 00810 Output* GetOutput(); 00811 void SetOutput(Output* out); 00812 protected: 00813 Solver(Input* in = NULL, Output* out = NULL); 00816 virtual void DeliverOutput() = 0; 00817 Input* p_in; 00818 Output* p_out; 00819 }; 00820 00825 template <class Input, class Output, class State> 00826 class LocalSearchSolver : public Solver<Input, Output> 00827 {public: 00828 void SetInitTrials(int t); 00829 void Solve(); 00834 virtual void ReSolve(); 00835 virtual void MultiStartSolve(unsigned int n); 00836 void SetInput(Input* in); 00837 virtual void Check(); 00838 fvalue InternalStateCost(); 00839 protected: 00840 LocalSearchSolver(StateManager<Input,State>* sm, 00841 OutputManager<Input,Output,State>* om, Input* in = NULL, Output* out = NULL); 00846 virtual void Run() = 0; 00848 virtual unsigned long NumberOfIterations() const = 0; 00849 void DeliverOutput(); 00850 virtual void FindInitialState(); 00851 void ComputeCost(); 00852 StateManager<Input,State>* p_sm; 00854 OutputManager<Input,Output,State>* p_om; 00856 fvalue internal_state_cost; 00857 State internal_state; 00858 unsigned int number_of_init_trials; 00860 }; 00861 00866 template <class Input, class Output, class State> 00867 class SimpleLocalSearch : public LocalSearchSolver<Input,Output,State> 00868 { 00869 public: 00870 void SetRunner(Runner<Input,State> *r); 00871 protected: 00872 SimpleLocalSearch(StateManager<Input,State>* sm, 00873 OutputManager<Input,Output,State>* om, 00874 Runner<Input,State>* r, Input* in = NULL, Output* out = NULL); 00875 SimpleLocalSearch(StateManager<Input,State>* sm, 00876 OutputManager<Input,Output,State>* om, Input* in = NULL, Output* out = NULL); 00877 void Run(); 00878 unsigned long NumberOfIterations() const; 00879 Runner<Input,State>* p_runner; 00880 }; 00881 00882 00886 template <class Input, class Output, class State> 00887 class MultiRunnerSolver : public LocalSearchSolver<Input,Output,State> 00888 { 00889 public: 00890 void ClearRunners(); 00891 void AddRunner(Runner<Input,State> *r); 00892 void SetRunner(Runner<Input,State> *r, unsigned int i); 00893 protected: 00894 MultiRunnerSolver(StateManager<Input,State>* sm, 00895 OutputManager<Input,Output,State>* om, Input* in = NULL, Output* out = NULL); 00896 unsigned long NumberOfIterations() const; 00897 unsigned long total_iterations; 00900 unsigned int start_runner; 00902 std::vector<Runner<Input,State>* > runners; 00904 }; 00905 00910 template <class Input, class Output, class State> 00911 class ComparativeSolver : public MultiRunnerSolver<Input,Output,State> 00912 { 00913 protected: 00922 ComparativeSolver(StateManager<Input,State>* sm, 00923 OutputManager<Input,Output,State>* om, 00924 Input* in = NULL, Output* out = NULL) 00925 : MultiRunnerSolver<Input,Output,State>(sm,om,in,out) {} 00926 void Run(); 00927 State start_state; 00929 }; 00930 00935 template <class Input, class Output, class State> 00936 class TokenRingSolver : public MultiRunnerSolver<Input,Output,State> 00937 {public: 00938 void SetRounds(unsigned int r); 00939 void SetStartRunner(unsigned int sr); 00940 void Check(); 00941 void Print(std::ostream& os = std::cout) const; 00942 protected: 00943 TokenRingSolver(StateManager<Input,State>* sm, 00944 OutputManager<Input,Output,State>* om, Input* in = NULL, Output* out = NULL); 00945 // Run all runners circularly on the same thread 00946 void Run(); 00947 int max_idle_rounds; 00949 // unsigned int start_runner; 00950 }; 00951 00964 template <class Input, class Output, class State> 00965 class AbstractMoveTester 00966 { 00967 public: 00968 AbstractMoveTester(std::string s); 00970 virtual ~AbstractMoveTester() {} 00971 std::string Name(); 00975 virtual void RunTestMenu(State& st) = 0; 00980 virtual void SetInput(Input* in) = 0; 00981 protected: 00982 std::string name; 00983 }; 00984 00989 template <class Input, class Output, class State, class Move> 00990 class MoveTester : public AbstractMoveTester<Input,Output,State> 00991 { 00992 public: 00993 MoveTester(StateManager<Input,State>* sm, OutputManager<Input,Output,State>* om, NeighborhoodExplorer<Input,State,Move>* ne, std::string nm, Input* in = NULL); 00994 void RunTestMenu(State& st); 00995 void SetInput(Input *in); 00996 protected: 00997 void ShowMenu(); 00998 void ExecuteChoice(State& st); 00999 StateManager<Input,State>* p_sm; 01001 NeighborhoodExplorer<Input,State,Move>* p_nhe; 01004 OutputManager<Input,Output,State>* p_om; 01006 Input* p_in; 01007 Output out; 01008 int choice; 01009 }; 01010 01014 template <class Input, class Output, class State> 01015 class StateTester 01016 { 01017 public: 01018 StateTester(StateManager<Input,State>* s, 01019 OutputManager<Input,Output,State>* o, Input* in = NULL); 01021 virtual ~StateTester() {} 01022 void RunTestMenu(State& s); 01023 void RunInputMenu(State& s); 01024 void SetInput(Input *in); 01025 protected: 01026 void ShowMenu(); 01027 void ShowReducedMenu(); 01028 void ExecuteChoice(State& st); 01029 StateManager<Input,State>* p_sm; 01031 OutputManager<Input,Output,State>* p_om; 01033 Input* p_in; 01034 Output out; 01035 int choice; 01036 }; 01037 01042 class AbstractTester 01043 { 01044 public: 01046 virtual ~AbstractTester() {} 01049 virtual void LoadInstance(std::string id) = 0; 01055 virtual int AddRunnerToSolver(std::string name, std::string type) = 0; 01056 void SetSolverTrials(unsigned int t); 01057 void SetLogFile(std::string s); 01058 void SetOutputPrefix(std::string s); 01059 void SetPlotPrefix(std::string s); 01061 virtual void StartSolver() = 0; 01067 virtual void SetRunningParameters(std::string name, std::string type, const ParameterBox& pb) = 0; 01068 protected: 01069 unsigned int trials; 01070 std::ostream* logstream; 01071 std::string output_file_prefix; 01073 std::string plot_file_prefix; 01075 }; 01076 01082 template <class Input, class Output, class State> 01083 class Tester : public AbstractTester 01084 { 01085 public: 01086 Tester(StateManager<Input,State>* sm, OutputManager<Input,Output,State>* om, Input* in = NULL); 01088 virtual ~Tester() {} 01089 void RunMainMenu(); 01090 void SetInput(Input *in); 01091 void SetMoveTester(AbstractMoveTester<Input,Output,State>* p_amt, int i); 01092 void AddMoveTester(AbstractMoveTester<Input,Output,State>* p_amt); 01093 void CleanMoveTesters(); 01094 void SetStateTester(StateTester<Input,Output,State>* p_st); 01095 void CleanRunners(); 01096 void SetRunner(Runner<Input,State>* p_ru, unsigned int i); 01097 void AddRunner(Runner<Input,State>* p_ru); 01098 void SetSolver(TokenRingSolver<Input,Output,State>* p_so); 01099 void SetSolverParameters(unsigned int rounds, unsigned int start_runner = 0); 01100 void LoadInstance(std::string id); 01101 int AddRunnerToSolver(std::string name, std::string type); 01102 void SetRunningParameters(std::string name, std::string type, const ParameterBox& pb); 01103 void StartSolver(); 01104 void ProcessBatch(std::string filename); 01105 void CleanSolver(); 01106 void Check(); 01107 void Print(std::ostream& os = std::cout) const; 01108 protected: 01109 void ShowMainMenu(); 01110 void ShowMovesMenu(); 01111 void ShowRunMenu(); 01112 void ShowDebuggingMenu(); 01113 void ExecuteMainChoice(); 01114 void ExecuteMovesChoice(); 01115 void ExecuteRunChoice(); 01116 void ExecuteDebuggingMenu(); 01117 std::vector<AbstractMoveTester<Input,Output,State>* > move_testers; 01119 std::vector<Runner<Input,State>* > runners; 01121 TokenRingSolver<Input,Output,State>* solver; 01124 StateTester<Input,Output,State>* state_tester; 01125 StateManager<Input,State>* p_sm; 01126 OutputManager<Input,Output,State>* p_om; 01127 State test_state; 01128 Input* p_in; 01129 Output out; 01130 int choice, 01131 sub_choice; 01132 }; 01133 }; // end namespace easylocal 01134 01135 #endif // define __EASYLOCAL_H |
|
Go to: the Main Page of the documentation. |