All Classes Namespaces Files Functions Variables Typedefs Enumerations Friends Macros Pages
local_search_obj_function.hpp
Go to the documentation of this file.
1 //=======================================================================
2 // Copyright (c) 2013 Piotr Wygocki
3 //
4 // Distributed under the Boost Software License, Version 1.0. (See
5 // accompanying file LICENSE_1_0.txt or copy at
6 // http://www.boost.org/LICENSE_1_0.txt)
7 //=======================================================================
15 #ifndef PAAL_LOCAL_SEARCH_OBJ_FUNCTION_HPP
16 #define PAAL_LOCAL_SEARCH_OBJ_FUNCTION_HPP
17 
18 #include "local_search.hpp"
21 
23 
24 #include <boost/range/adaptor/transformed.hpp>
25 
26 namespace paal {
27 namespace local_search {
28 
34 template <typename SearchComponentsObjFun>
36  using get_moves_t = typename data_structures::component_traits<
37  SearchComponentsObjFun>::template type<GetMoves>::type;
38  using obj_function_t = typename data_structures::component_traits<
39  SearchComponentsObjFun>::template type<ObjFunction>::type;
40  using commit_t = typename data_structures::component_traits<
41  SearchComponentsObjFun>::template type<Commit>::type;
42 };
43 
44 namespace detail {
45 
46 template <typename F, typename GetMoves, typename Commit>
48  F m_f;
49  GetMoves const m_get_moves;
50  Commit const m_commit;
51 
52 public:
53 
54  obj_fun_get_moves(F f, GetMoves get_moves, Commit commit)
55  : m_f(std::move(f)),
56  m_get_moves(std::move(get_moves)),
57  m_commit(std::move(commit)) {}
58 
59  template <typename Solution>
60  auto operator()(Solution const &solution) {
61  using move = typename move_type_from_get_moves<GetMoves, Solution>::reference;
62  return m_get_moves(solution) | boost::adaptors::transformed(
63  [&solution, this](move m) {
64  Solution new_solution(solution);
65  m_commit(new_solution, m);
66  return std::make_pair(m, m_f(new_solution));
67  });
68  }
69 };
70 
71 template <typename Fitness>
72 class obj_fun_gain {
73  Fitness & m_current_res;
74 
75 public:
76 
77  obj_fun_gain(Fitness & current_res)
78  : m_current_res(current_res) {}
79 
80  template <typename Solution, typename Move>
81  auto operator()(Solution const &solution, Move const &move) {
82  return move.second - m_current_res;
83  }
84 };
85 
86 template <typename Commit, typename Fitness>
88  Commit const m_commit;
89  Fitness & m_current_res;
90 
91 public:
92 
93  obj_fun_commit(Commit commit, Fitness & current_res)
94  : m_commit(std::move(commit)), m_current_res(current_res) {}
95 
96  template <typename Solution, typename Move>
97  auto operator()(Solution &solution, Move const &move) {
98  if (!m_commit(solution, move.first)) {
99  return false;
100  }
101  m_current_res = move.second;
102  return true;
103  }
104 };
105 
106 template <typename Solution, typename SearchObjFunctionComponents,
108  typename F = typename Traits::obj_function_t,
109  typename Fitness = pure_result_of_t<F(Solution &)>>
110 auto convert_comps(Solution & sol, SearchObjFunctionComponents components, Fitness & current_res) {
111  using commit_t = typename Traits::commit_t;
112  using get_moves_t = typename Traits::get_moves_t;
113 
117 
118  auto get_moves = std::move(components.template get<GetMoves>());
119  auto commit = std::move(components.template get<Commit>());
120  auto obj_fun = std::move(components.template get<ObjFunction>());
121 
122  return make_search_components(
124  obj_fun_gain(current_res),
125  obj_fun_commit(commit, current_res));
126 }
127 
128 } // !detail
129 
130 
132 template <typename SearchStrategy, typename ContinueOnSuccess,
133  typename ContinueOnFail, typename Solution,
134  typename SearchObjFunctionComponent,
135  typename... SearchObjFunctionComponents>
136 bool local_search_obj_fun(Solution &solution, SearchStrategy searchStrategy,
137  ContinueOnSuccess on_success, ContinueOnFail on_fail,
138  SearchObjFunctionComponent component,
139  SearchObjFunctionComponents ... components) {
140  //TODO make it work for many different objective functions
141  auto cur_res = component.template call<ObjFunction>(solution);
142 
143  return local_search(solution, searchStrategy, std::move(on_success),
144  std::move(on_fail), detail::convert_comps(solution, std::move(component ), cur_res),
145  detail::convert_comps(solution, std::move(components), cur_res)...);
146 }
147 
149 template <typename Solution, typename... Components>
150 bool obj_fun_first_improving(Solution &solution, Components... comps) {
153  std::move(comps)...);
154 }
155 
157 template <typename Solution, typename... Components>
158 bool obj_fun_best_improving(Solution &solution, Components... comps) {
161  std::move(comps)...);
162 }
163 
164 } // local_search
165 } // paal
166 
167 #endif // PAAL_LOCAL_SEARCH_OBJ_FUNCTION_HPP
This strategy chooses the best possible move and if it is improving applies it to the solution...
functor return false
Definition: functors.hpp:222
auto make_search_components(Args &&...args)
make function for search components
bool local_search_obj_fun(Solution &solution, SearchStrategy searchStrategy, ContinueOnSuccess on_success, ContinueOnFail on_fail, SearchObjFunctionComponent component, SearchObjFunctionComponents...components)
local search function for objective function case.
bool obj_fun_first_improving(Solution &solution, Components...comps)
simple version of local_search_obj_fun - first improving strategy
class describing Move
bool local_search(Solution &solution, SearchStrategy searchStrategy, ContinueOnSuccess succ, ContinueOnFail fail, components...comps)
detail
bool obj_fun_best_improving(Solution &solution, Components...comps)
simple version of local_search_obj_fun - best improving strategy
typename std::decay< typename std::result_of< F >::type >::type pure_result_of_t
return pure type of function (decays const and reference)
This strategy uses find_positive_predicate as stop condition.
functor return true
Definition: functors.hpp:227