// Copyright (C) 2015-17 Andrzej Jaszkiewicz
#include "quadtree.h"
#include "ttreeset.h"
#include "mfront.h"
#include "mfront2.h"
#include <sstream>
#include <chrono>
TProblem Problem;
vector <TPoint*> NDS_solutions;
bool frontsEqual(vector<TPoint*>& front1, vector<TPoint*>& front2) {
int i;
for (i = 0; i < front1.size(); i++) {
std::vector<TPoint*>::iterator it;
it = find(front2.begin(), front2.end(), front1[i]);
if (it == front2.end()) {
return false;
}
}
for (i = 0; i < front2.size(); i++) {
std::vector<TPoint*>::iterator it;
it = find(front1.begin(), front1.end(), front2[i]);
if (it == front1.end()) {
return false;
}
}
return true;
}
bool frontsSetEqual(vector<vector<TPoint*>>& fronts1, vector<vector<TPoint*>>& fronts2) {
if (fronts1.size() != fronts2.size()) {
return false;
}
int i;
for (i = 0; i < fronts1.size(); i++) {
if (!frontsEqual(fronts1[i], fronts2[i])) {
return false;
}
}
return true;
}
int sortingObjective;
bool better(TPoint* s1, TPoint* s2) {
return (s1->ObjectiveValues[sortingObjective] < s2->ObjectiveValues[sortingObjective]);
}
bool worse(TPoint* s1, TPoint* s2) {
return (s1->ObjectiveValues[sortingObjective] > s2->ObjectiveValues[sortingObjective]);
}
int DDA_NS(vector<vector<TPoint*>>& fronts) {
vector <TPoint*> unsortedSolutions;
unsortedSolutions = NDS_solutions;
vector<vector<vector<int>>> C_matrix;
vector<vector<int>> D_matrix;
int i;
for (i = 0; i < NDS_solutions.size(); i++) {
NDS_solutions[i]->index = i;
}
C_matrix.resize(NumberOfObjectives);
int j;
for (j = 0; j < NumberOfObjectives; j++) {
C_matrix[j].resize(NDS_solutions.size());
for (i = 0; i < NDS_solutions.size(); i++) {
C_matrix[j][i].resize(NDS_solutions.size(), 0);
}
}
for (j = 0; j < NumberOfObjectives; j++) {
sortingObjective = j;
std::sort(NDS_solutions.begin(), NDS_solutions.end(), worse);
int b1_row = NDS_solutions[0]->index;
for (i = 0; i < NDS_solutions.size(); i++) {
C_matrix[j][b1_row][i] = 1;
}
for (i = 1; i < NDS_solutions.size(); i++) {
int bi_row = NDS_solutions[i]->index;
if (NDS_solutions[i]->ObjectiveValues[j] == NDS_solutions[i - 1]->ObjectiveValues[j]) {
int bi_1_row = NDS_solutions[i - 1]->index;
C_matrix[j][bi_row] = C_matrix[j][bi_1_row];
}
else {
int i2;
for (i2 = i; i2 < NDS_solutions.size(); i2++) {
int bi2_row = NDS_solutions[i2]->index;
C_matrix[j][bi_row][bi2_row] = 1;
}
}
}
}
D_matrix.resize(NDS_solutions.size());
for (i = 0; i < NDS_solutions.size(); i++) {
D_matrix[i].resize(NDS_solutions.size(), 0);
}
for (j = 0; j < NumberOfObjectives; j++) {
for (i = 0; i < NDS_solutions.size(); i++) {
int i2;
for (i2 = 0; i2 < NDS_solutions.size(); i2++) {
D_matrix[i][i2] += C_matrix[j][i][i2];
}
}
}
for (i = 0; i < NDS_solutions.size(); i++) {
D_matrix[i][i] = 0;
}
vector<int> M_vector;
M_vector.resize(NDS_solutions.size(), -1);
int count = 0;
while (true) {
std::fill(M_vector.begin(), M_vector.end(), -1);
vector<TPoint*> front;
for (i = 0; i < NDS_solutions.size(); i++) {
if (D_matrix[i][i] >= 0) {
int i2;
for (i2 = 0; i2 < NDS_solutions.size(); i2++) {
if (M_vector[i] < D_matrix[i][i2]) {
M_vector[i] = D_matrix[i][i2];
}
}
}
}
int newCount = 0;
for (i = 0; i < NDS_solutions.size(); i++) {
if (M_vector[i] >= 0 && M_vector[i] < NumberOfObjectives) {
front.push_back(unsortedSolutions[i]);
newCount++;
D_matrix[i][i] = -1;
int i2;
for (i2 = 0; i2 < NDS_solutions.size(); i2++) {
D_matrix[i2][i] = -1;
}
}
}
count += newCount;
fronts.push_back(front);
if (count == NDS_solutions.size()) {
break;
}
}
return fronts.size();
}
bool frontDominates(vector <TPoint*> front, TPoint* solution) {
int i;
for (i = front.size() - 1; i >= 0; i--) {
TCompare comparisonResult = front[i]->Compare(*solution);
if (comparisonResult == _Dominating) {
return true;
}
}
return false;
}
int ENS_BS(vector<vector<TPoint*>>& fronts) {
// Sort solutions according to the first objective
sortingObjective = 0;
std::sort(NDS_solutions.begin(), NDS_solutions.end(), better);
// Sort lexicographically
for (sortingObjective = 1; sortingObjective < NumberOfObjectives; sortingObjective++) {
int sortStart = 0;
int i;
for (i = 1; i < NDS_solutions.size(); i++) {
if (NDS_solutions[i]->ObjectiveValues[sortingObjective - 1] != NDS_solutions[i - 1]->ObjectiveValues[sortingObjective - 1]) {
if (i - sortStart > 1) {
std::sort(NDS_solutions.begin() + sortStart, NDS_solutions.begin() + i, better);
}
sortStart = i;
}
else {
int a = 1;
}
}
}
vector<TPoint*> front0;
front0.push_back(NDS_solutions[0]);
fronts.push_back(front0);
int i;
for (i = 1; i < NDS_solutions.size(); i++) {
if (NDS_solutions[i]->ObjectiveValues[0] == 2901)
int a = 1;
int minFront = 0;
int maxFront = fronts.size();
while (true) {
if (maxFront - minFront == 0) {
if (maxFront == fronts.size()) {
vector<TPoint*> front;
fronts.push_back(front);
}
fronts[maxFront].push_back(NDS_solutions[i]);
break;
}
if (maxFront - minFront == 1) {
if (frontDominates(fronts[minFront], NDS_solutions[i])) {
if (maxFront == fronts.size()) {
vector<TPoint*> front;
fronts.push_back(front);
}
fronts[maxFront].push_back(NDS_solutions[i]);
break;
}
else {
fronts[minFront].push_back(NDS_solutions[i]);
break;
}
}
else {
int middleFront = (maxFront + minFront) / 2;
if (frontDominates(fronts[middleFront], NDS_solutions[i])) {
minFront = middleFront + 1;
}
else {
maxFront = middleFront;
}
}
}
}
return fronts.size();
}
int ENS_SS(vector<vector<TPoint*>>& fronts) {
// Sort solutions according to the first objective
sortingObjective = 0;
std::sort(NDS_solutions.begin(), NDS_solutions.end(), better);
// Sort lexicographically
for (sortingObjective = 1; sortingObjective < NumberOfObjectives; sortingObjective++) {
int sortStart = 0;
int i;
for (i = 1; i < NDS_solutions.size(); i++) {
if (NDS_solutions[i]->ObjectiveValues[sortingObjective - 1] != NDS_solutions[i - 1]->ObjectiveValues[sortingObjective - 1]) {
if (i - sortStart > 1) {
std::sort(NDS_solutions.begin() + sortStart, NDS_solutions.begin() + i, better);
}
sortStart = i;
}
else {
int a = 1;
}
}
}
vector<TPoint*> front0;
front0.push_back(NDS_solutions[0]);
fronts.push_back(front0);
int i;
for (i = 1; i < NDS_solutions.size(); i++) {
int k;
for (k = 0; k < fronts.size(); k++) {
if (!frontDominates(fronts[k], NDS_solutions[i])) {
fronts[k].push_back(NDS_solutions[i]);
break;
}
}
if (k == fronts.size()) {
vector<TPoint*> front;
front.push_back(NDS_solutions[i]);
fronts.push_back(front);
}
}
return fronts.size();
}
int NDS_NDTree(vector<vector<TPoint*>>& fronts) {
int frontsNum = 0;
vector <TPoint*> solutions;
int i;
for (i = 0; i < NDS_solutions.size(); i++) {
solutions.push_back(NDS_solutions[i]);
}
while (solutions.size() > 0) {
frontsNum++;
TTreeSet <TPoint> treeSet;
int l;
for (l = 0; l < solutions.size(); l++) {
solutions[l]->index = l;
bool treeAdded = treeSet.Update(*((TPoint*)(solutions[l])));
}
treeSet.saveToList();
vector <TPoint*> front;
for (l = 0; l < treeSet.listSet.size(); l++) {
front.push_back(solutions[treeSet.listSet[l]->index]);
solutions[treeSet.listSet[l]->index]->index = -1;
}
fronts.push_back(front);
for (l = 0; l < solutions.size(); l++) {
if (
评论0
最新资源