sa.hpp

Go to the documentation of this file.
00001 // $Id: sa.hpp,v 1.13 2005/04/12 04:22:57 jean_utke Exp $
00002 
00003 #ifndef         _sa_include_
00004 #define         _sa_include_
00005 
00006 
00007 //
00008 //  functions and operators for simulated annealing
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 // Generic SA algorithms
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 // cost operators
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; }  // costs: (og -> cg) + (cg -> J)
00167 };
00168 
00169 
00170 // =====================================================
00171 // neighbourhoods
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 // SA neighborhood either eliminate face from feh.lg 
00220 //   or undo some previous elimination f_k from feh.seq = (f_1, .., f_n)
00221 //   such that feh.olg --(f_1, ..., f_(k-1), f_(k+1), ..., f_n, f_k)--> feh.lg
00222 // new graph feh.lg', i.e. feh.olg --(f_1, ..., f_(k-1), f_(k+1), ..., f_n)-->feh.lg'
00223 //   is a predecessor of feh.lg in the meta-graph, see tec report for details
00224 // returns if it was successful
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 // Gamma adaption operators
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 } // namespace angel
00356 
00357 #include "sa_impl.hpp"
00358 
00359 #endif  // _sa_include_
00360 

Generated on Wed Mar 11 10:33:11 2009 for angel by  doxygen 1.5.3