00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027 #ifndef eoStochasticUniversalSelect_h
00028 #define eoStochasticUniversalSelect_h
00029
00030
00031
00032 #include <utils/eoRNG.h>
00033 #include <eoSelectOne.h>
00034 #include <utils/selectors.h>
00035 #include <eoPop.h>
00036
00037
00042
00043
00044 template <class EOT> class eoStochasticUniversalSelect: public eoSelectOne<EOT>
00045 {
00046 public:
00048 eoStochasticUniversalSelect(const eoPop<EOT>& pop = eoPop<EOT>())
00049 {
00050 if (minimizing_fitness<EOT>())
00051 throw std::logic_error("eoStochasticUniversalSelect: minimizing fitness");
00052 }
00053
00054 void setup(const eoPop<EOT>& _pop)
00055 {
00056 if (_pop.size() == 0) return;
00057
00058 std::vector<typename EOT::Fitness> cumulative(_pop.size());
00059
00060 cumulative[0] = _pop[0].fitness();
00061 for (unsigned i = 1; i < _pop.size(); ++i)
00062 {
00063 cumulative[i] = _pop[i].fitness() + cumulative[i-1];
00064 }
00065
00066 indices.reserve(_pop.size());
00067 indices.resize(0);
00068
00069 double fortune = rng.uniform() * cumulative.back();
00070 double step = cumulative.back() / double(_pop.size());
00071
00072 unsigned i = std::upper_bound(cumulative.begin(), cumulative.end(), fortune) - cumulative.begin();
00073
00074 while (indices.size() < _pop.size()) {
00075
00076 while (cumulative[i] < fortune) {i++;}
00077
00078 indices.push_back(i);
00079 fortune += step;
00080 if (fortune >= cumulative.back()) {
00081 fortune -= cumulative.back();
00082 i = 0;
00083 }
00084 }
00085
00086 for (int i = indices.size() - 1; i > 0; --i) {
00087 int j = rng.random(i+1);
00088 std::swap(indices[i], indices[j]);
00089 }
00090 }
00091
00094 const EOT& operator()(const eoPop<EOT>& _pop)
00095 {
00096 if (indices.empty()) setup(_pop);
00097
00098 unsigned index = indices.back();
00099 indices.pop_back();
00100 return _pop[index];
00101 }
00102
00103 private :
00104
00105 typedef std::vector<unsigned> IndexVec;
00106 IndexVec indices;
00107 };
00108
00109 #endif