0
$\begingroup$

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.

The input

  1. 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)
  2. table capacity (how many people can seat at one table - all of the tables are the same)
  3. list of guests, e.g. [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]
  4. list of groups of guests, that should seat at the same table, e.g. [[1,2], [3,4,5], [9,10]]
  5. list of groups of guests that should not seat at the same table, e.g. [[4,9], [1,10]]

Encoding

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.

Fitness function

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?

$\endgroup$
1
$\begingroup$

Just a few ideas you may find useful.

1. Change your encoding

Right now it's quite redundant, and it also allows some illegal solutions - like people sitting at more than one table. What I would suggest is using table numbers: 00 01 10 11 means people sitting at tables 0,1,2,3

It's only possible to encode solutions with people sitting at exactly one table, and for 15 guests and 4 tables, you need only 30 bits to encode a solution vs 60 bits with your encoding.

2. Change your fitness function

Consider a situation when there is a person A sitting at a table with two persons that he likes, and one person that he doesn't like, and person B that sits at a table with three people that he doesn't like. With your satisfaction measure being only 0 or 1, a solution including person A is as good as other solution including person B, while a solution with person A seems better and should have a higher chance of mating. Also, you may want to separate your constraints from your fitness function, right now they are built-in into it.

3. What about selection?

You didn't mention what kind of selection do you use. You complain about your operators being blind to constraints. Yes, they are blind to constraints, because constraints are not their responsibility. You need to implement a comparator that takes constraints into consideration, not only fitness function.

4. Is it a single objective problem?

It's certainly easier to implement a single objective optimisation, but perhaps you can consider two objectives: minimising the number of people that hate each other sitting at the same table, while also maximising the number of people that like each other sitting at the same table.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.