custom_components.hpp

Go to the documentation of this file.

//=======================================================================
// Copyright (c) 2013 Piotr Wygocki
//
// Distributed under the Boost Software License, Version 1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
//=======================================================================
#ifndef PAAL_CUSTOM_COMPONENTS_HPP
#define PAAL_CUSTOM_COMPONENTS_HPP

#include "paal/utils/functors.hpp"

#include "paal/local_search/local_search.hpp"

#include <chrono>
#include <random>

namespace paal {
namespace local_search {

template <typename Gain = utils::return_one_functor,
          typename Condition = utils::always_true>
struct conditional_gain_adaptor {

    conditional_gain_adaptor(Gain gain = Gain(), Condition cond = Condition())
        : m_gain(std::move(gain)), m_condition(std::move(cond)) {}

    template <typename... Args>
    auto operator()(Args &&... args)
        ->decltype(std::declval<Gain>()(std::forward<Args>(args)...)) {
        if (!m_condition(std::forward<Args>(args)...)) {
            return 0;
        }
        return m_gain(std::forward<Args>(args)...);
    }

  private:
    Gain m_gain;
    Condition m_condition;
};

template <typename Gain = utils::return_one_functor,
          typename Condition = utils::always_true>
conditional_gain_adaptor<Gain, Condition>
make_conditional_gain_adaptor(Gain gain = Gain(),
                              Condition cond = Condition()) {
    return conditional_gain_adaptor<Gain, Condition>(std::move(gain),
                                                     std::move(cond));
}

template <typename Gain, typename ValueType> class gain_cut_small_improves {
  public:
    gain_cut_small_improves(Gain gain, ValueType currOpt, double epsilon)
        : m_gain(std::move(gain)), m_curr_opt(currOpt), m_epsilon(epsilon) {}

    template <typename... Args> ValueType operator()(Args &&... args) {
        ValueType dist = m_gain(std::forward<Args>(args)...);
        if (dist > m_epsilon * m_curr_opt) {
            m_curr_opt -= dist;
            return dist;
        }
        return 0;
    }

    void set_epsilon(double e) { m_epsilon = e; }

    void set_current_opt(ValueType opt) { m_curr_opt = opt; }

  private:
    Gain m_gain;
    ValueType m_curr_opt;
    double m_epsilon;
};

class stop_condition_count_limit {
  public:
    stop_condition_count_limit(unsigned limit) : m_cnt(0), m_limit(limit) {}

    template <typename... Args> bool operator()(Args &&...) const {
        return ++m_cnt >= m_limit;
    }

  private:
    mutable unsigned m_cnt;
    const unsigned m_limit;
};

template <typename duration = std::chrono::seconds,
          typename clock = std::chrono::system_clock>
class stop_condition_time_limit {
  public:
    stop_condition_time_limit(duration d)
        : m_duration(d), m_start(clock::now()) {}

    template <typename... Args> bool operator()(Args &&...) {
        return m_start + m_duration < clock::now();
    }

    void restart() { m_start = clock::now(); }

  private:
    typename clock::time_point m_start;
    const duration m_duration;
};

template <typename Gain, typename ValueType> struct compute_gain_wrapper {
    compute_gain_wrapper(compute_gain_wrapper gain, ValueType &val)
        : m_gain(gain), m_val(val) {}

    template <typename... Args> ValueType operator()(Args &&... args) {
        auto diff = m_gain(std::forward<Args>(args)...);
        m_val += diff;
        return diff;
    }

    ValueType get_val() const { return m_val; }

  private:
    Gain m_gain;
    ValueType &m_val;
};

template <typename TabuList, typename Gain = utils::return_one_functor,
          typename AspirationCriteria = utils::always_true>
struct tabu_gain_adaptor {

    tabu_gain_adaptor(TabuList tabuList = TabuList(), Gain gain = Gain(),
                      AspirationCriteria aspirationCriteria =
                          AspirationCriteria())
        : m_tabu_list(std::move(tabuList)),
          m_aspiration_criteria_gain(std::move(gain),
                                     std::move(aspirationCriteria)) {}

    template <typename... Args>
    auto operator()(Args &&... args)
        ->decltype(std::declval<Gain>()(std::forward<Args>(args)...)) {
        if (!m_tabu_list.is_tabu(std::forward<Args>(args)...)) {
            auto diff = m_aspiration_criteria_gain(std::forward<Args>(args)...);
            if (detail::positive_delta(diff)) {
                m_tabu_list.accept(std::forward<Args>(args)...);
            }
            return diff;
        }
        return decltype(std::declval<Gain>()(std::forward<Args>(args)...)){};
    }

  private:
    TabuList m_tabu_list;
    conditional_gain_adaptor<Gain, AspirationCriteria>
        m_aspiration_criteria_gain;
};

template <typename TabuList, typename Gain = utils::always_true,
          typename AspirationCriteria = utils::always_true>
tabu_gain_adaptor<TabuList, Gain, AspirationCriteria>
make_tabu_gain_adaptor(TabuList tabuList, Gain gain = Gain(),
                       AspirationCriteria aspirationCriteria =
                           AspirationCriteria()) {
    return tabu_gain_adaptor<TabuList, Gain, AspirationCriteria>(
        std::move(tabuList), std::move(gain), std::move(aspirationCriteria));
}

template <typename Commit, typename Solution, typename Comparator = utils::less>
struct record_solution_commit_adapter {

    record_solution_commit_adapter(Solution &solution, Commit commit = Commit{},
                                   Comparator comparator = Comparator{})
        : m_solution(&solution), m_commit(std::move(commit)),
          m_comparator(std::move(comparator)) {}

    template <typename Move> bool operator()(Solution &sol, const Move &move) {
        auto ret = m_commit(sol, move);
        if (m_comparator(*m_solution, sol)) {
            *m_solution = sol;
        }
        return ret;
    }

    const Solution &get_solution() const { return *m_solution; }

    Solution &get_solution() { return *m_solution; }

  private:
    Solution *m_solution;
    Commit m_commit;
    Comparator m_comparator;
};

template <typename Commit, typename Solution, typename Condition>
record_solution_commit_adapter<Commit, Solution, Condition>
make_record_solution_commit_adapter(Solution &s, Commit commit, Condition c) {
    return record_solution_commit_adapter<Commit, Solution, Condition>(
        s, std::move(commit), std::move(c));
}

} // local_search
} // paal

#endif // PAAL_CUSTOM_COMPONENTS_HPP