angel  mercurial changeset:
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 #############################################################
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 
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines