00001 #ifndef eoEpsilonArchive_h
00002 #define eoEpsilonArchive_h
00003
00004 #include <moo/eoMOFitness.h>
00005 #include <list>
00006
00007 template <class EOT>
00008 class eoEpsilonArchive {
00009
00010 typedef typename EOT::Fitness::fitness_traits Traits;
00011
00012 struct Node {
00013 EOT element;
00014 std::vector<long> discretized;
00015
00016 Node(const EOT& eo) : element(eo), discretized(Traits::nObjectives()) {}
00017
00018 dominance::dominance_result check(const Node& other) const {
00019 return dominance::check_discrete(discretized, other.discretized);
00020 }
00021 };
00022
00023 typedef std::vector<Node> archive_t;
00024
00025 archive_t archive;
00026 std::vector<double> inv_eps;
00027
00028 unsigned max_size;
00029
00030 public:
00031
00032 static double direction(unsigned i) { return 1; }
00033 static double tol() { return 1e-6; }
00034
00035
00036 eoEpsilonArchive(const std::vector<double>& eps_, unsigned max_size_ = std::numeric_limits<unsigned>::max()) : max_size(max_size_) {
00037 inv_eps.resize(eps_.size());
00038 for (unsigned i = 0; i < inv_eps.size(); ++i) {
00039 inv_eps[i] = 1.0 / eps_[i];
00040 }
00041 if (inv_eps.size() != Traits::nObjectives()) throw std::logic_error("eoEpsilonArchive: need one epsilon for each objective");
00042 }
00043
00044 bool empty() { return archive.size() == 0; }
00045
00046 void operator()(const EOT& eo) {
00047
00048 using std::cout;
00049 using std::endl;
00050
00051
00052 Node node(eo);
00053 for (unsigned i = 0; i < eo.fitness().size(); ++i) {
00054 double val = Traits::direction(i) * eo.fitness()[i];
00055
00056 node.discretized[i] = (long) floor(val*inv_eps[i]);
00057 }
00058
00059 using namespace dominance;
00060
00061 unsigned box = archive.size();
00062
00063
00064
00065 for (unsigned i = 0; i != archive.size(); ++i) {
00066 dominance_result result = node.check(archive[i]);
00067
00068 switch (result) {
00069 case first : {
00070 std::swap( archive[i], archive.back());
00071 archive.pop_back();
00072 --i;
00073 break;
00074 }
00075 case second : {
00076 return;
00077 }
00078 case non_dominated : break;
00079 case non_dominated_equal : {
00080 box = i;
00081 goto exitLoop;
00082 }
00083 }
00084
00085 }
00086
00087 exitLoop:
00088
00089 if (box >= archive.size()) {
00090 archive.push_back(node);
00091 } else {
00092 int dom = node.element.fitness().check_dominance( archive[box].element.fitness() );
00093
00094 switch (dom) {
00095 case 1: archive[box] = node; break;
00096 case -1: break;
00097 case 0: {
00098 double d1 = 0.0;
00099 double d2 = 0.0;
00100
00101 for (unsigned i = 0; i < node.element.fitness().size(); ++i) {
00102 double a = Traits::direction(i) * node.element.fitness()[i] * inv_eps[i];
00103 double b = Traits::direction(i) * archive[box].element.fitness()[i] * inv_eps[i];
00104
00105 d1 += pow( a - node.discretized[i], 2.0);
00106 d2 += pow( b - node.discretized[i], 2.0);
00107 }
00108
00109 if (d1 > d2) {
00110 archive[box] = node;
00111 }
00112 break;
00113 }
00114 }
00115 }
00116
00117 if (archive.size() > max_size) {
00118 unsigned idx = rng.random(archive.size());
00119 if (idx != archive.size()-1) std::swap(archive[idx], archive.back());
00120 archive.pop_back();
00121 }
00122
00123 }
00124
00125 void appendTo(eoPop<EOT>& pop) const {
00126 for (typename archive_t::const_iterator it = archive.begin(); it != archive.end(); ++it) {
00127 pop.push_back( it->element );
00128 }
00129 }
00130
00131 const EOT& selectRandom() const {
00132 int i = rng.random(archive.size());
00133 return archive[i].element;
00134 }
00135
00136 };
00137
00138
00139 #endif
00140