00001
00002 #include <limits>
00003 #include <moo/eoNSGA_IIa_Eval.h>
00004
00005 namespace nsga2a {
00006
00007 double calc_distance(const std::vector<double>& f1, const std::vector<double>& f2) {
00008 double dist = 0;
00009 for (unsigned i = 0; i < f1.size(); ++i) {
00010 double d = (f1[i] - f2[i]);
00011 dist += pow(fabs(d), 1./2);
00012
00013 }
00014 return dist;
00015 }
00016
00017 unsigned assign_worths(std::vector<detail::FitnessInfo> front, unsigned rank, std::vector<double>& worths) {
00018
00019 unsigned nDim = front[0].fitness.size();
00020
00021
00022 std::vector<unsigned> processed(nDim);
00023
00024 for (unsigned i = 1; i < front.size(); ++i) {
00025 for (unsigned dim = 0; dim < nDim; ++dim) {
00026 if (front[i].fitness[dim] > front[processed[dim]].fitness[dim]) {
00027 processed[dim] = i;
00028 }
00029 }
00030 }
00031
00032
00033 std::vector<detail::FitnessInfo> boundaries;
00034 for (unsigned i = 0; i < processed.size(); ++i) {
00035
00036 worths[ front[ processed[i] ].index] = rank;
00037
00038
00039
00040 boundaries.push_back( front[ processed[i] ] );
00041 }
00042 rank--;
00043
00044
00045 sort(processed.begin(), processed.end());
00046 for (unsigned i = 1; i < processed.size(); ++i) {
00047 if (processed[i] == processed[i-1]) {
00048 std::swap(processed[i], processed.back());
00049 processed.pop_back();
00050 --i;
00051 }
00052 }
00053
00054 while (processed.size()) {
00055 unsigned idx = processed.back();
00056
00057 processed.pop_back();
00058 std::swap(front.back(), front[idx]);
00059 front.pop_back();
00060 }
00061
00062
00063
00064 std::vector<double> distances(front.size(), std::numeric_limits<double>::infinity());
00065
00066 unsigned selected = 0;
00067
00068 for (unsigned i = 0; i < front.size(); ++i) {
00069
00070 for (unsigned k = 0; k < boundaries.size(); ++k) {
00071 double d = calc_distance( front[i].fitness, boundaries[k].fitness);
00072 if (d < distances[i]) {
00073 distances[i] = d;
00074 }
00075 }
00076
00077 if (distances[i] > distances[selected]) {
00078 selected = i;
00079 }
00080 }
00081
00082
00083 while (!front.empty()) {
00084
00085 detail::FitnessInfo last = front[selected];
00086
00087 std::swap(front[selected], front.back());
00088 front.pop_back();
00089
00090 std::swap(distances[selected], distances.back());
00091 distances.pop_back();
00092
00093
00094 worths[last.index] = rank--;
00095
00096 if (front.empty()) break;
00097
00098 selected = 0;
00099
00100 for (unsigned i = 0; i < front.size(); ++i) {
00101 double d = calc_distance(front[i].fitness, last.fitness);
00102
00103 if (d < distances[i]) {
00104 distances[i] = d;
00105 }
00106
00107 if (distances[i] >= distances[selected]) {
00108 selected = i;
00109 }
00110 }
00111 }
00112
00113 return rank;
00114 }
00115
00116 unsigned assign_worths2(std::vector<detail::FitnessInfo> front, unsigned rank, std::vector<double>& worths) {
00117
00118 unsigned nDim = front[0].fitness.size();
00119
00120
00121 std::vector<unsigned> processed(nDim);
00122
00123 for (unsigned i = 1; i < front.size(); ++i) {
00124 for (unsigned dim = 0; dim < nDim; ++dim) {
00125 if (front[i].fitness[dim] > front[processed[dim]].fitness[dim]) {
00126 processed[dim] = i;
00127 }
00128 }
00129 }
00130
00131
00132 std::vector<detail::FitnessInfo> boundaries;
00133 for (unsigned i = 0; i < processed.size(); ++i) {
00134
00135 worths[ front[ processed[i] ].index] = rank;
00136
00137
00138
00139 boundaries.push_back( front[ processed[i] ] );
00140 }
00141 rank--;
00142
00143
00144 sort(processed.begin(), processed.end());
00145 for (unsigned i = 1; i < processed.size(); ++i) {
00146 if (processed[i] == processed[i-1]) {
00147 std::swap(processed[i], processed.back());
00148 processed.pop_back();
00149 --i;
00150 }
00151 }
00152
00153 while (processed.size()) {
00154 unsigned idx = processed.back();
00155
00156 processed.pop_back();
00157 std::swap(front.back(), front[idx]);
00158 front.pop_back();
00159 }
00160
00161
00162
00163 std::vector< std::vector<double> > distances(front.size(), std::vector<double>(nDim, std::numeric_limits<double>::infinity()));
00164
00165 double bestsum = 0;
00166 unsigned selected = 0;
00167
00168 for (unsigned i = 0; i < front.size(); ++i) {
00169
00170 for (unsigned k = 0; k < boundaries.size(); ++k) {
00171 for (unsigned dim = 0; dim < nDim; ++dim) {
00172 double d = front[i].fitness[dim] - boundaries[k].fitness[dim];
00173 if (d > 0 && d < distances[i][dim]) {
00174 distances[i][dim] = d;
00175 }
00176 }
00177 }
00178
00179 double sum = 0;
00180 for (unsigned dim = 0; dim < nDim; ++dim) sum += distances[i][dim];
00181
00182 if (sum > bestsum) {
00183 selected = i;
00184 bestsum = sum;
00185 }
00186 }
00187
00188
00189 while (!front.empty()) {
00190
00191 detail::FitnessInfo last = front[selected];
00192
00193 std::swap(front[selected], front.back());
00194 front.pop_back();
00195
00196 std::swap(distances[selected], distances.back());
00197 distances.pop_back();
00198
00199
00200 worths[last.index] = rank--;
00201
00202 if (front.empty()) break;
00203
00204 selected = 0;
00205 bestsum = 0;
00206
00207 for (unsigned i = 0; i < front.size(); ++i) {
00208 double sum = 0;
00209 for (unsigned dim = 0; dim < nDim; ++dim) {
00210 double d = front[i].fitness[dim] - last.fitness[dim];
00211 if (d > 0 && d < distances[i][dim]) {
00212 distances[i][dim] = d;
00213 }
00214
00215 sum += distances[i][dim];
00216 }
00217
00218 if (sum > bestsum) {
00219 selected = i;
00220 bestsum = sum;
00221 }
00222 }
00223 }
00224
00225 return rank;
00226 }
00227
00228 }