Organism Placement the Population

This document describes the interaction between organisms and the population.

The Death of an Organism

When an organism is killed off, its location in the population (that is, its population cell) needs to be emptied, the scheduler needs to be notified, and various statistics need to be update to reflect the recently deceased. All of this is handled with the method below. In a default avida setup, this method will only be called when a cell needs to be cleared out for a new occupant, but you've already seen this method used when you implemented the kill-related events in a previous homework. We'll see it also called from code displayed in the next section of this document.

  void cPopulation::KillOrganism(cPopulationCell & in_cell)
  {
    // do we actually have something to kill?
    if (in_cell.IsOccupied() == false) {
      return;
    }

    // Statistics...
    cOrganism * organism = in_cell.GetOrganism();
    stats.RecordDeath(in_cell.GetID(), organism->GetGenotype()->GetID(),
                      organism->GetPhenotype().GetAge());
    num_organisms--;

    if (organism->GetPhenotype().IsParasite() == true) {
      organism->GetGenotype()->AddParasite();
    }
    organism->GetGenotype()->RemoveOrganism();

    // And clear it!
    in_cell.RemoveOrganism();
    delete organism;
  
    // adjust the scheduler
    schedule->Adjust( in_cell.GetID(), cMerit(0) );
  }

This method takes as an argument the cell that needs to be emptied. It starts off by making sure that the cell in question actually has an organism in it to be killed. If not, it stops right there. If so, it records some statistics about that organism's life, and updates its counter of living organisms to reflect that there is one fewer. If the organism is a parasite, it also lets the genotype know this. The genotype object keeps track of the number of organisms of that genotype that have exhibited parasitic behavior since some organisms may only moonlight as parasites, but be perfectly normal at other times. Note that this currently only works for old-style parasites that are separate organisms. The new style parasites that exist within other organisms and cannot be so easily detected, but I will likely add new code here in the future to monitor the "infection rates" of genotypes.

Once the statistics are finished, the cell itself is cleared with the cPopulationCell::RemoveOrganism() method (in which the pointer to the organism it once contained is set to NULL), and the old organism is deleted. Finally, the scheduler (which is the object that doles out CPU cycles to the individual organisms) is updated to reflect that this cell is now empty.

Activating an Organism in a Specific Cell

If an organism is going to be placed into a specific cell of the population, the method ActivateOrganism can be called on the population, telling it the location in memory of the organism to be placed and the cell to place it in. This method will call the KillOrganism() method to make sure the cell is unoccupied. In turn, this method is called from the Inject() method as well as ActivateOffspring(), described below. Here is the ActivateOrganism method:

  void cPopulation::ActivateOrganism(cOrganism * in_organism,
                                     cPopulationCell & target_cell)
  {
    assert(in_organism != NULL);
  
    // If the organism does not have a genotype, give it one!
    if (in_organism->GetGenotype() == NULL) {
      cGenotype * new_genotype = genebank->AddGenotype(in_organism->GetGenome());
      in_organism->SetGenotype(new_genotype);
    }
    cGenotype * in_genotype = in_organism->GetGenotype();
  
    // Save the old genotype from this cell...
    cGenotype * old_genotype = (target_cell.IsOccupied()) ?
      target_cell.GetOrganism()->GetGenotype() : NULL;
  
    // Update the contents of the target cell.
    KillOrganism(target_cell);
    target_cell.InsertOrganism(*in_organism);
  
    // Update the genebank...
    in_genotype->AddOrganism();
  
    if (old_genotype != NULL) genebank->AdjustGenotype(*old_genotype);
    genebank->AdjustGenotype(*in_genotype);
  
    // Initialize the time-slice for this new organism.
    schedule->Adjust(target_cell.GetID(),in_organism->GetPhenotype().GetMerit());
  
    // Special handling for certain birth methods.
    if (cConfig::GetBirthMethod() == POSITION_CHILD_FULL_SOUP_ELDEST) {
      reaper_queue.Push(&target_cell);
    }
  
    num_organisms++;
  
    // Statistics...
    stats.RecordBirth(target_cell.GetID(), in_genotype->GetID(),
                      in_organism->GetPhenotype().ParentTrue());
  }

After asserting that we are indeed injecting a legal organism, the first thing we do is check to see if that organism has already been assigned its genotype. If an organism was born from a parent in the population, it will have been assigned a genotype by the time this method is called. If it does not have a genotype, however, the genebank object will be called to look up any genotypes that match this genome. The genebank will either return an exact match, or else create a new genotype, add it to the genebank, and return its pointer. In either case, we now have a genotype for this organism.

