neighborhoodexplorer.hh

Go to the documentation of this file.

#if !defined(_NEIGHBORHOOD_EXPLORER_HH_)
#define _NEIGHBORHOOD_EXPLORER_HH_

#include <typeinfo>
#include <iostream>
#include <stdexcept>
#include <memory>
#include <iterator>
#include <functional>

#include "easylocal/helpers/deltacostcomponent.hh"
#include "easylocal/helpers/statemanager.hh"
#include "easylocal/utils/random.hh"

namespace EasyLocal {
  
  namespace Core {    
    
    class EmptyNeighborhood : public std::logic_error
    {
    public:
      EmptyNeighborhood() : std::logic_error("Empty neighborhood") {}
    };    
    
    template <class Move, typename CFtype>
    struct EvaluatedMove
    {
      static EvaluatedMove empty;
      EvaluatedMove() : is_valid(false) {}
      EvaluatedMove(const Move& move) : move(move), is_valid(false) {}
      EvaluatedMove(const Move& move, CostStructure<CFtype> cost) : is_valid(true), move(move), cost(cost) {}
      
      Move move;
      bool is_valid;
      CostStructure<CFtype> cost;
    };
    
    template <class Move, typename CFtype>
    std::ostream& operator<<(std::ostream& os, const EvaluatedMove<Move, CFtype>& em)
    {
      os << em.move;
      if (em.is_valid)
        os << " " << em.cost;
      else
        os << " not_valid";
      return os;
    }
    
    template <class Move, typename CFtype>
    EvaluatedMove<Move, CFtype> EvaluatedMove<Move, CFtype>::empty = EvaluatedMove<Move, CFtype>();
    
    template <class Input, class State, class Move, typename CFtype = int>
    class NeighborhoodExplorer
    {
    public:
      typedef Input InputType;
      typedef Move MoveType;
      typedef State StateType;
      typedef CFtype CostType;      
      
      typedef typename std::function<bool(const Move& mv, CostStructure<CFtype> move_cost)> MoveAcceptor;
      
      /* Copies all the delta cost components from another neighborhood explorer of the same class
       @param ne the neighborhood explorer from which the data has to be copied
       */
      void CopyDeltaCostComponents(const NeighborhoodExplorer<Input, State, Move, CFtype>& ne)
      {
        this->delta_hard_cost_components = ne.delta_hard_cost_components;
        this->delta_soft_cost_components = ne.delta_soft_cost_components;
        this->dcc_adapters = ne.dcc_adapters;
        this->unimplemented_hard_components = ne.unimplemented_hard_components;
        this->unimplemented_soft_components = ne.unimplemented_soft_components;
      }
      
      virtual bool FeasibleMove(const State &st, const Move& mv) const
      { return true; }
      
      virtual void RandomMove(const State &st, Move& mv) const throw (EmptyNeighborhood) = 0;
      
      virtual void FirstMove(const State& st, Move& mv) const throw (EmptyNeighborhood) = 0;
      
      virtual bool NextMove(const State &st, Move& mv) const = 0;
      
      virtual void MakeMove(State &st, const Move& mv) const = 0;
      
      virtual CostStructure<CFtype> DeltaCostFunctionComponents(const State& st, const Move& mv, const std::vector<double>& weights = std::vector<double>(0)) const;
      
      virtual void AddDeltaCostComponent(DeltaCostComponent<Input, State, Move, CFtype>& dcc);
      
      virtual void AddCostComponent(CostComponent<Input, State, CFtype>& cc);
      
      virtual size_t DeltaCostComponents() const
      {
        return delta_hard_cost_components.size() + delta_soft_cost_components.size();
      }
      
      virtual size_t Modality() const
      { return 1; }
      
      NeighborhoodExplorer(const Input& in, StateManager<Input, State, CFtype>& sm, std::string name);
      
      virtual ~NeighborhoodExplorer() {}
      
      virtual EvaluatedMove<Move, CFtype> SelectFirst(const State& st, size_t& explored, const MoveAcceptor& AcceptMove, const std::vector<double>& weights = std::vector<double>(0)) const throw (EmptyNeighborhood);
      
      virtual EvaluatedMove<Move, CFtype> SelectBest(const State& st, size_t& explored, const MoveAcceptor& AcceptMove, const std::vector<double>& weights = std::vector<double>(0)) const throw (EmptyNeighborhood);
      
      virtual EvaluatedMove<Move, CFtype> RandomFirst(const State& st, size_t samples, size_t& explored, const MoveAcceptor& AcceptMove, const std::vector<double>& weights = std::vector<double>(0)) const throw (EmptyNeighborhood);
      
      virtual EvaluatedMove<Move, CFtype> RandomBest(const State& st, size_t samples, size_t& explored, const MoveAcceptor& AcceptMove, const std::vector<double>& weights = std::vector<double>(0)) const throw (EmptyNeighborhood);
      
    protected:
      
      const Input& in;
      StateManager<Input, State, CFtype>& sm; 
      std::vector<DeltaCostComponent<Input, State, Move, CFtype>*> delta_hard_cost_components, delta_soft_cost_components;
      
