Abstract
Abstract
Compatibility between flatmates in college dorms is important for student life - it ensures people with similar sleep schedules, cleaning habits, etc. are put together to prevent friction between different lifestyles. In this computational essay, we implement a genetic algorithm to sort students into apartments of 4 based on responses from a housing survey. From an international student body, the algorithm also optimizes for diversity in languages and nationalities to ensure students get exposed to a wide variety of other cultures.
Introduction
Introduction
The algorithm shown here was originally written in python by Sebastian Simon, myself and other members of the integration IT team to sort the incoming first year Bachelor students at Ecole Polytechnique into their student apartments. A few weeks earlier, we sent out a housing survey for the students to select their preferences. This survey was the heart of the algorithm - using the responses to the survey, we were able to assign a numerical score to each configuration of apartments and maximize it throughout successive iterations of the algorithm.
In[]:=
Housing Survey
Housing Survey
The housing survey was a questionnaire asking for student preferences. The first part was for demographic information, and the second asked students to numerically rate themselves in certain aspects. For brevity, we won't go over the individual questions here but an example of an entry after the data cleaning is as follows:
In[]:=
entry="index"2,"age"17,"gender""male","nationality"{"french"},"language"{"french"},"noiseDay"3,"noiseNight"1,"sleepWday","sleepWend","cleanAction"2,"cleanTolerance"2,"cooking"2,"studying"1;
For this project we removed the name and contact information for privacy reasons and identified people by an anonymous index. Most of the questions are on a scale of 1 to 5 (lower being stricter). For example, noiseDay and noiseNight denote the tolerance to music and noise during the day and night, cleanAction and cleanTolerance are about how often they want to clean the apartment and how strict they are about cleanliness. Only cooking and studying were multiple choice asking about how often they cook (translated to a scale from 1-3) and whether they prefer to study in a group (1 for yes, 2 for no).
Based on this information, we assigned weights out of 20 to each of these values based on how important we considered them to be.
In[]:=
importance=<|"noiseDay"->9,"noiseNight"->14.5,"sleepWday"->14,"sleepWend"->8,"cleanAction"->14.5,"cleanTolerance"->16,"cooking"->11.5,"studying"->5,"languageDiversity"->15,"nationalityDiversity"->15|>;
Data Import and Cleaning
Data Import and Cleaning
data=;
The original dataset was cleaned in python and converted to a pickle file, thus some cleaning was necessary to convert the data into a Wolfram friendly format. The names have been re[;acWe defined functions to adjust the times of all those who misunderstood the 24 hour clock from the google form (I'm sure nobody sleeps at 10 AM during the week), and some functions to determine the earliest and latest sleep timings from a selection relative to our time window.
In[]:=
TimeClean[time_]:=If[time>TimeObject[{6,0,0}]&&time<TimeObject[{18,0,0}],time+Quantity[12,"Hours"],time]TimeDifference[time1_,time2_]:=Module[{difference=Abs[time1-time2]},If[difference>Quantity[12,"Hours"],Quantity[24,"Hours"]-difference,difference]]MaxTime[timeList_]:=Module[{postMid=Select[timeList,#<TimeObject[{6,0,0}]&],preMid=Select[timeList,#>TimeObject[{18,0,0}]&]},If[postMid!={},Max[postMid],Max[preMid]]]MinTime[timeList_]:=Module[{postMid=Select[timeList,#<TimeObject[{6,0,0}]&],preMid=Select[timeList,#>TimeObject[{18,0,0}]&]},If[preMid!={},Min[preMid],Min[postMid]]]
This is finally used in a function that can clean an entire dataset entry at a time. An additional note is that we deleted English from the list of languages known since it is understood that everyone speaks English in an undergraduate program taught in English, so it's not needed in the language diversity section.
In[]:=
CleanRow[{index_,name_,age_,gender_,nationality_,language_,noiseDay_,noiseNight_,sleepWday_,sleepWend_,cleanAction_,cleanTolerance_,cooking_,studying_,interests_}]:=<|"index"->index,"age"->ToExpression[age],"gender"->gender,"nationality"->StringSplit[StringDelete[nationality,{"[","]"," ","'"}],","],"language"->DeleteCases[StringSplit[StringDelete[language,{"[","]"," ","'"}],","],"english"],"noiseDay"->ToExpression[noiseDay],"noiseNight"->ToExpression[noiseNight],"sleepWday"->TimeClean[TimeObject[ToExpression/@StringSplit[sleepWday,":"]]],"sleepWend"->TimeClean[TimeObject[ToExpression/@StringSplit[sleepWend,":"]]],"cleanAction"->ToExpression[cleanAction],"cleanTolerance"->ToExpression[cleanTolerance],"cooking"->ToExpression[cooking],"studying"->ToExpression[studying]|>
In[]:=
cleanData=CleanRow/@Normal/@data;
Configurations and Scoring
Configurations and Scoring
We denote a single apartment as a list containing 4 students, each student is an association with keys as the column headers and values as the cleaned survey response. We have the function below to calculate the 'score' of an apartment:
In[]:=
ApartmentScore[studentList_]:=Module[{importance=<|"noiseDay"->9,"noiseNight"->14.5,"sleepWday"->14,"sleepWend"->8,"cleanAction"->14.5,"cleanTolerance"->16,"cooking"->11.5,"studying"->5,"languageDiversity"->15,"nationalityDiversity"->15|>,score=0},score+=(1-(MaximalBy[studentList,#["noiseDay"]&,1][[1]]["noiseDay"]-MinimalBy[studentList,#["noiseDay"]&,1][[1]]["noiseDay"])/4)*importance["noiseDay"];score+=(1-(MaximalBy[studentList,#["noiseNight"]&,1][[1]]["noiseNight"]-MinimalBy[studentList,#["noiseNight"]&,1][[1]]["noiseNight"])/4)*importance["noiseNight"];score+=(1-(MaximalBy[studentList,#["cleanAction"]&,1][[1]]["cleanAction"]-MinimalBy[studentList,#["cleanAction"]&,1][[1]]["cleanAction"])/3)*importance["cleanAction"];score+=(1-(MaximalBy[studentList,#["cleanTolerance"]&,1][[1]]["cleanTolerance"]-MinimalBy[studentList,#["cleanTolerance"]&,1][[1]]["cleanTolerance"])/5)*importance["cleanTolerance"];score+=(1-(MaximalBy[studentList,#["cooking"]&,1][[1]]["cooking"]-MinimalBy[studentList,#["cooking"]&,1][[1]]["cooking"])/5)*importance["cooking"];score+=(1-(MaximalBy[studentList,#["studying"]&,1][[1]]["studying"]-MinimalBy[studentList,#["studying"]&,1][[1]]["studying"]))*importance["studying"];score+=(1-QuantityMagnitude[MaxTime["sleepWday"/.studentList]-MinTime["sleepWday"/.studentList]]/5)*importance["sleepWday"];score+=(1-QuantityMagnitude[MaxTime["sleepWend"/.studentList]-MinTime["sleepWend"/.studentList]]/5)*importance["sleepWend"];score+=Length[DeleteDuplicates[Flatten["language"/.(studentList//Normal)]]]/16*importance["languageDiversity"];score+=Mean[Length/@("language"/.(studentList//Normal))]/4*importance["languageDiversity"];score+=Length[DeleteDuplicates[Flatten["nationality"/.(studentList//Normal)]]]/8*importance["nationalityDiversity"];score+=Mean[Length/@("nationality"/.(studentList//Normal))]/2*importance["nationalityDiversity"];score]
For noise, cleaning, sleep timing, cooking and studying scores, we simple take the difference between the students with the most and least tolerance to find the overall for the apartment. For language and nationality diversity, we consider both the total number of languages/nationalities represented and the average per person. This may seem like counting twice, but we normalize it against the maximum of the entire dataset to get a number between 0 and 1 before multiplying it by the importance, so it roughly cancels out.
If we add up all the importance scores, we get roughly 150 as the upper limit of apartment scores. This is not the theoretical maximum since the score function uses some specifics from our given dataset, but we can take it as such for practical purposes. Next, we find the score of an entire configuration as the sum of the mean apartment score and the minimum. This ensures that the standard deviation of the configuration we tend to is kept low.
In[]:=
CombinationScore[combination_]:=Module[{apartmentScores=ApartmentScore/@combination},Mean[apartmentScores]+Min[apartmentScores]]
Thus, the practical maximum configuration score is about 300. We target anything above 200 to 250 as a good score.
Genetic Algorithm
Genetic Algorithm
Finally, we get to the main algorithm. Our approach is to first come up with a random configuration and make swaps a set number of times to make it better. We first define the function that takes a configuration and tries to make a swap. If it is an improvement, we keep it otherwise we return the original configuration.
In[]:=
MakeValidChange[combination_]:=Module[{combinationCopy=combination,studentList1,studentList2,student1,student2},studentList1=RandomChoice[combination];student1=RandomChoice[studentList1];combinationCopy=DeleteCases[combinationCopy,studentList1];studentList2=RandomChoice[combination];student2=RandomChoice[studentList2];combinationCopy=DeleteCases[combinationCopy,studentList2];If[(ApartmentScore[studentList1/.student1->student2]-ApartmentScore[studentList1])+(ApartmentScore[studentList2/.student2->student1]-ApartmentScore[studentList2])>0,combinationCopy=Join[combinationCopy,{studentList1/.student1->student2,studentList2/.student2->student1}],combinationCopy=Join[combinationCopy,{studentList1,studentList2}]];combinationCopy]
In each generation, we make 5 different random changes to the same configuration and choose the best one to go forward. This is repeated for as many generations we need until we are satisfied with the result.
In[]:=
initialCombination=Partition[RandomSample[cleanData//Normal],UpTo[4]];current=initialCombination;scores={CombinationScore[current]};min={Min[ApartmentScore/@current]};average={Mean[ApartmentScore/@current]};For[i=0,i<50,i++,changes=Table[MakeValidChange[current],5];current=MaximalBy[changes,CombinationScore][[1]];scores=Append[scores,CombinationScore[current]];min=Append[min,Min[ApartmentScore/@current]];average=Append[average,Mean[ApartmentScore/@current]];]CombinationScore[current]
We keep track of the score, minimum apartment score and average over the iterations. They are all shown in the graph below.
We can see that all of them increase over time and give us better overall rooms. An interesting observation is that while the average does not increase a whole lot, the minimum does start at a very low number before jumping up to around 100. This probably tells us that there was a large standard deviation at the start, and over the iterations the worst rooms improve considerably. This is part of the reason why it was important to consider the minimum as well in the score.
Conclusion
Conclusion
The results we got are very promising. We were able to come up with a good sorting of students into their apartments, much better than if it were done randomly. In the python implementation, we had various limitations that would rule out certain configurations as "invalid", such as too much age difference, a difference greater than 3 points in cleanliness or noise, etc. Furthermore, we set a hard limit or not more than half the apartment being the same nationality/language to prevent apartments in which one person is left out. In this one, we instead included the nationality and language diversity as a heavily prioritized part of the score to create more diverse apartments and try to get the best possible configuration in terms of raw compatibility.