00001
00025
00026
00027 #ifndef eoNDSorting_h
00028 #define eoNDSorting_h
00029
00030 #include <EO.h>
00031 #include <algorithm>
00032 #include <eoPop.h>
00033 #include <eoPerf2Worth.h>
00034 #include <cassert>
00035
00041 template <class EOT>
00042 class eoNDSorting : public eoPerf2WorthCached<EOT, double>
00043 {
00044 public :
00045
00046 using eoPerf2WorthCached<EOT, double>::value;
00047 eoNDSorting(bool nasty_flag_ = false)
00048 : nasty_declone_flag_that_only_is_implemented_for_two_objectives(nasty_flag_)
00049 {}
00050
00051
00052 eoNDSorting()
00053 : nasty_declone_flag_that_only_is_implemented_for_two_objectives(false)
00054 {}
00055
00060 virtual std::vector<double> niche_penalty(const std::vector<unsigned>& current_front, const eoPop<EOT>& _pop) = 0;
00061
00062 void calculate_worths(const eoPop<EOT>& _pop)
00063 {
00064
00065 value().resize(_pop.size());
00066
00067 typedef typename EOT::Fitness::fitness_traits traits;
00068
00069 switch (traits::nObjectives())
00070 {
00071 case 1:
00072 {
00073 one_objective(_pop);
00074 return;
00075 }
00076 case 2:
00077 {
00078 two_objectives(_pop);
00079 return;
00080 }
00081 default :
00082 {
00083 m_objectives(_pop);
00084 }
00085 }
00086 }
00087
00088 private :
00089
00094 class DummyEO : public EO<typename EOT::Fitness>
00095 {
00096 public: unsigned index;
00097 };
00098
00099 void one_objective(const eoPop<EOT>& _pop)
00100 {
00101 unsigned i;
00102 std::vector<DummyEO> tmp_pop;
00103 tmp_pop.resize(_pop.size());
00104
00105
00106 for (i = 0; i < _pop.size(); ++i)
00107 {
00108 tmp_pop[i].fitness(_pop[i].fitness());
00109 tmp_pop[i].index = i;
00110 }
00111
00112 std::sort(tmp_pop.begin(), tmp_pop.end(), std::greater<DummyEO>());
00113
00114 for (i = 0; i < _pop.size(); ++i)
00115 {
00116 value()[tmp_pop[i].index] = _pop.size() - i;
00117 }
00118
00119
00120 }
00121
00140 void two_objectives(const eoPop<EOT>& _pop)
00141 {
00142 unsigned i;
00143 typedef typename EOT::Fitness::fitness_traits traits;
00144 assert(traits::nObjectives() == 2);
00145
00146 std::vector<unsigned> sort1(_pop.size());
00147
00148 for (i = 0; i < _pop.size(); ++i)
00149 {
00150 sort1[i] = i;
00151 }
00152
00153 std::sort(sort1.begin(), sort1.end(), Sorter(_pop));
00154
00155
00156
00157 unsigned last_front = 0;
00158
00159 double max1 = -1e+20;
00160 for (i = 0; i < _pop.size(); ++i)
00161 {
00162 max1 = std::max(max1, _pop[i].fitness()[1]);
00163 }
00164
00165 max1 = max1 + 1.0;
00166
00167 unsigned prev_front = 0;
00168 std::vector<double> d;
00169 d.resize(_pop.size(), max1);
00170
00171 std::vector<std::vector<unsigned> > fronts(_pop.size());
00172
00173 for (i = 0; i < _pop.size(); ++i)
00174 {
00175 unsigned index = sort1[i];
00176
00177
00178 if (i > 0)
00179 {
00180 unsigned prev = sort1[i-1];
00181 if ( _pop[index].fitness() == _pop[prev].fitness())
00182 {
00183
00184 if (nasty_declone_flag_that_only_is_implemented_for_two_objectives)
00185
00186 fronts.back().push_back(index);
00187 else
00188 fronts[prev_front].push_back(index);
00189 continue;
00190 }
00191 }
00192
00193 double value2 = _pop[index].fitness()[1];
00194
00195 if (traits::maximizing(1))
00196 value2 = max1 - value2;
00197
00198
00199 std::vector<double>::iterator it =
00200 std::upper_bound(d.begin(), d.begin() + last_front, value2);
00201
00202 unsigned front = unsigned(it - d.begin());
00203 if (front == last_front) ++last_front;
00204
00205 assert(it != d.end());
00206
00207 *it = value2;
00208 fronts[front].push_back(index);
00209
00210 prev_front = front;
00211 }
00212
00213
00214
00215 for (i = 0; i < fronts.size(); ++i)
00216 {
00217 if (fronts[i].size() == 0) continue;
00218
00219
00220 std::vector<double> niche_count = niche_penalty(fronts[i], _pop);
00221
00222
00223 if (niche_count.size() != fronts[i].size())
00224 {
00225 throw std::logic_error("eoNDSorting: niche and front should have the same size");
00226 }
00227
00228 double max_niche = *std::max_element(niche_count.begin(), niche_count.end());
00229
00230 for (unsigned j = 0; j < fronts[i].size(); ++j)
00231 {
00232 value()[fronts[i][j]] = i + niche_count[j] / (max_niche + 1.);
00233 }
00234
00235 }
00236
00237
00238 rank_to_worth();
00239 }
00240
00241 class Sorter
00242 {
00243 public:
00244 Sorter(const eoPop<EOT>& _pop) : pop(_pop) {}
00245
00246 bool operator()(unsigned i, unsigned j) const
00247 {
00248 typedef typename EOT::Fitness::fitness_traits traits;
00249
00250 double diff = pop[i].fitness()[0] - pop[j].fitness()[0];
00251
00252 if (fabs(diff) < traits::tol())
00253 {
00254 diff = pop[i].fitness()[1] - pop[j].fitness()[1];
00255
00256 if (fabs(diff) < traits::tol())
00257 return false;
00258
00259 if (traits::maximizing(1))
00260 return diff > 0.;
00261 return diff < 0.;
00262 }
00263
00264 if (traits::maximizing(0))
00265 return diff > 0.;
00266 return diff < 0.;
00267 }
00268
00269 const eoPop<EOT>& pop;
00270 };
00271
00272 void m_objectives(const eoPop<EOT>& _pop)
00273 {
00274 unsigned i;
00275
00276 typedef typename EOT::Fitness::fitness_traits traits;
00277
00278 std::vector<std::vector<unsigned> > S(_pop.size());
00279 std::vector<unsigned> n(_pop.size(), 0);
00280
00281 unsigned j;
00282 for (i = 0; i < _pop.size(); ++i)
00283 {
00284 for (j = 0; j < _pop.size(); ++j)
00285 {
00286 if (_pop[i].fitness().dominates(_pop[j].fitness()))
00287 {
00288 S[i].push_back(j);
00289
00290
00291 }
00292 else if (_pop[j].fitness().dominates(_pop[i].fitness()))
00293 {
00294 n[i]++;
00295
00296
00297 }
00298 }
00299 }
00300
00301 std::vector<unsigned> current_front;
00302 current_front.reserve(_pop.size());
00303
00304
00305 for (i = 0; i < _pop.size(); ++i)
00306 {
00307 if (n[i] == 0)
00308 {
00309 current_front.push_back(i);
00310 }
00311 }
00312
00313 std::vector<unsigned> next_front;
00314 next_front.reserve(_pop.size());
00315
00316 unsigned front_index = 0;
00317 while (!current_front.empty())
00318 {
00319
00320 std::vector<double> niche_count = niche_penalty(current_front, _pop);
00321
00322
00323 if (niche_count.size() != current_front.size())
00324 {
00325 throw std::logic_error("eoNDSorting: niche and front should have the same size");
00326 }
00327
00328 double max_niche = *std::max_element(niche_count.begin(), niche_count.end());
00329
00330 for (i = 0; i < current_front.size(); ++i)
00331 {
00332 value()[current_front[i]] = front_index + niche_count[i] / (max_niche + 1.);
00333 }
00334
00335
00336
00337 for (i = 0; i < current_front.size(); ++i)
00338 {
00339 for (j = 0; j < S[current_front[i]].size(); ++j)
00340 {
00341 unsigned dominated_individual = S[current_front[i]][j];
00342 n[dominated_individual]--;
00343
00344 if (n[dominated_individual] == 0)
00345 {
00346 next_front.push_back(dominated_individual);
00347 }
00348 }
00349 }
00350
00351 front_index++;
00352 swap(current_front, next_front);
00353 next_front.clear();
00354 }
00355
00356 rank_to_worth();
00357 }
00358
00359 void rank_to_worth()
00360 {
00361
00362 double max_fitness = *std::max_element(value().begin(), value().end());
00363
00364
00365 max_fitness = ceil(max_fitness);
00366
00367 for (unsigned i = 0; i < value().size(); ++i)
00368 {
00369 value()[i] = max_fitness - value()[i];
00370 }
00371
00372 }
00373 public : bool nasty_declone_flag_that_only_is_implemented_for_two_objectives;
00374 };
00375
00379 template <class EOT>
00380 class eoNDSorting_I : public eoNDSorting<EOT>
00381 {
00382 public :
00383 eoNDSorting_I(double _nicheSize, bool nasty_flag_ = false) : eoNDSorting<EOT>(nasty_flag_), nicheSize(_nicheSize) {}
00384
00385 std::vector<double> niche_penalty(const std::vector<unsigned>& current_front, const eoPop<EOT>& _pop)
00386 {
00387 std::vector<double> niche_count(current_front.size(), 0.);
00388
00389 for (unsigned i = 0; i < current_front.size(); ++i)
00390 {
00391 for (unsigned j = 0; j < current_front.size(); ++j)
00392 {
00393 if (i == j)
00394 continue;
00395
00396 double dist = 0.0;
00397
00398 for (unsigned k = 0; k < _pop[current_front[j]].fitness().size(); ++k)
00399 {
00400 double d = _pop[current_front[i]].fitness()[k] - _pop[current_front[j]].fitness()[k];
00401 dist += d*d;
00402 }
00403
00404 if (dist < nicheSize)
00405 {
00406 niche_count[i] += 1.0 - pow(dist / nicheSize,2.);
00407 }
00408 }
00409 }
00410
00411 return niche_count;
00412 }
00413
00414 private :
00415
00416 double nicheSize;
00417 };
00418
00433 template <class EOT>
00434 class eoNDSorting_II : public eoNDSorting<EOT>
00435 {
00436 public:
00437
00438 eoNDSorting_II(bool nasty_flag_ = false) : eoNDSorting<EOT>(nasty_flag_) {}
00439
00440 typedef std::pair<double, unsigned> double_index_pair;
00441
00442 class compare_nodes
00443 {
00444 public :
00445 bool operator()(const double_index_pair& a, const double_index_pair& b) const
00446 {
00447 return a.first < b.first;
00448 }
00449 };
00450
00452 std::vector<double> niche_penalty(const std::vector<unsigned>& _cf, const eoPop<EOT>& _pop)
00453 {
00454 typedef typename EOT::Fitness::fitness_traits traits;
00455 unsigned i;
00456 std::vector<double> niche_count(_cf.size(), 0.);
00457
00458
00459 unsigned nObjectives = traits::nObjectives();
00460
00461 for (unsigned o = 0; o < nObjectives; ++o)
00462 {
00463
00464 std::vector<std::pair<double, unsigned> > performance(_cf.size());
00465 for (i =0; i < _cf.size(); ++i)
00466 {
00467 performance[i].first = _pop[_cf[i]].fitness()[o];
00468 performance[i].second = i;
00469 }
00470
00471 std::sort(performance.begin(), performance.end(), compare_nodes());
00472
00473 std::vector<double> nc(niche_count.size(), 0.0);
00474
00475 for (i = 1; i < _cf.size()-1; ++i)
00476 {
00477 nc[performance[i].second] = performance[i+1].first - performance[i-1].first;
00478 }
00479
00480 double max_dist = *std::max_element(nc.begin(), nc.end());
00481
00482
00483 nc[performance[0].second] += max_dist + 1;
00484 nc[performance.back().second] += max_dist + 1;
00485
00486 for (i = 0; i < nc.size(); ++i)
00487 {
00488 niche_count[i] += (max_dist + 1 - nc[i]);
00489 }
00490 }
00491
00492 return niche_count;
00493 }
00494 };
00495
00496 #endif