EIG.h

Go to the documentation of this file.

 
#ifndef DIGNEA_EIG_H
#define DIGNEA_EIG_H
 
#include <dignea/core/AbstractEA.h>
#include <dignea/core/Crossover.h>
#include <dignea/core/Mutation.h>
#include <dignea/core/Replacement.h>
#include <dignea/core/Selection.h>
#include <dignea/crossovers/UniformCrossover.h>
#include <dignea/distances/Euclidean.h>
#include <dignea/generator/AbstractDomain.h>
#include <dignea/generator/evaluations/EasyInstances.h>
#include <dignea/generator/evaluations/InstanceFitness.h>
#include <dignea/generator/evaluations/Weighted.h>
#include <dignea/metrics/AverageFitness.h>
#include <dignea/metrics/BestFitness.h>
#include <dignea/mutations/UniformOneMutation.h>
#include <dignea/replacements/EGenerational.h>
#include <dignea/searches/NSFeatures.h>
#include <dignea/searches/NoveltySearch.h>
#include <dignea/selections/BinaryTournamentSelection.h>
#include <dignea/utilities/exceptions/Mismatch.h>
#include <dignea/utilities/random/PseudoRandom.h>
 
#include <numeric>
#include <vector>
 
using namespace std;
 
template <typename IP, typename IS, typename OP, typename OS>
class EIG : public AbstractEA<IS> {
   public:
    using Alg = AbstractEA<OS>; 
    EIG(const float &fitness = 0.6f, const float &novelty = 0.4f);
 
    virtual ~EIG() = default;
 
    void run() override;
 
    [[nodiscard]] json to_json() const override;
 
    [[nodiscard]] string getName() const override { return "EIG"; };
 
    [[nodiscard]] string getID() const override { return getName(); };
 
    virtual Front<IS> getResults() const override;
 
    const IP *getInstanceProblem() const { return instProb.get(); }
 
    void setInstanceProblem(unique_ptr<IP> problem);
 
    vector<Alg *> getPortfolio() const;
 
    void setPortfolio(vector<unique_ptr<Alg>> &configs);
 
    [[nodiscard]] float getMutationRate() const { return mutationRate; }
 
    void setMutationRate(float mRate) { this->mutationRate = mRate; }
 
    [[nodiscard]] float getCrossoverRate() const { return crossoverRate; }
 
    void setCrossoverRate(float cRate) { this->crossoverRate = cRate; }
 
    [[nodiscard]] int getRepetitions() const { return repetitions; }
 
    void setRepetitions(int reps) { this->repetitions = reps; }
 
    Mutation<IS> *getMutation() const { return mutation.get(); }
 
    void setMutation(unique_ptr<Mutation<IS>> mut) {
        this->mutation = move(mut);
    }
    Crossover<IS> *getCrossover() const { return crossover.get(); }
 
    void setCrossover(unique_ptr<Crossover<IS>> cx) {
        this->crossover = move(cx);
    }
    Selection<IS> *getSelection() const { return selection.get(); }
 
    void setSelection(unique_ptr<Selection<IS>> sel) {
        this->selection = move(sel);
    }
 
    void setReplacement(unique_ptr<Replacement<IS>> rep) {
        this->repOperator = move(rep);
    }
 
    [[nodiscard]] InstanceFitness *getEvaluation() const {
        return instanceFitness.get();
    }
    void setInstanceFitness(unique_ptr<InstanceFitness> eval) {
        this->instanceFitness = move(eval);
    }
 
    inline int getGenerations() { return this->getMaxEvaluations(); };
 
    const NoveltySearch<IS> *getNoveltySearch() const {
        return noveltySearch.get();
    }
    void setNoveltySearch(unique_ptr<NoveltySearch<IS>> noveltySearch) {
        this->noveltySearch = move(noveltySearch);
    }
 
    void setWeightedFunction(const float &fW, const float &nW) {
        this->weightedFitness = make_unique<Weighted<IS>>(fW, nW);
    }
 
   protected:
    void initProgress() override;
 
    void updateProgress() override;
 
    void finishProgress() override;
 
    bool isStoppingConditionReached() override;
 
    void createInitialPopulation() override;
 
