NSGA2.h

 
#ifndef DIGNEA_NSGA2_H
#define DIGNEA_NSGA2_H
 
#include <dignea/core/AbstractGA.h>
#include <dignea/core/Crossover.h>
#include <dignea/core/Mutation.h>
#include <dignea/core/Solution.h>
#include <dignea/utilities/Comparator.h>
#include <dignea/utilities/Sorter.h>
#include <dignea/utilities/random/PseudoRandom.h>
 
#include <ranges>
#include <string>
#include <vector>
 
using namespace std;
 
template <class S>
class NSGA2 : public AbstractGA<S> {
   public:
    NSGA2();
 
    virtual ~NSGA2() = default;
    string getName() const override {
        return "Non-dominated Sorting Genetic Algorithm II";
    }
    string getID() const override { return "NSGA-II"; }
 
    void run() override;
 
    void setProblem(shared_ptr<Problem<S>> prob) override;
 
    void setProblem(Problem<S> *prob) override;
 
    virtual Front<S> getResults() const;
 
   protected:
    void initProgress() override;
 
    void updateProgress() override;
 
    virtual void createInitialPopulation() override;
 
    virtual void evaluatePopulation(vector<S> &pop) override;
 
    virtual vector<S> createMating() override;
 
    virtual void reproduction(S &, S &) override;
 
   private:
    void rankPopulation();
    vector<S> rankCrowdingPopulation(vector<S> &combinedPopulation);
};
 
template <class S>
NSGA2<S>::NSGA2() : AbstractGA<S>() {}
 
template <class S>
void NSGA2<S>::createInitialPopulation() {
    this->population.resize(this->populationSize);
    for (int i = 0; i < this->getPopulationSize(); i++) {
        this->population[i] = this->problem->createSolution();
    }
    // Usamos el método por si empleamos un evaluador paralelo
    this->evaluatePopulation(this->population);
    // Reseteamos el printingcheck --> Para el uso de repeticiones en los
    // experimentos
    this->nextCheckpoint = 0;
    this->updateEvolution(0, this->population);
    this->initProgress();
}
 
template <class S>
void NSGA2<S>::initProgress() {
    this->performedEvaluations = this->populationSize;
}
 
template <class S>
void NSGA2<S>::run() {
    if (this->problem) {
        this->createInitialPopulation();
        this->startTime = chrono::system_clock::now();
        this->rankPopulation();
        while (!this->isStoppingConditionReached()) {
            vector offspring = this->createMating();
 
            offspring.insert(offspring.end(), this->population.begin(),
                             this->population.end());
            this->population = this->rankCrowdingPopulation(offspring);
            this->updateEvolution(this->performedEvaluations, this->population);
        }
        this->endTime = chrono::system_clock::now();
        this->finishProgress();
    } else {
        throw std::runtime_error("Problem is not set in GA::run");
    }
}
 
template <class S>
void NSGA2<S>::rankPopulation() {
    vector<vector<S>> fronts =
        fastNonDominatedSort(this->population, this->problem.get());
    this->population.clear();
    for (vector<S> front : fronts) {
        for (S solution : front) {
            this->population.push_back(solution);
        }
    }
}
 
template <class S>
vector<S> NSGA2<S>::rankCrowdingPopulation(vector<S> &combinedPopulation) {
    vector<vector<S>> fronts =
        fastNonDominatedSort(combinedPopulation, this->problem.get());
    vector<S> newPopulation;
    newPopulation.reserve(this->populationSize);
    auto toInsert = this->populationSize;
    auto index = 0;
    // We sort the front using the crowding operator
    // Then we include each solution in the new population
    std::for_each(fronts.begin(), fronts.end(),
                  [&](vector<S> &f) { crowOrder(f, this->problem.get()); });
    // Include all solutions in the fronts that fits perfectly
    bool fits = toInsert <= (int)fronts[0].size();
    while (fits) {
        for (S solution : fronts[index]) {
            newPopulation.push_back(solution);
            toInsert--;
            if (toInsert == 0) {
                break;
            }
        }
        index++;
        if ((toInsert <= 0) || (toInsert <= (int)fronts[index].size())) {
            fits = false;
        }
    }
    // If we don't have enough solutions yet to create a new population
    // and the remaining fronts doesn't fit entirely, we include only
    // the `n` necessary new solutions
    if (toInsert > 0) {
        vector<vector<S>> remaining(fronts.begin() + index, fronts.end());
        auto jv = std::ranges::join_view(remaining);
        std::ranges::for_each(
            jv | std::ranges::views::take(toInsert),
            [&](const S &solution) { newPopulation.push_back(solution); });
    }
    return newPopulation;
}
 
template <class S>
void NSGA2<S>::evaluatePopulation(vector<S> &pop) {
    this->evaluator->evaluate(pop, this->problem.get());
}
 
template <class S>
vector<S> NSGA2<S>::createMating() {
    // Generates offsprings
    vector<S> offspring;
    for (int i = 0; i < this->populationSize; i++) {
        S child1 = this->selection->select(this->population);
        S child2 = this->selection->select(this->population);
        reproduction(child1, child2);
        this->problem->evaluate(child1);
        this->problem->evaluate(child2);
        offspring.push_back(child1);
        offspring.push_back(child2);
        this->performedEvaluations += 2;
    }
    return offspring;
}
 
template <class S>
void NSGA2<S>::reproduction(S &child1, S &child2) {
    // Cruzamos los individuos con cierta probabilidad
    if (PseudoRandom::randDouble() < this->crossRate) {
        this->crossover->run(child1, child2);
    }
    this->mutation->run(child1, this->mutationRate, this->problem.get());
    this->mutation->run(child2, this->mutationRate, this->problem.get());
}
 
template <class S>
void NSGA2<S>::updateProgress() {
    this->performedEvaluations += 2;
}
 
template <class S>
void NSGA2<S>::setProblem(shared_ptr<Problem<S>> prob) {
    if (prob->getNumberOfObjs() != 2) {
        std::string where = "NSGA2 setProblem";
        throw(NoMOAllowed(where));
    }
    this->problem = prob;
}
template <class S>
void NSGA2<S>::setProblem(Problem<S> *prob) {
    if (prob->getNumberOfObjs() != 2) {
        std::string where = "NSGA2 setProblem";
        throw(NoMOAllowed(where));
    }
    this->problem.reset(prob);
}
 
template <class S>
Front<S> NSGA2<S>::getResults() const {
    Front<S> front(0);
    std::ranges::for_each(this->population, [&](const S &solution) {
        front.addSolution(solution, this->problem.get());
    });
    return front;
}
 
#endif  // DIGNEA_NSGA2_H