Making Groups – A Genetic Algorithm Experiment
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.
You can see the code directly here at CodePen, or play with it below.
[codepen_embed height=”265″ theme_id=”0″ slug_hash=”rmebEQ” default_tab=”js,result” user=”emwdx”]See the Pen GroupMaker by Evan Weinberg (@emwdx) on CodePen.[/codepen_embed]
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.
It’s interesting that when I do this ( https://arundquist.wordpress.com/2012/10/15/matching-students-with-projects/ ) I don’t bother with your first two steps, which I interpreted as starting the population making sure you haven’t violated any hard rules. Instead I’m lazy and just randomly place people and have a huge fitness penalty for any candidates that break those hard rules. I say lazy because I think your way is probably better but I do like how it always works out in the end (the final solution always avoids those heavy penalties). It’s possible I misinterpreted what you said and you do the same, of course.
No Andy, I’m every bit as lazy as you. (I mean this as a good thing!)
In the score calculation step, I put in a major penalty if there is someone in the group that is in a group member’s exclude list. I think one of my struggles with the entire algorithm was whether a penalty would be tough enough to prevent one of the things I didn’t want to happen. How do I know if a penalty is enough? Do I need to actually do a final algorithmic check in the end to make sure that these rules isn’t violated?
Now that I’ve actually done it, I can see that it’s pretty easy to verify whether this is the case or not from the score. I also feel more comfortable with my skills using Javascript objects to monitor this themselves and ‘announce’ they have problems rather than having to do a set of logical checks in the end of a beefy array. Trusting the algorithm to work was key.
I tried to minimize the conflicts in my school’s schedule using a genetic algorithm. It didn’t work out (I had to use a more “direct” algorithm), but it was a fun experience.
This is great to see Dominick – thanks for letting me know about your experiment!