model.hh

Go to the documentation of this file.

// METSlib source file - model.hh                                -*- C++ -*-
//
/*
 * Software License Agreement (BSD License)
 *
 *  Copyright (c) 2006-2012, Mirko Maischberger <mirko.maischberger@gmail.com>
 *  All rights reserved.
 *
 *  Redistribution and use in source and binary forms, with or without
 *  modification, are permitted provided that the following conditions
 *  are met:
 *
 *   * Redistributions of source code must retain the above copyright
 *     notice, this list of conditions and the following disclaimer.
 *   * Redistributions in binary form must reproduce the above
 *     copyright notice, this list of conditions and the following
 *     disclaimer in the documentation and/or other materials provided
 *     with the distribution.
 *
 *  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 *  "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 *  LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
 *  FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
 *  COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
 *  INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
 *  BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 *  LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
 *  CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 *  LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
 *  ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 *  POSSIBILITY OF SUCH DAMAGE.
 *
 */

#ifndef METS_MODEL_HH_
#define METS_MODEL_HH_

namespace mets {

  typedef double gol_type;

  class no_moves_error 
    : public std::runtime_error
  {
  public:
    no_moves_error() 
      : std::runtime_error("There are no more available moves.") {}
    no_moves_error(const std::string message) 
      : std::runtime_error(message) {}
  };

  class sequence
  {
  public:
    sequence(int start = 0) 
      : value_m(start) 
    { }
    int operator()() 
    { return value_m++; }
  protected:
    int value_m;
  };

  class clonable {
  public:
    virtual 
    ~clonable() {};
    virtual clonable* 
    clone() const = 0;
  };

  class hashable {
  public:
    virtual 
    ~hashable() {};
    virtual size_t 
    hash() const = 0;
  };

  class copyable {
  public:
    virtual 
    ~copyable() {};
    virtual void 
    copy_from(const copyable&) = 0;
  };

  class printable {
  public:
    virtual 
    ~printable() {}
    virtual void 
    print(std::ostream& /*os*/) const { };
  };


  class feasible_solution
  {
  public:
    virtual
    ~feasible_solution() 
    { }

  };


  class evaluable_solution : public feasible_solution, 
                             public copyable
  { 
  public:
    virtual gol_type 
    cost_function() const = 0;
  };

  class permutation_problem: public evaluable_solution 
  {
  public:
    
    permutation_problem(); 

    permutation_problem(int n) : pi_m(n), cost_m(0.0)
    { std::generate(pi_m.begin(), pi_m.end(), sequence(0)); }

    void copy_from(const copyable& other);

    virtual gol_type
    compute_cost() const = 0;

    virtual gol_type
    evaluate_swap(int i, int j) const = 0;

    size_t 
    size() const
    { return pi_m.size(); }

    gol_type cost_function() const 
    { return cost_m; }

    void
    update_cost() 
    { cost_m = compute_cost(); }
    
    void
    apply_swap(int i, int j)
    { cost_m += evaluate_swap(i,j); std::swap(pi_m[i], pi_m[j]); }
    

  protected:
    std::vector<int> pi_m;
    gol_type cost_m;
    template<typename random_generator> 
    friend void random_shuffle(permutation_problem& p, random_generator& rng);
  };


  template<typename random_generator>
  void random_shuffle(permutation_problem& p, random_generator& rng)
  {
#if defined (METSLIB_TR1_BOOST)
    boost::uniform_int<size_t> unigen;
    boost::variate_generator<random_generator&,
      boost::uniform_int<size_t> >gen(rng, unigen);
#elif defined (METSLIB_HAVE_UNORDERED_MAP) && !defined (METSLIB_TR1_MIXED_NAMESPACE)
    std::uniform_int<size_t> unigen;
    std::variate_generator<random_generator&, 
      std::uniform_int<size_t> >gen(rng, unigen);
#else
    std::tr1::uniform_int<size_t> unigen;
    std::tr1::variate_generator<random_generator&, 
      std::tr1::uniform_int<size_t> >gen(rng, unigen);
#endif
    std::random_shuffle(p.pi_m.begin(), p.pi_m.end(), gen);
    p.update_cost();
  }
  
  template<typename random_generator>
  void perturbate(permutation_problem& p, unsigned int n, random_generator& rng)
  {
#if defined (METSLIB_TR1_BOOST)
    boost::uniform_int<> int_range;
#elif defined (METSLIB_HAVE_UNORDERED_MAP) && !defined (METSLIB_TR1_MIXED_NAMESPACE)
    std::uniform_int<> int_range;
#else
    std::tr1::uniform_int<> int_range;
#endif
    for(unsigned int ii=0; ii!=n;++ii) 
      {
        int p1 = int_range(rng, p.size());
        int p2 = int_range(rng, p.size());
        while(p1 == p2) 
          p2 = int_range(rng, p.size());
        p.apply_swap(p1, p2);
      }
  }
    
