As you probably have seen from the title, the mystery I’m going to be talking about is genetic algorithms. So, here is a little background on why I was so enchanted by this case. In my Software Engineering class, I am part of a team (hello Max) that works on building a schedule for the teachers in the CTE department using an algorithm. This algorithm takes the rooms, teachers, and possible classes, along with the teacher preferences to make the best possible schedule. This task was assigned to us by the CTE department, and hopefully it will soon be in use for the rest of the departments. 

But, what is this algorithm? The algorithm in use is called a genetic algorithm. A genetic algorithm as most things in computer science does, takes ideas from the natural world and implements them in the coding world. A genetic algorithm borrows ideas from how a gene mutates and evolves, hence the name of genetics. Genes mutate and change by taking snippets of DNA strings and either, substituting it with other genes, adding it to the end of the gene or another gene, simply removing it, or moving it to a completely different location. Genetic algorithms inherit that idea and use it to serve its own purpose. Genetic algorithms are used to quickly find the best solution or the best solutions from a solution set. While it would be easy to check the best solution from a set that only has 2 solutions, when there are over 4 billion solutions in the set, like the one we have, the computer would take years to find the best solution. In order to efficiently find the best solution, a genetic algorithm takes (or in our case, creates) random solutions and ranks them based on a standard. This is our initial generation. The standard is based on how close it is to a theoretical perfect solution. If we don’t know the perfect solution, we would lay requirements or checkpoints the solution has to meet to be a “good” or perfect solution. This is the normal case, as we might know one perfect solution, but not the rest of the prefect solutions. After the solutions are ranked, we then take the best of those solutions and mutate them. This is kind of how evolution works. You know, survival of the fittest. After all the mutations occur, we call the new set of solutions generation 1. Then, every time we mutate, add, and subtract solutions in our set, we increase our generation. When we get the best or perfect solution, we stop there and use our solution we got. 

This is what we use in our software engineering project. We randomly generate a schedule with rooms, teachers, and classes and we check how good it is using something called the fitness function. The fitness function checks if all the requirements are met, such as a teacher teaching the appropriate class, and if the room can accommodate that class. For example, Mr. Schmit can teach Software Engineering, but he cannot teach Senior Foods. A schedule with Mr. Schmit teaching Software Engineering would be ranked higher than a schedule where Mr. Schmit is teaching Senior Foods. Currently we are working on the other types of mutations, which we are calling the mutator methods. This will attempt to make a schedule better by performing random operations to it. And finally, we have the regeneration function, which creates a new generation after performing all the mutations. Along the way, we will calculate the threshold values at which we would remove a schedule, add a schedule, and when we have found a good enough schedule.

What makes a genetic algorithm so useful is that it finds the best possible solution with a lot of parameters in the fastest way possible because the user of the genetic algorithm can define what the requirements are and when a good schedule is found. Once the algorithm knows that, it can quickly find the best solution. Although in the real world, genetic mutations can take millions of years to mutate, a computer can use this algorithm to find a solution in minutes, and sometimes even seconds. Even though our project may have so many inputs, like when a class needs to be taught, and where a teacher would like to teach, our algorithm can account for all of that and create the best schedule in an instant. 

So, I guess the lesson for this blog is, sometimes the best solution to a problem may be found by just taking a walk through nature, and understanding the mysteries of the natural world. And… That’s one less mystery for me to solve!