selection.hpp

Go to the documentation of this file.

 
#pragma once
 
#include <algorithm>
#include <numeric>
#include <random>
#include <stdexcept>
#include <vector>
 
#include "pulsatrix/assert.hpp"
#include "pulsatrix/individual.hpp"
 
namespace pulsatrix {
 
template <typename Genotype, typename FitnessT, typename RNG>
size_t TournamentSelect(const std::vector<Individual<Genotype, FitnessT>>& population,
                         size_t tournament_size, RNG& rng) {
    if (population.empty()) {
        throw std::invalid_argument("TournamentSelect: population must not be empty");
    }
    if (tournament_size == 0 || tournament_size > population.size()) {
        throw std::invalid_argument(
            "TournamentSelect: tournament_size must be in [1, population.size()]");
    }
 
    std::vector<size_t> indices(population.size());
    std::iota(indices.begin(), indices.end(), size_t{0});
    std::shuffle(indices.begin(), indices.end(), rng);
 
    size_t best_index = indices[0];
    for (size_t i = 1; i < tournament_size; ++i) {
        if (population[indices[i]].fitness > population[best_index].fitness) {
            best_index = indices[i];
        }
    }
    return best_index;
}
 
template <typename Genotype, typename FitnessT>
size_t RouletteSelectByDraw(const std::vector<Individual<Genotype, FitnessT>>& population,
                            FitnessT draw) {
    if (population.empty()) {
        throw std::invalid_argument("RouletteSelectByDraw: population must not be empty");
    }
    FitnessT total{};
    for (const auto& ind : population) {
        if (ind.fitness < FitnessT{0}) {
            throw std::invalid_argument("RouletteSelectByDraw: fitness must be non-negative");
        }
        total += ind.fitness;
    }
    if (!(total > FitnessT{0})) {
        throw std::invalid_argument("RouletteSelectByDraw: total fitness must be positive");
    }
    if (draw < FitnessT{0} || draw >= total) {
        throw std::invalid_argument("RouletteSelectByDraw: draw must be in [0, total_fitness)");
    }
 
    FitnessT cumulative{};
    for (size_t i = 0; i < population.size(); ++i) {
        cumulative += population[i].fitness;
        if (draw < cumulative) {
            return i;
        }
    }
    // Unreachable: draw < total is enforced above, and cumulative reaches total by the last
    // element -- an internal invariant, not a condition a caller can trigger.
    PULSATRIX_ASSERT(false);
    return population.size() - 1;
}
 
template <typename Genotype, typename FitnessT, typename RNG>
size_t RouletteSelect(const std::vector<Individual<Genotype, FitnessT>>& population, RNG& rng) {
    FitnessT total{};
    for (const auto& ind : population) {
        total += ind.fitness;
    }
    std::uniform_real_distribution<FitnessT> dist(FitnessT{0}, total);
    return RouletteSelectByDraw(population, dist(rng));
}
 
template <typename Genotype, typename FitnessT>
size_t RankSelectByDraw(const std::vector<Individual<Genotype, FitnessT>>& population,
                        double draw) {
    if (population.empty()) {
        throw std::invalid_argument("RankSelectByDraw: population must not be empty");
    }
 
    std::vector<size_t> order(population.size());
    std::iota(order.begin(), order.end(), size_t{0});
    std::sort(order.begin(), order.end(), [&population](size_t a, size_t b) {
        return population[a].fitness < population[b].fitness;
    });
 
    const double n = static_cast<double>(population.size());
    const double total_weight = n * (n + 1.0) / 2.0;  // 1 + 2 + ... + n
    if (draw < 0.0 || draw >= total_weight) {
        throw std::invalid_argument("RankSelectByDraw: draw must be in [0, total_weight)");
    }
 
    double cumulative = 0.0;
    for (size_t i = 0; i < order.size(); ++i) {
        cumulative += static_cast<double>(i + 1);  // rank of order[i] is i+1 (1-indexed)
        if (draw < cumulative) {
            return order[i];
        }
    }
    // Unreachable: draw < total_weight is enforced above -- an internal invariant.
    PULSATRIX_ASSERT(false);
    return order.back();
}
 
template <typename Genotype, typename FitnessT, typename RNG>
size_t RankSelect(const std::vector<Individual<Genotype, FitnessT>>& population, RNG& rng) {
    const double n = static_cast<double>(population.size());
    const double total_weight = n * (n + 1.0) / 2.0;
    std::uniform_real_distribution<double> dist(0.0, total_weight);
    return RankSelectByDraw(population, dist(rng));
}
 
}  // namespace pulsatrix