Home

A04: Wedding seat assignment

This assignment helps you practice with genetic algorithms. It was inspired by this StackOverflow post.

Our goal is to find an arrangement of guests at a wedding reception such that the most guests are happy with their arrangement. Naturally, some guests prefer to sit near each other while others will be extremely upset with certain people in their proximity. Suppose we represent two kinds of relationships: friends and enemies. If A and B are friends, they prefer to sit near each other; if A and B are enemies, they prefer not to sit near each other.

Background

With a large number of guests, the number of possible seat assignments is extremely large (with $n$ guests, the number of assignments to check is $n!$, since we are dealing with permutations). We most certainly do not want to check the goodness of every possible seat assignment in order to find the best. If we’re willing to live with a near-optimal assignment, then a simple solution to the problem is genetic algorithms.

We can design a genetic algorithm to search only a very small subset of possible seat assignments. In fact, we can control the number of iterations, and thus control the algorithm run time. More iterations will usually produce a more desirable seat assignment, i.e., an assignment with maximum guest satisfaction according to their preferences.

Besides the number of iterations, we also need to define a function to evaluate fitness and some functions to produce candidate solutions. Using natural evolution and sexual reproduction as analogs, we’ll need a “genetic representation” of a seating assignment, a crossover function that “breeds” a new seat assignment based on the parents, and a “mutation” function that randomly perturbs the genes of a seating assignment in order to cover a more diverse swath of the search space.

Task

Start with the weddingseats.py and fill in the missing bits. See the file details. In summary, you are asked to provide the following functions:

Example results

I implemented a fitness function based on distance (close friends increases fitness, close enemies reduces fitness), and the “OBX” and “PBX” crossover functions from the paper “Genetic algorithms for the traveling salesman problem” by Jean-Yves Potvin, in Annals of Operations Research 63 (1996), as well as a random crossover function. The graph below shows the performance of the different crossover functions and whether or not mutation was included. The best fitness discovered by each generation is shown with lines; the boxplots show the distribution of fitnesses for all “surviving” candidate seating assignments. We see that mutation is advantageous and the “PBX” crossover function performed best by finding a high fitness configuration early (and no algorithm eventually found one any higher).

Wedding seat assignment comparison

Deliverables

Modify weddingseats.py available on londo at /home/jeckroth/csci431/assignments/A04 and submit that single file.

Grading rubric

Out of 5 points:

CSCI 431 material by Joshua Eckroth is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License. Source code for this website available at GitHub.