Empirical
World_select.h
Go to the documentation of this file.
1 
10 #ifndef EMP_EVO_WORLD_SELECT_H
11 #define EMP_EVO_WORLD_SELECT_H
12 
13 #include <map>
14 #include <functional>
15 
16 #include "../base/array.h"
17 #include "../base/assert.h"
18 #include "../base/vector.h"
19 #include "../base/macros.h"
20 #include "../tools/IndexMap.h"
21 #include "../tools/Random.h"
22 #include "../tools/vector_utils.h"
23 
24 namespace emp {
25 
26  template<typename ORG> class World;
27 
33  template<typename ORG>
34  void EliteSelect(World<ORG> & world, size_t e_count=1, size_t copy_count=1) {
35  emp_assert(e_count > 0 && e_count <= world.GetNumOrgs(), e_count);
36  emp_assert(copy_count > 0);
37 
38  // Load the population into a multimap, sorted by fitness.
39  std::multimap<double, size_t> fit_map;
40  for (size_t id = 0; id < world.GetSize(); id++) {
41  if (world.IsOccupied(id)) {
42  const double cur_fit = world.CalcFitnessID(id);
43  fit_map.insert( std::make_pair(cur_fit, id) );
44  }
45  }
46 
47  // Grab the top fitnesses and move them into the next generation.
48  auto m = fit_map.rbegin();
49  for (size_t i = 0; i < e_count; i++) {
50  const size_t repro_id = m->second;
51  world.DoBirth( world.GetGenomeAt(repro_id), repro_id, copy_count);
52  ++m;
53  }
54  }
55 
60  template<typename ORG>
61  void RandomSelect(World<ORG> & world, size_t r_count=1, size_t copy_count=1) {
62  emp_assert(r_count > 0, r_count);
63  emp_assert(copy_count > 0);
64 
65  Random & random = world.GetRandom();
66 
67  // Pick r_count organisms;
68  for (size_t i = 0; i < r_count; i++) {
69  // Choose an organism at random
70  size_t id = random.GetUInt(world.GetSize());
71  while (world.IsOccupied(id) == false) id = random.GetUInt(world.GetSize());
72 
73  // Make copy_count copies.
74  world.DoBirth( world.GetGenomeAt(id), id, copy_count);
75  }
76  }
77 
85  template<typename ORG>
86  void TournamentSelect(World<ORG> & world, size_t t_size, size_t tourny_count=1) {
87  emp_assert(t_size > 0, "Cannot have a tournament with zero organisms.", t_size, world.GetNumOrgs());
88  emp_assert(t_size <= world.GetNumOrgs(), "Tournament too big for world.", t_size, world.GetNumOrgs());
89  emp_assert(tourny_count > 0);
90 
91  emp::vector<size_t> entries;
92  for (size_t T = 0; T < tourny_count; T++) {
93  entries.resize(0);
94  // Choose organisms for this tournament (with replacement!)
95  for (size_t i=0; i < t_size; i++) entries.push_back( world.GetRandomOrgID() );
96 
97  double best_fit = world.CalcFitnessID(entries[0]);
98  size_t best_id = entries[0];
99 
100  // Search for a higher fit org in the tournament.
101  for (size_t i = 1; i < t_size; i++) {
102  const double cur_fit = world.CalcFitnessID(entries[i]);
103  if (cur_fit > best_fit) {
104  best_fit = cur_fit;
105  best_id = entries[i];
106  }
107  }
108 
109  // Place the highest fitness into the next generation!
110  world.DoBirth( world.GetGenomeAt(best_id), best_id, 1 );
111  }
112  }
113 
114 
119  template<typename ORG>
120  void RouletteSelect(World<ORG> & world, size_t count=1) {
121  emp_assert(count > 0);
122 
123  Random & random = world.GetRandom();
124 
125  // Load fitnesses from current population.
126  IndexMap fitness_index(world.GetSize());
127  for (size_t id = 0; id < world.GetSize(); id++) {
128  fitness_index.Adjust(id, world.CalcFitnessID(id));
129  }
130 
131  for (size_t n = 0; n < count; n++) {
132  const double fit_pos = random.GetDouble(fitness_index.GetWeight());
133  const size_t parent_id = fitness_index.Index(fit_pos);
134  const size_t offspring_id = world.DoBirth( world.GetGenomeAt(parent_id), parent_id ).GetIndex();
135  if (world.IsSynchronous() == false) {
136  fitness_index.Adjust(offspring_id, world.CalcFitnessID(offspring_id));
137  }
138  }
139  }
140 
141 
142  EMP_CREATE_OPTIONAL_METHOD(TriggerOnLexicaseSelect, TriggerOnLexicaseSelect);
143 
150  template<typename ORG>
152  const emp::vector< std::function<double(ORG &)> > & fit_funs,
153  size_t repro_count=1,
154  size_t max_funs=0)
155  {
156  emp_assert(world.GetSize() > 0);
157  emp_assert(fit_funs.size() > 0);
158 
159  // @CAO: Can probably optimize a bit!
160 
161  std::map<typename ORG::genome_t, int> genotype_counts;
162  emp::vector<emp::vector<size_t>> genotype_lists;
163 
164  // Find all orgs with same genotype - we can dramatically reduce
165  // fitness evaluations this way.
166  for (size_t org_id = 0; org_id < world.GetSize(); org_id++) {
167  if (world.IsOccupied(org_id)) {
168  const typename decltype(World<ORG>())::genome_t gen = world.GetGenomeAt(org_id);
169  if (emp::Has(genotype_counts, gen)) {
170  genotype_lists[genotype_counts[gen]].push_back(org_id);
171  } else {
172  genotype_counts[gen] = genotype_lists.size();
173  genotype_lists.emplace_back(emp::vector<size_t>{org_id});
174  }
175  }
176  }
177 
178  emp::vector<size_t> all_gens(genotype_lists.size()), cur_gens, next_gens;
179 
180  for (size_t i = 0; i < genotype_lists.size(); i++) {
181  all_gens[i] = i;
182  }
183 
184  if (!max_funs) max_funs = fit_funs.size();
185  // std::cout << "in lexicase" << std::endl;
186  // Collect all fitness info. (@CAO: Technically only do this is cache is turned on?)
187  emp::vector< emp::vector<double> > fitnesses(fit_funs.size());
188  for (size_t fit_id = 0; fit_id < fit_funs.size(); ++fit_id) {
189  fitnesses[fit_id].resize(genotype_counts.size());
190  // std::cout << fit_id << std::endl;
191  int id = 0;
192  for (auto & gen : genotype_lists) {
193  fitnesses[fit_id][id] = fit_funs[fit_id](world.GetOrg(gen[0]));
194  id++;
195  }
196  }
197 
198  // std::cout << to_string(fitnesses) << std::endl;
199  // std::cout << "fitness calculated" << std::endl;
200  // Go through a new ordering of fitness functions for each selections.
201  // std::cout << "randdomized" << std::endl;
202  for (size_t repro = 0; repro < repro_count; ++repro) {
203  // std::cout << "repro: " << repro << std::endl;
204  // Determine the current ordering of the functions.
205  emp::vector<size_t> order;
206 
207  if (max_funs == fit_funs.size()) {
208  order = GetPermutation(world.GetRandom(), fit_funs.size());
209  } else {
210  order.resize(max_funs); // We want to limit the total numebr of tests done.
211  for (auto & x : order) x = world.GetRandom().GetUInt(fit_funs.size());
212  }
213  // @CAO: We could have selected the order more efficiently!
214  // std::cout << "reoreder" << std::endl;
215  // Step through the functions in the proper order.
216  cur_gens = all_gens; // Start with all of the organisms.
217  int depth = -1;
218  for (size_t fit_id : order) {
219  // std::cout << "fit_id: " << fit_id << std::endl;
220  depth++;
221 
222  // std::cout << "about to index" << std::endl;
223  // std::cout << to_string(fitnesses[fit_id]) << std::endl;
224  // std::cout << cur_orgs[0] << std::endl;
225  double max_fit = fitnesses[fit_id][cur_gens[0]];
226  next_gens.push_back(cur_gens[0]);
227  // std::cout << "Starting max: " << max_fit << to_string(cur_gens) << std::endl;
228  for (size_t gen_id : cur_gens) {
229 
230  const double cur_fit = fitnesses[fit_id][gen_id];
231  // std::cout << "gen_id: " << gen_id << "Fit: " << cur_fit << std::endl;
232  if (cur_fit > max_fit) {
233  max_fit = cur_fit; // This is a the NEW maximum fitness for this function
234  next_gens.resize(0); // Clear out orgs with former maximum fitness
235  next_gens.push_back(gen_id); // Add this org as only one with new max fitness
236  // std::cout << "New max: " << max_fit << " " << cur_gens.size() << std::endl;
237  }
238  else if (cur_fit == max_fit) {
239  next_gens.push_back(gen_id); // Same as cur max fitness -- save this org too.
240  // std::cout << "Adding: " << gen_id << std::endl;
241  }
242  }
243  // Make next_orgs into new cur_orgs; make cur_orgs allocated space for next_orgs.
244  std::swap(cur_gens, next_gens);
245  next_gens.resize(0);
246 
247  if (cur_gens.size() == 1) break; // Stop if we're down to just one organism.
248  }
249 
250  // Place a random survivor (all equal) into the next generation!
251  emp_assert(cur_gens.size() > 0, cur_gens.size(), fit_funs.size(), all_gens.size());
252  size_t options = 0;
253  for (size_t gen : cur_gens) {
254  options += genotype_lists[gen].size();
255  }
256  size_t winner = world.GetRandom().GetUInt(options);
257  int repro_id = -1;
258 
259  for (size_t gen : cur_gens) {
260  if (winner < genotype_lists[gen].size()) {
261  repro_id = (int) genotype_lists[gen][winner];
262  break;
263  }
264  winner -= genotype_lists[gen].size();
265  }
266  emp_assert(repro_id != -1, repro_id, winner, options);
267 
268  // std::cout << depth << "abotu to calc used" <<std::endl;
269  emp::vector<size_t> used = Slice(order, 0, depth+1);
270  // If the world has a OnLexicaseSelect method, call it
271  // std::cout << depth << " " << to_string(used) << std::endl;
272  TriggerOnLexicaseSelect(world, used, repro_id);
273  world.DoBirth( world.GetGenomeAt(repro_id), repro_id );
274  }
275  // std::cout << "Done with lex" << std::endl;
276  }
277 
278  // EcoSelect works like Tournament Selection, but also uses a vector of supplimentary fitness
279  // functions. The best individuals on each supplemental function divide up a resource pool.
280  // NOTE: You must turn off the FitnessCache for this function to work properly.
281  template<typename ORG>
282  void EcoSelect(World<ORG> & world, const emp::vector<std::function<double(ORG &)> > & extra_funs,
283  const emp::vector<double> & pool_sizes, size_t t_size, size_t tourny_count=1)
284  {
285  emp_assert(world.GetFitFun(), "Must define a base fitness function");
286  emp_assert(world.GetSize() > 0);
287  emp_assert(t_size > 0 && t_size <= world.GetSize(), t_size, world.GetSize());
288  // emp_assert(world.IsCacheOn() == false, "Ecologies mean constantly changing fitness!");
289 
290  if (world.IsCacheOn()) {
291  world.ClearCache();
292  }
293 
294  // Setup info to track fitnesses.
295  emp::vector<double> base_fitness(world.GetSize());
296  emp::vector< emp::vector<double> > extra_fitnesses(extra_funs.size());
297  emp::vector<double> max_extra_fit(extra_funs.size(), 0.0);
298  emp::vector<size_t> max_count(extra_funs.size(), 0);
299  for (size_t i=0; i < extra_funs.size(); i++) {
300  extra_fitnesses[i].resize(world.GetSize());
301  }
302 
303  // Collect all fitness info.
304  for (size_t org_id = 0; org_id < world.GetSize(); org_id++) {
305  base_fitness[org_id] = world.CalcFitnessID(org_id);
306  for (size_t ex_id = 0; ex_id < extra_funs.size(); ex_id++) {
307  double cur_fit = extra_funs[ex_id](world.GetOrg(org_id));
308  extra_fitnesses[ex_id][org_id] = cur_fit;
309  if (cur_fit > max_extra_fit[ex_id]) {
310  max_extra_fit[ex_id] = cur_fit;
311  max_count[ex_id] = 1;
312  }
313  else if (cur_fit == max_extra_fit[ex_id]) {
314  max_count[ex_id]++;
315  }
316  }
317  }
318 
319  // Readjust base fitness to reflect extra resources.
320  for (size_t ex_id = 0; ex_id < extra_funs.size(); ex_id++) {
321  if (max_count[ex_id] == 0) continue; // No one gets this reward...
322 
323  // The current bonus is divided up among the organisms that earned it...
324  const double cur_bonus = pool_sizes[ex_id] / max_count[ex_id];
325  // std::cout << "Bonus " << ex_id << " = " << cur_bonus
326  // << " max_extra_fit = " << max_extra_fit[ex_id]
327  // << " max_count = " << max_count[ex_id]
328  // << std::endl;
329 
330  for (size_t org_id = 0; org_id < world.GetSize(); org_id++) {
331  // If this organism is the best at the current resource, git it the bonus!
332  if (extra_fitnesses[ex_id][org_id] == max_extra_fit[ex_id]) {
333  base_fitness[org_id] += cur_bonus;
334  }
335  }
336  }
337 
338 
339  emp::vector<size_t> entries;
340  for (size_t T = 0; T < tourny_count; T++) {
341  entries.resize(0);
342  for (size_t i=0; i<t_size; i++) entries.push_back( world.GetRandomOrgID() ); // Allows replacement!
343 
344  double best_fit = base_fitness[entries[0]];
345  size_t best_id = entries[0];
346 
347  // Search for a higher fit org in the tournament.
348  for (size_t i = 1; i < t_size; i++) {
349  const double cur_fit = base_fitness[entries[i]];
350  if (cur_fit > best_fit) {
351  best_fit = cur_fit;
352  best_id = entries[i];
353  }
354  }
355 
356  // Place the highest fitness into the next generation!
357  world.DoBirth( world.GetGenomeAt(best_id), best_id, 1 );
358  }
359  }
360 
362  template<typename ORG>
363  void EcoSelect(World<ORG> & world, const emp::vector<typename World<ORG>::fun_calc_fitness_t > & extra_funs,
364  double pool_sizes, size_t t_size, size_t tourny_count=1)
365  {
366  emp::vector<double> pools(extra_funs.size(), pool_sizes);
367  EcoSelect(world, extra_funs, pools, t_size, tourny_count);
368  }
369 
370 }
371 
372 #endif
void Adjust(size_t id, const double new_weight)
Definition: IndexMap.h:176
Random & GetRandom()
Return a reference to the random number generator currently being used by world.
Definition: World.h:770
WorldPosition DoBirth(const genome_t &mem, size_t parent_pos, size_t copy_count=1)
Place one or more copies of an offspring into population; return position of last placed...
Definition: World.h:1244
A versatile and non-patterned pseudo-random-number generator (Mersenne Twister).
Definition: ce_random.h:52
bool IsSynchronous() const
Definition: World.h:284
void push_back(PB_Ts &&...args)
Definition: vector.h:189
Setup a World with a population of organisms that can evolve or deal with ecological effects...
Definition: World.h:94
size_t size() const
Definition: vector.h:151
void emplace_back(ARGS &&...args)
Definition: vector.h:219
constexpr uint32_t GetUInt(const uint32_t max)
Definition: ce_random.h:191
void TournamentSelect(World< ORG > &world, size_t t_size, size_t tourny_count=1)
Definition: World_select.h:86
void RouletteSelect(World< ORG > &world, size_t count=1)
Definition: World_select.h:120
void LexicaseSelect(World< ORG > &world, const emp::vector< std::function< double(ORG &)> > &fit_funs, size_t repro_count=1, size_t max_funs=0)
Definition: World_select.h:151
size_t GetSize() const
How many organisms can fit in the world?
Definition: World.h:245
bool IsCacheOn() const
Are we currently caching fitness values?
Definition: World.h:280
constexpr double GetDouble()
Definition: ce_random.h:166
emp::vector< T > Slice(emp::vector< T > vec, int start, int stop)
Definition: vector_utils.h:101
const genome_t & GetGenomeAt(size_t id)
Retrive the genome corresponding to the organism at the specified position.
Definition: World.h:342
bool Has(const MAP_T &in_map, const KEY_T &key)
Take any map type, and run find to determine if a key is present.
Definition: map_utils.h:21
void resize(size_t new_size)
Definition: vector.h:161
void ClearCache(size_t id)
Clear the cache value at the specified position.
Definition: World.h:195
std::function< double(ORG &)> fun_calc_fitness_t
Function type for calculating fitness.
Definition: World.h:108
void RandomSelect(World< ORG > &world, size_t r_count=1, size_t copy_count=1)
Definition: World_select.h:61
void EliteSelect(World< ORG > &world, size_t e_count=1, size_t copy_count=1)
Definition: World_select.h:34
ORG & GetOrg(size_t id)
Definition: World.h:316
If we are in emscripten, make sure to include the header.
Definition: array.h:37
size_t GetRandomOrgID()
Get the id of a random occupied cell.
Definition: World.h:1274
double CalcFitnessID(size_t id)
Use the configured fitness function on the organism at the specified position.
Definition: World.h:1187
#define emp_assert(...)
Definition: assert.h:199
emp::vector< size_t > GetPermutation(Random &random, size_t size)
Return an emp::vector<int> numbered 0 through size-1 in a random order.
Definition: random_utils.h:40
size_t GetNumOrgs() const
How many organisms are currently in the world?
Definition: World.h:248
Definition: IndexMap.h:23
fun_calc_fitness_t GetFitFun()
Get the fitness function currently in use.
Definition: World.h:400
void EcoSelect(World< ORG > &world, const emp::vector< std::function< double(ORG &)> > &extra_funs, const emp::vector< double > &pool_sizes, size_t t_size, size_t tourny_count=1)
Definition: World_select.h:282
bool IsOccupied(WorldPosition pos) const
Does the specified cell ID have an organism in it?
Definition: World.h:277