Before we erase the organism currently in this cell, we want to keep track of what genotype it was part of for use in updating the genebank later. We then kill the organism in the cell (as described above) and insert the new one. The cPopulationCell::InsertOrganism() method will setup the organism based on the environmental conditions of this cell (mutation rate, tasks rewarded, etc), and store the organism for future use.

We then adjust the genotype to let it know a new organism of its type has been created, and tell the genebank that it should also adjust the genotypes to reflect their new abundances (one genotype has grown by one, the other has shrunk, so the genotype ordering may change). Other maintenance we need to do at this point includes adjusting the scheduler to let it know the merit of this new organism, and the "reaper_queue" if we keep track of the birth order of organisms so that we can always kill off the oldest in the population.

Finally, we adjust some more statistics by incrementing the number of organisms in the population and let the statistics object know that a new organism was born, with all of its information. Remember, if this cell was already occupied, KillOrganism() would have decremented it, so this will properly reflect the number of organisms alive in the population at any moment.

Placing an Offspring in the Population

When an organism gives birth, we must collect some relevent statistics, which can best be accomplished in the population object. Then we must place the offspring into its own cell in the population. This is all done with the following method:

  void cPopulation::ActivateOffspring(cOrganism * child_organism,
  				    cOrganism & parent_organism)
  {
    assert(child_organism != NULL);
    assert(&parent_organism != NULL);
    assert(child_organism != &parent_organism);
  
    // First, setup the genotype of the offspring.
    cGenotype * parent_genotype = parent_organism.GetGenotype();
    cGenotype * child_genotype = parent_genotype;
  
    // If the parent genotype is not correct for the child, adjust it.
    if (parent_organism.GetPhenotype().CopyTrue() == false) {
      child_genotype =
        genebank->AddGenotype(child_organism->GetGenome(), parent_genotype);
    }
  
    // And set the genotype now that we know it.
    child_organism->SetGenotype(child_genotype);
    parent_genotype->SetBreedStats(*child_genotype);
  
  
    // Determine the placement of the offspring...
    const int parent_id = parent_organism.PopInterface().GetCellID();
  
    cPopulationCell & parent_cell = cell_array[ parent_id ];
    cPopulationCell & target_cell = PositionChild( parent_cell );
  
    // Update the parent's and child's phenotype.
    cPhenotype & parent_phenotype = parent_organism.GetPhenotype();
    const int child_length = child_organism->GetGenome().GetSize();
    parent_phenotype.DivideReset(parent_organism.GetGenome().GetSize());
    child_organism->GetPhenotype().SetupOffspring(parent_phenotype,child_length);
  
    // If we're not about to kill the parent, do some extra work on it.
    if (parent_cell.GetID() != target_cell.GetID()) {
      schedule->Adjust(parent_cell.GetID(), parent_phenotype.GetMerit());
  
      // In a local run, face the child towards the parent.
      if (cConfig::GetBirthMethod() < NUM_LOCAL_POSITION_CHILD) {
        target_cell.Rotate(parent_cell);
      }
    }
  
    // Do any statistics on the parent that just gave birth...
    parent_genotype->AddGestationTime( parent_phenotype.GetGestationTime() );
    parent_genotype->AddFitness(       parent_phenotype.GetFitness()       );
    parent_genotype->AddMerit(         parent_phenotype.GetMerit()         );
    parent_genotype->AddCopiedSize(    parent_phenotype.GetCopiedSize()    );
    parent_genotype->AddExecutedSize(  parent_phenotype.GetExecutedSize()  );
  
    // Place the offspring...
    ActivateOrganism(child_organism, target_cell);
  }

This method takes as arguments the parent and child organisms that we're working with. It is called by the divide command via the population interface. The first thing it does is assert that both the parent and child are valid organisms, and that their not the same as each other (since we don't allow strange time-travel paradoxes in Avida).

The default genotype of the child is the same as its parent. If, however, there were any mutations, the "copy true" flag will be false causing the genebank to be called to determine its real genotype. The child will then have its genotype assigned, and the parent will have its breed statistics updated to help keep track of phylogenetic tree information.

The next section of code is in charge of finding where in the population this organism should be placed. The cell of the parent is looked up, and then the PositionChild() method is called to determine the child's cell. Since there are so many possible placement options that can be set in the genesis file, PositionChild() is actually reasonably complicated and I will devote a section to it below.

A couple of values are setup as easy-to-use variables, and then the DivideReset() method is run on the parent's phenotype to update everything that has to be done on a divide, and SetupOffpsring() is run on the child's phenotype to initialize it, using information from the parent.

