tabu-search.hh
Go to the documentation of this file.
00001 // METSlib source file - tabu-search.hh                          -*- C++ -*-
00002 /*
00003  * Software License Agreement (BSD License)
00004  *
00005  *  Copyright (c) 2006-2012, Mirko Maischberger <mirko.maischberger@gmail.com>
00006  *  All rights reserved.
00007  *
00008  *  Redistribution and use in source and binary forms, with or without
00009  *  modification, are permitted provided that the following conditions
00010  *  are met:
00011  *
00012  *   * Redistributions of source code must retain the above copyright
00013  *     notice, this list of conditions and the following disclaimer.
00014  *   * Redistributions in binary form must reproduce the above
00015  *     copyright notice, this list of conditions and the following
00016  *     disclaimer in the documentation and/or other materials provided
00017  *     with the distribution.
00018  *
00019  *  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
00020  *  "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
00021  *  LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
00022  *  FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
00023  *  COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
00024  *  INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
00025  *  BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
00026  *  LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
00027  *  CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
00028  *  LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
00029  *  ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
00030  *  POSSIBILITY OF SUCH DAMAGE.
00031  *
00032  */
00033 
00034 #ifndef METS_TABU_SEARCH_HH_
00035 #define METS_TABU_SEARCH_HH_
00036 
00037 namespace mets {
00038 
00041 
00052   class aspiration_criteria_chain
00053   {
00054   public:
00058     explicit
00059     aspiration_criteria_chain(aspiration_criteria_chain *next = 0)
00060       : next_m(next) 
00061     { }
00062     
00064     aspiration_criteria_chain(const aspiration_criteria_chain& other);
00066     aspiration_criteria_chain& 
00067     operator=(const aspiration_criteria_chain& other);
00068 
00070     virtual 
00071     ~aspiration_criteria_chain() 
00072     { } 
00073 
00076     virtual void 
00077     reset();
00078 
00089     virtual void 
00090     accept(feasible_solution& fs, move& mov, gol_type evaluation);
00091     
00097     virtual bool 
00098     operator()(feasible_solution& fs, move& mov, gol_type evaluation) const;
00099     
00100   protected:
00101     aspiration_criteria_chain* next_m;
00102   };
00103 
00109   class tabu_list_chain
00110   {
00111   public:
00112     tabu_list_chain();
00114     tabu_list_chain(const tabu_list_chain&);
00116     tabu_list_chain& operator=(const tabu_list_chain&);
00117 
00119     explicit
00120     tabu_list_chain(unsigned int tenure) 
00121       : next_m(0), tenure_m(tenure) 
00122     { }
00123 
00126     tabu_list_chain(tabu_list_chain* next, unsigned int tenure) 
00127       : next_m(next), tenure_m(tenure) 
00128     { }
00129 
00131     virtual 
00132     ~tabu_list_chain() 
00133     { } 
00134 
00147     virtual void 
00148     tabu(feasible_solution& sol, move& mov) = 0;
00149 
00163     virtual bool 
00164     is_tabu(feasible_solution& sol, move& mov) const = 0;
00165 
00172     virtual unsigned int
00173     tenure() const
00174     { return tenure_m; }
00175 
00181     virtual void
00182     tenure(unsigned int tenure) 
00183     { tenure_m = tenure; }
00184 
00185   protected:
00186     tabu_list_chain* next_m;
00187     unsigned int tenure_m;
00188   };
00189   
00197   template<typename move_manager_type>
00198   class tabu_search : public abstract_search<move_manager_type>
00199   {
00200   public:
00201     typedef tabu_search<move_manager_type> search_type;
00224     tabu_search(feasible_solution& starting_solution, 
00225                 solution_recorder& best_recorder, 
00226                 move_manager_type& move_manager_inst,
00227                 tabu_list_chain& tabus,
00228                 aspiration_criteria_chain& aspiration,
00229                 termination_criteria_chain& termination);
00230 
00231     tabu_search(const search_type&);
00232     search_type& operator=(const search_type&);
00233 
00234     virtual 
00235     ~tabu_search() {}
00236 
00243     void 
00244     search() 
00245       throw(no_moves_error);
00246     
00247     enum {
00248       ASPIRATION_CRITERIA_MET = abstract_search<move_manager_type>::LAST,
00249       LAST
00250     };
00251 
00253     const tabu_list_chain& 
00254     get_tabu_list() const { return tabu_list_m; }
00255     
00257     const aspiration_criteria_chain& 
00258     get_aspiration_criteria() const { return aspiration_criteria_m; }
00259 
00261     const termination_criteria_chain& 
00262     get_termination_criteria() const { return termination_criteria_m; }
00263   protected:
00264     tabu_list_chain& tabu_list_m;
00265     aspiration_criteria_chain& aspiration_criteria_m;
00266     termination_criteria_chain& termination_criteria_m;
00267   };
00268 
00282   class simple_tabu_list 
00283     : public tabu_list_chain
00284   {
00285   public:
00289     simple_tabu_list(unsigned int tenure) 
00290       : tabu_list_chain(tenure), 
00291         tabu_moves_m(), 
00292         tabu_hash_m(tenure) {}
00293 
00298     simple_tabu_list(tabu_list_chain* next, unsigned int tenure) 
00299       : tabu_list_chain(next, tenure), 
00300         tabu_moves_m(), 
00301         tabu_hash_m(tenure) {}
00302 
00304     ~simple_tabu_list();
00305 
00312     void
00313     tabu(feasible_solution& sol, /* const */ move& mov);
00314 
00324     bool
00325     is_tabu(feasible_solution& sol, move& mov) const;
00326 
00327   protected:
00328     typedef std::deque<move*> move_list_type;
00329 #if defined (METSLIB_TR1_BOOST)
00330     typedef boost::unordered_map<
00331           mana_move*, // Key type
00332           int, //insert a move and the number of times it's present in the list
00333           mana_move_hash,
00334           dereferenced_equal_to<mana_move*> > move_map_type;
00335 #elif defined (METSLIB_HAVE_UNORDERED_MAP) && !defined (METSLIB_TR1_MIXED_NAMESPACE)
00336     typedef std::unordered_map<
00337       mana_move*, // Key type
00338       int, //insert a move and the number of times it's present in the list
00339       mana_move_hash, 
00340       dereferenced_equal_to<mana_move*> > move_map_type;
00341 #else
00342     typedef std::tr1::unordered_map<
00343       mana_move*, // Key type
00344       int, //insert a move and the number of times it's present in the list
00345       mana_move_hash, 
00346       dereferenced_equal_to<mana_move*> > move_map_type;
00347 #endif    
00348     move_list_type tabu_moves_m;
00349     move_map_type tabu_hash_m;
00350   };
00351 
00359   class best_ever_criteria : public aspiration_criteria_chain
00360   {
00361   public:
00362     explicit
00363     best_ever_criteria(double min_improvement = 1e-6);
00364 
00365     explicit
00366     best_ever_criteria(aspiration_criteria_chain* next,
00367                        double min_improvement = 1e-6);
00368     
00369     void 
00370     reset();
00371 
00372     void
00373     accept(feasible_solution& fs, move& mov, gol_type evaluation);
00374 
00375     bool 
00376     operator()(feasible_solution& fs, move& mov, gol_type evaluation) const;
00377 
00378   protected:
00379     gol_type best_m;
00380     gol_type tolerance_m;
00381   };
00382   
00384 }
00385 
00386 template<typename move_manager_t>
00387 mets::tabu_search<move_manager_t>::
00388 tabu_search (feasible_solution& starting_solution, 
00389              solution_recorder& best_recorder, 
00390              move_manager_t& move_manager_inst,
00391              tabu_list_chain& tabus,
00392              aspiration_criteria_chain& aspiration,
00393              termination_criteria_chain& termination)
00394   : abstract_search<move_manager_t>(starting_solution, 
00395                                     best_recorder, 
00396                                     move_manager_inst),
00397     tabu_list_m(tabus),
00398     aspiration_criteria_m(aspiration),
00399     termination_criteria_m(termination)
00400 {}
00401 
00402 template<typename move_manager_t>
00403 void mets::tabu_search<move_manager_t>::search()
00404   throw(no_moves_error)
00405 {
00406   typedef abstract_search<move_manager_t> base_t;
00407   while(!termination_criteria_m(base_t::working_solution_m))
00408     {
00409       // call listeners
00410       base_t::step_m = base_t::ITERATION_BEGIN;
00411       this->notify();
00412 
00413       base_t::moves_m.refresh(base_t::working_solution_m);
00414       
00415       typename move_manager_t::iterator best_movit = base_t::moves_m.end(); 
00416       gol_type best_move_cost = std::numeric_limits<gol_type>::max();
00417       
00418       for(typename move_manager_t::iterator movit = base_t::moves_m.begin(); 
00419           movit != base_t::moves_m.end(); ++movit)
00420         {
00421           // evaluate proposed move
00422           gol_type cost = (*movit)->evaluate(base_t::working_solution_m);
00423           
00424           // save tabu status
00425           bool is_tabu = tabu_list_m.is_tabu(base_t::working_solution_m, 
00426                                                  **movit);
00427 
00428           // for each non-tabu move record the best one
00429           if(cost < best_move_cost)
00430             {
00431               
00432               bool aspiration_criteria_met = false;
00433               
00434               // not interesting if this is not a tabu move (and if we
00435               // are not improving over other moves)
00436               if(is_tabu) 
00437                 {
00438                   aspiration_criteria_met = 
00439                     aspiration_criteria_m(base_t::working_solution_m, 
00440                                           **movit,
00441                                           cost);
00442                 }
00443               
00444               if(!is_tabu || aspiration_criteria_met)
00445                 {
00446                   best_move_cost = cost;
00447                   best_movit = base_t::current_move_m = movit;
00448                   if(aspiration_criteria_met)
00449                     {
00450                       base_t::step_m = ASPIRATION_CRITERIA_MET;
00451                       this->notify();
00452                     }
00453                 }
00454             }
00455         } // end for each move
00456       
00457       if(best_movit == base_t::moves_m.end())
00458         throw no_moves_error();
00459 
00460       // make move tabu
00461       tabu_list_m.tabu(base_t::working_solution_m, **best_movit);
00462 
00463       // do the best non tabu move (unless overridden by aspiration
00464       // criteria, of course)
00465       (*best_movit)->apply(base_t::working_solution_m);
00466 
00467       // call listeners
00468       base_t::step_m = base_t::MOVE_MADE;
00469       this->notify();
00470       
00471       aspiration_criteria_m.accept(base_t::working_solution_m, 
00472                                    **best_movit, 
00473                                    best_move_cost);
00474       
00475       if(base_t::solution_recorder_m.accept(base_t::working_solution_m))
00476         {
00477           base_t::step_m = base_t::IMPROVEMENT_MADE;
00478           this->notify();
00479         }
00480 
00481       // call listeners
00482       base_t::step_m = base_t::ITERATION_END;
00483       this->notify();
00484       
00485     } // end while(!termination)
00486 }
00487 
00488 // chain of responsibility
00489 
00490 inline void
00491 mets::tabu_list_chain::tabu(feasible_solution& sol, /* const */ move& mov)
00492 {
00493   if(next_m)
00494     next_m->tabu(sol, mov);
00495 }
00496 
00497 inline bool
00498 mets::tabu_list_chain::is_tabu(feasible_solution& sol, /* const */ move& mov) const
00499 {
00500   if(next_m) 
00501     return next_m->is_tabu(sol, mov);
00502   else 
00503     return false;
00504 }
00505 
00506 inline mets::simple_tabu_list::~simple_tabu_list()
00507 { 
00508   for(move_map_type::iterator m = tabu_hash_m.begin(); 
00509       m!=tabu_hash_m.end(); ++m)
00510     delete m->first;
00511 }
00512 
00513 inline void
00514 mets::simple_tabu_list::tabu(feasible_solution& sol, /* const */ move& mov)
00515 {
00516   mana_move* mc = 
00517     dynamic_cast<mana_move&>(mov).opposite_of();
00518 
00519   // This does nothing if the move was already tabu (can happen when
00520   // aspiration criteria is met).
00521   std::pair<move_map_type::iterator, bool> 
00522     insert_result = tabu_hash_m.insert(std::make_pair(mc, 1));
00523 
00524   // If it was already in the map, increase the counter
00525   if(!insert_result.second) 
00526     {
00527       insert_result.first->second++;
00528       delete mc;
00529       mc = insert_result.first->first;
00530     }
00531   // Always add the move at the end of the list (when aspiration
00532   // criteria is met a move can be present more than one time in this
00533   // list: this is correct, so the last made move is always the last
00534   // in the queue). 
00535   tabu_moves_m.push_back(mc);
00536 
00537   // Since we use the hash size, the tenure is the number of different
00538   // moves on the list (the tabu_moves_m can have more than tenure
00539   // elements)
00540   while(tabu_hash_m.size() > this->tenure())
00541     {
00542       // update hash map *and* list structures
00543       move_map_type::iterator elem = tabu_hash_m.find
00544         (dynamic_cast<mana_move*>(tabu_moves_m.front()));
00545       elem->second--;
00546       if(elem->second == 0) 
00547         {
00548           mana_move* tmp = elem->first;
00549           tabu_hash_m.erase(elem);
00550           delete tmp;
00551         }
00552       tabu_moves_m.pop_front();
00553     }
00554   tabu_list_chain::tabu(sol, mov);
00555 }
00556 
00557 inline bool
00558 mets::simple_tabu_list::is_tabu(feasible_solution& sol, move& mov) const
00559 {
00560   // hash set. very fast but requires C++ ISO TR1 extension
00561   // and an hash function in every move (Omega(1)).
00562   bool tabu = (tabu_hash_m.find(&dynamic_cast<mana_move&>(mov)) 
00563                != tabu_hash_m.end());
00564 
00565   if(tabu)
00566     return true;
00567 
00568   return tabu_list_chain::is_tabu(sol, mov);
00569 }
00570 
00572 // aspiration_criteria_chain
00573 inline void 
00574 mets::aspiration_criteria_chain::reset()
00575 {
00576   if(next_m)
00577     return next_m->reset();
00578 }
00579 
00580 inline void 
00581 mets::aspiration_criteria_chain::accept(feasible_solution& fs, 
00582                                         move& mov,
00583                                         gol_type eval)
00584 {
00585   if(next_m) next_m->accept(fs, mov, eval);
00586 }
00587 
00588 inline bool 
00589 mets::aspiration_criteria_chain::operator()(feasible_solution& fs, 
00590                                             move& mov,
00591                                             gol_type eval) const
00592 {
00593   if(next_m)
00594     return next_m->operator()(fs, mov, eval);
00595   else
00596     return false;
00597 }
00598 
00600 // best_ever_criteria
00601 inline mets::best_ever_criteria::best_ever_criteria(double tolerance) 
00602   : aspiration_criteria_chain(),
00603     best_m(std::numeric_limits<gol_type>::max()),
00604     tolerance_m(tolerance)
00605 { }
00606 
00607 inline mets::best_ever_criteria::best_ever_criteria(aspiration_criteria_chain* next, double tolerance) 
00608   : aspiration_criteria_chain(next),
00609     best_m(std::numeric_limits<gol_type>::max()),
00610     tolerance_m(tolerance)
00611 { }
00612     
00613 inline void 
00614 mets::best_ever_criteria::reset()
00615 {
00616   best_m = std::numeric_limits<mets::gol_type>::max();
00617   aspiration_criteria_chain::reset();
00618 }
00619 
00620 inline void
00621 mets::best_ever_criteria::accept(feasible_solution& fs, 
00622                                  move& mov, 
00623                                  gol_type eval) 
00624 {
00625   best_m = std::min(dynamic_cast<const evaluable_solution&>(fs).cost_function(), best_m);
00626   aspiration_criteria_chain::accept(fs, mov, eval);
00627 }  
00628 
00629 inline bool 
00630 mets::best_ever_criteria::operator()(feasible_solution& fs, 
00631                                      move& mov, 
00632                                      gol_type eval) const
00633 { 
00635   if(eval < best_m - tolerance_m)
00636     return true;
00637   else
00638     return aspiration_criteria_chain::operator()(fs, mov, eval); 
00639 }
00640 
00641 #endif


pcl
Author(s): Open Perception
autogenerated on Wed Aug 26 2015 15:34:15