angel
mercurial changeset:
|
00001 // $Id: sa.hpp,v 1.13 2005/04/12 04:22:57 jean_utke Exp $ 00002 /* 00003 ############################################################# 00004 # This file is part of angel released under the BSD license # 00005 # The full COPYRIGHT notice can be found in the top # 00006 # level directory of the angel distribution # 00007 ############################################################# 00008 */ 00009 00010 00011 #ifndef _sa_include_ 00012 #define _sa_include_ 00013 00014 00015 // 00016 // functions and operators for simulated annealing 00017 // 00018 00019 #include <cmath> 00020 #include <numeric> 00021 #include <vector> 00022 00023 #include "angel_exceptions.hpp" 00024 #include "angel_types.hpp" 00025 #include "angel_tools.hpp" 00026 #include "angel_io.hpp" 00027 #include "eliminations.hpp" 00028 #include "heuristics.hpp" 00029 00030 #ifdef USE_MPI 00031 #include "angel_comm.hpp" 00032 #endif // USE_MPI 00033 00034 namespace angel { 00035 00036 // ===================================================== 00037 // Generic SA algorithms 00038 // ===================================================== 00039 00041 class LOG_temperature_t { 00042 double gamma; 00043 public: 00045 LOG_temperature_t (double p_gamma) : gamma (p_gamma) {} 00047 double operator() (int it) const { 00048 return gamma / log (double (it+2)); } 00049 }; 00050 00052 class fixed_temperature_t { 00053 double t; 00054 public: 00056 fixed_temperature_t (double p_t) : t (p_t) {} 00058 double operator() (int it) const { 00059 return t; } 00060 }; 00061 00067 template <class Temp_t> 00068 inline double SA_acceptance (int diff, int it, Temp_t temp) { 00069 return exp (diff / temp (it)); } 00070 00088 template <class Object_t, class Neighbor_t, class Cost_t, class Temp_t> 00089 int SA (Object_t& object, Neighbor_t neighbor, Cost_t costs, Temp_t temp, int max_iter); 00090 00105 template <class Object_t, class Neighbor_t, class Cost_t> 00106 inline int LSA (Object_t& object, Neighbor_t neighbor, Cost_t costs, double gamma, int max_iter) { 00107 LOG_temperature_t temp (gamma); 00108 return SA (object, neighbor, costs, temp, max_iter); } 00109 00124 template <class Object_t, class Neighbor_t, class Cost_t> 00125 inline int FTSA (Object_t& object, Neighbor_t neighbor, Cost_t costs, double t, int max_iter) { 00126 fixed_temperature_t temp (t); 00127 return SA (object, neighbor, costs, temp, max_iter); } 00128 00146 template <class Object_t, class Neighbor_t, class Cost_t, class Adaption_t> 00147 int ALSA (Object_t& object, Neighbor_t neighbor, Cost_t costs, Adaption_t adaption, 00148 double& gamma, int max_iter); 00149 00150 // ===================================================== 00151 // cost operators 00152 // ===================================================== 00153 00154 00155 00162 template <class Heuristic_t> 00163 class SA_elimination_cost_t { 00164 Heuristic_t h; 00165 public: 00167 SA_elimination_cost_t (Heuristic_t p_h) : h (p_h) {} 00168 00170 template <class Ad_graph_t, class El_spec_t> 00171 int operator() (const elimination_history_t<Ad_graph_t, El_spec_t>& eh) { 00172 std::vector<El_spec_t> el_seq; 00173 int rcosts= use_heuristic (eh.cg, el_seq, h); 00174 return eh.ccosts + rcosts; } // costs: (og -> cg) + (cg -> J) 00175 }; 00176 00177 00178 // ===================================================== 00179 // neighbourhoods 00180 // ===================================================== 00181 00183 void neighbor_swap (const std::vector<int>& old_seq, std::vector<int>& seq); 00184 00189 struct neighbor_last_removable_t { 00190 template <class Ad_graph_t, class El_spec_t> 00191 bool operator() (elimination_history_t<Ad_graph_t, El_spec_t>& eh); 00192 }; 00193 00199 class neighbor_multi_step_t { 00200 int max_steps; 00201 public: 00203 neighbor_multi_step_t (int m) : max_steps (m) {} 00204 template <class Ad_graph_t, class El_spec_t> 00205 bool operator() (elimination_history_t<Ad_graph_t, El_spec_t>& eh); 00206 }; 00207 00217 struct neighbor_sequence_check_t { 00218 template <class Ad_graph_t, class El_spec_t> 00219 bool operator() (elimination_history_t<Ad_graph_t, El_spec_t>& eh); 00220 }; 00221 00222 00223 00224 // ------------------------------------------------------------------------- 00225 00226 // 00227 // SA neighborhood either eliminate face from feh.lg 00228 // or undo some previous elimination f_k from feh.seq = (f_1, .., f_n) 00229 // such that feh.olg --(f_1, ..., f_(k-1), f_(k+1), ..., f_n, f_k)--> feh.lg 00230 // new graph feh.lg', i.e. feh.olg --(f_1, ..., f_(k-1), f_(k+1), ..., f_n)-->feh.lg' 00231 // is a predecessor of feh.lg in the meta-graph, see tec report for details 00232 // returns if it was successful 00233 // 00234 00246 struct neighbor_check_meta_t { 00247 template <class Ad_graph_t, class El_spec_t> 00248 bool operator() (elimination_history_t<Ad_graph_t, El_spec_t>& eh); 00249 }; 00250 00251 // ===================================================== 00252 // Gamma adaption operators 00253 // ===================================================== 00254 00265 class gamma_adaption_max_t { 00266 int D, diff, max_diff, last_min, last_max, imp; 00267 double scaling; 00268 public: 00273 gamma_adaption_max_t (int p_D, double p_scaling= 1.0) : 00274 D (p_D), diff (0), max_diff (0), last_min (0), imp (0), scaling (p_scaling) { 00275 THROW_DEBUG_EXCEPT_MACRO (D <= 0 && scaling <= 0.0, consistency_exception, 00276 "D and scaling must be greater 0"); } 00277 00283 void operator() (int costs, double& gamma) { 00284 if (imp >= D) return; 00285 if (last_min == 0) { // very first iteration must be distinguished 00286 last_max= last_min= costs; return; } 00287 if (costs < last_min) { 00288 diff= last_max - costs; last_max= last_min= costs; 00289 if (diff > max_diff) max_diff= diff; 00290 if (++imp >= D) gamma= scaling * double (max_diff); 00291 } else if (costs > last_max) last_max= costs; 00292 } 00293 }; 00294 00304 class gamma_adaption_average_t { 00305 int D, sum_diff, last_min, last_max, imp; 00306 double scaling; 00307 public: 00312 gamma_adaption_average_t (int p_D, double p_scaling= 1.0) : 00313 D (p_D), sum_diff (0), last_min (0), imp (0), scaling (p_scaling) { 00314 THROW_DEBUG_EXCEPT_MACRO (D <= 0 && scaling <= 0.0, consistency_exception, 00315 "D and scaling must be greater 0"); } 00316 00322 void operator() (int costs, double& gamma) { 00323 if (imp >= D) return; 00324 if (last_min == 0) { // very first iteration must be distinguished 00325 last_max= last_min= costs; return; } 00326 if (costs < last_min) { 00327 sum_diff+= last_max - costs; last_max= last_min= costs; 00328 if (++imp >= D) {gamma= scaling * double (sum_diff) / double (imp); } 00329 } else if (costs > last_max) last_max= costs; 00330 } 00331 }; 00332 00333 00334 00335 #ifdef USE_MPI 00336 00338 template <class Temp_t> 00339 int pick_processor_sa (int my_costs, int it, Temp_t temp, const MPI::Intracomm& comm); 00340 00362 template <class Object_t, class Neighbor_t, class Cost_t, class Inner_temp_t, class Outer_temp_t, 00363 class Pre_comm_t, class Post_comm_t> 00364 int parallel_SA (Object_t& object, Neighbor_t neighbor, Cost_t costs, 00365 Inner_temp_t inner_temp, Outer_temp_t outer_temp, int inner_iter, int max_iter, 00366 const GMPI::Intracomm& comm, Pre_comm_t pre_comm, Post_comm_t post_comm); 00367 00369 template <class Object_t, class Neighbor_t, class Cost_t, class Inner_temp_t, class Outer_temp_t> 00370 inline int parallel_SA (Object_t& object, Neighbor_t neighbor, Cost_t costs, 00371 Inner_temp_t inner_temp, Outer_temp_t outer_temp, int inner_iter, int max_iter, 00372 const GMPI::Intracomm& comm) { 00373 empty_operator_t<Object_t> empty_pre_post_comm; 00374 return parallel_SA (object, neighbor, costs, inner_temp, outer_temp, inner_iter, max_iter, comm, 00375 empty_pre_post_comm, empty_pre_post_comm); 00376 } 00377 00378 #endif // USE_MPI 00379 00380 } // namespace angel 00381 00382 #include "sa_impl.hpp" 00383 00384 #endif // _sa_include_ 00385