1 // METS lib source file - local-search.hh -*- C++ -*-
2 //
3 /*
4 * Software License Agreement (BSD License)
5 *
6 * Copyright (c) 2006-2012, Mirko Maischberger <mirko.maischberger@gmail.com>
7 * All rights reserved.
8 *
9 * Redistribution and use in source and binary forms, with or without
10 * modification, are permitted provided that the following conditions
11 * are met:
12 *
13 * * Redistributions of source code must retain the above copyright
14 * notice, this list of conditions and the following disclaimer.
15 * * Redistributions in binary form must reproduce the above
16 * copyright notice, this list of conditions and the following
17 * disclaimer in the documentation and/or other materials provided
18 * with the distribution.
19 *
20 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
21 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
22 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
23 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
24 * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
25 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
26 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
27 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
28 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
29 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
30 * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
31 * POSSIBILITY OF SUCH DAMAGE.
32 *
33 */
34
35 #ifndef LOCAL_SEARCH_HH_
36 #define LOCAL_SEARCH_HH_
37
38 namespace mets {
39 /// @defgroup local_search Local Search
40 /// @{
41
42 /// @brief Local search algorithm.
43 ///
44 /// With customary phase alternation
45 /// and move managers generated neighborhood this can be used to do
46 /// also a Random Restart Local Search, a Greedy Search,
47 /// an Iterated Local Search and a Variable Neighborhood Search.
48 template<typename move_manager_type>
49 class local_search : public mets::abstract_search<move_manager_type>
50 {
51 public:
52 /// @brief Creates a local search instance
53 ///
54 /// @param working The working solution (this will be modified
55 /// during search)
56 ///
57 /// @param best_so_far A different solution
58 /// instance used to store the best solution found
59 ///
60 /// @param moveman A problem specific implementation of the
61 /// move_manager_type concept used to generate the neighborhood.
62 ///
63 /// @param short_circuit Wether the search should stop on
64 /// the first improving move or not.
65 local_search(evaluable_solution& starting_point,
66 solution_recorder& recorder,
67 move_manager_type& moveman,
68 gol_type epsilon = 1e-7,
69 bool short_circuit = false);
70
71 /// purposely not implemented (see Effective C++)
72 local_search(const local_search&);
73 local_search& operator=(const local_search&);
74
75 /// @brief This method starts the local search process.
76 ///
77 /// To have a real local search you should provide an
78 /// move_manager_type than enumerates all feasible
79 /// moves.
80 ///
81 virtual void
82 search();
83
84 protected:
85 bool short_circuit_m;
86 gol_type epsilon_m;
87 };
88
89 /// @}
90
91 }
92
93 template<typename move_manager_t>
local_search(evaluable_solution & working,solution_recorder & recorder,move_manager_t & moveman,gol_type epsilon,bool short_circuit)94 mets::local_search<move_manager_t>::local_search(evaluable_solution& working,
95 solution_recorder& recorder,
96 move_manager_t& moveman,
97 gol_type epsilon,
98 bool short_circuit)
99 : abstract_search<move_manager_t>(working, recorder, moveman),
100 short_circuit_m(short_circuit), epsilon_m(epsilon)
101 {
102 using base_t = abstract_search<move_manager_t>;
103 base_t::step_m = 0;
104 }
105
106 template<typename move_manager_t>
107 void
search()108 mets::local_search<move_manager_t>::search()
109 {
110 using base_t = abstract_search<move_manager_t>;
111 typename move_manager_t::iterator best_movit;
112
113 base_t::solution_recorder_m.accept(base_t::working_solution_m);
114
115 gol_type best_cost =
116 static_cast<mets::evaluable_solution&>(base_t::working_solution_m)
117 .cost_function();
118
119 do
120 {
121 base_t::moves_m.refresh(base_t::working_solution_m);
122 best_movit = base_t::moves_m.end();
123 for(typename move_manager_t::iterator movit = base_t::moves_m.begin();
124 movit != base_t::moves_m.end(); ++movit)
125 {
126 // evaluate the cost after the move
127 gol_type cost = (*movit)->evaluate(base_t::working_solution_m);
128 if(cost < best_cost - epsilon_m)
129 {
130 best_cost = cost;
131 best_movit = movit;
132 if(short_circuit_m) break;
133 }
134 } // end for each move
135
136 if(best_movit != base_t::moves_m.end())
137 {
138 (*best_movit)->apply(base_t::working_solution_m);
139 base_t::solution_recorder_m.accept(base_t::working_solution_m);
140 base_t::current_move_m = best_movit;
141 this->notify();
142 }
143
144 } while(best_movit != base_t::moves_m.end());
145 }
146 #endif
147