Animal Foraging and the Evolution of Goal-Directed Cognition

Materials by Randal S. Olson

All code in this notebook is usable under the terms of the BSD license.

This entire notebook is licensed under a Creative Commons Attribution 3.0 Unported License.

Creative Commons License


In this 2006 paper, Thomas Hills explored the evolution of an optimal foraging behavior called area-restricted search (ARS):

ARS is characterized by a concentration of searching effort around areas where rewards in the form of specific resources have been found in the past. When resources are encountered less frequently, behavior changes such that the search becomes less sensitive, but covers more space. In an ecological context, animals using ARS will turn more frequently following an encounter with food, restricting their search around the area where food was last encountered. As the period of time since the last food encounter increases, animals turn less frequently and begin to move away, following a more linear path. Fig. 1 allows you to experience ARS in a visual search task (read the directions please).

You can read more about ARS and Hills' work in the paper. (Free to download: Here, we're interested in the model that Hills used to explore the evolutionary feasibility of ARS in various environments:

To further test the evolutionary robustness of this behavior, I developed a genetic algorithm, using NetLogo, that allows agents to search for food in a two-dimensional space. The goal of the genetic algorithm is twofold: to understand the conditions where ARS is likely to evolve and also to understand a minimal set of mechanistic parameters required for the behavior’s evolution. In this simulation, the agents have three genes that control turning angle per time step when they are “on food,” turning angle per time step when they are “off food,” and a memory depth that describes the number of time steps it takes for the animals to progress from the on-food to the off-food turning angle once they have left food (the inverse of memory depth is the slope of change in turning angle per time step). The initial population is generated with a random 24-bit genome per individual (8 bits per gene). The genes assign the foraging rules each generation. Animals then compete in a two-dimensional foraging arena. After an appropriate life span, individuals mate and recombine—disproportionately according to how well they foraged—and a new generation is created, subject to a small mutation rate.

Following good practice, Hills also included a link to an implementation of the model:

Now, let's say we're animal behavior researchers who specialize in ARS and we want to explore Hills' findings a little more in his model. Unfortunately, NetLogo doesn't work on our computer, so we have the re-implement the model ourselves. Below is one such implementation of Hills' model in Python using IPythonBlocks.


1) Read through the Python code and write comments taking note of where Hills' description matches the code. Does this implementation do anything differently than described in Hills' text?

2) Run the model for 100 generations and observe how the forager behavior evolves over that time period. Does ARS evolve? How quickly does it evolve?

3) Run the model a few more times for 100 generations each and observe how the forager behavior evolves over that time period. Does ARS evolve? Does it evolve faster or slower than the other runs?

4) Change the number of food patches, num_patches, and size of the food patches, patch_size, and run the model again. Does ARS evolve with those settings? Repeat this procedure several times. Can you find settings that cause ARS to no longer evolve?

5) It's important to run evolutionary models several times to make sure that the phenomenon you observe isn't simply due to chance. Fortunately, it's easy to repeat evolutionary models several times in replicate in a short amount of time. Modify the Python code to run the model with default settings in replicate 30 times, save the data from each run separately, and plot the mean of the fitness and traits for those 30 replicates over all 100 generations with 95% confidence intervals.

6) Repeat #5 except with settings that do not select for the evolution of ARS behavior. Plot the mean and 95% confidence interval of the fitness and traits of these runs on the same plot as #5. What traits are different between the two experiments? Why?

7) What do these findings entail in biological terms?

8) What are the limitations of this model?

9) What are some possible extensions of this model? What other questions could be explored with this model? We will use these ideas for the next part of the homework.

Bonus) Find a quantitative measure that captures how much the forager follows an area-restricted search. Plot it over evolutionary time for an experiment that evolves ARS.

In [12]:
# load all of the libraries we'll need for the model
from ipythonblocks import BlockGrid
from IPython.display import clear_output
import random
In [13]:
# environment variables
world_width = 150
world_height = 150
num_patches = 20
patch_size = 5

# genetic algorithm variables
population_size = 30
mutation_rate = 0.01
generations = 100
evaluation_ticks = 1000
number_evaluations_per_generation = 1
visualization_display_frequency = 1
In [14]:
# load all of the functions we'll need for the model

def setup_world():
    Sets up a grid world with randomly-placed food patches
    and returns the grid.
    # setup world visualization
    grid = BlockGrid(world_width, world_height, block_size=4)
    grid.lines_on = False
    # choose random (x, y) positions to place food patches
    patch_centers = []
    for i in range(num_patches):
        patch_x = random.randrange(0, world_width)
        patch_y = random.randrange(0, world_height)
        patch_centers.append((patch_x, patch_y))
    # mark the centers of the food patches
    for (x, y) in patch_centers:
        grid[x, y].green = 255
    # fill in the food patches
    for iteration in range(patch_size):
        blocks_to_fill = []
        for x in range(world_width):
            for y in range(world_height):
                # if any of the non-diagonal blocks next to this block have food
                if (grid[(x - 1) % world_width, y].green == 255 or
                    grid[x, (y - 1) % world_height].green == 255 or
                    grid[(x + 1) % world_width, y].green == 255 or
                    grid[x, (y + 1) % world_height].green == 255):
                    blocks_to_fill.append([x, y])
        for (x, y) in blocks_to_fill:
            grid[x, y].green = 255
    return grid

def convert_bit_list_to_int(bit_list):
    Takes a list of bits (binary representation of a number) and converts it into the corresponding integer.
    return int(str(bit_list).strip("[]").replace(", ", ""), 2)

