Given, say, 27 students. And they all have various interests/hobbies in their life, like hiking, clubbing, dancing, swimming, maybe hanging out with girls, etc.
A dormitory has 9 rooms. Three students can be accommodated in each room.
The problem to pack them all in such a way, so that all roommates would share as many interests/hobbies with each other, as possible. To make them happy and tight-knit.
This is how it can be solved using simannealing package:
from __future__ import print_function
import sys
import math, os
import random
from simanneal import Annealer
init_state = [[0,1,2],[3,4,5],[6,7,8],[9,10,11],[12,13,14],[15,16,17],[18,19,20],[21,22,23],[24,25,26]]
GROUPS=len(init_state)
# interests/hobbies for each student
interests=[
0b10101110, 0b01000000, 0b11111100, 0b11001001, 0b00111010, 0b10100000, 0b11100001, 0b01000010, 0b00111101,
0b01011000, 0b10110101, 0b00010011, 0b11100001, 0b10010010, 0b00101011, 0b10101101, 0b10010111, 0b11100110,
0b00001000, 0b11111101, 0b10000110, 0b01101000, 0b11001111, 0b01001101, 0b00110010, 0b01000111, 0b11000100]
# https://stackoverflow.com/questions/407587/python-set-bits-count-popcount
def POPCNT(i):
assert 0 <= i < 0x100000000
i = i - ((i >> 1) & 0x55555555)
i = (i & 0x33333333) + ((i >> 2) & 0x33333333)
return (((i + (i >> 4) & 0xF0F0F0F) * 0x1010101) & 0xffffffff) >> 24
def fitness(state, dump_info):
f=0
for group in state:
s1=group[0]
s2=group[1]
s3=group[2]
i1=POPCNT(interests[s1] & interests[s2])
i2=POPCNT(interests[s2] & interests[s3])
i3=POPCNT(interests[s3] & interests[s1])
if dump_info:
total=i1+i2+i3
print ("* group")
print ("students: ", s1, s2, s3)
print ("common interests between 1 and 2: ", i1)
print ("common interests between 2 and 3: ", i2)
print ("common interests between 3 and 1: ", i3)
print ("total" , total)
f=f+i1
f=f+i2
f=f+i3
if dump_info:
print ("total across all groups:" , f)
return f
def random_two_non_eq(max_):
while True:
v1=random.randint(0, max_-1)
v2=random.randint(0, max_-1)
if v1 != v2:
return v1, v2
class TestProblem(Annealer):
# pass extra data (the distance matrix) into the constructor
def __init__(self, state):
super(TestProblem, self).__init__(state) # important!
def move(self):
# swap two random students from distinct groups:
g1, g2 = random_two_non_eq(GROUPS)
s1=random.randint(0, 2)
s2=random.randint(0, 2)
self.state[g1][s1], self.state[g2][s2] = self.state[g2][s2], self.state[g1][s1]
def energy(self):
return -fitness(self.state, False)
test = TestProblem(init_state)
test.steps = 5000000
# since our state is just a list, slice is the fastest way to copy
test.copy_strategy = "slice"
state, e = test.anneal()
print()
print("%i energy:" % e)
for e in state:
print("\t", e)
fitness(state, True)
-67 energy: [20, 13, 2] [25, 21, 17] [26, 15, 1] [11, 5, 24] [18, 3, 12] [9, 19, 22] [14, 16, 10] [4, 8, 0] [7, 23, 6] * group students: 20 13 2 common interests between 1 and 2: 2 common interests between 2 and 3: 2 common interests between 3 and 1: 2 total 6 * group students: 25 21 17 common interests between 1 and 2: 1 common interests between 2 and 3: 2 common interests between 3 and 1: 3 total 6 * group students: 26 15 1 common interests between 1 and 2: 2 common interests between 2 and 3: 0 common interests between 3 and 1: 1 total 3 * group students: 11 5 24 common interests between 1 and 2: 0 common interests between 2 and 3: 1 common interests between 3 and 1: 2 total 3 * group students: 18 3 12 common interests between 1 and 2: 1 common interests between 2 and 3: 3 common interests between 3 and 1: 0 total 4 * group students: 9 19 22 common interests between 1 and 2: 3 common interests between 2 and 3: 5 common interests between 3 and 1: 2 total 10 * group students: 14 16 10 common interests between 1 and 2: 2 common interests between 2 and 3: 4 common interests between 3 and 1: 2 total 8 * group students: 4 8 0 common interests between 1 and 2: 3 common interests between 2 and 3: 3 common interests between 3 and 1: 3 total 9 * group students: 7 23 6 common interests between 1 and 2: 1 common interests between 2 and 3: 2 common interests between 3 and 1: 1 total 4 total across all groups: 53
It has to be executed several times to get better result. This is not the best result, but it may be good enough to be used in practice.
On contrary, my MaxSAT solution chokes on bigger problems, but gives you a best result possible.
Also, simulated annealing algorithm is so simple and primitive in comparison to SAT/MaxSAT solvers.
→ [list of blog posts] Please drop me email about bug(s) and/or suggestion(s): my emails.