The Sword of GodNew York City, New York 2013-10-22
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.
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.
In many ways, the mutation function is the most critical part of an effective evolution-based algorithm. My mutation function consisted of six rules:
- Every generation, randomly choose an operon (row, column or block).
- Swap two values within the selected operon based on a fixed mutation rate.
- Every “epoch” (250 generations), nuclear fallout increases the mutation rate to 100%.
- Every three “epochs”, gamma rays from space scramble an operon in half the population.
- Every six “epoch”s, most of the population has a percentage of their genes scrambled by a virus.
- Every “eon” (10 epochs), a meteor impact kills virtually all life and evolution begins anew.
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.