searchengine.hh

Go to the documentation of this file.

#if !defined(RUNNER_HH_)
#define RUNNER_HH_

#include <stdexcept>
#include <climits>
#include <chrono>
#include <condition_variable>
#include <atomic>

#include "easylocal/helpers/statemanager.hh"
#include "easylocal/helpers/neighborhoodexplorer.hh"
#include "easylocal/utils/interruptible.hh"
#include "easylocal/utils/parameter.hh"

namespace EasyLocal {
  
  namespace Debug {
    
    template <class Input, class State, typename CFtype>
    class AbstractTester;
  }
  
  namespace Core {
    
    
    template <class Input, class State, typename CFtype = int>
    class SearchEngine : public Interruptible<CostStructure<CFtype>, State&>, public Parametrized
    {
      friend class Debug::AbstractTester<Input, State, CFtype>;
      
    public:
      
      typedef Input InputType;
      typedef State StateType;
      typedef CFtype CostFunctionType;
      
      CostStructure<CFtype> Go(State& s) throw (ParameterNotSet, IncorrectParameterValue);
      
      CostStructure<CFtype> Step(State& s, unsigned int n = 1) throw (ParameterNotSet, IncorrectParameterValue);
      
      virtual void RegisterParameters();
      
      virtual void ReadParameters(std::istream& is = std::cin, std::ostream& os = std::cout);
      
      virtual void Print(std::ostream& os = std::cout) const;
      
      unsigned int IterationOfBest() const
      {
        return iteration_of_best;
      }
      
      unsigned long int Iteration() const
      {
        return iteration;
      }
      
      const std::string name;
      
      const std::string description;
      
      virtual ~SearchEngine() {}
      
      virtual size_t Modality() const = 0;
      
      static std::vector<SearchEngine<Input, State, CFtype>*> searchengines;
      
    protected:
      
      SearchEngine(const Input& i, StateManager<Input, State, CFtype>&, std::string, std::string);
      
      virtual void InitializeRun() throw (ParameterNotSet, IncorrectParameterValue) {}
      
      virtual void TerminateRun() = 0;
      
      virtual void PrepareIteration();
      
      virtual void CompleteIteration();
      
      virtual bool StopCriterion() = 0;
      
      virtual bool LowerBoundReached() const;
      
      bool MaxEvaluationsExpired() const;
      
      virtual void SelectMove() = 0;
      
      virtual bool AcceptableMoveFound() = 0;
      
      virtual void PrepareMove() {};
      
      virtual void MakeMove() = 0;
      
      virtual void CompleteMove() {};
      
      virtual std::function<CostStructure<CFtype>(State&)> MakeFunction()
      {
        return [this](State& s) -> CostStructure<CFtype> { return this->Go(s); };
      }
      
      bool no_acceptable_move_found;
      
      const Input& in;
      
      StateManager<Input, State, CFtype>& sm;
      
      std::shared_ptr<State> p_current_state,
      p_best_state;
      
      CostStructure<CFtype> current_state_cost;
      
      CostStructure<CFtype> best_state_cost;
      
      unsigned long int iteration_of_best;
      
      unsigned long int iteration;
      
      unsigned long int evaluations;
      
      Parameter<unsigned long int> max_evaluations;
      
      std::vector<double> weights;
      
    private:
      
      virtual void UpdateBestState() = 0;
      
      void InitializeRun(State&) throw (ParameterNotSet, IncorrectParameterValue);
      
      CostStructure<CFtype> TerminateRun(State&);
    };
    
    /*************************************************************************
     * Implementation
     *************************************************************************/
    
    template <class Input, class State, typename CFtype>
    std::vector<SearchEngine<Input, State, CFtype>*> SearchEngine<Input, State, CFtype>::searchengines;
    
    template <class Input, class State, typename CFtype>
    SearchEngine<Input, State, CFtype>::SearchEngine(const Input& in, StateManager<Input, State, CFtype>& sm, std::string name, std::string description)
    : // Parameters
    Parametrized(name, description), name(name), description(description), no_acceptable_move_found(false), in(in), sm(sm), weights(0)
    {
      // Add to the list of all searchengines
      searchengines.push_back(this);
    }
    
    template <class Input, class State, typename CFtype>
    void SearchEngine<Input, State, CFtype>::RegisterParameters()
    {
      max_evaluations("max_evaluations", "Maximum total number of cost function evaluations allowed", this->parameters);
      // This parameter has a default value
      max_evaluations = std::numeric_limits<unsigned long int>::max();
    }
    
    template <class Input, class State, typename CFtype>
    CostStructure<CFtype> SearchEngine<Input, State, CFtype>::Go(State& s) throw (ParameterNotSet, IncorrectParameterValue)
    {
      InitializeRun(s);
      while (!MaxEvaluationsExpired() && !StopCriterion() && !LowerBoundReached() && !this->TimeoutExpired())
      {
        PrepareIteration();
        try
        {
          SelectMove();
          if (AcceptableMoveFound())
          {
            PrepareMove();
            MakeMove();
            CompleteMove();
            UpdateBestState();
          }
        }
        catch (EmptyNeighborhood)
        {
          break;
        }
        CompleteIteration();
      }
      
      return TerminateRun(s);
    }
    
    
    template <class Input, class State, typename CFtype>
    void SearchEngine<Input, State, CFtype>::PrepareIteration()
    {
      no_acceptable_move_found = false;
      iteration++;
    }
    
    template <class Input, class State, typename CFtype>
    void SearchEngine<Input, State, CFtype>::CompleteIteration()
    {}
    
    template <class Input, class State, typename CFtype>
    void SearchEngine<Input, State, CFtype>::InitializeRun(State& s) throw (ParameterNotSet, IncorrectParameterValue)
    {
      iteration = 0;
      iteration_of_best = 0;
      evaluations = 0;
      p_best_state = std::make_shared<State>(s);    // creates the best state object by copying the content of s
      p_current_state = std::make_shared<State>(s); // creates the current state object by copying the content of s
      best_state_cost = current_state_cost = sm.CostFunctionComponents(s);
      InitializeRun();
    }
    
    template <class Input, class State, typename CFtype>
    CostStructure<CFtype> SearchEngine<Input, State, CFtype>::TerminateRun(State& s)
    {
      s = *p_best_state;
      TerminateRun();
      return best_state_cost;
    }
    
    template <class Input, class State, typename CFtype>
    bool SearchEngine<Input, State, CFtype>::LowerBoundReached() const
    {
      return sm.LowerBoundReached(current_state_cost.total);
    }
    
    template <class Input, class State, typename CFtype>
    bool SearchEngine<Input, State, CFtype>::MaxEvaluationsExpired() const
    {
      return evaluations >= max_evaluations;
    }
    
    template <class Input, class State, typename CFtype>
    void SearchEngine<Input, State, CFtype>::ReadParameters(std::istream& is, std::ostream& os)
    {
      os << this->name << " -- INPUT PARAMETERS" << std::endl;
      Parametrized::ReadParameters(is, os);
    }
    
    template <class Input, class State, typename CFtype>
    void SearchEngine<Input, State, CFtype>::Print(std::ostream& os) const
    {
      os  << "  " << this->name << std::endl;
      Parametrized::Print(os);  
    }
  }
}

#endif // _RUNNER_HH_