Cumulative culture in open-ended problem spaces

This notebook provides a simple demonstration of the agent-based model (ABM) used in Winters (2019). To perform your own runs, hit the remix button in the top right corner of the page.

Introduction

The overarching goal of this ABM was to capture two distinct causal processes in cultural evolution: cultural adaptation (where cultural traits are refined towards a functional objective) and cultural exaptation (the repurposing of cultural traits towards a new functional goal). In particular, I was interested in how these two processes were related to cumulative culture, and aimed to address the absence of rich, high-dimensional problem spaces in cultural evolutionary models.

Cultural evolutionary dynamics are modelled here as search processes over the space of both solutions and problems. Solutions exist as the physical manifestations of culture and input problems are the specific functional challenges. If a search process is biased to find solutions that better approximate a given input problem, then we can think of this optimization process as cultural adaptation. Alternatively, if the search process seeks out novel input problems for a specific solution, then this process of repurposing solutions is a form of cultural exaptation.

In this model, agents make two major decisions. The first concerns what type of solution an agent adopts. The second decision focuses on whether or not an agent will try to solve a novel problem. To capture these processes, solutions and problems are represented as binary strings of N-length. Modelling solutions and problems in this way affords (potentially) unbounded searches over solution and problem spaces. Agents attempt to solve problems by moving around in a procedurally generated problem space. Movement between problems is represented in terms of distance: an agent can only consider neighbouring input problems that are a single edit distance away (see Fig.1).

Solutions are derived from two sources: those which are socially transmitted within a population and those which are asocially generated via mechanisms of innovation. Importantly, both social and asocial mechanisms act on solutions indirectly, through modifications to an underlying graph. Asocial mechanisms are restricted to single changes per time step and social transmission is biased towards parsimonious reconstructions.

Two general parameters, corresponding to the extent to which solutions undergo optimization ( $\lambda$ ) and the rate with which agents explore the problem space ( $\Theta$ ), are manipulated. At each time step, an agent generates a pool of possible solutions from asocial and social sources. On the basis of the optimization strength ( $\lambda$ ), as well as the current input problem, one of these solutions is then adopted and assigned to an agent's memory as their stored solution. The exploration threshold ( $\Theta$ ) interacts with the current fit between a solution and an input problem to determine whether or not an agent moves to a new problem. If the solution is well-fitted to the problem, then an agent will remain with the current input problem. Otherwise, if the solution provides a poor fit, an agent will relocate and attempt to solve a new problem.

Following 10 time steps, all agents in a population die and their currently stored solution is inherited by newly created offspring agents (i.e., a 1:1 replacement rate). Crucially, these inherited solutions also undergo transmission (from parent-to-child), which means they are also subject to a bias for parsimony/simplicity during reconstruction.

ABM

Generally, I tend to view agent-based models (ABMs) as hypothesis-generating tools, and serve as a means for (computationally) operationalizing theoretical research. My personal preference is to use ABMs in two situations: as a means of enriching experiments and to systematically think about theoretical problems. The model here is definitely of the latter variety (with one eye on developing an experimental framework to see if the findings generalise beyond abstract models).

Preliminaries

The first step to clone the repository that contains the model, install a fast implementation for calculating the Levenshtein distance (via the editdistance library), followed by an installation of the Seaborn library (for plotting the data):

pip install editdistance

pip install seaborn

Once the packages are installed, the next step is to set the directory path for the ABM:

import sys

sys.path.insert(0, '/cumulative/model/')

Parameters

