Seating plan optimisation

A place to discuss the science of computers and programs, from algorithms to computability.

Formal proofs preferred.

Moderators: phlip, Moderators General, Prelates

zed0
Posts: 179
Joined: Sun Dec 17, 2006 11:00 pm UTC

Seating plan optimisation

This is very much inspired by xkcd 0173: Movie Seating.

My university computer society recently put together a graph of the relationship network of the society (anonymized to protect the not so innocent):
Spoiler:

We also have regular LAN parties for which we have seating plans. These typically consist of 4 long tables, seating 10 people on each side.

How would one go about determining both the optimally sociable and the optimally awkward arrangement of people on this seating plan?

On another note, it has already been pointed out that our graph is non-planar (damn it 21/30), are there any other interesting or amusing features of the graph that we haven't spotted?

Ambeco
Posts: 105
Joined: Thu Mar 03, 2011 12:17 am UTC

Re: Seating plan optimisation

Interesting problem, but it's more complicated. I assume your intent was to have people sit near others they have lines too, but near is probably the seat on either side, and the three seats across the table. Also, real-live people can dislike each other. Eg, 10's girlfriend probably doesn't want 39 anywhere nearby.

My first thought is make a genetic algorithm to minimize distances, with different tables counting as 10 seats away, weighting "more than kissed" as twice as important as "kissed.", mostly because it's fairly straightforward, and simple.

Manually, I'd guess I'd start by attempting to divide the people into four tables, minimizing lines going between tables (again, weighted if you want). Then, being lazy, I'd put the most connected person of each table in the middle of the table, surround by their connections, then their connections, and fudge it to make it work. Not precise, but it's simple.

zed0
Posts: 179
Joined: Sun Dec 17, 2006 11:00 pm UTC

Re: Seating plan optimisation

As you say, there are complications, especially as the graph is an entire history and not what's currently happening. I'm not too worried about actual feelings for/against people at the moment, I mostly want to do something cool with graphs.
I'll probably settle for grouping people with lines together as you say.
In fact across the table isn't very close together at all as there tend to be a lot of computer cases/monitors in the way of seeing the person across from you so it could be considered as 8 single rows of 10.

While I understand the basic principal I failed to do our neural computing course and thus don't really know much about genetic algorithms, how would one implement this in a sensible way?

Xanthir
My HERO!!!
Posts: 5426
Joined: Tue Feb 20, 2007 12:49 am UTC
Contact:

Re: Seating plan optimisation

Genetic algorithms are really simple. You just need (a) a way to encode a complete solution, preferably as some 1d data structure, and (b) some way to "rate" a solution.

Then you just make a bunch of random solutions, and repeatedly iterate through a rate->cull->breed->rate cycle. The exact details of how you cull and breed can affect how your solution turns out, but one simple method is to kill the lower half of the solutions, and then just copy the survivors, making some random mutations in the copies. This is emulating asexual reproduction. You can also do sexual reproduction by somehow splicing together the sequences for two solutions.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

Ambeco
Posts: 105
Joined: Thu Mar 03, 2011 12:17 am UTC

Re: Seating plan optimisation

This problem is easily convertable to a simple 1d structure (DNA). However, I can't think of a structure/sex concept that makes much sense at all. So simplist asexual way is to generate a DNA array of N integers 1-N, and shuffle it. The first 8 numbers are the people in one row, the next 8 are the next row...
Easist steps with a mutation rate of M (about N/20, but M should be at least 2.) would be:
1 generate 20 random starting DNA (via shuffling the numbers)
2 score each one (count how many connections internally between each set of eight)
3 sort them decreasing by score, and display highest.
4 create a DNA mutation array of N bools.
5 For each element in mutation array, set it to (rand(1, N)>=M). If less than two elements are true, set one or two random ones to true (so at least two are true). [F, f, t, f, t, f, f, t]
6 replace DNA#20 (worst=dead) with one of the top 19 (#20 to be a child of a winner), weighted so that better DNAs are picked more. [4, 2, 8, 1, 5, 7, 3, 6]
7 rotate the elements in the child DNA (#20) who's corresponding element in the mutation array is true. 1->7->6. [4, 2, 8, 6, 5, 1, 3, 7] (if you have duplicate and/or missing numbers in a DNA, bug is probably here)
8 if its a duplicate of anything else in the list, goto 4.
8 score it
9 insert sort it back into the list. If its now highest, print it.
10 goto 4, (infinite loop)

The intent here is to have the top 20 at all times, and each number 1-N should be in each DNA. After testing it, run it for a day or two, and the last line on the screen is your answer.

I did think of a breeding concept, but its far slower than the rest. If you add this, you can remove the 2 minimum of the mutation.
These steps go after step 6:
6.1 create breed array of bools, where each i is set to (rand(1,3)==1) (closer to 1-sqrt(.5)=29.289% is best, but 1/3=33.333% is close)
6.2 pick a different DNA from the top 19 (weighted towards the best ranks). I'll call this male, and the one copied to #20 female.
6.3 for each element i where breed array is true, find male[i] in the female's DNA, (we'll call this index j), and swap (i, j) in the female's DNA.

The rand(1,3) does tend toward the father slightly (5/9), but that seems ok, as everyone has equal chance to be mother/father.