Main Page | Modules | Namespace List | Class Hierarchy | Alphabetical List | Class List | File List | Namespace Members | Class Members | Related Pages | Search for

# selectors.h

    00001 /* -*- mode: c++; c-indent-level: 4; c++-member-init-indent: 8; comment-column: 35; -*-
    00002
    00003   -----------------------------------------------------------------------------
    00004   selectors.h
    00005     A bunch of useful selector functions. They generally have three forms:
    00006
    00007     template <class It>
    00008     It select(It begin, It end, params, eoRng& gen = rng);
    00009
    00010     template <class EOT>
    00011     const EOT& select(const eoPop<EOT>& pop, params, eoRng& gen = rng);
    00012
    00013     template <class EOT>
    00014     EOT& select(eoPop<EOT>& pop, params, eoRng& gen = rng);
    00015
    00016     where select is one of: roulette_wheel, deterministic_tournament
    00017     and stochastic_tournament (at the moment).
    00018
    00019  (c) Maarten Keijzer (mak@dhi.dk) and GeNeura Team, 1999, 2000
    00020
    00021     This library is free software; you can redistribute it and/or
    00022     modify it under the terms of the GNU Lesser General Public
    00023     License as published by the Free Software Foundation; either
    00024     version 2 of the License, or (at your option) any later version.
    00025
    00026     This library is distributed in the hope that it will be useful,
    00027     but WITHOUT ANY WARRANTY; without even the implied warranty of
    00028     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
    00029     Lesser General Public License for more details.
    00030
    00031     You should have received a copy of the GNU Lesser General Public
    00032     License along with this library; if not, write to the Free Software
    00033     Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
    00034
    00035     Contact: todos@geneura.ugr.es, http://geneura.ugr.es
    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; // Assuming people don't do anything fancy in the default constructor!
    00053     EOT eo2;
    00054
    00055     /* Dear user, when the two line below do not compile you are most
    00056        likely not working with scalar fitness values. In that case we're sorry
    00057        but you cannot use lottery or roulette_wheel selection...
    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) ); // tried to cast it to an EOT::Fitness, but for some reason GNU barfs on this
    00065     eo2.fitness( typename EOT::Fitness(1.0) );
    00066 #endif
    00067
    00068     return eo2 < eo1; // check whether we have a minimizing fitness
    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; // no differences in fitness, population converged!
    00076     }
    00077     // else
    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     // unfortunately a second loop is neccessary to scale the fitness
    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     float roulette = _gen.uniform(total);
    00147
    00148     if (roulette == 0.0)           // covers the case where total==0.0
    00149       return _begin + _gen.random(_end - _begin); // uniform choice
    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     float roulette = _gen.uniform(total);
    00165
    00166     if (roulette == 0.0)           // covers the case where total==0.0
    00167       return _pop[_gen.random(_pop.size())]; // uniform choice
    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)           // covers the case where total==0.0
    00185       return _pop[_gen.random(_pop.size())]; // uniform choice
    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; // try again
    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       // else
    00275
    00276       return i1;
    00277    }
    00278     else
    00279     {
    00280       if (return_better) return i1;
    00281       // else
    00282     }
    00283     // else
    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       // else
    00312
    00313       return i2;
    00314    }
    00315     else
    00316     {
    00317       if (return_worse) return i2;
    00318       // else
    00319     }
    00320     // else
    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