Genetic Algorithms

Screenshot of multiple agents in a genetic algorithm generation avoiding moving coronaviruses observed via radar

Inspiration

Our project went through a series of iterations, beginning with a focus on infected “hive mind” populations controlled by a single genetic algorithm (GA) and continuing on to include GAs controlling a variety of agent types in different scenarios, usually COVID-related. Initially, we were motivated by a common interest in (Pythonic) machine learning methodologies and simple, stripped-down susceptible-infected-recovered (SIR) animations, such as those which appear in the Washington Post and the videos of popular mathematics YouTuber 3Blue1Brown. We eventually generalized this latter inspiration and considered a larger class of COVID simulation projects.

What it does

In its final iteration, our project simulates an individual trying to survive in an environment that contains infected beings. The goal is to avoid coming into contact with the infected objects, and we try to accomplish this goal by training a neural network through NeuroEvolution of Augmenting Topologies (NEAT). In each generation of training, the best individuals are chosen and are used to generate offspring to population the next generation. The idea is that over-time the population increases in fitness by doing a better job of avoiding getting infected and the best “genes” are conserved over time.

How I built it

We chose to do this project in Python because it was the language that we were most familiar with. To implement the neural networks and genetic algorithms, we used the neat-python library. For visualization, we used pygame and matplotlib. We liberally employed object-oriented methodologies and made significant use of version control through GitHub, facilitating a workflow wherein all three group members could actively and separately contribute.

Challenges I ran into

We struggled to find a problems which were simultaneously non-trivial—i.e., which actually motivated the use of an advanced problem-solving approach—and solvable that we could solve with our methodology of choice, the genetic algorithm. In particular, our project ideas either involved too much random variance or actors that could drastically influence their environment, both of which prevent models from learning general tactics. We also found the plethora of potential customizations/modification—such as fitness functions and disease transmission probability functions—and hyperparameters associated with our genetic algorithms to be difficult to optimize effectively and simultaneously for a given problem.

Accomplishments that I'm proud of

Our process featured a variety of successes, large and small. From the start, we were able to demonstrate to ourselves the potential of genetic algorithms, initially demonstrated through the effectiveness of a simple Processing script which exhibited a genetic algorithm swiftly learning how to traverse a room. We were able to maximize the utility of the poorly-documented matplotlib.animation library, producing visual simulations featuring moving agents with time-dependent colors. We also found success in hacking together a solution when we required the radars—essentially “eyes” allowing our agents to access distances to the nearest objects in various directions—to operate more robustly than in environments where it had previously been employed by other users. We also were able to maintain organization and cohesion at every stage of the project, remaining on the same page through Discord-facilitated communication—both through voice and text channels—and extensive pseudocode-based collaborative planning sessions, developing and managing multi-contributor workflows through GitHub, and consistently agreeing upon even workload distributions which allowed all members to remain engaged and productive.

What I learned

We each came into the project with different strengths and weaknesses. While some of us honed our skills in matplotlib and its esoteric animation capabilities, others got a chance to practice data manipulation with pythonic tools like list comprehension. As a group, this project allowed us to practice the utilization and implementation of Pythonic object-oriented design practices. We also developed varying degrees of familiarity with the PyGame library. Finally, genetic algorithms in general were pretty new to most of us, and the whole group learned about these methods, their applications, and how to implement them with libraries like neat-python.

What's next for Genetic Algorithms

Given more time, the next major step would be to get our evaders to actually learn to evade the virus objects. We were left with lots of unanswered questions about how the neat-framework works and how we could improve our use of the neat-python library.

This project is still unfinished, and maybe its results are unexplained. For example, even after generations of training, there are still large segments of the population which still exhibit behavior similar to how the population behaved in the first generation. These individuals randomly disperse and become infected very quickly.

Overall, the most room for improvement is in defining a better network structure and a better fitness reward system. We could fiddle with the neural network topology, adding hidden layers, or changing activation functions. In the future, we could also maybe look into other techniques such as Q learning.