Perfect Table Plan - create a table seating plan for your wedding or event

 

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 15511210043330985984000000 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! = 15511210043330985984000000

 

50! = 30414093201713378043612608166064768844377641568960512000000000000

 

100! = 93326215443944152681699238856266700490715968264381621468592963895217599993229915608

941463976156518286253697920827223758251185210916864000000000000000000000000

 

200! = 788657867364790503552363213932185062295135977687173263294742533244359449963403342920304284

011984623904177212138919638830257642790242637105061926624952829931113462857270763317237396

988943922445621451664240254033291864131227428294853277524242407573903240321257405579568660

226031904170324062351700858796178922222789623703897374720000000000000000000000000000000000

000000000000000

 

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:

 

 News  Tips  Clip art  Poster prints  Place cards  Terms  Privacy  Links  About us  Contact us  Site map