MasterMind/src/heuristics/GGA.cpp

#include "heuristics/GGA.h"


int* selector(int i, void* object) {
    Candidate** tab = (Candidate**) object;
    return tab[i]->sol;
}

GGA::GGA(int mu, int lda, int selection, int crossover_method, int version, std::default_random_engine& randomizer) {
    m_mu = mu;
    m_lambda = lda;
    m_selection = selection;
    m_crossover_method = crossover_method;
    m_version = version;

    m_randomizer = randomizer;
    m_is_prepared = false;
    x_tab = nullptr;

    if(m_mu==0 || (selection==COMMA && m_mu>m_lambda)) {
        std::cout << "Bad parameters for GA !" << std::endl;
        exit(EXIT_FAILURE);
    }
}

void GGA::prepare_tab() {
    if(m_is_prepared) return;

    x_tab = new Candidate*[m_mu+m_lambda];
    for(int i=0; i<m_mu+m_lambda; i++) {
        int* x = m_problem->get_random_candidate();
        x_tab[i] = new Candidate(x, 0);
    }

    m_uniform_dist  = std::uniform_int_distribution<int>(0, m_mu-1);
    m_is_prepared = true;
}

Result GGA::run() {
    MasterMind* pb = m_problem;
    prepare_tab();
    clear_record();

    // Initial parents
    for(int i=0; i<m_mu; i++) {
        int* x = pb->get_random_candidate();
        delete[] x_tab[i]->sol;
        x_tab[i]->sol = x;
        x_tab[i]->value = pb->try_candidate(x);
    }
    std::sort(x_tab, x_tab+m_mu, cmp_candidates);

    Candidate* x_best = x_tab[0];
    int nb_calls = m_mu;

    while(! pb->is_optimal(x_best->sol, x_best->value, m_objective)) {
        double progress = pb->get_progress(x_best->sol, x_best->value);
        double sbm_proba = get_sbm_proba(progress);
        std::binomial_distribution<int> mutation = std::binomial_distribution<int>(m_problem->get_max_radius(), sbm_proba);
        std::bernoulli_distribution crossover(get_crossover_proba(progress));

        // Evaluation fitness of the parent population
        std::vector<double> parent_fitness_dist_tab;
        for(int i=0; i<m_mu; i++)
            parent_fitness_dist_tab.push_back(exp(x_tab[i]->value));
        std::discrete_distribution<int> parent_fitness_dist(parent_fitness_dist_tab.begin(), parent_fitness_dist_tab.end());

        // Variation phase
        for(int i=0; i<m_lambda; i++) {
            Candidate* y = x_tab[m_mu+i];
            bool crossover_step = crossover(m_randomizer);
            switch(m_version) {
                case GA_V1:
                    if(crossover_step) {
                        if(m_mu == 1)
                            pb->copy_candidate(x_tab[m_uniform_dist(m_randomizer)]->sol, y->sol);
                        else
                            pb->crossover(y->sol, (void*) x_tab, m_mu, &selector, m_crossover_method);
                    } else {
                        int r = mutation(m_randomizer);
                        if(sbm_proba < 0)
                            r = round(m_problem->get_max_radius() * (-sbm_proba));
                        int parent_index = m_uniform_dist(m_randomizer);
                        pb->copy_candidate(x_tab[parent_index]->sol, y->sol);
                        pb->modify_with_radius(y->sol, r);
                    }
                    y->value = pb->try_candidate(y->sol);
                    break;

                case GA_V2:
                    if(crossover_step) {
                        if(m_mu == 1)
                            pb->copy_candidate(x_tab[m_uniform_dist(m_randomizer)]->sol, y->sol);
                        else {
                            // Choose parents
                            int ind1 = parent_fitness_dist(m_randomizer);
                            int ind2 = ind1;
                            while(ind1 == ind2)
                                ind2 = parent_fitness_dist(m_randomizer);

                            // Proceed crossover
                            int pos1 = (ind1 <= 1) ? ind1 : ((ind2 <= 1) ? 1-ind2 : 0);
                            int pos2 = 1-pos1;
                            swap_candidates(x_tab, pos1, ind1);
                            swap_candidates(x_tab, pos2, ind2);
                            pb->crossover(y->sol, (void*) x_tab, 2, &selector, m_crossover_method);
                            swap_candidates(x_tab, pos1, ind1);
                            swap_candidates(x_tab, pos2, ind2);
                        }
                    } else {
                        int parent_index = parent_fitness_dist(m_randomizer);
                        pb->copy_candidate(x_tab[parent_index]->sol, y->sol);
                    }
                    int r = mutation(m_randomizer);
                    pb->modify_with_radius(y->sol, r);
                    y->value = pb->try_candidate(y->sol);
                    break;
            }
        }

        // Selection phase
        if(m_selection == PLUS) {
            // Selection among parent population and offspring population
            std::sort(x_tab, x_tab+(m_mu+m_lambda), cmp_candidates);
            x_best = x_tab[0];
        } else {
            // Selection among ONLY offspring population
            std::sort(x_tab+(m_mu), x_tab+(m_mu+m_lambda), cmp_candidates);
            for(int i=0; i<m_mu; i++)
                swap_candidates(x_tab, i, m_mu+i);
            x_best = x_tab[0];
        }
        nb_calls += m_lambda;
        record(nb_calls, x_best->value);

        if(m_abortion_limit > 0 && nb_calls >= m_abortion_limit) {
            int* final_sol = pb->get_random_candidate();
            pb->copy_candidate(x_best->sol, final_sol);
            return Result(final_sol, x_best->value, nb_calls, true);
        }
    }

    int* final_sol = pb->get_random_candidate();
    pb->copy_candidate(x_best->sol, final_sol);
    return Result(final_sol, x_best->value, nb_calls);
}

GGA::~GGA() {
    if(m_is_prepared) {
        for(int i=0, s=m_mu+m_lambda; i<s; i++) {
            Candidate* y = x_tab[i];
            delete[] y->sol;
            delete y;
        }
        delete[] x_tab;
    }
}