00001
00002
00003 #ifndef _sa_include_
00004 #define _sa_include_
00005
00006
00007
00008
00009
00010
00011 #include <cmath>
00012 #include <numeric>
00013 #include <vector>
00014
00015 #include "angel_exceptions.hpp"
00016 #include "angel_types.hpp"
00017 #include "angel_tools.hpp"
00018 #include "angel_io.hpp"
00019 #include "eliminations.hpp"
00020 #include "heuristics.hpp"
00021
00022 #ifdef USE_MPI
00023 #include "angel_comm.hpp"
00024 #endif // USE_MPI
00025
00026 namespace angel {
00027
00028
00029
00030
00031
00033 class LOG_temperature_t {
00034 double gamma;
00035 public:
00037 LOG_temperature_t (double p_gamma) : gamma (p_gamma) {}
00039 double operator() (int it) const {
00040 return gamma / log (double (it+2)); }
00041 };
00042
00044 class fixed_temperature_t {
00045 double t;
00046 public:
00048 fixed_temperature_t (double p_t) : t (p_t) {}
00050 double operator() (int it) const {
00051 return t; }
00052 };
00053
00059 template <class Temp_t>
00060 inline double SA_acceptance (int diff, int it, Temp_t temp) {
00061 return exp (diff / temp (it)); }
00062
00080 template <class Object_t, class Neighbor_t, class Cost_t, class Temp_t>
00081 int SA (Object_t& object, Neighbor_t neighbor, Cost_t costs, Temp_t temp, int max_iter);
00082
00097 template <class Object_t, class Neighbor_t, class Cost_t>
00098 inline int LSA (Object_t& object, Neighbor_t neighbor, Cost_t costs, double gamma, int max_iter) {
00099 LOG_temperature_t temp (gamma);
00100 return SA (object, neighbor, costs, temp, max_iter); }
00101
00116 template <class Object_t, class Neighbor_t, class Cost_t>
00117 inline int FTSA (Object_t& object, Neighbor_t neighbor, Cost_t costs, double t, int max_iter) {
00118 fixed_temperature_t temp (t);
00119 return SA (object, neighbor, costs, temp, max_iter); }
00120
00138 template <class Object_t, class Neighbor_t, class Cost_t, class Adaption_t>
00139 int ALSA (Object_t& object, Neighbor_t neighbor, Cost_t costs, Adaption_t adaption,
00140 double& gamma, int max_iter);
00141
00142
00143
00144
00145
00146
00147
00154 template <class Heuristic_t>
00155 class SA_elimination_cost_t {
00156 Heuristic_t h;
00157 public:
00159 SA_elimination_cost_t (Heuristic_t p_h) : h (p_h) {}
00160
00162 template <class Ad_graph_t, class El_spec_t>
00163 int operator() (const elimination_history_t<Ad_graph_t, El_spec_t>& eh) {
00164 std::vector<El_spec_t> el_seq;
00165 int rcosts= use_heuristic (eh.cg, el_seq, h);
00166 return eh.ccosts + rcosts; }
00167 };
00168
00169
00170
00171
00172
00173
00175 void neighbor_swap (const std::vector<int>& old_seq, std::vector<int>& seq);
00176
00181 struct neighbor_last_removable_t {
00182 template <class Ad_graph_t, class El_spec_t>
00183 bool operator() (elimination_history_t<Ad_graph_t, El_spec_t>& eh);
00184 };
00185
00191 class neighbor_multi_step_t {
00192 int max_steps;
00193 public:
00195 neighbor_multi_step_t (int m) : max_steps (m) {}
00196 template <class Ad_graph_t, class El_spec_t>
00197 bool operator() (elimination_history_t<Ad_graph_t, El_spec_t>& eh);
00198 };
00199
00209 struct neighbor_sequence_check_t {
00210 template <class Ad_graph_t, class El_spec_t>
00211 bool operator() (elimination_history_t<Ad_graph_t, El_spec_t>& eh);
00212 };
00213
00214
00215
00216
00217
00218
00219
00220
00221
00222
00223
00224
00225
00226
00238 struct neighbor_check_meta_t {
00239 template <class Ad_graph_t, class El_spec_t>
00240 bool operator() (elimination_history_t<Ad_graph_t, El_spec_t>& eh);
00241 };
00242
00243
00244
00245
00246
00257 class gamma_adaption_max_t {
00258 int D, diff, max_diff, last_min, last_max, imp;
00259 double scaling;
00260 public:
00265 gamma_adaption_max_t (int p_D, double p_scaling= 1.0) :
00266 D (p_D), diff (0), max_diff (0), last_min (0), imp (0), scaling (p_scaling) {
00267 THROW_DEBUG_EXCEPT_MACRO (D <= 0 && scaling <= 0.0, consistency_exception,
00268 "D and scaling must be greater 0"); }
00269
00275 void operator() (int costs, double& gamma);
00276 };
00277
00287 class gamma_adaption_average_t {
00288 int D, sum_diff, last_min, last_max, imp;
00289 double scaling;
00290 public:
00295 gamma_adaption_average_t (int p_D, double p_scaling= 1.0) :
00296 D (p_D), sum_diff (0), last_min (0), imp (0), scaling (p_scaling) {
00297 THROW_DEBUG_EXCEPT_MACRO (D <= 0 && scaling <= 0.0, consistency_exception,
00298 "D and scaling must be greater 0"); }
00299
00305 void operator() (int costs, double& gamma);
00306 };
00307
00308
00309
00310 #ifdef USE_MPI
00311
00313 template <class Temp_t>
00314 int pick_processor_sa (int my_costs, int it, Temp_t temp, const MPI::Intracomm& comm);
00315
00337 template <class Object_t, class Neighbor_t, class Cost_t, class Inner_temp_t, class Outer_temp_t,
00338 class Pre_comm_t, class Post_comm_t>
00339 int parallel_SA (Object_t& object, Neighbor_t neighbor, Cost_t costs,
00340 Inner_temp_t inner_temp, Outer_temp_t outer_temp, int inner_iter, int max_iter,
00341 const GMPI::Intracomm& comm, Pre_comm_t pre_comm, Post_comm_t post_comm);
00342
00344 template <class Object_t, class Neighbor_t, class Cost_t, class Inner_temp_t, class Outer_temp_t>
00345 inline int parallel_SA (Object_t& object, Neighbor_t neighbor, Cost_t costs,
00346 Inner_temp_t inner_temp, Outer_temp_t outer_temp, int inner_iter, int max_iter,
00347 const GMPI::Intracomm& comm) {
00348 empty_operator_t<Object_t> empty_pre_post_comm;
00349 return parallel_SA (object, neighbor, costs, inner_temp, outer_temp, inner_iter, max_iter, comm,
00350 empty_pre_post_comm, empty_pre_post_comm);
00351 }
00352
00353 #endif // USE_MPI
00354
00355 }
00356
00357 #include "sa_impl.hpp"
00358
00359 #endif // _sa_include_
00360