I had some experience with genetic algorithms during my computer science studies. I wanted to refresh my knowledge and decided to write a simple prototype for automated seating people at tables (e.g. at a wedding). However, the results I get are disappointing and I've run into some problems.
- number of tables (assume tables are round and the only thing that matters is at which table someone is located - exact seat at the table doesn't matter)
- table capacity (how many people can seat at one table - all of the tables are the same)
- list of guests, e.g.
- list of groups of guests, that should seat at the same table, e.g.
[[1,2], [3,4,5], [9,10]]
- list of groups of guests that should not seat at the same table, e.g.
My idea is to use a bit string consisting of smaller bit string for each guest. The small bit string would represent at which table a guest is seated. A bit string for three guests and three tables could look like this:
100100010 - the first guest seats at the 1st table, 2nd guest also at the 1st table, 3rd guest at the 2nd table.
Value representing how many guests are satisfied (the higher the better). A guest is satisfied if:
- he is seated only at one table (i.e. his bit string part contains only one '1')
- all of the people he should seat with are at his table
- none of the people he should not be seated with are at his table
- there are no more people at his table than table capacity allows
Crossover and mutation
Simple crossover methods lead to rubbish results like a person seating in two places, nowhere or overcrowded tables. Same with mutation. These operators are blind to constraints. At first I thought that maybe I could just let it be and then fitness function would do the optimization (not rewarding overcrowded tables or people seating nowhere or at more than one table) but the results do not confirm my strategy.
What can I do better?