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
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038 #ifndef SELECT__H
00039 #define SELECT__H
00040
00041 #include <stdexcept>
00042
00043 #include "eoRNG.h"
00044 #include <eoPop.h>
00049 template <class EOT>
00050 bool minimizing_fitness()
00051 {
00052 EOT eo1;
00053 EOT eo2;
00054
00055
00056
00057
00058
00059
00060 #ifdef _MSC_VER
00061 eo1.fitness( EOT::Fitness(0.0) );
00062 eo2.fitness( EOT::Fitness(1.0) );
00063 #else
00064 eo1.fitness( typename EOT::Fitness(0.0) );
00065 eo2.fitness( typename EOT::Fitness(1.0) );
00066 #endif
00067
00068 return eo2 < eo1;
00069 }
00070
00071 inline double scale_fitness(const std::pair<double, double>& _minmax, double _value)
00072 {
00073 if (_minmax.first == _minmax.second)
00074 {
00075 return 0.0;
00076 }
00077
00078
00079 return (_value - _minmax.first) / (_minmax.second - _minmax.first);
00080 }
00081
00082 template <class It>
00083 double sum_fitness(It begin, It end)
00084 {
00085 double sum = 0.0;
00086
00087 for (; begin != end; ++begin)
00088 {
00089 double v = static_cast<double>(begin->fitness());
00090 if (v < 0.0)
00091 throw std::logic_error("sum_fitness: negative fitness value encountered");
00092 sum += v;
00093 }
00094
00095 return sum;
00096 }
00097
00098 template <class EOT>
00099 double sum_fitness(const eoPop<EOT>& _pop)
00100 {
00101 return sum_fitness(_pop.begin(), _pop.end());
00102 }
00103
00104 template <class EOT>
00105 double sum_fitness(const eoPop<EOT>& _pop, std::pair<double, double>& _minmax)
00106 {
00107 double rawTotal, scaledTotal;
00108
00109 typename eoPop<EOT>::const_iterator it = _pop.begin();
00110
00111 _minmax.first = it->fitness();
00112 _minmax.second = it++->fitness();
00113
00114 for(; it != _pop.end(); ++it)
00115 {
00116 double v = static_cast<double>(it->fitness());
00117
00118 _minmax.first = std::min(_minmax.first, v);
00119 _minmax.second = std::max(_minmax.second, v);
00120
00121 rawTotal += v;
00122 }
00123
00124 if (minimizing_fitness<EOT>())
00125 {
00126 std::swap(_minmax.first, _minmax.second);
00127 }
00128
00129 scaledTotal = 0.0;
00130
00131
00132 for (it = _pop.begin(); it != _pop.end(); ++it)
00133 {
00134 double v = scale_fitness(_minmax, static_cast<double>(it->fitness()));
00135
00136 scaledTotal += v;
00137 }
00138
00139 return scaledTotal;
00140 }
00141
00142 template <class It>
00143 It roulette_wheel(It _begin, It _end, double total, eoRng& _gen = rng)
00144 {
00145
00146 double roulette = _gen.uniform(total);
00147
00148 if (roulette == 0.0)
00149 return _begin + _gen.random(_end - _begin);
00150
00151 It i = _begin;
00152
00153 while (roulette > 0.0)
00154 {
00155 roulette -= static_cast<double>(*(i++));
00156 }
00157
00158 return --i;
00159 }
00160
00161 template <class EOT>
00162 const EOT& roulette_wheel(const eoPop<EOT>& _pop, double total, eoRng& _gen = rng)
00163 {
00164 double roulette = _gen.uniform(total);
00165
00166 if (roulette == 0.0)
00167 return _pop[_gen.random(_pop.size())];
00168
00169 typename eoPop<EOT>::const_iterator i = _pop.begin();
00170
00171 while (roulette > 0.0)
00172 {
00173 roulette -= static_cast<double>((i++)->fitness());
00174 }
00175
00176 return *--i;
00177 }
00178
00179 template <class EOT>
00180 EOT& roulette_wheel(eoPop<EOT>& _pop, double total, eoRng& _gen = rng)
00181 {
00182 float roulette = _gen.uniform(total);
00183
00184 if (roulette == 0.0)
00185 return _pop[_gen.random(_pop.size())];
00186
00187 typename eoPop<EOT>::iterator i = _pop.begin();
00188
00189 while (roulette > 0.0)
00190 {
00191 roulette -= static_cast<double>((i++)->fitness());
00192 }
00193
00194 return *--i;
00195 }
00196
00197 template <class It>
00198 It deterministic_tournament(It _begin, It _end, unsigned _t_size, eoRng& _gen = rng)
00199 {
00200 It best = _begin + _gen.random(_end - _begin);
00201
00202 for (unsigned i = 0; i < _t_size - 1; ++i)
00203 {
00204 It competitor = _begin + _gen.random(_end - _begin);
00205
00206 if (*best < *competitor)
00207 {
00208 best = competitor;
00209 }
00210 }
00211
00212 return best;
00213 }
00214
00215 template <class EOT>
00216 const EOT& deterministic_tournament(const eoPop<EOT>& _pop, unsigned _t_size, eoRng& _gen = rng)
00217 {
00218 return *deterministic_tournament(_pop.begin(), _pop.end(), _t_size, _gen);
00219 }
00220
00221 template <class EOT>
00222 EOT& deterministic_tournament(eoPop<EOT>& _pop, unsigned _t_size, eoRng& _gen = rng)
00223 {
00224 return *deterministic_tournament(_pop.begin(), _pop.end(), _t_size, _gen);
00225 }
00226
00227 template <class It>
00228 It inverse_deterministic_tournament(It _begin, It _end, unsigned _t_size, eoRng& _gen = rng)
00229 {
00230 It worst = _begin + _gen.random(_end - _begin);
00231
00232 for (unsigned i = 1; i < _t_size; ++i)
00233 {
00234 It competitor = _begin + _gen.random(_end - _begin);
00235
00236 if (competitor == worst)
00237 {
00238 --i;
00239 continue;
00240 }
00241
00242 if (*competitor < *worst)
00243 {
00244 worst = competitor;
00245 }
00246 }
00247
00248 return worst;
00249 }
00250
00251 template <class EOT>
00252 const EOT& inverse_deterministic_tournament(const eoPop<EOT>& _pop, unsigned _t_size, eoRng& _gen = rng)
00253 {
00254 return *inverse_deterministic_tournament<EOT>(_pop.begin(), _pop.end(), _t_size, _gen);
00255 }
00256
00257 template <class EOT>
00258 EOT& inverse_deterministic_tournament(eoPop<EOT>& _pop, unsigned _t_size, eoRng& _gen = rng)
00259 {
00260 return *inverse_deterministic_tournament(_pop.begin(), _pop.end(), _t_size, _gen);
00261 }
00262
00263 template <class It>
00264 It stochastic_tournament(It _begin, It _end, double _t_rate, eoRng& _gen = rng)
00265 {
00266 It i1 = _begin + _gen.random(_end - _begin);
00267 It i2 = _begin + _gen.random(_end - _begin);
00268
00269 bool return_better = _gen.flip(_t_rate);
00270
00271 if (*i1 < *i2)
00272 {
00273 if (return_better) return i2;
00274
00275
00276 return i1;
00277 }
00278 else
00279 {
00280 if (return_better) return i1;
00281
00282 }
00283
00284
00285 return i2;
00286 }
00287
00288 template <class EOT>
00289 const EOT& stochastic_tournament(const eoPop<EOT>& _pop, double _t_rate, eoRng& _gen = rng)
00290 {
00291 return *stochastic_tournament(_pop.begin(), _pop.end(), _t_rate, _gen);
00292 }
00293
00294 template <class EOT>
00295 EOT& stochastic_tournament(eoPop<EOT>& _pop, double _t_rate, eoRng& _gen = rng)
00296 {
00297 return *stochastic_tournament(_pop.begin(), _pop.end(), _t_rate, _gen);
00298 }
00299
00300 template <class It>
00301 It inverse_stochastic_tournament(It _begin, It _end, double _t_rate, eoRng& _gen = rng)
00302 {
00303 It i1 = _begin + _gen.random(_end - _begin);
00304 It i2 = _begin + _gen.random(_end - _begin);
00305
00306 bool return_worse = _gen.flip(_t_rate);
00307
00308 if (*i1 < *i2)
00309 {
00310 if (return_worse) return i1;
00311
00312
00313 return i2;
00314 }
00315 else
00316 {
00317 if (return_worse) return i2;
00318
00319 }
00320
00321
00322 return i1;
00323 }
00324
00325 template <class EOT>
00326 const EOT& inverse_stochastic_tournament(const eoPop<EOT>& _pop, double _t_rate, eoRng& _gen = rng)
00327 {
00328 return *inverse_stochastic_tournament(_pop.begin(), _pop.end(), _t_rate, _gen);
00329 }
00330
00331 template <class EOT>
00332 EOT& inverse_stochastic_tournament(eoPop<EOT>& _pop, double _t_rate, eoRng& _gen = rng)
00333 {
00334 return *inverse_stochastic_tournament(_pop.begin(), _pop.end(), _t_rate, _gen);
00335 }
00336
00337
00338 #endif