abstract-search.hh

Go to the documentation of this file.

/*
 * 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.
 *
 */

#include <iostream>

#ifndef METS_ABSTRACT_SEARCH_HH_
#define METS_ABSTRACT_SEARCH_HH_

namespace mets {


  class solution_recorder {
  public:
    solution_recorder() {}
    solution_recorder(const solution_recorder&);
    solution_recorder& operator=(const solution_recorder&);

    virtual 
    ~solution_recorder();

    virtual bool 
    accept(const feasible_solution& sol) = 0;

    virtual gol_type 
    best_cost() const = 0;
  };

  template<typename move_manager_type>
  class abstract_search : public subject< abstract_search<move_manager_type> >
  {
  public:
    abstract_search(feasible_solution& working,
                    solution_recorder& recorder,
                    move_manager_type& moveman)
      : subject<abstract_search<move_manager_type> >(), 
        solution_recorder_m(recorder),
        working_solution_m(working),
        moves_m(moveman),
        current_move_m(),
        step_m()
    { }
                         
    abstract_search(const abstract_search<move_manager_type>&);
    abstract_search& operator==(const abstract_search<move_manager_type>&);

    virtual 
    ~abstract_search() 
    { };

    enum {
      MOVE_MADE = 0,  
      IMPROVEMENT_MADE,
      ITERATION_BEGIN,
      ITERATION_END,
      LAST
    };
     
    virtual void
    search() 
      throw(no_moves_error) = 0;

    const solution_recorder&
    recorder() const 
    { return solution_recorder_m; };
    
    const feasible_solution&
    working() const 
    { return working_solution_m; }
    
    feasible_solution&
    working() 
    { return working_solution_m; }

    const move&
    current_move() const 
    { return **current_move_m; }

    move&
    current_move() 
    { return **current_move_m; }
 
    const move_manager_type& 
    move_manager() const 
    { return moves_m; }

    move_manager_type& 
    move_manager() 
    { return moves_m; }

    int
    step() const 
    { return step_m; }
    
  protected:
    solution_recorder& solution_recorder_m;
    feasible_solution& working_solution_m;
    move_manager_type& moves_m;
    typename move_manager_type::iterator current_move_m;
    int step_m;
  };



  class best_ever_solution : public solution_recorder 
  {
  public:
    best_ever_solution(evaluable_solution& best) : 
      solution_recorder(), 
      best_ever_m(best) 
    { }

    best_ever_solution();
    best_ever_solution(const best_ever_solution&);
    best_ever_solution& operator=(const best_ever_solution&);

    bool accept(const feasible_solution& sol);

    const evaluable_solution& best_seen() const 
    { return best_ever_m; }

    gol_type best_cost() const 
    { return best_ever_m.cost_function(); }
  protected:
    evaluable_solution& best_ever_m;
  };
    
  template<typename move_manager_type>
  class search_listener : public observer<abstract_search<move_manager_type> >
  {
  public:
    typedef abstract_search<move_manager_type> search_type;
    explicit
    search_listener() : observer<search_type>() 
    { }

    search_listener(const search_listener<search_type>& other);
    search_listener<search_type>& 
    operator=(const search_listener<search_type>& other);

    virtual 
    ~search_listener() 
    { }

    virtual void
    update(search_type* algorithm) = 0;
  };


  template<typename neighborhood_t>
  struct iteration_logger : public mets::search_listener<neighborhood_t>
  {
    explicit
    iteration_logger(std::ostream& o) 
      : mets::search_listener<neighborhood_t>(), 
        iteration(0), 
        os(o) 
    { }
    
    void 
    update(mets::abstract_search<neighborhood_t>* as) 
    {
      const mets::feasible_solution& p = as->working();
      if(as->step() == mets::abstract_search<neighborhood_t>::MOVE_MADE)
        {
          os << iteration++ << "\t" 
             << static_cast<const mets::evaluable_solution&>(p).cost_function()
             << "\n";
        }
    }
    
  protected:
    int iteration;
    std::ostream& os;
  };

  template<typename neighborhood_t>
  struct improvement_logger : public mets::search_listener<neighborhood_t>
  {
    explicit
    improvement_logger(std::ostream& o, gol_type epsilon = 1e-7) 
      : mets::search_listener<neighborhood_t>(), 
        iteration_m(0), 
        best_m(std::numeric_limits<double>::max()),
        os_m(o),
        epsilon_m(epsilon)
    { }
    
    void 
    update(mets::abstract_search<neighborhood_t>* as) 
    {
      const mets::feasible_solution& p = as->working();

      if(as->step() == mets::abstract_search<neighborhood_t>::MOVE_MADE)
        {
          iteration_m++;
          double val = static_cast<const mets::evaluable_solution&>(p)
            .cost_function();
          if(val < best_m - epsilon_m) 
            {        
              best_m = val;
              os_m << iteration_m << "\t" 
                   << best_m
                   << " (*)\n";
            }
        }
    }
    
  protected:
    int iteration_m;
    double best_m;
    std::ostream& os_m;
    gol_type epsilon_m;
  };



}

inline mets::solution_recorder::~solution_recorder() 
{ }

inline bool
mets::best_ever_solution::accept(const mets::feasible_solution& sol)
{
  const evaluable_solution& s = dynamic_cast<const mets::evaluable_solution&>(sol);
  if(s.cost_function() < best_ever_m.cost_function())
    {
      best_ever_m.copy_from(s);
      return true;
    }
  return false;
}

#endif