    void evaluatePopulation(vector<IS> &individuals) override;
 
    [[maybe_unused]] void evaluateIndividual(IS &individual);
 
    virtual void evaluationPhase(vector<IS> &individuals);
 
    virtual void reproduction(IS &solution, IS &solution2);
 
    virtual void replacement(vector<IS> &individuals);
 
    virtual void updateEvolution(vector<IS> &solutions);
 
   protected:
    unique_ptr<IP> instProb; 
    vector<unique_ptr<Alg>>
        algPortfolio; 
    unique_ptr<Mutation<IS>> mutation;   
    unique_ptr<Crossover<IS>> crossover; 
    unique_ptr<Selection<IS>> selection; 
    unique_ptr<Replacement<IS>> repOperator;
 
    float mutationRate;  
    float crossoverRate; 
    int repetitions; 
    unique_ptr<NoveltySearch<IS>> noveltySearch;  
    unique_ptr<InstanceFitness> instanceFitness;  // Evaluation formulation
    unique_ptr<Weighted<IS>> weightedFitness;
 
    AverageFitness<OS> averageFitness; 
    BestFitness<OS>
        bestFitness; 
};
 
template <typename IP, typename IS, typename OP, typename OS>
EIG<IP, IS, OP, OS>::EIG(const float &fitness, const float &novelty)
    : AbstractEA<IS>(),
      mutationRate(0.05),
      crossoverRate(0.8),
      repetitions(10),
      averageFitness(),
      bestFitness() {
    // Easy instances by default
    instanceFitness = make_unique<EasyInstances>();
    weightedFitness = make_unique<Weighted<IS>>(fitness, novelty);
    noveltySearch = make_unique<NSFeatures<IS>>(make_unique<Euclidean<float>>(),
                                                this->maxEvaluations, 3.0, 15);
    this->evolutionInterval = 1;
}
 
template <typename IP, typename IS, typename OP, typename OS>
void EIG<IP, IS, OP, OS>::run() {
    if (instProb) {
#ifdef DEBUG
        std::cout << "Running EIG" << std::endl;
#endif
        // Defines FirstImprove replacement if other not set
        if (!repOperator) {
            this->repOperator = make_unique<FirstImprove<IS>>();
        }
        createInitialPopulation();
        this->startTime = chrono::system_clock::now();
        vector<IS> offspring(this->populationSize);
        while (!isStoppingConditionReached()) {
#ifdef DEBUG
            std::cout << "Performing Generation " << this->performedEvaluations
                      << std::endl;
#endif
            for (int i = 0; i < this->populationSize; i++) {
                IS firstChild = selection->select(this->population);
                IS secondChild = selection->select(this->population);
                reproduction(firstChild, secondChild);
                offspring[i] = firstChild;
            }
            evaluationPhase(offspring);
            replacement(offspring);
            // Updates the fitness evolution
            this->updateEvolution(this->population);
            updateProgress();
        }
        this->endTime = chrono::system_clock::now();
        finishProgress();
    } else {
        throw std::logic_error("AbstractDomain not set in EIG::run");
    }
}
 
template <typename IP, typename IS, typename OP, typename OS>
void EIG<IP, IS, OP, OS>::updateEvolution(vector<IS> &solutions) {
    if (this->performedEvaluations % 10 == 0) {
        this->evolution.update(this->performedEvaluations, solutions);
        this->avgEvolution.update(this->performedEvaluations, solutions);
    }
}
 
template <typename IP, typename IS, typename OP, typename OS>
void EIG<IP, IS, OP, OS>::evaluationPhase(vector<IS> &individuals) {
    // Evaluates with the Instance type and the EAs (only Fitness)
    evaluatePopulation(individuals);
    // Computes the diversity of each individual
    individuals = noveltySearch->run(individuals, this->instProb.get());
    // Computes the weighted sum of both fit + div
#ifdef DEBUG
    auto [fRatio, nRatio] = this->weightedFitness->getFAndNRatios();
    std::cout << fmt::format("{:=^120}", "") << std::endl;
    std::cout << fmt::format("{:^20}({})\t{:^20}({})\t{:^20}",
                             "Performance Score ", fRatio, "Diversity Score ",
                             nRatio, "Fitness")
              << std::endl;
    std::cout << fmt::format("{:=^120}", "") << std::endl;
#endif
    weightedFitness->computeFitness(individuals);
}
 
