Creating a Class Schedule

Genetic Algorithms in Elixir — by Sean Moriarity (64 / 101)

👈 Chapter 8 Replacing and Transitioning | TOC | Understanding Reinsertion 👉

Imagine you’re trying to decide what classes you should sign up for for the fall semester. You can choose from the following classes: Algorithms, Artificial Intelligence, Calculus, Chemistry, Data Structures, Discrete Math, History, Literature, Physics, and Volleyball. You can only take eighteen credits. Additionally, you weigh each of these classes based on their difficulty, usefulness to you, and your own interest in them. You’ve rated each class in each of these categories from 1 to 10. To keep things simple, you weigh each of these criteria evenly.

Your goal is to make the best possible schedule according to these criteria that also meets your credit-hour limitation. You’ve already assigned weights to each class according to the following table:

This is a constrained optimization problem with multiple objectives — meaning, it’s perfect to address using a genetic algorithm.

Start by creating a new file schedule.exs in scripts. Next, in schedule.exs outline a basic Problem implementation, like this:

​ ​defmodule​ Schedule ​do​
​   @behaviour Problem
​   alias Types.Chromosome
​ 
​   @impl true
​   ​def​ genotype, ​do​: ​# ...​
​ 
​   @impl true
​   ​def​ fitness_function(chromosome), ​do​: ​# ...​
​ 
​   @impl true
​   ​def​ terminate?(population, generation), ​do​: ​# ...​
​ 
​ ​end​

Now all you have to do is implement each of these functions and run your algorithm.

Representing Schedules

The easiest way to represent a schedule is with a binary genotype. A binary genotype ensures the size of your chromosome remains fixed, even with a varying number of classes in your schedule.

In this case, each index represents a specific class. The value at that index, 1 or 0, represents whether or not you’re taking that class. The schedule [1, 1, 0, 0, 0, 1, 0, 0, 1, 1] means you’re taking Algorithms, Artificial Intelligence, Discrete Math, Physics, and Volleyball.

Implement genotype/0 like this:

​ ​def​ genotype ​do​
​   genes = for _ <- 1..10, ​do​: Enum.random(0..1)
​   %Chromosome{​genes:​ genes, ​size:​ 10}
​ ​end​

You’ve seen this before in problems like the One-Max problem, introduced in Chapter 1, ​Writing Your First Genetic Algorithm​. You create a binary genotype of size 10 with a for-comprehension.

Evaluating Schedules

Evaluating a schedule is a bit tricky. First, you need to equally weigh all of your criteria: difficulty, usefulness, and interest. Second, you obviously want to maximize interest and usefulness while minimizing difficulty. Third, you need to consider the constraint of eighteen credit hours when constructing schedules.

You’ve decided to weigh each criteria evenly, so difficulty, usefulness, and interest are all worth 33% of a class’s final rating. You can use each of these weights to calculate the fitness of each schedule as a sum of each weighted criteria. Additionally, you’ll have to introduce a penalty for schedules that don’t meet your credit-hour obligation. Because it’s possible for a schedule to be rated negatively, you’ll want your penalty to be a really large negative value, like -99999.

Implement fitness_function/1 like this:

​ ​def​ fitness_function(chromosome) ​do​
​   schedule = chromosome.genes
​   fitness =
​     [schedule, difficulties(), usefulness(), interest()]
​     |> Enum.zip()
​     |> Enum.map(
​         ​fn​ {class, diff, ​use​, int} ->
​           class * (0.3*​use​ + 0.3*int - 0.3*diff)
​         ​end​
​       )
​     |> Enum.sum()
​   credit =
​     schedule
​     |> Enum.zip(credit_hours())
​     |> Enum.map(​fn​ {class, credits} -> class * credits ​end​)
​     |> Enum.sum()
​ 
​   ​if​ credit > 18.0, ​do​: -99999, ​else​: fitness
​ ​end​
​ 
​ ​defp​ credit_hours, ​do​: [3.0, 3.0, 3.0, 4.5, 3.0, 3.0, 3.0, 3.0, 4.5, 1.5]
​ ​defp​ difficulties, ​do​: [8.0, 9.0, 4.0, 3.0, 5.0, 2.0, 4.0, 2.0, 6.0, 1.0]
​ ​defp​ usefulness, ​do​: [8.0, 9.0, 6.0, 2.0, 8.0, 9.0, 1.0, 2.0, 5.0, 1.0]
​ ​defp​ interest, ​do​: [8.0, 8.0, 5.0, 9.0, 7.0, 2.0, 8.0, 2.0, 7.0, 10.0]

Quite a bit is going on here. First, you define each of the associated criteria values outside of the function for clarity. Next, you use Enum.zip/1 to combine all of these values into a tuple. Then you use Enum.map/2 to determine the score for each class based on criteria and whether or not it’s present in the schedule. Finally, you calculate the number of credit hours in a schedule, and if it exceeds the limit, return -99999; otherwise, you return fitness.

All that’s left to do is define some termination criteria and run the algorithm.

Terminating and Running

Because you don’t know the exact fitness of the optimal schedule, you’ll terminate based on the generation. 1000 generations is sufficient, but you can experiment with evolving for more or less generations. Implement terminate?/2 like this:

​ ​def​ terminate?(_population, generation), ​do​: generation == 1000

Next, you need to run your algorithm. Add the following below Schedule:

​ soln = Genetic.run(Schedule)
​ 
​ IO.write(​"​​\n"​)
​ IO.inspect(soln.genes)

Now, run the algorithm:

​ ​$​ mix run scripts/schedule.exs
​ Current ​best:​ 14.7000 ​Generation:​ 1000
​ %Types.Chromosome{
​   ​age:​ 1,
​   ​fitness:​ 14.7,
​   ​genes:​ [0, 1, 1, 0, 1, 1, 1, 0, 0, 1],
​   ​size:​ 10
​ }

According to this evolution, the best schedule is [0, 1, 1, 0, 1, 1, 1, 0, 0, 1], which represents Artificial Intelligence, Calculus, Data Structures, Discrete Math, History, and Volleyball.

Now, you’ll experiment with different reinsertion strategies to see how they affect your evolutions, if at all.

👈 Chapter 8 Replacing and Transitioning | TOC | Understanding Reinsertion 👉

Genetic Algorithms in Elixir by Sean Moriarity can be purchased in other book formats directly from the Pragmatic Programmers. If you notice a code error or formatting mistake, please let us know here so that we can fix it.