evolution_selection.tcc

Go to the documentation of this file.

 
#if !defined(ULTRA_EVOLUTION_SELECTION_H)
#  error "Don't include this file directly, include the specific .h instead"
#endif
 
#if !defined(ULTRA_EVOLUTION_SELECTION_TCC)
#define      ULTRA_EVOLUTION_SELECTION_TCC

template<Evaluator E>
strategy<E>::strategy(E &eva, const parameters &params)
  : eva_(eva), params_(params)
{
}

template<Evaluator E>
template<SizedRandomAccessPopulation P>
std::vector<typename tournament<E>::scored_t>
tournament<E>::operator()(const P &pop) const
{
  Expects(!this->params_.needs_init());
 
  const auto rounds(this->params_.evolution.tournament_size);
  assert(0 < rounds);
  assert(rounds <= parameters::evolution_parameters::max_tournament_size);
 
  std::vector<std::pair<typename P::coord, evaluator_fitness_t<E>>> ret;
  ret.reserve(rounds);
 
  // This is the inner loop of an insertion sort algorithm. It's simple, fast
  // (if `rounds` is small) and doesn't perform too much comparisons.
  // DO NOT USE `std::sort` it's way slower.
  const auto mate_zone(this->params_.evolution.mate_zone);
  const auto target(random::coord(pop));
 
  for (std::size_t i(0); i < rounds; ++i)
  {
    const auto new_coord(random::coord(pop, target, mate_zone));
    const auto new_fitness(this->eva_(pop[new_coord]));
 
    ret.emplace_back(new_coord, new_fitness);
 
    auto k(i);
    while (k && ret[k - 1].second < ret[k].second)
    {
      std::swap(ret[k - 1], ret[k]);
      --k;
    }
  }
 
  assert(std::ranges::is_sorted(ret,
                                [](const auto &i1, const auto &i2)
                                {
                                  return i1.second > i2.second;
                                }));
 
  std::vector<scored_t> rs;
  rs.reserve(ret.size());
  std::ranges::transform(ret, std::back_inserter(rs),
                         [&pop](const auto &c)
                         {
                           return scored_t{pop[c.first], c.second};
                         });
 
  Ensures(rs.size() == rounds);
  return rs;
}

template<Evaluator E>
template<PopulationWithMutex P>
std::array<typename alps<E>::scored_t, 2>
alps<E>::operator()(alps_layer_pair<const P> pops) const
{
  Expects(!this->params_.needs_init());
 
  struct candidate
  {
    evaluator_individual_t<E> ind;
 
    // Extends the basic fitness with the age and takes advantage of the
    // lexicographic comparison capabilities of `std::pair`.
    std::pair<bool, evaluator_fitness_t<E>> rank;
  };
 
  const auto sample([this](const auto &layer)
  {
    auto ind(random::individual(layer));
    const auto rank(std::pair(ind.age() <= layer.max_age(),
                              this->eva_(ind)));
 
    return candidate{std::move(ind), rank};
  });
 
  auto best(sample(pops.primary()));
  auto second(sample(pops.primary()));
 
  if (best.rank < second.rank)
    std::swap(best, second);
 
  const auto ts(this->params_.evolution.tournament_size);
  assert(0<ts && ts<=parameters::evolution_parameters::max_tournament_size);
 
  const auto p_main_layer(this->params_.alps.p_main_layer);
  assert(in_0_1(p_main_layer));
 
  for (auto rounds(ts - 1); rounds; --rounds)
  {
    auto incoming(sample(pops.random(p_main_layer)));
 
    if (second.rank < incoming.rank)
    {
      second = std::move(incoming);
 
      if (best.rank < second.rank)
        std::swap(best, second);
    }
 
    assert(best.rank >= second.rank);
    assert(best.rank.first || !second.rank.first);
  }
 
  return  {scored_t{std::move(best.ind), best.rank.second},
           scored_t{std::move(second.ind), second.rank.second}};
}

template<SizedRandomAccessPopulation P>
de::selected_refs<typename P::value_type>
de::operator()(P &pop) const
{
  const auto target(random::coord(pop));
  const auto base(random::coord(pop));
  const auto a(random::coord(pop));
  const auto b(random::coord(pop));
 
  // We don't force constraints on indices.
 
  return {pop[target], pop[base], pop[a], pop[b]};
}
 
#endif  // include guard