Introduction to genetic algorithms in c# with a real application
Genetic algorithm is one of the most popular algorithms in Artificial Intelligence commonly used for optimization problems, in this article we will present the GA from a software engineering perspective rather than computer science.
So as an example project, we will work on a mini-school management system that generates a time table for a semester with the following requirements
In our system, we have 100 registered students everyone can pick up to 5 courses from the available 10 courses, we have only 8 teachers so some of them will be assigned to more than one course and only 4 classrooms.
Our system should generate a conflict-free weekly time table for the school. From the previous requirements, I can design the timetable and avoid the conflicts by writing a very complex logic, I believe that with normal code this task will be very hard and the code will not mentionable.
1- Project Initiation
Before we start doing the magic with Genetic Algorithm let’s take a look at our entities.
I prefer to have these classes in a separate class library let’s call it TimeTable.DAL or TimeTable.Core
This is normal entity framework entities classes that will be used with a normal DBContext
2-Time Table Builder
Now let's create a console application and call it TimeTable.Builder. Please add a reference to the DAL project and add the accord.genetic nugget package.
Before we go into the code which is very easy let’s take a look on the genetic algorithm steps.
1- Generate Initial Random Solutions (Initial Population)
2- For each solution evaluate how good is it. (Evaluate Fitness)
3- Merge the best solutions to create new solutions (Cross Over)
4- Do a random change to the new population (Mutation)
5- Check if any of the solutions is good enough, if not repeat step 3 and 4.
so basically our system will apply the genetic algorithm by doing the following
1- Create Random Schedules
2-Evaluate these schedules by checking how many conflicts are in each schedule Fitness=1/Conflicts.
3- Merge the best solutions by taking a random part from each schedule.
4- We will do a random change by changing a random session time or change a day.
5- The solution is accepted if there are no conflicts.
2.1 Create a chromosomal representation for a time slot (session)
In the Genetic Algorithm, we will do some heavy processing a lot of times so it is a good idea to not deal with database Model Timeslot but a simplified struct will be better.
2.2 Create the TimeTable Chromosome
TimeTable chromosome is a population member ( a candidate schedule solution) that the genetic algorithm will be applied on it (step 1).
As we are using accord.net our TimeTableChromosome class should inherit from ChromosomeBase.
1- A schedule is a set of sessions (timeslots) that will get repeated every week so we created the property Value as List of TimeSlotChromosomes.
2- The method Generate is responsible for generating a random schedule and the easiest way was to loop on very course and put it in a random ClassRoom at a random time (within the working hours).
3- The method Clone just copies the TimeSlotChromosome having the TimeSlotChromosome as a struct helps us here as it is passed by value.
4- The muted function picks a random course and changes it is day to random day.
5- The Crossover function, I love to call it the marriage function, it merges the male schedule (the parameter) into the female schedule the current instance by replacing a random amount of the current schedule sessions.
6- The Fitness Function which is implemented in a standalone class that implements the IFitnessFunction interface just counts the conflicts by summing the number of courses with time overlap, which will be in the same classroom and that have the same teacher and the common students.
The fitness = 1/conlficts
2.3 The final part Run the genetic algorithm and save the result
It is quite simple we create the initial population 1000 member of TimeTableChromsome that will be evaluated using our FintessFunction and we will select the best candidates using the framework EliteSelection
Population population = new Population(1000, new TimeTableChromosome(dataContext),new TimeTableChromosome.FitnessFunction(), new EliteSelection());
We will keep the genetic algorithm running until we found a solution or after 1000 epoch
while (true)
{
population.RunEpoch();
i++;
if (population.FitnessMax >= 0.99 || i >= 1000)
{
break;
}
}and then we will save the schedule solution back to the database
var timetable = (population.BestChromosome as TimeTableChromosome).Value.Select(chromosome =>
new TimeSlot()
{
CourseId = chromosome.CourseId,
PlaceId = chromosome.PlaceId,
Day = (DayOfWeek) chromosome.Day,
Start = chromosome.StartAt,
End = chromosome.EndAt,
Id = Guid.NewGuid().ToString()
}
).ToList();
dataContext.TimeSlots.AddRange(timetable);
dataContext.SaveChanges();Finally showing the result
I continued the project by creating a web API and xamarin mobile app that visualizes the schedule
and here is my xamarin app code
<?xml version="1.0" encoding="utf-8" ?>
<ContentPage xmlns="http://xamarin.com/schemas/2014/forms"
xmlns:x="http://schemas.microsoft.com/winfx/2009/xaml"
xmlns:d="http://xamarin.com/schemas/2014/forms/design"
xmlns:mc="http://schemas.openxmlformats.org/markup-compatibility/2006"
mc:Ignorable="d"
xmlns:views="clr-namespace:TimeTable.App.Views"
xmlns:xForms="clr-namespace:Syncfusion.SfSchedule.XForms;assembly=Syncfusion.SfSchedule.XForms"
x:Class="TimeTable.App.Views.MainPage"><xForms:SfSchedule x:Name="schedule" ScheduleView ="WeekView"></xForms:SfSchedule>
</ContentPage>
Before you leave, make sure that you are following me on twitter
support me on ko-fi.com
And For recommendation please read The Nature Of Code by Daniel Shiffman this book will really help you to come with very simple solutions to complex coding problems regardless of your level in coding this book will improve it.