      std::vector<std::shared_ptr<DeltaCostComponentAdapter<Input, State, Move, CFtype>>> dcc_adapters;
      
      std::string name;
      
      bool unimplemented_hard_components, unimplemented_soft_components;
    };
    
    template <class Input, class State, class Move, typename CFtype>
    NeighborhoodExplorer<Input, State, Move, CFtype>::NeighborhoodExplorer(const Input& i, StateManager<Input, State, CFtype>& e_sm, std::string e_name)
    : in(i), sm(e_sm), name(e_name), unimplemented_hard_components(false), unimplemented_soft_components(false)
    {}
    
    template <class Input, class State, class Move, typename CFtype>
    CostStructure<CFtype> NeighborhoodExplorer<Input, State, Move, CFtype>::DeltaCostFunctionComponents(const State& st, const Move & mv, const std::vector<double>& weights) const
    {
      CFtype delta_hard_cost = 0, delta_soft_cost = 0;
      double delta_weighted_cost = 0.0;
      std::vector<CFtype> delta_cost_function(CostComponent<Input, State, CFtype>::CostComponents(), (CFtype)0);
      
      for (size_t i = 0; i < delta_hard_cost_components.size(); i++)
      {
        DeltaCostComponent<Input, State, Move, CFtype>* dcc = delta_hard_cost_components[i];
        if (dcc->IsDeltaImplemented())
        {
          CFtype current_delta_cost = delta_cost_function[dcc->Index()] = dcc->DeltaCost(st, mv);
          delta_hard_cost += current_delta_cost;
          if (!weights.empty())
            delta_weighted_cost += HARD_WEIGHT * weights[dcc->Index()] * current_delta_cost;
        }
      }
      for (size_t i = 0; i < delta_soft_cost_components.size(); i++)
      {
        DeltaCostComponent<Input, State, Move, CFtype>* dcc = delta_soft_cost_components[i];
        if (dcc->IsDeltaImplemented())
        {
          CFtype current_delta_cost = delta_cost_function[dcc->Index()] = dcc->DeltaCost(st, mv);
          delta_soft_cost += current_delta_cost;
          if (!weights.empty())
            delta_weighted_cost += weights[dcc->Index()] * current_delta_cost;
        }
      }
      
      // only if there is at least one unimplemented delta cost component (i.e., a wrapper along a cost component)
      if (unimplemented_hard_components || unimplemented_soft_components)
      {
        // compute move
        State new_st = st;
        MakeMove(new_st, mv);
        
        if (unimplemented_hard_components)
          for (size_t i = 0; i < delta_hard_cost_components.size(); i++)
          {
            DeltaCostComponent<Input, State, Move, CFtype>* dcc = delta_hard_cost_components[i];
            if (!dcc->IsDeltaImplemented())
            {
              // get reference to cost component
              CostComponent<Input, State, CFtype>& cc = dcc->GetCostComponent();
              CFtype current_delta_cost = delta_cost_function[cc.Index()] =  cc.Weight() * (cc.ComputeCost(new_st) - cc.ComputeCost(st));
              delta_hard_cost += current_delta_cost;
              if (!weights.empty())
                delta_weighted_cost += HARD_WEIGHT * weights[cc.Index()] * current_delta_cost;
            }
          }
        if (unimplemented_soft_components)
          for (size_t i = 0; i < delta_soft_cost_components.size(); i++)
          {
            DeltaCostComponent<Input, State, Move, CFtype>* dcc = delta_soft_cost_components[i];
            if (!dcc->IsDeltaImplemented())
            {
              // get reference to cost component
              CostComponent<Input, State, CFtype>& cc = dcc->GetCostComponent();
              CFtype current_delta_cost =  delta_cost_function[cc.Index()] =  cc.Weight() * (cc.ComputeCost(new_st) - cc.ComputeCost(st));
              delta_soft_cost += current_delta_cost;
              if (!weights.empty())
                delta_weighted_cost += weights[cc.Index()] * current_delta_cost;
            }
          }
      }
      
      if (!weights.empty())
        return CostStructure<CFtype>(HARD_WEIGHT * delta_hard_cost + delta_soft_cost, delta_weighted_cost, delta_hard_cost, delta_soft_cost, delta_cost_function);
      else
        return CostStructure<CFtype>(HARD_WEIGHT * delta_hard_cost + delta_soft_cost, delta_hard_cost, delta_soft_cost, delta_cost_function);
    }
    
    template <class Input, class State, class Move, typename CFtype>
    void NeighborhoodExplorer<Input, State, Move, CFtype>::AddDeltaCostComponent(DeltaCostComponent<Input, State, Move, CFtype>& dcc)
    {
      if (dcc.IsHard())
        delta_hard_cost_components.push_back(&dcc);
      else
        delta_soft_cost_components.push_back(&dcc);
    }
    
