The Sword of God

Description

Tasked with creating a genetic algorithm to solve Sudoku puzzles, I came up with a solution based on a jealous and vengeful god punishing a disobedient population.

Inspiration

Working on this project caused in me something akin to a religious epiphany. During my early attempts, I found that super fast convergence made spinning out at a local maximum a common occurrence. In other words, the population reached a point at which it thought it was perfect, even though it was not.

After watching my puzzle population repeatedly stop evolving beyond mediocrity, I found myself getting increasingly frustrated—it was as though I had a plan for them and they just couldn’t see it. This brought to mind myths of floods and plagues and ultimately led to a functional algorithm that punishes a non-cooperative population with increasing severity.

Mutation

In many ways, the mutation function is the most critical part of an effective evolution-based algorithm. My mutation function consisted of six rules:

1. Every generation, randomly choose an operon (row, column or block).
2. Swap two values within the selected operon based on a fixed mutation rate.
3. Every “epoch” (250 generations), nuclear fallout increases the mutation rate to 100%.
4. Every three “epochs”, gamma rays from space scramble an operon in half the population.
5. Every six “epoch”s, most of the population has a percentage of their genes scrambled by a virus.
6. Every “eon” (10 epochs), a meteor impact kills virtually all life and evolution begins anew.

Acknowledgments

This project was created for Patrick Hebron’s Evolution as a Creative Tool course at NYU and was built upon a skeleton project created by Patrick.