GENEIAL  0.2=/
 All Classes Pages
FitnessProportionalSelection.hpp
1 #pragma once
2 
3 #include <geneial/core/operations/selection/FitnessProportionalSelection.h>
4 #include <geneial/utility/Random.h>
5 
6 #include <cassert>
7 
8 geneial_private_namespace(geneial)
9 {
10 geneial_private_namespace(operation)
11 {
12 geneial_private_namespace(selection)
13 {
14 using ::geneial::population::Population;
15 using ::geneial::utility::Random;
16 using ::geneial::population::management::BaseManager;
17 
18 geneial_export_namespace
19 {
20 
21 template<typename FITNESS_TYPE>
22 typename BaseSelectionOperation<FITNESS_TYPE>::selection_result_set FitnessProportionalSelection<FITNESS_TYPE>::doSelect(
23  const Population<FITNESS_TYPE> &population, BaseManager<FITNESS_TYPE> &manager) const
24 {
25 
26  //shorthands for type mess
27  typedef std::multimap<FITNESS_TYPE, typename BaseChromosome<FITNESS_TYPE>::ptr> map_type;
28  typedef typename BaseChromosome<FITNESS_TYPE>::ptr chrom_ptr_type;
29  typedef typename BaseSelectionOperation<FITNESS_TYPE>::selection_result_set result_set;
30 
31  result_set result;
32  result.reserve(this->getSettings().getNumberOfParents()+this->_settings->getNumberSelectBest());
33 
34  //Calculate total sum of fitness
35  const FITNESS_TYPE sum = std::accumulate(population.getFitnessMap().cbegin(), population.getFitnessMap().cend(), 0,
36  [](FITNESS_TYPE total, const typename Population<FITNESS_TYPE>::fitness_map::value_type& mapdata)
37  {
38  total += (mapdata.second)->getFitness().get();
39  return total;
40  });
41 
42  assert(sum > 0);
43 
44  //Create a multimap with fitness-proportional probability as key
45  map_type sorted_multimap;
46  for (const auto& it : population.getFitnessMap())
47  {
48  const FITNESS_TYPE prop_fitness = (it.second)->getFitness().get() / sum;
49  sorted_multimap.insert(std::pair<FITNESS_TYPE, chrom_ptr_type>(prop_fitness, it.second));
50  }
51 
52  unsigned int left_select = this->getSettings().getNumberOfParents();
53  //First, handle elitism, iterate backwards over the sorted multimap and select the best chromosomes.
54 
55  //TODO (bewo) OPTIMIZE: using sth like transform(i, j, back_inserter(v), select2nd<MapType::value_type>()); instead ???
56  unsigned int elitism_to_select = this->_settings->getNumberSelectBest();
57 
58  auto crit = sorted_multimap.rbegin();
59  for (; crit != sorted_multimap.rend() && elitism_to_select > 0; ++crit)
60  {
61  result.emplace_back(crit->second);
62  elitism_to_select--;
63  }
64  //Strip the inserted part from the map
65  sorted_multimap.erase(crit.base(), sorted_multimap.end());
66 
67  assert(result.size() == this->_settings->getNumberSelectBest());
68  left_select -= this->_settings->getNumberSelectBest();
69  assert(left_select <= sorted_multimap.size());
70 
71  //now select the remainder based on proportional probability.
72  while (left_select > 0)
73  {
74  //wrap around if necessary.
75  auto crit = sorted_multimap.rbegin();
76  while (crit != sorted_multimap.rend() && left_select > 0)
77  {
78  chrom_ptr_type chrom = crit->second;
79  double prob = (crit->first);
80  if (Random::decision(prob))
81  {
82  //Use it.
83  result.emplace_back(chrom);
84  left_select--;
85  sorted_multimap.erase((++crit).base()); //erase requires normal iterator,
86  }
87  else
88  {
89  //Skip this chromosome for now.
90  ++crit;
91  }
92  }
93  assert(left_select <= sorted_multimap.size());
94  }
95  return result;
96 }
97 
98 } /* geneial_export_namespace */
99 } /* private namespace selection */
100 } /* private namespace operation */
101 } /* private namespace geneial */
102