    template <class Input, class State, class Move, typename CFtype>
    void NeighborhoodExplorer<Input, State, Move, CFtype>::AddCostComponent(CostComponent<Input, State, CFtype>& cc)
    {
      
      dcc_adapters.push_back(std::make_shared<DeltaCostComponentAdapter<Input, State, Move, CFtype>>(in, cc, *this));
      if (cc.IsHard())
      {
        unimplemented_hard_components = true;
        delta_hard_cost_components.push_back(dcc_adapters[dcc_adapters.size() - 1].get());
      }
      else
      {
        unimplemented_soft_components = true;
        delta_soft_cost_components.push_back(dcc_adapters[dcc_adapters.size() - 1].get());
      }
    }
        
    template <class Input, class State, class Move, typename CFtype>
    EvaluatedMove<Move, CFtype> NeighborhoodExplorer<Input, State, Move, CFtype>::SelectFirst(const State& st, size_t& explored, const MoveAcceptor& AcceptMove, const std::vector<double>& weights) const throw (EmptyNeighborhood)
    {
      explored = 0;
      EvaluatedMove<Move, CFtype> mv;
      FirstMove(st, mv.move);
      do
      {
        mv.cost = DeltaCostFunctionComponents(st, mv.move, weights);
        explored++;
        mv.is_valid = true;
        
        if (AcceptMove(mv.move, mv.cost))
          return mv; // mv passes the acceptance criterion
      }
      while (NextMove(st, mv.move));
      
      // exiting this loop means that there is no mv passing the acceptance criterion
      return EvaluatedMove<Move, CFtype>::empty;
    }
    
    template <class Input, class State, class Move, typename CFtype>
    EvaluatedMove<Move, CFtype> NeighborhoodExplorer<Input, State, Move, CFtype>::SelectBest(const State& st, size_t& explored, const MoveAcceptor& AcceptMove, const std::vector<double>& weights) const throw (EmptyNeighborhood)
    {
      unsigned int number_of_bests = 0; // number of moves found with the same best value
      explored = 0;
      EvaluatedMove<Move, CFtype> mv, best_move;
      FirstMove(st, mv.move);
      
      do
      {
        mv.cost = DeltaCostFunctionComponents(st, mv.move, weights);
        explored++;
        mv.is_valid = true;
        if (AcceptMove(mv.move, mv.cost))
        {
          if (number_of_bests == 0)
          {
            best_move = mv;
            number_of_bests = 1;
          }
          else if (mv.cost < best_move.cost)
          {
            best_move = mv;
            number_of_bests = 1;
          }
          else if (mv.cost == best_move.cost)
          {
            if (Random::Int(0, number_of_bests) == 0) // accept the move with probability 1 / (1 + number_of_bests)
              best_move = mv;
              number_of_bests++;
          }
        }
      }
      while (NextMove(st, mv.move));
      
      if (number_of_bests == 0)
        return EvaluatedMove<Move, CFtype>::empty;
      
      return best_move;
    }
    
    template <class Input, class State, class Move, typename CFtype>
    EvaluatedMove<Move, CFtype> NeighborhoodExplorer<Input, State, Move, CFtype>::RandomFirst(const State& st, size_t samples, size_t& explored, const MoveAcceptor& AcceptMove, const std::vector<double>& weights) const throw (EmptyNeighborhood)
    {
      EvaluatedMove<Move, CFtype> mv;
      explored = 0;
      while (explored < samples)
      {
        RandomMove(st, mv.move);
        mv.cost = DeltaCostFunctionComponents(st, mv.move, weights);
        mv.is_valid = true;
        explored++;
        if (AcceptMove(mv.move, mv.cost))
          return mv;
      }
      // exiting this loop means that there is no mv passing the acceptance criterion
      return EvaluatedMove<Move, CFtype>::empty;
    }
    
    template <class Input, class State, class Move, typename CFtype>
    EvaluatedMove<Move, CFtype> NeighborhoodExplorer<Input, State, Move, CFtype>::RandomBest(const State& st, size_t samples, size_t& explored, const MoveAcceptor& AcceptMove, const std::vector<double>& weights) const throw (EmptyNeighborhood)
    {
      unsigned int number_of_bests = 0; // number of moves found with the same best value
      EvaluatedMove<Move, CFtype> mv, best_move;
      
      explored = 0;
      while (explored < samples)
      {
        RandomMove(st, mv.move);
        mv.cost = DeltaCostFunctionComponents(st, mv.move, weights);
        mv.is_valid = true;
        explored++;
        if (AcceptMove(mv.move, mv.cost))
        {
          if (number_of_bests == 0)
          {
            best_move = mv;
            number_of_bests = 1;
          }
          else if (mv.cost < best_move.cost)
          {
            best_move = mv;
            number_of_bests = 1;
          }
          else if (mv.cost == best_move.cost)
          {
            if (Random::Int(0, number_of_bests) == 0) // accept the move with probability 1 / (1 + number_of_bests)
              best_move = mv;
              number_of_bests++;
          }
        }
      }
      
      if (number_of_bests == 0)
        return EvaluatedMove<Move, CFtype>::empty;
      
      return best_move;
    }
  }
}

#endif // _NEIGHBORHOOD_EXPLORER_HH_