def fitness_evaluation(world, genotype, display=False):
    Evaluates the given genome of a forager and returns its fitness.
    # map the genotype into its corresponding phenotype
    # first 8 bits encode the angle the forager turns when it doesn't find any food on the current grid
    forager_turn_no_food = convert_bit_list_to_int(genotype[0:8])
    # next 8 bits encode the angle the forager turns when it finds food on the current grid
    forager_turn_food = convert_bit_list_to_int(genotype[8:16])
    # last 8 bits encode how many ticks the forager stays in the "food" state when it doesn't find any food
    # on the current grid before moving into the "no food" state
    forager_memory = convert_bit_list_to_int(genotype[16:24])
    # forager starting location and facing
    forager_x = random.randrange(0, world_width)
    forager_y = random.randrange(0, world_height)
    forager_facing = random.randrange(0, 360)
    ticks_since_last_food = forager_memory
    for tick in range(evaluation_ticks):
        ticks_since_last_food += 1
        # if food is present at current location OR memory limit has not been exceeded yet
        # == 255 and == 0 means there is food and the predator hasn't eaten it
        # == 255 and == 255 means there is food and the predator has eaten it
        # == 0 and == 0 means there is no food and the predator hasn't visited that block
        # == 0 and == 255 means there is no food and the predator has visited that block
        if (world[forager_x, forager_y].green == 255 and world[forager_x, forager_y].red == 0):
            ticks_since_last_food = 0
        # mark the location where the predator has visited
        world[forager_x, forager_y].red = 255
        # forager is in "food" mode
        if ticks_since_last_food < forager_memory:
            forager_facing = random.triangular(forager_facing - 2.0 * forager_turn_food, forager_facing + 2.0 * forager_turn_food)
        # forager is in "no food" mode
            forager_facing = random.triangular(forager_facing - 2.0 * forager_turn_no_food, forager_facing + 2.0 * forager_turn_no_food)

        forager_facing %= 360
        # move the forager in the direction it's facing (diagonal moves allowed)
        direction_to_move = int(((forager_facing + 22.5) % 360.0) / 45.0)
        offset_dict = { 0:(1, 0),    # to the right
                        1:(1, 1),    # up and to the right
                        2:(0, 1),    # up
                        3:(-1, 1),   # up and to the left
                        4:(-1, 0),   # to the left
                        5:(-1, -1),  # down and to the left
                        6:(0, -1),   # down
                        7:(1, -1) }  # down and to the right
        xoff, yoff = offset_dict[direction_to_move]
        forager_x += xoff
        forager_y += yoff
        # keep the forager within the bounds of the world
        forager_x %= world_width
        forager_y %= world_height
    # display the forager's activity if the display flag is active
    if display:
        print("forager_turn_no_food: " + str(forager_turn_no_food))
        print("forager_turn_food: " + str(forager_turn_food))
        print("forager_memory: " + str(forager_memory))
    # evaluate the fitness by counting how many food blocks the forager picked up
    fitness = 0
    for block in world:
        if == 255 and == 255:
            fitness += 1
        # also unmark the predator's movement to "clean up" for the next evaluation = 0
    # disallow <= 0 fitness
    if fitness <= 0:
        fitness = 1
    return fitness
In [15]:
# run the genetic algorithm to evolve the prey foragers

# best forager data
best_fitness_over_time = []
best_forager_turn_no_food_over_time = []
best_forager_turn_food_over_time = []
best_forager_memory_over_time = []

# population averages
population_fitness_over_time = []
population_turn_no_food_over_time = []
population_turn_food_over_time = []
population_memory_over_time = []

# seed the GA populaton with blank genotypes
population = []
for forager in range(population_size):
    genotype = []
    for bit in range(24):
for generation in range(1, generations + 1):
    # evaluate the fitnesses of the population of foragers
    world = setup_world()
    population_fitnesses = []
    highest_fitness = 0
    fittest_genotype = None
    for genotype in population:
        fitness = 0
        for evaluation_number in range(number_evaluations_per_generation):
            fitness += fitness_evaluation(world, genotype) / float(number_evaluations_per_generation)
        if fitness > highest_fitness:
            highest_fitness = fitness
            fittest_genotype = list(genotype)
    # keep track of best forager over time
    # keep track of population averages over time
    population_fitness = 0.0
    population_turn_no_food = 0.0
    population_turn_food = 0.0
    population_memory = 0.0
    for index, genotype in enumerate(population):
        population_fitness += population_fitnesses[index]
        population_turn_no_food += convert_bit_list_to_int(genotype[0:8])
        population_turn_food += convert_bit_list_to_int(genotype[8:16])
        population_memory += convert_bit_list_to_int(genotype[16:24])
    population_fitness_over_time.append(population_fitness / float(population_size))
    population_turn_no_food_over_time.append(population_turn_no_food / float(population_size))
    population_turn_food_over_time.append(population_turn_food / float(population_size))
    population_memory_over_time.append(population_memory / float(population_size))
    # display the performance of the fittest forager at a regular interval
    if generation % visualization_display_frequency == 0:
        fitness_evaluation(world, fittest_genotype, display=True)
        print("generation " + str(generation) + " fittest genotype")
    # apply fitness proportionate selection to determine the genotypes that reproduce into the next generation
    fitness_sum = sum(population_fitnesses)
    new_population = []
    for new_offspring_counter in range(population_size):
        roll = random.random() * fitness_sum
        sum_so_far = 0
        for index, genotype in enumerate(population):
            sum_so_far += population_fitnesses[index]
            # if the genotype is chosen to reproduce
            if sum_so_far >= roll:
                parent = list(genotype)
                offspring = []
                # copy the offspring's genotype from the parent's genotype
                for bit in parent:
                    # mutations sometimes occur
                    if random.random() <= mutation_rate:
                        offspring.append(random.randrange(0, 2))
    population = list(new_population)