  class move
  {
  public:

    virtual 
    ~move() 
    { }; 

    virtual gol_type
    evaluate(const feasible_solution& sol) const = 0;

    virtual void
    apply(feasible_solution& sol) const = 0;


  };

  class mana_move : 
    public move, 
    public clonable, 
    public hashable
  {
  public:
    
    virtual mana_move*
    opposite_of() const 
    { return static_cast<mana_move*>(clone()); }
    
    virtual bool 
    operator==(const mana_move& other) const = 0;
    
  };

  template<typename rndgen> class swap_neighborhood; // fw decl

  class swap_elements : public mets::mana_move 
  {
  public:  

    swap_elements(int from, int to) 
      : p1(std::min(from,to)), p2(std::max(from,to)) 
    { }
    
    gol_type
    evaluate(const mets::feasible_solution& s) const
    { const permutation_problem& sol = 
        static_cast<const permutation_problem&>(s);
      return sol.cost_function() + sol.evaluate_swap(p1, p2); }
    
    void
    apply(mets::feasible_solution& s) const
    { permutation_problem& sol = static_cast<permutation_problem&>(s);
      sol.apply_swap(p1, p2); }
            
    clonable* 
    clone() const
    { return new swap_elements(p1, p2); }

    size_t
    hash() const
    { return (p1)<<16^(p2); }
    
    bool 
    operator==(const mets::mana_move& o) const;
    
    void change(int from, int to)
    { p1 = std::min(from,to); p2 = std::max(from,to); }

  protected:
    int p1; 
    int p2; 

    template <typename> 
    friend class swap_neighborhood;
  };

  class invert_subsequence : public mets::mana_move 
  {
  public:  

    invert_subsequence(int from, int to) 
      : p1(from), p2(to) 
    { }
    
    gol_type
    evaluate(const mets::feasible_solution& s) const;

    void
    apply(mets::feasible_solution& s) const;
        
    clonable* 
    clone() const
    { return new invert_subsequence(p1, p2); }

    size_t
    hash() const
    { return (p1)<<16^(p2); }
    
    bool 
    operator==(const mets::mana_move& o) const;
    
    void change(int from, int to)
    { p1 = from; p2 = to; }
    
  protected:
    int p1; 
    int p2; 
    
    // template <typename> 
    // friend class invert_full_neighborhood;
  };

  class move_manager
  {
  public:
    move_manager() 
      : moves_m() 
    { }

    virtual ~move_manager() 
    { }

    virtual void 
    refresh(mets::feasible_solution& s) = 0;
    
    typedef std::deque<move*>::iterator iterator;
    
    typedef std::deque<move*>::size_type size_type;

    iterator begin() 
    { return moves_m.begin(); }

    iterator end() 
    { return moves_m.end(); }

    size_type size() const 
    { return moves_m.size(); }

  protected:
    std::deque<move*> moves_m; 
    move_manager(const move_manager&);
  };
  

#if defined (METSLIB_TR1_BOOST)
  template<typename random_generator = boost::minstd_rand0>
#elif defined (METSLIB_HAVE_UNORDERED_MAP) && !defined (METSLIB_TR1_MIXED_NAMESPACE)
  template<typename random_generator = std::minstd_rand0>
#else
  template<typename random_generator = std::tr1::minstd_rand0>
#endif
  class swap_neighborhood : public mets::move_manager
  {
  public:
    swap_neighborhood(random_generator& r, 
                      unsigned int moves);

    ~swap_neighborhood();

    void refresh(mets::feasible_solution& s);
    
  protected:
    random_generator& rng;

#if defined (METSLIB_TR1_BOOST)
    boost::uniform_int<> int_range;
#elif defined (METSLIB_HAVE_UNORDERED_MAP) && !defined (METSLIB_TR1_MIXED_NAMESPACE)
    std::uniform_int<> int_range;
#else
    std::tr1::uniform_int<> int_range;
#endif
    unsigned int n;

    void randomize_move(swap_elements& m, unsigned int size);
  };

  //________________________________________________________________________
  template<typename random_generator>
  mets::swap_neighborhood< random_generator
                           >::swap_neighborhood(random_generator& r, 
                                                unsigned int moves)
                             : mets::move_manager(), rng(r), int_range(0), n(moves)
  { 
    // n simple moves
    for(unsigned int ii = 0; ii != n; ++ii) 
      moves_m.push_back(new swap_elements(0,0));
  }  
  
  template<typename random_generator>
  mets::swap_neighborhood<random_generator>::~swap_neighborhood()
  {
    // delete all moves
    for(iterator ii = begin(); ii != end(); ++ii)
      delete (*ii);
  }