If the parent is not about to be killed off (due to being replaced by the child), we actually want to do a bit more work -- we need to adjust it in the schedule in case its merit has changed over this gestation cycle, and (if we are on a grid) we want to turn the child so that it is facing its parent.

Finally, we collect a bunch of statistics for the parent's genotype object, and we run ActivateOffspring using the cell we have chosen in order the place the child into the population.

Injecting an Organism into the Population

Injecting a genome into the population that does not have a parent (such as with the inject event) is somewhat easier to deal with:

  void cPopulation::InjectGenome(int cell_id, const cGenome & genome)
  {
    assert(cell_id >= 0 && cell_id < cell_array.GetSize());
  
    cOrganism * new_organism = new cOrganism(genome, default_interface,
                                             environment);
  
    // Setup the genotype...
    cGenotype * new_genotype = genebank->AddGenotype(genome);
    new_organism->SetGenotype(new_genotype);
  
    // Setup the phenotype...
    cPhenotype & phenotype = new_organism->GetPhenotype();
    phenotype.SetupInject(genome.GetSize());
    phenotype.SetMerit( cMerit(new_genotype->GetTestMerit()) );
  
    // Activate the organism in the population...
    ActivateOrganism(new_organism, cell_array[cell_id]);
  }

Basically, all that this method needs to do is build the organism with the proper genome, determine its genotype, setup its phenotype, put it into a test CPU to get its initial merit, and activate it! You should be able to go line-by-line through the code to see how exactly this happens for yourself.

Choosing the Position of a Child

The final method we're going to examine here is the one that determines which population cell a child organism should be placed into

  cPopulationCell & cPopulation::PositionChild(cPopulationCell & parent_cell)
  {
    // If we are not using a local (grid) placement method, this is easy.
    if (cConfig::GetBirthMethod() >= NUM_LOCAL_POSITION_CHILD) {
      switch (cConfig::GetBirthMethod()) {
      case POSITION_CHILD_FULL_SOUP_RANDOM:
        return GetCell(g_random.GetUInt(cell_array.GetSize()));
      case POSITION_CHILD_FULL_SOUP_ELDEST:
        return *( reaper_queue.PopRear() );
      }
    }
  
    // Construct a list of equally viable locations to place the child...
    tList<cPopulationCell> found_list;
  
    // First, check if there is an empty organism to work with (always preferred)
    tList<cPopulationCell> & conn_list = parent_cell.ConnectionList();
    FindEmptyCell(conn_list, found_list);
  
    // If we have not found an empty organism, we must use the specified function
    // to determine how to choose among the filled organisms.
    if (found_list.GetSize() == 0) {
      switch(cConfig::GetBirthMethod()) {
      case POSITION_CHILD_AGE:
        PositionAge(parent_cell, found_list);
        break;
      case POSITION_CHILD_MERIT:
        PositionMerit(parent_cell, found_list);
        break;
      case POSITION_CHILD_RANDOM:
        found_list.Append(conn_list);
        found_list.Push(&parent_cell);
        break;
      case POSITION_CHILD_EMPTY:
        // Nothing is in list if no empty cells are found...
        // Just return the parent.
        return parent_cell;
        break;
      }
    }
  
    // Choose the organism randomly from those in the list, and return it.
    int choice = g_random.GetUInt(found_list.GetSize());
    return *( found_list.GetPos(choice) );
  }

This method first checks if we are using a global or local replacement method. Global methods are easier to deal with, so it handles those first. The two currently implemented are "Replace Random in the Full Population" (mass action) and "Replace Oldest in the Full Population" (a la Tierra). The first of these simply requests a random number and returns the corresponding cell. The second uses the reaper_queue, discussed earlier, to return the ID of the last cell in it.

The remainder of this method deals with the local replacement methods We create a list of population cells (initially empty) called found_list as a place to contain the cells that are good candidates for replacement. We then create a second list called conn_list that contains all of the cells that the current cell is connected to. We run this connection list through a method called FindEmptyCell() to see if out job is going to be easy -- if there are any empty cells, they should always be our first choice for replacement.

Alas, if there are no empty cells, we need to do some more work, and we have a collection of options that can be chosen by the user in the genesis file. We select the appropriate case, and use it to fill out the found_list. Currently, in all cases except "Find Empty" there will always be at least one cell placed in the found_list.

If the found list ends with more than one candidate cell in it, the one used is selected randomly from the options available.


Project hosted by:
SourceForge.net