Genetic algorithm

<< Click to Display Table of Contents >>

Navigation:  Reference > Seat assignment >

Genetic algorithm

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 by 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. 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 very quickly.

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

52175999932299156089414639761565182862536979208272237582511852109168640

00000000000000000000000

 

200! = 7886578673647905035523632139321850622951359776871732632947425332

44359449963403342920304284011984623904177212138919638830257642790242637

10506192662495282993111346285727076331723739698894392244562145166424025

40332918641312274282948532775242424075739032403212574055795686602260319

04170324062351700858796178922222789623703897374720000000000000000000000

000000000000000000000000000

 

500! = 1220136825991110068701238785423046926253574342803192842192413588

38584537315388199760549644750220328186301361647714820358416337872207817

72004807852051593292854779075719393306037729608590862704291745478824249

12726344305670173270769461062802310452644218878789465754777149863494367

78103764427403382736539747138647787849543848959553753799042324106127132

69843277457155463099772027810145610811883737095310163563244329870295638

96628911658974769572087926928871281780070265174507768410719624390394322

53642260523494585012991857150124870696156814162535905669342381300885624

92468915641267756544818865065938479517753608940057452389403357984763639

44905313062323749066445048824665075946735862074637925184200459369692981

02226397195259719094521782333175693458150855233282076282002340262690789

83424517120062077146409794561161276291459512372299133401695523638509428

85592018727433795173014586357570828355780158735432768888680120399882384

70215146760544540766353598417443048012893831389688163948746965881750450

69263653381750554781286400000000000000000000000000000000000000000000000

00000000000000000000000000000000000000000000000000000000000000000000000

000000

 

1000! = a number 2568 digits long (if you printed it out 5 digits per centimetre it would be more than 5 metres long).

 

4000! = a number 12674 digits long (if you printed it out 5 digits per centimetre it would be more than 25 metres long).

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

See also:

online factorial calculator