00001 #include <moo/eoFrontSorter.h>
00002
00003 using namespace std;
00004
00005 namespace detail {
00006
00007 void one_objective(std::vector<FitnessInfo>& fitness, std::vector< std::vector<FitnessInfo> >& front, double tol)
00008 {
00009 std::sort(fitness.begin(), fitness.end(), CompareOn(0, tol));
00010
00011 front.clear();
00012 front.resize(1);
00013 front[0].push_back(fitness[0]);
00014 for (unsigned i = 1; i < fitness.size(); ++i) {
00015 if (fitness[i].fitness[0] < fitness[i-1].fitness[0]) {
00016 front.push_back( std::vector<FitnessInfo>() );
00017 }
00018
00019 front.back().push_back( fitness[i] );
00020 }
00021 }
00022
00023
00030 void two_objectives(std::vector<FitnessInfo>& fitness, std::vector< std::vector<FitnessInfo> >& front, double tol)
00031 {
00032 std::sort(fitness.begin(), fitness.end(), CompareOn(0, tol));
00033
00034 front.clear();
00035
00036 std::vector<FitnessInfo> front_leader;
00037
00038 for (unsigned i = 0; i < fitness.size(); ++i) {
00039
00040
00041 vector<FitnessInfo>::iterator it = upper_bound( front_leader.begin(), front_leader.end(), fitness[i], CompareOn(1, tol));
00042
00043 if (it == front_leader.end()) {
00044 front_leader.push_back(fitness[i]);
00045 front.push_back( vector<FitnessInfo>(1, fitness[i]) );
00046 } else {
00047 *it = fitness[i];
00048 front[ it - front_leader.begin() ].push_back(fitness[i]);
00049 }
00050 }
00051 }
00052
00053 bool dominates(const FitnessInfo& a, const FitnessInfo& b, double tol) {
00054 bool better_on_one = false;
00055
00056 for (unsigned i = 0; i < a.fitness.size(); ++i) {
00057 if (fabs(a.fitness[i] - b.fitness[i]) < tol) continue;
00058
00059 if (a.fitness[i] < b.fitness[i]) return false;
00060 if (a.fitness[i] > b.fitness[i]) better_on_one = true;
00061 }
00062
00063 return better_on_one;
00064 }
00065
00066 void m_objectives(std::vector<FitnessInfo>& fitness, std::vector< std::vector<FitnessInfo> >& front, double tol) {
00067 unsigned i;
00068
00069 std::vector<std::vector<unsigned> > S(fitness.size());
00070 std::vector<unsigned> n(fitness.size());
00071
00072 unsigned j;
00073 for (i = 0; i < fitness.size(); ++i)
00074 {
00075 for (j = 0; j < fitness.size(); ++j)
00076 {
00077 if ( dominates(fitness[i], fitness[j], tol) )
00078 {
00079 S[i].push_back(j);
00080 }
00081 else if (dominates(fitness[j], fitness[i], tol))
00082 {
00083 n[i]++;
00084 }
00085 }
00086 }
00087
00088 front.clear();
00089 front.resize(1);
00090
00091 for (i = 0; i < fitness.size(); ++i)
00092 {
00093 if (n[i] == 0)
00094 {
00095 front.back().push_back( fitness[i] );
00096 }
00097 }
00098
00099 while (!front.back().empty())
00100 {
00101 front.push_back(vector<FitnessInfo>());
00102 vector<FitnessInfo>& last_front = front[front.size()-2];
00103
00104
00105
00106 for (i = 0; i < last_front.size(); ++i)
00107 {
00108 for (j = 0; j < S[ last_front[i].index ].size(); ++j)
00109 {
00110 unsigned dominated_individual = S[ last_front[i].index ][j];
00111 n[dominated_individual]--;
00112
00113 if (n[dominated_individual] == 0)
00114 {
00115 front.back().push_back( fitness[dominated_individual] );
00116 }
00117 }
00118 }
00119 }
00120
00121 front.pop_back();
00122 }
00123
00124 void front_sorter_impl(std::vector<FitnessInfo>& fitness, std::vector< std::vector<FitnessInfo> >& front_indices, double tol) {
00125
00126 switch (fitness[0].fitness.size())
00127 {
00128 case 1:
00129 {
00130 one_objective(fitness, front_indices, tol);
00131 return;
00132 }
00133 case 2:
00134 {
00135 two_objectives(fitness, front_indices, tol);
00136 return;
00137 }
00138 default :
00139 {
00140 m_objectives(fitness, front_indices, tol);
00141 }
00142 }
00143 }
00144
00145 }
00146