How Genetic Algorithms work using Hamlet as an Example

Hi!

I’ve officially run out of blog topics, so I’m going to expand upon Aarav’s (hi Aarav) blog about Genetic algorithms (we are on the same software engineering team, so I think this is alright!)

It’s also been awhile since his blog, and we’ve had to rework a lot of how our code works. 

Let’s start from the very beginning!

We have this really great spreadsheet that helps us to read data in. You can see it below:

We pretty much process all of this data into our code, and save it for later. 

After that’s done we need to make a bunch of really bad schedules (the initial generation, think Mendel’s original green and white pea plants), this is where we start with. Basically, we just have to put together 8 lists of room/teacher/class assignments (that makes one schedule, since each list represents a class period, multiplied by 8 makes a full day). Let’s say we have 100 of these to start out. 

Something we’ve improved from last time was the schedules we generate are actually possible schedules! That doesn’t sound super good, but our old code used to stick random teachers with random classes (think of Ms. Hitzeman teaching Software Engineering  – sorry Ms. Hitzeman :)). Now, we start all of our schedules off on the right foot. 

Any time we’re making a new schedule, we have a lot of “Teacher” objects: think various versions of Hamlet. We know each version of Hamlet has a super dramatic “To be or not to be” speech, weird dynamics between Hamlet and Gertrude, along with many other similarities. 

Like each version of Hamlet, where each is different but all have constant ideas/people/scenes, each “Teacher” object has a designated “Class” they teach, as well as a designated “Room” they teach that class in. Since we’d rather not store these values for every teacher for every period manually, we have two lists that hold these values. 

We have a class_list variable, think of it like Hamlet’s revenge checklist. He must talk to Horatio, out Claudius as a killer with the players, kill Polonius, and fence with Laertes. Similarly, each teacher object contains a list like this: [AP Lit, 2, Ap Lit, Lunch, 5, 6, 7, 8]. These hold class data for us. 

Next, we have to make changes to make better schedules. For example, while Ms. Hitzeman could teach 8 classes every single day, that probably isn’t good or healthy for her – so by randomly replacing teachers/classes/rooms between schedules, we can slightly alter how each schedule works (theoretically if we do this enough, combined with the next two steps, we’ll get a good schedule).

Now we have a bunch of mutated schedules, we need to get rid of the bad ones and add new ones! 

Think of making schedules like a AP Lit Hamlet Academic discussion: while we can have 20 people talk for the entire period, what they contribute to the conversation will probably decrease over time. So if we swap out the old people (delete a bad schedule) and sub in a fresh perspective (generating another schedule) then we can keep the very insightful Hamlet discussion going. 

After we do this, we’ve successfully progressed a single generation! If we go back to the AP lit discussion, let’s say that’s one period of discussion. (For the example to work let’s pretend people get carried over from period to period). 

I’m in second period, so let’s say we bring in the 3rd period kids. They’re all new and have great things to add to our conversation! So by progressing to another generation, where we repeat the previous 5-10 steps, we continue talking about how random Hamlet sometimes is and definitely how heroic Horatio is – all while a function is checking to see if we’ve reached a good schedule (think Ms. Hitzeman writing notes until someone finally arrives to the most insightful thing to discuss about Hamlet ever). 

We rinse and repeat for maybe 1000 generations (that would be a lot of AP discussions!), and once we’ve finally reached a good schedule, we save it and output it! 

Some other cool parts about our genetic algorithm: 

This is our super technologically advanced and modernly designed home page!!! Made by the illustrious Jonathan Qunell. Very cool I know. This site is just set up so the teacher who would want to generate schedules simply inputs the values into the spreadsheet I showed above, uploads it through upload data, then can create a schedule using that data, and finally can view any old schedules generated. 

Thanks for reading! I hope this provides some much-needed insight into Hamlet quantified programming.

-Max