  template<typename random_generator>
  void
  mets::swap_neighborhood<random_generator>::refresh(mets::feasible_solution& s)
  {
    permutation_problem& sol = dynamic_cast<permutation_problem&>(s);
    iterator ii = begin();
    
    // the first n are simple qap_moveS
    for(unsigned int cnt = 0; cnt != n; ++cnt)
      {
        swap_elements* m = static_cast<swap_elements*>(*ii);
        randomize_move(*m, sol.size());
        ++ii;
      }
    
  }
  
  template<typename random_generator>
  void
  mets::swap_neighborhood<random_generator
                          >::randomize_move(swap_elements& m, unsigned int size)
  {
    int p1 = int_range(rng, size);
    int p2 = int_range(rng, size);
    while(p1 == p2) 
      p2 = int_range(rng, size);
    // we are friend, so we know how to handle the nuts&bolts of
    // swap_elements
    m.p1 = std::min(p1,p2); 
    m.p2 = std::max(p1,p2); 
  }

  class swap_full_neighborhood : public mets::move_manager
  {
  public:
    swap_full_neighborhood(int size) : move_manager()
    {
      for(int ii(0); ii!=size-1; ++ii)
        for(int jj(ii+1); jj!=size; ++jj)
          moves_m.push_back(new swap_elements(ii,jj));
    } 

    ~swap_full_neighborhood() { 
      for(move_manager::iterator it = moves_m.begin(); 
          it != moves_m.end(); ++it)
        delete *it;
    }
    
    void refresh(mets::feasible_solution& /*s*/) { }
    
  };


  class invert_full_neighborhood : public mets::move_manager
  {
  public:
    invert_full_neighborhood(int size) : move_manager()
    {
      for(int ii(0); ii!=size; ++ii)
        for(int jj(0); jj!=size; ++jj)
          if(ii != jj)
            moves_m.push_back(new invert_subsequence(ii,jj));
    } 

    ~invert_full_neighborhood() { 
      for(std::deque<move*>::iterator it = moves_m.begin(); 
          it != moves_m.end(); ++it)
        delete *it;
    }

    void 
    refresh(mets::feasible_solution& /*s*/)
    { }

  };


  class mana_move_hash 
  {
  public:
    size_t operator()(mana_move const* mov) const 
    {return mov->hash();}
  };
  
  template<typename Tp>
  struct dereferenced_equal_to 
  {
    bool operator()(const Tp l, 
                    const Tp r) const 
    { return l->operator==(*r); }
  };

}

//________________________________________________________________________
inline void
mets::permutation_problem::copy_from(const mets::copyable& other)
{
  const mets::permutation_problem& o = 
    dynamic_cast<const mets::permutation_problem&>(other);
  pi_m = o.pi_m;
  cost_m = o.cost_m;
}

//________________________________________________________________________
inline bool
mets::swap_elements::operator==(const mets::mana_move& o) const
{
  try {
    const mets::swap_elements& other = 
      dynamic_cast<const mets::swap_elements&>(o);
    return (this->p1 == other.p1 && this->p2 == other.p2);
  } catch (std::bad_cast& e) {
    return false;
  }
}

//________________________________________________________________________

inline void
mets::invert_subsequence::apply(mets::feasible_solution& s) const
{ 
  mets::permutation_problem& sol = 
    static_cast<mets::permutation_problem&>(s);
  int size = static_cast<int>(sol.size());
  int top = p1 < p2 ? (p2-p1+1) : (size+p2-p1+1);
  for(int ii(0); ii!=top/2; ++ii)
    {
      int from = (p1+ii)%size;
      int to = (size+p2-ii)%size;
      assert(from >= 0 && from < size);
      assert(to >= 0 && to < size);
      sol.apply_swap(from, to); 
    }
}

inline mets::gol_type
mets::invert_subsequence::evaluate(const mets::feasible_solution& s) const
{ 
  const mets::permutation_problem& sol = 
    static_cast<const mets::permutation_problem&>(s);
  int size = static_cast<int>(sol.size());
  int top = p1 < p2 ? (p2-p1+1) : (size+p2-p1+1);
  mets::gol_type eval = 0.0;
  for(int ii(0); ii!=top/2; ++ii)
    {
      int from = (p1+ii)%size;
      int to = (size+p2-ii)%size;
      assert(from >= 0 && from < size);
      assert(to >= 0 && to < size);
      eval += sol.evaluate_swap(from, to); 
    }
  return eval;
}

inline bool
mets::invert_subsequence::operator==(const mets::mana_move& o) const
{
  try {
    const mets::invert_subsequence& other = 
      dynamic_cast<const mets::invert_subsequence&>(o);
    return (this->p1 == other.p1 && this->p2 == other.p2);
  } catch (std::bad_cast& e) {
    return false;
  }
}

#endif