Genetic algorithm

Top  Previous  Next

You don't need to know how a genetic algorithm works to use PerfectTablePlan. This section 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 a staggering 15,511,210,043,330,985,984,000,000 different ways. So we have to find an efficient way to search though the possible assignments to find a good one in a reasonable time. PerfectTablePlan does this using a 'genetic algorithm'.

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

1.An initial population of assignments is created using various rules of thumb ('heuristics').
2.The assignments are randomly mutated and spliced to produce new layouts.
3.Weak assignments (those with low scores) are eliminated from the population.
4.If the best assignment isn't satisfactory go to step 2.

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 assignment score with simple drag and drop. But if we 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 in a reasonable time.

Problem size

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

25! = 15511210043330985984000000

50! = 30414093201713378043612608166064768844377641568960512000000000000

100! = 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

200! = 788657867364790503552363213932185062295135977687173263294742533244359449963403342920304284011984623904177212138919638830257642790242637105061926624952829931113462857270763317237396988943922445621451664240254033291864131227428294853277524242407573903240321257405579568660226031904170324062351700858796178922222789623703897374720000000000000000000000000000000000000000000000000

So don't be surprised if PerfectTablePlan takes a while to do an automatic assignment for 1000+ guests.