template <typename IP, typename IS, typename OP, typename OS>
Front<IS> EIG<IP, IS, OP, OS>::getResults() const {
    return noveltySearch->getResults();
}
 
template <typename IP, typename IS, typename OP, typename OS>
void EIG<IP, IS, OP, OS>::initProgress() {
    this->performedEvaluations = 0;
}
 
template <typename IP, typename IS, typename OP, typename OS>
void EIG<IP, IS, OP, OS>::updateProgress() {
    this->performedEvaluations++;
}
 
template <typename IP, typename IS, typename OP, typename OS>
void EIG<IP, IS, OP, OS>::finishProgress() {
    std::chrono::duration<double> diff = this->endTime - this->startTime;
    this->elapsedTime = diff.count();
}
 
template <typename IP, typename IS, typename OP, typename OS>
bool EIG<IP, IS, OP, OS>::isStoppingConditionReached() {
    return (this->performedEvaluations >= this->maxEvaluations);
}
 
template <typename IP, typename IS, typename OP, typename OS>
void EIG<IP, IS, OP, OS>::createInitialPopulation() {
    this->population.reserve(this->populationSize);
    this->population = instProb->createSolutions(this->populationSize);
    evaluatePopulation(this->population);
    // Computes the diversity of each individual
    this->population =
        noveltySearch->run(this->population, this->instProb.get());
    // Computes the weighted sum of both fit + div
    weightedFitness->computeFitness(this->population);
    this->updateEvolution(this->population);
    initProgress();
}
 
template <typename IP, typename IS, typename OP, typename OS>
void EIG<IP, IS, OP, OS>::evaluatePopulation(vector<IS> &individuals) {
    instProb->beforeEvaluation(individuals);
    for (IS &individual : individuals) {
        // Creates the optimisation problem for the EAs
        shared_ptr<OP> optProblem = instProb->genOptProblem(individual);
 
        vector<float> avgBestFitEAs;  // Avg. Best fitness from each alg.
        avgBestFitEAs.reserve(algPortfolio.size());
        vector<vector<float>> bestSolsEAs;  // Best #reps solutions/algorithm
 
        for (unique_ptr<Alg> &config : algPortfolio) {
            vector<float> bestF(repetitions, 0.0);  // Resets the bestF
            // Run the problem rep times
            for (int rep = 0; rep < repetitions; rep++) {
                config->setProblem(optProblem);
                config->run();
                // Get the results and compute the best founds
                Front<OS> front = config->getResults();
                OS bestSolution = bestFitness.getBestSolution(front);
                bestF[rep] = bestSolution.getFitness();
            }
            // Saves avg. of the best found in #reps
            float averageBestFitness = averageFitness.computeValue(bestF);
            avgBestFitEAs.push_back(averageBestFitness);
            // Saves all best #reps solutions for analysis
            bestSolsEAs.push_back(bestF);
        }
 
        // Saves the fitness founds to future analysis
        individual.setConfigFitness(bestSolsEAs);
        individual.setAvgConfigFitness(avgBestFitEAs);
        // Set the biased fitness depending on the type of instance to generate
        // (easy or hard)
        individual.setBiasedFitness(
            this->instanceFitness->compute(avgBestFitEAs));
    }
    // Problem dependent changes that must be executed after evaluate the
    // instances
    instProb->afterEvaluation(individuals);
}
 
template <typename IP, typename IS, typename OP, typename OS>
[[maybe_unused]] void EIG<IP, IS, OP, OS>::evaluateIndividual(IS &individual) {
    // Creates the optimisation problem for the EAs
    shared_ptr<OP> optProblem = instProb->genOptProblem(individual);
    vector<float> allFitness;
    allFitness.reserve(algPortfolio.size());
    for (unique_ptr<Alg> &config : algPortfolio) {
        Front<OS> solutions(repetitions);
        for (int rep = 0; rep < repetitions; rep++) {
            config->setProblem(optProblem);
            config->run();
            Front<OS> front = config->getResults();
            OS bestSolution = bestFitness.getBestSolution(front);
            solutions.addSolution(bestSolution);
        }
        // Set the fitness as the avg. of the best found in #repetitions times
        float averageBestFitness = averageFitness.computeValue(solutions);
        allFitness.push_back(averageBestFitness);
    }
    individual.setBiasedFitness(instanceFitness->compute(allFitness));
}
 
template <typename IP, typename IS, typename OP, typename OS>
void EIG<IP, IS, OP, OS>::reproduction(IS &solution1, IS &solution2) {
    // Cruzamos los individuos con cierta probabilidad
    if (PseudoRandom::randDouble() < this->crossoverRate) {
        this->crossover->run(solution1, solution2);
    }
    this->mutation->run(solution1, this->mutationRate, this->instProb.get());
}
 
template <typename IP, typename IS, typename OP, typename OS>
void EIG<IP, IS, OP, OS>::replacement(vector<IS> &individuals) {
    if (individuals.size() != this->population.size()) {
        std::string where = " replacement at EIG";
        throw(Mismatch(where));
    }
    const float probIncl = this->populationSize / 100.0;
    for (int i = 0; i < this->populationSize; i++) {
        if (this->population[i].getDiversity() >=
                this->noveltySearch->getThreshold() ||
            ((PseudoRandom::randDouble() > probIncl) &&
             (this->population[i].getBiasedFitness() > 0))) {
            // Always check feasibility
            this->noveltySearch->insertIntoArchive(this->population[i]);
        }
    }
    // Novelty Search procedures to include individuals in the solution set
    this->noveltySearch->cmpFinals(this->population);
    // Performs the replacement operator
    this->population =
        this->repOperator->replace(this->population, individuals);
}
 
template <typename IP, typename IS, typename OP, typename OS>
void EIG<IP, IS, OP, OS>::setPortfolio(vector<unique_ptr<Alg>> &configs) {
    algPortfolio.clear();
    algPortfolio.reserve(configs.size());
    for (unsigned int i = 0; i < configs.size(); i++) {
        algPortfolio.push_back(move(configs[i]));
    }
}
 
template <typename IP, typename IS, typename OP, typename OS>
void EIG<IP, IS, OP, OS>::setInstanceProblem(unique_ptr<IP> problem) {
    this->instProb = move(problem);
}
 
template <typename IP, typename IS, typename OP, typename OS>
vector<AbstractEA<OS> *> EIG<IP, IS, OP, OS>::getPortfolio() const {
    vector<Alg *> configurations;
    configurations.reserve(algPortfolio.size());
    for (const unique_ptr<Alg> &config : algPortfolio) {
        configurations.push_back(config.get());
    }
    return configurations;
}
 
template <typename IP, typename IS, typename OP, typename OS>
json EIG<IP, IS, OP, OS>::to_json() const {
    json data;
    Evolution copy = this->evolution;
    AvgEvolution avgCopy = this->avgEvolution;
    data["name"] = this->getName();
    data["max_generations"] = this->getMaxEvaluations();
    data["repetitions"] = this->repetitions;
    data["pop_size"] = this->populationSize;
    data["mutation"] = this->mutation->getName();
    data["crossover"] = this->crossover->getName();
    data["replacement"] = this->repOperator->getName();
    data["mutation_rate"] = this->mutationRate;
    data["crossover_rate"] = this->crossoverRate;
    data["elapsed_time"] = this->elapsedTime;
    data["evolution"] = copy.results();
    data["avg_evolution"] = avgCopy.results();
    data["novelty_search"] = this->noveltySearch->to_json();
    auto [fRatio, nRatio] = this->weightedFitness->getFAndNRatios();
    data["weighted_function"]["fitness_ratio"] = fRatio;
    data["weighted_function"]["novelty_ratio"] = nRatio;
    int i = 0;
    bool target = true;
    for (const unique_ptr<Alg> &config : this->algPortfolio) {
        data["portfolio"][i] = config->to_json();
        data["portfolio"][i]["isTarget"] = target;
        i++;
        target = false;
    }
 
    return data;
}
 
#endif