00001 #include <map>
00002 #include <iostream>
00003 #include <stdexcept>
00004 #include <vector>
00005 #include <algorithm>
00006 #include <math.h>
00007
00008 using namespace std;
00009
00010
00011
00012
00013 template <class T = double>
00014 struct fitness_traits
00015 {
00016
00017 const static bool needs_mapping = false;
00018
00019
00020 typedef T storage_type;
00021
00022
00023 typedef T performance_type;
00024
00025
00026 typedef T worth_type;
00027
00028
00029 static performance_type& access_performance(storage_type& a) { return a; }
00030
00031
00032 static worth_type& access_worth(storage_type& a) { return a; }
00033
00034
00035 static performance_type get_performance(storage_type a) { return a; }
00036
00037
00038 static worth_type get_worth(storage_type a) { return a; }
00039
00040
00041 template <class EOT>
00042 static worth_type get_fitness(const EOT& _eo) { return _eo.performance(); }
00043
00044
00045 template <class EOT>
00046 static bool is_better(const EOT& _eo1, const EOT& _eo2)
00047 {
00048 return _eo1.performance() > _eo2.performance();
00049 }
00050 };
00051
00052 struct minimization {};
00053 struct maximization {};
00054
00055 struct fitness_traits<minimization> : public fitness_traits<double>
00056 {
00057
00058 template <class EOT>
00059 static bool is_better(const EOT& _eo1, const EOT& _eo2)
00060 {
00061 return _eo1.performance() < _eo2.performance();
00062 }
00063 };
00064
00065
00066 struct fitness_traits<maximization> : public fitness_traits<double> {};
00067
00068
00069
00070
00071
00072
00073
00074
00075 template <class Performance, class Worth>
00076 struct fitness_traits< pair<Performance, Worth> >
00077 {
00078 typedef pair<Performance, Worth> storage_type;
00079 typedef Performance performance_type;
00080 typedef Worth worth_type;
00081
00082 const static bool needs_mapping = true;
00083
00084 static performance_type& access_performance(storage_type& a) { return a.first; }
00085 static worth_type& access_worth(storage_type& a) { return a.second; }
00086
00087 static performance_type get_performance(const storage_type& a) { return a.first; }
00088 static worth_type get_worth(const storage_type& a) { return a.second; }
00089
00090
00091
00092 template <class EOT>
00093 static worth_type get_fitness(const EOT& _eo) { return _eo.worth(); }
00094
00095 template <class EOT>
00096 static bool is_better(const EOT& _eo1, const EOT& _eo2)
00097 {
00098 return _eo1.worth() > _eo2.worth();
00099 }
00100 };
00101
00102
00103
00104
00105
00106
00107
00108
00109
00110 template <class Fitness, class Traits = fitness_traits<Fitness> >
00111 class EO
00112 {
00113 public :
00114
00115 typedef Traits fitness_traits;
00116 typedef typename Traits::storage_type storage_type;
00117 typedef typename Traits::performance_type performance_type;
00118 typedef typename Traits::worth_type worth_type;
00119
00120 EO() : valid_performance(false), valid_worth(false), rep_fitness() {}
00121
00122
00123 void fitness(performance_type perf)
00124 {
00125 performance(perf);
00126 }
00127
00128 void performance(performance_type perf)
00129 {
00130 valid_performance = true;
00131 Traits::access_performance(rep_fitness) = perf;
00132 }
00133
00134 performance_type performance(void) const
00135 {
00136 if(!valid_performance) throw runtime_error("no performance");
00137 return Traits::get_performance(rep_fitness);
00138 }
00139
00140 void worth(worth_type worth)
00141 {
00142 valid_worth = true;
00143 Traits::access_worth(rep_fitness) = worth;
00144 }
00145
00146 worth_type worth(void) const
00147 {
00148 if(!valid_worth) throw runtime_error("no worth");
00149 if(!Traits::needs_mapping) throw runtime_error("no mapping");
00150 return Traits::get_worth(rep_fitness);
00151 }
00152
00153 worth_type fitness(void) const
00154 {
00155 return Traits::get_fitness(*this);
00156 }
00157
00158 void invalidate(void)
00159 {
00160 valid_performance = false;
00161 valid_worth = false;
00162 }
00163
00164 void invalidate_worth(void)
00165 {
00166 valid_worth = false;
00167 }
00168
00169 bool operator<(const EO<Fitness, Traits>& other) const
00170 {
00171 return !Traits::is_better(other, *this);
00172 }
00173
00174 bool operator>(const EO<Fitness, Traits>& other) const
00175 {
00176 return Traits::is_better(other, *this);
00177 }
00178
00179 private :
00180
00181 bool valid_performance;
00182 bool valid_worth;
00183 storage_type rep_fitness;
00184 };
00185
00186
00187
00188
00189
00190
00191 template <class EOT> class eoPop;
00192
00193 template <class EOT>
00194 void exponential_scaling(eoPop<EOT>& _pop)
00195 {
00196 for (unsigned i = 0; i < _pop.size(); ++i)
00197 {
00198 _pop[i].worth(exp(-_pop[i].performance()));
00199 }
00200 }
00201
00202 template <class EOT>
00203 class eoPerf2Worth
00204 {
00205 public :
00206 virtual void operator()(eoPop<EOT>& _pop)
00207 {
00208 return exponential_scaling(_pop);
00209 }
00210 };
00211
00212
00213
00214
00215
00216
00217 template <class EOT>
00218 class eoPop : public vector<EOT>
00219 {
00220 public :
00221
00222 typedef typename EOT::fitness_traits fitness_traits;
00223
00224 eoPop(void) : p2w(0) {}
00225
00226 void sort()
00227 {
00228 scale();
00229
00230 std::sort(begin(), end(), greater<EOT>());
00231 }
00232
00233 void scale()
00234 {
00235 if (p2w)
00236 {
00237 if (!fitness_traits::needs_mapping)
00238 {
00239 throw runtime_error("eoPop: no scaling needed, yet a scaling function is defined");
00240 }
00241
00242 (*p2w)(*this);
00243 }
00244 else if (fitness_traits::needs_mapping)
00245 {
00246 throw runtime_error("eoPop: no scaling function attached to the population, while one was certainly called for");
00247 }
00248 }
00249
00250 void setPerf2Worth(eoPerf2Worth<EOT>& _p2w)
00251 {
00252 p2w = &_p2w;
00253 }
00254
00255 void setPerf2Worth(eoPerf2Worth<EOT>* _p2w)
00256 {
00257 p2w = _p2w;
00258 }
00259
00260 eoPerf2Worth<EOT>* getPerf2Worth() { return p2w; }
00261
00262 void swap(eoPop<EOT>& other)
00263 {
00264 vector<EOT>::swap(other);
00265 eoPerf2Worth<EOT>* tmp = p2w;
00266 p2w = other.p2w;
00267 other.p2w = tmp;
00268 }
00269
00270 private :
00271
00272
00273 eoPerf2Worth<EOT>* p2w;
00274 };
00275
00276
00277 template <class EOT>
00278 void swap(eoPop<EOT>& _p1, eoPop<EOT>& _p2)
00279 {
00280 _p1.swap(_p2);
00281 }
00282
00283
00284
00285
00286
00287 template <class EOT>
00288 void algo(eoPop<EOT>& _pop)
00289 {
00290 eoPop<EOT> offspring;
00291 offspring.setPerf2Worth(_pop.getPerf2Worth());
00292
00293 std::copy(_pop.begin(), _pop.end(), back_inserter(offspring));
00294
00295 offspring.sort();
00296
00297 swap(_pop, offspring);
00298 }
00299
00300 void minimization_test()
00301 {
00302 typedef EO<minimization> eo_type;
00303
00304 eo_type eo1;
00305 eo_type eo2;
00306
00307 eo1.performance(1.0);
00308 eo2.performance(2.0);
00309
00310 std::cout << "With minimizing fitness" << std::endl;
00311 std::cout << eo1.fitness() << " < " << eo2.fitness() << " returns " << (eo1 < eo2) << std::endl;
00312 std::cout << eo2.fitness() << " < " << eo1.fitness() << " returns " << (eo2 < eo1) << std::endl;
00313 }
00314
00315 void the_main()
00316 {
00317 typedef EO<double> simple_eo;
00318 typedef EO<pair<double, double> > scaled_eo;
00319
00320 simple_eo eo1;
00321 simple_eo eo3;
00322
00323
00324
00325 eo1.fitness(10);
00326 eo3.fitness(5);
00327
00328 std::cout << eo1.fitness() << std::endl;
00329 std::cout << eo3.fitness() << std::endl;
00330
00331 std::cout << "eo1 < eo3 = " << (eo1 < eo3) << std::endl;
00332
00333
00334 scaled_eo eo2;
00335 scaled_eo eo4;
00336 eo2.performance(10);
00337 eo4.performance(8);
00338
00339
00340
00341 try
00342 {
00343 std::cout << eo2.fitness() << std::endl;
00344 std::cout << "did not throw" << std::endl;
00345 assert(false);
00346 }
00347 catch(std::exception& e)
00348 {
00349 std::cout << "Fitness threw exception, as it should" << std::endl;
00350 std::cout << e.what() << std::endl;
00351 }
00352
00353
00354
00355 eo2.worth(3);
00356 eo4.worth(5);
00357
00358 std::cout << "with maximization " << std::endl;
00359 std::cout << eo2.fitness() << std::endl;
00360 std::cout << eo4.fitness() << std::endl;
00361 std::cout << eo2.fitness() << " < " << eo4.fitness() << " returns " << (eo2 < eo4) << std::endl;
00362
00363
00364 minimization_test();
00365
00366
00367
00368
00369
00370 eoPop<simple_eo> pop0;
00371 pop0.resize(1);
00372 pop0[0].fitness(1);
00373
00374 algo(pop0);
00375
00376 std::cout << pop0[0].fitness() << std::endl;
00377
00378 assert(pop0[0].fitness() == 1);
00379
00380
00381
00382 eoPerf2Worth<scaled_eo> perf2worth;
00383 eoPop<scaled_eo> pop1;
00384
00385 pop1.resize(1);
00386
00387 pop1[0].fitness(1.0);
00388
00389
00390 try
00391 {
00392 std::cout << pop1[0].fitness() << std::endl;
00393 std::cout << "did not throw" << std::endl;
00394 assert(false);
00395 }
00396 catch(std::exception& e)
00397 {
00398 std::cout << "Fitness threw exception, as it should" << std::endl;
00399 std::cout << e.what() << std::endl;
00400 }
00401
00402
00403 try
00404 {
00405 algo(pop1);
00406 assert(false);
00407 }
00408 catch(std::exception& e)
00409 {
00410 std::cout << e.what() << std::endl;
00411 }
00412
00413
00414 pop1.setPerf2Worth(perf2worth);
00415
00416 algo(pop1);
00417
00418 std::cout << "the fitness has been transformed from " << pop1[0].performance() << " to exp(-1) = " << pop1[0].fitness() << std::endl;
00419 }
00420
00421 int main()
00422 {
00423 try
00424 {
00425 the_main();
00426 }
00427 catch(std::exception& e)
00428 {
00429 std::cout << e.what() << std::endl;
00430 }
00431 }
00432
00433