The PerfectTablePlan genetic algorithm

You don't need to know anything about genetic algorithms to use PerfectTablePlan. This page is just included in case you are interested.

It isn't possible to try every combination of guests and seats, because there are so many. Even just 25 guests can be assigned to 25 seats in 15, 511, 210, 043, 330, 985, 984, 000, 000 different ways. An efficient approach is required to search though the possible layouts to find a good solution in a reasonable time. PerfectTablePlan does this using a genetic algorithm.

A genetic algorithm works by mimicking the Darwinian process of natural selection over successive generations:

  1. an initial population of layouts is created using various rules of thumb ('heuristics').
  2. the layouts are randomly mutated and spliced to produce new layouts, which are added to the population.
  3. weak layouts (those with low scores) are eliminated from the population.
  4. go to step 2.

This process continues until a satisfactory solution is reached. In PerfectTablePlan you can choose to stop:

  • after a specified number of seconds; or
  • after a specified number of generations without improvement; or
  • either of the above (whichever happens first)

Because of the way a genetic algorithm works, it cannot be guaranteed to give a mathematically optimal answer - sometimes you can spot ways to improve the layout score with simple drag and drop. But if PerfectTablePlan were to use an approach that was guaranteed to give a mathematically optimal answer, it might take years to run. The PerfectTablePlan genetic algorithm will usually get close to an optimal solution very quickly.

The number of combinations for seating n guests in n seats is n! ( n factorial). This means that the difficulty of the problem rises very rapidly with the number of guests. For example:

25! = 150, 511, 210, 043, 330, 985, 984, 000, 000

50! = 3, 041, 409, 320, 171, 337, 804, 361, 260, 816, 606, 476, 884, 437, 764, 156, 896, 051, 200, 000, 000, 000

100! = 93, 326, 215, 443, 944, 152, 681, 699, 238, 856, 266, 700, 490, 715, 968, 264, 381, 621, 468, 592, 963, 895, 217, 599, 993, 229, 915, 608, 941, 463, 976, 156, 518, 286, 253, 697, 920, 827, 223, 758, 251, 185, 210, 916, 864, 000, 000, 000, 000, 000, 000, 000, 000

1000! has 2,568 digits. So don't be surprised if PerfectTablePlan takes a while to do an automatic layout for 1000+ guests!

More information on genetic algorithms: