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.
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.
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:
fitness(seating)– a function that scores the fitness or goodness of a particular seating arrangement, according to the friends/enemies relationships
crossover(parent1, parent2)– a crossover function that returns a new seating arrangement by taking elements from both parents
mutate(seating)– a mutation function that randomly alters a particular seating; this will be called with the result generated by
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).
weddingseats.py available on londo at
/home/jeckroth/csci431/assignments/A04 and submit that single file.
Out of 5 points:
- 5 pts: Reasonable crossover, mutation, and fitness functions are coded so that solutions are found. “Reasonable” here is a judgment call. Note, a random crossover function is considered unreasonable.
- 4 pts: Unreasonable (e.g., random or otherwise poorly-performing) crossover, mutation, and fitness functions are coded so that (poor) solutions are found. “Unreasonable” here is a judgment call.
- 3 pts: Reasonable crossover and fitness functions are defined but no mutation function is defined; yet still solutions are found.
- 2 pts: An unreasonble crossover and/or unreasonable fitness function is defined but no mutation function is defined; yet still (poor) solutions are found.
- 1 pt: Incomplete/non-functional crossover function, or otherwise broken/non-functional code is submitted.
- 0 pts: No submission.