There are several parameters in this model. The two main ones are optimization and exploration. Respectively, these control the strength of optimization, which refers to how often an agent chooses the most optimal solution given a pool of solutions and an input problem, and an exploration threshold, which determines the point at which an agent will consider a new input problem (based on the normalized Levenshtein distance between an input problem and an agent's currently stored solution).

• n: number of agents in a population.

• generations: number of generations for a given run.

• trans_param: proportion with which agents receive a transmitted solution from another agent in the population. Takes any value in the range $[0.0,1.0]$ where $0.0$ corresponds to no within-group transmission and $1.0$ means agents always transmit solutions to one another.

• optimization: proportion with which choices are biased or unbiased. Takes any value in the range $[0.0,1.0]$ where $0.0$ corresponds to unbiased adoption of a solution and $1.0$ means agents are always biased to choose the most optimized solution (for a given input problem).

• exploration: the threshold at which agents consider moving to a novel problem in the problem space. Takes any value in the range $[0.0,1.0]$ where $0.0$ means agents will move to a novel problem if the normalized Levenshtein distance (of a solution and input problem) is greater than $0.0$. Conversely, if the normalized Levenshtein distance is $1.0$, then agents will remain stationary at their current input problem.

• directory: where you store the output of a run (if out=True). Importantly, for Nextjournal, you must store it in the results folder, e.g., 'results/nameofoutput.csv'.

• run: value for specific run of a model.

• out: If out=True then the model performs a run which outputs data to the specified directory. If out=False then the model simply prints the output.

• pspace: Determines the probability an agent will move to a problem of the same length, a longer one, or a shorter one. Default values are P(Same) = $0.5$, P(Longer) = $0.3$, and P(Shorter) = $0.2$.

You can also try other configurations for the trans_param and the pspace. For instance, changing the proportion of transmission events is expected to reduce the overall solution complexity, as agents have less opportunities to disseminate solutions across a population. Similarly, manipulating pspace can make it harder or easier for agents to move through the problem space, which in turn will impact the types of cultures that emerge.

Setting up the runs

The multiprocessing package allows us to perform multiple runs simultaneously (well, sort of). Below is a relatively simple example of how to use the multiprocessing package with this model. However, in the actual paper, I used it to systematically explore the parameter space and to iterate through multiple runs. Keep in mind that for a single run, this comes with the caveat of longish run times (in this case, approximately 500 seconds).

#import multiprocessing package

import multiprocessing

#pull all functions from ABM.py script

from ABM import *

#set output directory for results

direct1 = "/results/res1.csv"

direct2 = "/results/res2.csv"

direct3 = "/results/res3.csv"

#create function for the multiprocessing runs

"""

Parameters

----------

n,generations,trans_param,optimization,exploration,directory,run,out,pspace

"""

def main():

  p1 = multiprocessing.Process(target=simulation, args=(100,100,1.0,0.6,0.2,direct1,0,True,[0.5,0.3,0.2]))

  p2 = multiprocessing.Process(target=simulation, args=(100,100,1.0,1.0,0.6,direct2,1,True,[0.5,0.3,0.2]))

  p3 = multiprocessing.Process(target=simulation, args=(100,100,1.0,0.6,0.6,direct3,2,True,[0.5,0.3,0.2]))

  p1.start()

  p2.start()

  p3.start()

  p1.join()

  p2.join()

  p3.join()

main()

out=True returns three tables with the outputs of each run. These are read in at section 3.1 as the data used for the graphs in the subsequent sections.

Results

The following results consider three interesting outcomes in the parameter space:$$$$

• λ=1.0; Θ = 0.6 [strong optimization and low exploration]

• λ=0.6; Θ = 0.6 [moderate optimization and low exploration]

• λ=0.6; Θ = 0.2 [moderate optimization and high exploration]

We will look at these specific parameters for just one set of results from the paper, namely: the level of optimization and the average solution complexity. However, there were several other relevant findings, such as the role of within group social transmission (which will require reading the paper for a deeper understanding).

The goal here is to just provide you with a flavour of what is possible in this model.

Reading in and plotting data

First, we import Pandas (for data manipulation), followed by matplotlib and Seaborn for plotting:

import pandas as pd

import seaborn as sns; sns.set()

import matplotlib.pyplot as plt

Once these libraries are ready, we can read in the data from the three csv files:

cc1 = pd.read_csv(
res1.csv
,sep=";",header=None)

cc2 = pd.read_csv(
res1.csv
,sep=";",header=None)

cc3 = pd.read_csv(
res1.csv
,sep=";",header=None)

The next step is to construct a merged dataframe (df). This begins with us establishing the column names, then assigning them to the names of each df, and finally concatenating these dfs to form cc:

#column names

colnames = ["sim_run","generation","ts","population","optimization","exploration","solution_pool","problem_pool","solution_length","problem_length","solution_entropy","problem_entropy","LD","LD_norm","trans_freq","inn_freq","del_freq","rec_freq","solution_complexity"]

#rename columns of dfs

cc1.columns = colnames

cc2.columns = colnames

cc3.columns = colnames

#merge into single df

cc = pd.concat([cc1, cc2, cc3])

The very last thing is for us to set a custom set of colours for the plots we are going to produce in the following section. These hex colours correspond to the specific parameter values for optimization and exploration:

colours = ["#00AFBB", "#E7B800", "#FC4E07"]

customPalette = sns.color_palette(colours)

Optimization

The first graph shows us the three parameter configurations for optimization. The level of optimization was operationalised as the (normalized) Levenshtein distance between a solution and a problem:

where $LD_{s,p} (i,j)$ is the distance between the ith element of solution $S$ and the jth element of problem $p$. As such, the Levenshtein distance tells us the minimum number of single-element edits (insertions, deletions or substitutions) required to transform a solution into a problem. Fewer transformations between a solution and a problem acts as a proxy for higher levels of optimization. Solution-problem mappings needing more transformations are less optimized than those with lower values.

Here, values closer to 0.0 are maximally optimized, and values approaching 1.0 are suboptimal:

fig, ax = plt.subplots()

#create lineplot where data is categorised by parameters

sns.lineplot(x="generation", y="LD_norm", data=cc, hue = "sim_run", palette=customPalette, ci=None, legend=False)

#setting legend

fig.legend(title='parameters', loc=7,labels=["λ=0.6,Θ=0.2","λ=1.0,Θ=0.6","λ=0.6,Θ=0.6"])

#set title for plot and labels for axes

ax.set_title('Optimization',weight="bold",size=20)

ax.set_xlabel('Generation',weight="bold",size=15)

ax.set_ylabel('Level of Optimization',weight="bold",size=15)

ax.tick_params(labelsize=12)

#display figure

fig

Complexity

The second graph shows us the three parameter configurations for the solution complexity. Solution complexity is the product of string entropy and solution length:

where $S_i$ is a binary value found within a solution, $P(S_i)$ is the probability of value $i$ given a solution string $S$, and $\ell(S)$ is the length of the solution. $H_{L}(S)$ is therefore the average amount of information within a specific solution string of N-length.

In this sense, $H_{L}(S)$ acts as a proxy for solution complexity: lower values correspond to less complex solutions than ones with a higher $H_{L}(S)$:

fig, ax = plt.subplots()

#create lineplot where data is categorised by parameters

sns.lineplot(x="generation", y="solution_complexity", data=cc, hue = "sim_run", palette=customPalette, ci=None, legend=False)

#setting legend

fig.legend(title='parameters', loc=7,labels=["λ=0.6,Θ=0.2","λ=1.0,Θ=0.6","λ=0.6,Θ=0.6"])

#set title for plot and labels for axes

ax.set_title('Complexity',weight="bold",size=20)

ax.set_xlabel('Generation',weight="bold",size=15)

ax.set_ylabel('Solution Complexity',weight="bold",size=15)

ax.tick_params(labelsize=12)

#display figure

fig

Summary

What these two graphs tell us is that cultures can end up in very different states depending on the tradeoff between the rate of exploration (across the problem space) and the strength of optimization (in choosing solutions):

• If optimization is too strong (relative to exploration), populations end up in an optimization trap: the dynamics of change quickly converge on a collection of highly optimized, homogeneous solutions of low overall complexity (λ=1.0; Θ = 0.6);

• Decreasing the strength of optimization allows populations to escape these optimization traps. However, when the rate of exploration is too slow, growth in complexity stagnates and populations end up with poorly optimized solutions (λ=0.6; Θ = 0.6);

• Open-ended growth in complexity only occurs when the process of optimization is strong enough to keep apace with the exploration of increasingly difficult input problems, but not so strong as to end up in an optimization trap (λ=0.6; Θ = 0.2).

Conclusion

There you have it! A (relatively) simple introduction to the model reported in Winters (2019).

Comments are welcome and I'm happy to update the document on points of clarity. I also think there's plenty of scope for improvements to this model. I'm actively working on stress-testing some of the assumptions as well as adding extensions.

On a final note, remember: All models are wrong! (But hopefully this one is useful.)

References

Winters, J. (2019). Escaping optimization traps: the role of cultural adaptation and cultural exaptation in facilitating open-ended cumulative dynamics. Palgrave Communications. 5:149. doi:10.1057/s41599-019-0361-3.