local_search_lambda_sa_tabu_example.cpp
Go to the documentation of this file.
1 //=======================================================================
3 //
5 // accompanying file LICENSE_1_0.txt or copy at
7 //=======================================================================
21
22 #include <vector>
23 #include <iostream>
24
25 int main() {
26  namespace ls = paal::local_search;
27  using Solution = int;
28  using Move = int;
29
30  auto f = [](int x) { return -x * x + 12 * x - 27; };
31  // creating solution
32  int solution(0);
33
34  // neighborhood
35  std::vector<int> neighb{ 10, -10, 1, -1 };
36
37  auto getMoves = [ = ](int) {
38  return boost::make_iterator_range(neighb.begin(), neighb.end());
39  };
40
41  auto gain = [ = ](int sol, int move) { return f(sol + move) - f(sol); };
42
43  auto commit = [](int & sol, int move) {
44  sol = sol + move;
45  return true;
46  };
47
48  // search
49  ls::first_improving(solution,
51
52  // print
53  std::cout << "Local search solution: " << solution << std::endl;
54
55  // simulated annealing:
56  // now each move is accepted with certain probability depending on
57  // the move quality and iteration id.
58  solution = 0;
60  1000, 0.999); // this is just a functor returning double
62  gain, cooling); // we create new gain by adopting the old one
64  solution, ls::make_search_components(getMoves, gainSA,
65  commit)); // we run local search
66
67  // print
68  std::cout << "Simulated annealing solution: " << solution << std::endl;
69
70  int currentSolution(0);
71  int best(0);
72
73  // getMovesRandom returns random move
74  std::default_random_engine engine;
75  std::uniform_int_distribution<> dist(0, 4);
76  auto getMovesRandom = [ = ](int)mutable {
77  auto iter = neighb.begin() + dist(engine);
78  return boost::make_iterator_range(iter, iter + 1);
79  };
80
81  ls::stop_condition_count_limit stop_condition(1000);
83
84  // this commit remembers the best solution
85  // in many cases it should be also used in simulated annealing
87  best, // the reference to the best found solution which is going to be
88  // updated during the search
89  commit,
91  f)); // recordSolutionCommit must know how to compare solutions
92
93  // random walk
95  paal::utils::make_not_functor(stop_condition), on_fail,
97  getMovesRandom, paal::utils::return_one_functor(),
98  recordSolutionCommit));
99
100  // print
101  std::cout << "Random walk solution: " << best << std::endl;
102
103  // tabu search
104  // one of the implementations of tabu list, remembers las 20 (solution,
105  // move) pairs.
106
107  currentSolution = 0;
108  best = 0;
111  Move, Solution>(20),
112  gain);
113
115  currentSolution, ls::best_improving_strategy{},
116  paal::utils::make_not_functor(stop_condition), on_fail,
117  ls::make_search_components(getMoves, gainTabu, recordSolutionCommit));
118
119  // print
120  std::cout << "Tabu solution: " << best << std::endl;
121
122  return 0;
123 }
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 first_improving(Solution &solution, components...comps)
bool best(Solution &solution, ContinueOnSuccess on_success, components...comps)
This local search chooses the best possible move and applies it to the solution. Note that this strat...
This functors returns potential (temperature) using the following schema. The start potential equals ...
This is custom StopCondition , it returns true after given count limit.
auto make_functor_to_comparator(Functor functor, Compare compare=Compare())
make for functor to comparator
Definition: functors.hpp:654
int main()
[Local Search Example]
auto make_not_functor(Functor functor)
make for Not
Definition: functors.hpp:922
This Tabu list remember both current solution and move It is implemented as tabu_list_remember_move&lt;p...
Definition: tabu_list.hpp:96
auto make_simulated_annealing_gain_adaptor(Gain gain, GetTemperature getTemperature, random_generator rand=random_generator())