1 of 14

SimEvo: A Simple Python Library for Simulations of Natural Selection

Yu-Jie, Zheng

1

2024 Spring NSD - Final Project - SimEvo: A Simple Python Library for Simulations of Natural Selection - Yu-Jie, Zheng

/14

2 of 14

Outline

The Story
Problem to Solve
Prospective Users
System Architecture
Algorithm
Evaluation
Appendix

2

2024 Spring NSD - Final Project - SimEvo: A Simple Python Library for Simulations of Natural Selection - Yu-Jie, Zheng

/14

3 of 14

The Story

I have considered creating a ball collision simulation engine for fun, but I have never started.
After some research, I realized that collision simulations are quite common online. To create something unique, I should incorporate more complex features, such as 3D collisions, or consider practical use cases to make it more interesting.
I also saw a video about the simulation of evolution of neural networks in organisms, where the code is open-sourced. The project is built with C++ but allows users to control it only through a configuration file.

3

2024 Spring NSD - Final Project - SimEvo: A Simple Python Library for Simulations of Natural Selection - Yu-Jie, Zheng

/14

4 of 14

The Story

Then, YouTube showed me a video titled "Simulating Natural Selection" by Primer. The simulation engine used in the video is not open sourced.
There is considerable scope for user customization through scripting, such as adjusting the space size, food distribution, mutation methods, and reproduction strategies.
Recalling the initial step of my story, I want to create something related to spatial data. This simulator involves extensive collision detection.

4

2024 Spring NSD - Final Project - SimEvo: A Simple Python Library for Simulations of Natural Selection - Yu-Jie, Zheng

/14

5 of 14

Problem to Solve

The simulation involves complex calculation among organisms and their environments to check whether it should be react or interact with.
Leverages the computational efficiency of C++ for the core simulation engine and offers an intuitive Python interface for ease of use and accessibility.
Better to have intuitive way for python user to customize some critical point of the simulation.

5

2024 Spring NSD - Final Project - SimEvo: A Simple Python Library for Simulations of Natural Selection - Yu-Jie, Zheng

/14

6 of 14

Problem to Solve

By default, each organism has its own genes representing three traits: speed, size, and awareness of itself.
Every trait has its cost, which by default is calculated as by the following formula

The organism will chase and try to eat the food or other organisms smaller than itself.
Each organism can reproduce itself with its own genes, including some variations.

6

examples/chasing.py

examples/food_path.py

2024 Spring NSD - Final Project - SimEvo: A Simple Python Library for Simulations of Natural Selection - Yu-Jie, Zheng

/14

7 of 14

Prospective Users

Educators and Students:

For teaching and learning evolutionary concepts through interactive simulations.

Researchers:

For conducting experiments on evolutionary strategies and hypotheses.

Hobbyists:

For exploring the principles of evolution in a virtual environment.

7

2024 Spring NSD - Final Project - SimEvo: A Simple Python Library for Simulations of Natural Selection - Yu-Jie, Zheng

/14

8 of 14

Algorithm - Quad-Tree

Construction:

Create a Quadtree where the root node represents the entire area. Subdivide the area into four child nodes, further splitting as needed until each contains fewer than a set number of objects.

Object Insertion:

Add new objects to the appropriate node. If a node exceeds capacity, subdivide it to maintain manageability.

Collision Detection:

Traverse the Quadtree, checking for collisions only within the same node. This reduces the number of potential collisions significantly due to spatial locality.

Update and Maintenance:

Update the Quadtree when objects move. If an object changes nodes, remove it from the original node and add it to the new one. Merge nodes if necessary to improve efficiency.

8

2024 Spring NSD - Final Project - SimEvo: A Simple Python Library for Simulations of Natural Selection - Yu-Jie, Zheng

/14

9 of 14

System Architecture

Separating Spatial Indexing from Core Environment Logic
Providing a Common Interface for Spatial Indexing
Enabling Design-Time Dependency Injection through Constructor

9

core logic

algo impl

2024 Spring NSD - Final Project - SimEvo: A Simple Python Library for Simulations of Natural Selection - Yu-Jie, Zheng

/14

From the previous part we see the algo behind the simulation. However, if I start to program as I know quadtree, it very hard to check the correctness of the implementation

Therefore, there is an abstraction layer to abstract the spatial index, from the grap you can see that by doing so, the core logic will not relay on the implementation of algorithm instead it only depend on the Interface.

After this, I can just use the “DefaultSpatialIndex”, which is the brute force approach, to testing out the implementation of core part

And also it is also port to pythton that make users able to choose which type of indexing technique to use, and the “optimized” is the quad tree.

And by doing so I actually can write one test for the interface and testing out two implementations using google test

10 of 14

System Architecture

Dependency Graph

10

Environment

EnvironmentObject

Organism

Food

Genes

ISpatialIndex

SpatialObject

DefaultSpatialIndex

OptimizedSpatialIndex

core does not depends on spatial index implementation

2024 Spring NSD - Final Project - SimEvo: A Simple Python Library for Simulations of Natural Selection - Yu-Jie, Zheng

/14

11 of 14

System Architecture

Expose callback initialization to python for detailed customization

11

Using callback function to customize lifespanof organism

Using callback function to integrate with matplotlab visualizer

2024 Spring NSD - Final Project - SimEvo: A Simple Python Library for Simulations of Natural Selection - Yu-Jie, Zheng

/14

12 of 14

Evaluation

Distance calculation in each iteration is reduce dramatically, and query time actually reduce a lot.
For 100 organism and 50 food in the Environment

DefaultSpatialIndex (Bruteforce) - total: 0.082048 ms

Average handleInteractions duration: 0.070801 ms
Average postIteration duration: 0.011247 ms

OptimizedSpatialIndex (Quadtree) - total: 0.086085 ms

Average handleInteractions duration: 0.032080 ms
Average postIteration duration: 0.054405 ms

There are still some implementations in the post-iteration needs to be work on to make the Environment more friendly to different indexing method. Currently has a lot of remove and update in each iterations.

12

2024 Spring NSD - Final Project - SimEvo: A Simple Python Library for Simulations of Natural Selection - Yu-Jie, Zheng

/14

13 of 14

Appendix

Some DevOps stuff I tried:

Automatically version bumping through Github Workflow and Github Bot.
Add tag of release in each version.
Release to PyPI after build and test.
Using codefactor for code quality scanning.

13

2024 Spring NSD - Final Project - SimEvo: A Simple Python Library for Simulations of Natural Selection - Yu-Jie, Zheng

/14

14 of 14

Appendix

Interesting example scripts you can find in examples/ directories

14

2024 Spring NSD - Final Project - SimEvo: A Simple Python Library for Simulations of Natural Selection - Yu-Jie, Zheng

/14