00001 /** 00002 * \file KMLocalSearchLloyd.h 00003 * \brief Lloyd's algorithm with random restarts 00004 * 00005 * Copyright 2007-2010 IMP Inventors. All rights reserved. 00006 * 00007 */ 00008 #ifndef IMPSTATISTICS_KM_LOCAL_SEARCH_LLOYD_H 00009 #define IMPSTATISTICS_KM_LOCAL_SEARCH_LLOYD_H 00010 00011 #include "KMLocalSearch.h" 00012 #include "statistics_config.h" 00013 #include "IMP/base_types.h" 00014 00015 IMPSTATISTICS_BEGIN_NAMESPACE 00016 #ifndef IMP_DOXYGEN 00017 00018 //! KMLocalSearchLloyd 00019 /** Lloyd's algorithm with random restarts. 00020 Each run is broken into trails, we keep to prefrom trails as long as we improve 00021 the global distortion. The first failed trail ( a trail in which we could not 00022 improve the total distortion) finalized the run as well. Each trail is broekn 00023 into few lloyd stages. 00024 A run starts by sampling center points at random. 00025 Each run is provided two parameters, a maximum number 00026 of runs per stage (maxRunStage) and a minimum accumulated 00027 relative distortion loss (minAccumRDL). If the accumulated RDL 00028 for the run exceeds this value, then the run ends in success. 00029 If the number of stages is exceeded before this happens, the run 00030 ends in failure. 00031 \unstable{KMLocalSearchLlouyd} 00032 */ 00033 class IMPSTATISTICSEXPORT KMLocalSearchLloyd : public KMLocalSearch { 00034 public: 00035 KMLocalSearchLloyd(KMFilterCenters *sol, KMTerminationCondition *term) 00036 : KMLocalSearch(sol,term) {} 00037 protected: 00038 //!Get the relative distortion loss for a trail 00039 double get_accumulated_rdl() { 00040 return (init_trail_dist_ - curr_->get_distortion()) / init_trail_dist_; 00041 } 00042 void log_stage(std::ostream &out=std::cout); 00043 void log_run() { 00044 IMP_LOG(VERBOSE,"<Generating new random centers>" << std::endl); 00045 } 00046 //! Do base class resetting. Initialize is_new_phase to false and save 00047 //! the initial run distortion. 00048 virtual void reset(); 00049 //! Do base class processing. If there has been an improvement in distortion, 00050 //! save the current solution. 00051 void end_stage(); 00052 //! Checks if the run is done 00053 /** If the number of stages exceeds the maximum stages (total or per run), 00054 then we are done. If this is the first stage of the run, then we are not 00055 done, and we do beginning of run processing. Otherwise, if the relative 00056 distortion loss (RDL) is greater than minimum val then we are done (success). 00057 */ 00058 virtual bool is_run_done(); 00059 //! End the run 00060 /** If the accumulated RDL is smaller that the minimum predefined accumulated 00061 RDL then the run has ended unsuccessfully and we request the start of a new 00062 run. Otherwise the run has ended successfully, and we start a new run by 00063 saving the current run distortion. 00064 */ 00065 void end_run(); 00066 void preform_stage(); 00067 double init_trail_dist_; // initial distortion for a trail 00068 bool is_new_trail_; 00069 }; 00070 00071 #endif 00072 00073 IMPSTATISTICS_END_NAMESPACE 00074 #endif /* IMPSTATISTICS_KM_LOCAL_SEARCH_LLOYD_H */
