I've wanted to experiment with genetic algorithms for a long time, but never quite found the time to make it happen. I guess part of it was that I never believed the algorithm would work and find what I wanted. I decided recently to pick this project back up after a long time (with some prodding from good people) and actually make it work. I think the major push came when I realized that I wanted the ability to make mixed groups, or homogeneous groups, and balance gender, and prevent certain students from being together. Was I over-constraining? Was the possibility that I was over-constraining keeping me from even trying to do this in the first place?
Thus, I decided to actually make this happen. I also decided I wanted to make it look much nicer than the Python version I've been using now for over four years.
The basic algorithm is this:
- Fill in a list of students with names, genders, skill levels, and an optional list of names with whom a given student should not be grouped. Line 2
- Generate a bunch of random groups of students with these properties. For each group, calculate a series of metrics that the fitness of a given group. Lines 45-156
- Calculate the score of a grouping, which consists of a full set of groups that contain all of the students of the class. Line 200
- Generate a bunch of groupings, sort them according to score. Take the top 10 groups, and make swaps of students between groups to make a long list of groups. (This is lines 214-224.) This is the mutation step of the genetic algorithm. Sort them again according to score.
- Repeat for a few generations, then take the top group.
It's pretty fascinating to watch it work. I made the scoring step uniform for gender by tweaking the coefficients in Line 200. You could also make this score value gender balance, a range of abilities, or anything else.
This is screaming for a nicer UI, which I have in the works. For now, it's out there in its fairly un-commented state. If you want to hack this to use with your own students, you'll want to tweak the student list in Line 2, the numbers of groups of each size (groups of 1, groups of 2, groups of 3, and so on) in Line 242, and possibly the values I use in the score generation line in line 200.