31:T611,md`## Beleidskeuzes Eén van de beslissing die moet genomen worden is welke waarde men aan een eerste keuze hecht, vergeleken met een tweede, een derde enz. Beschouw volgend voorbeeld ter verduidelijking: Voor een plaats in school A komen student 1 en student 2 in aanmerking. School A was de eerste keuze van student 1 en slechts de tweede keuze van student 2. Aan welke student geef je bij voorkeur de plaats: 1. Student 1: het was immers zijn eerste keuze en we willen een maximaal aantal studenten hun voorkeursschool toewijzen. 2. Student 2: het feit dat hij aanspraak moet doen op zijn tweede keuze wil zeggen dat hij zijn eerste keuze niet krijgt en we willen dan toch minstens proberen om zijn tweede voorkeur te verwezenlijken. 3. Geen van beide: we laten het lot beslissen. Het voordeel van strategie 1 is dat het aantal studenten die hun voorkeursschool krijgen maximaal zal zijn. Het nadeel van deze strategie is dat in geval van een capaciteitsprobleem, studenten die hun eerste keuze niet krijgen, een bijzonder lage kans hebben om hun tweede en zelfs derde keuze binnen te halen. Strategie 2 komt aan dit probleem tegemoet door voorrang te geven aan zij die een betere keuze niet haalden. Dit echter ten koste van plaatsen die voor iemand anders eerste keuze zouden gebruikt kunnen worden. Strategie 3 is een compromis en zoekt het midden tussen enerzijds het maximaal aantal studenten de beste keuze te geven en anderzijds het maximaal aantal studenten een goede keuze. **Het huidige algoritme lijkt deze strategie te gebruiken**. `32:T96f,md`## Keuze algoritme Uiteraard zal ook de keuze van het algoritme belangrijk zijn voor het resultaat. Op de meldjeaan-website staan enkele eisen vermeld: - Door slechts 1 keuze op te geven mag de kans niet groter worden dat je deze krijgt - Meer scholen opnemen in je rangschikking, mag er niet voor zorgen dat je kansen voor je voorkeursschool dalen - Rekening houden met de strategie uit de vorige sectie ### Kiezen per school Het gebruikte algoritme zal voor elke school afzonderlijk een voorkeurslijst opstellen en werkt als volgt: 1. Voor elke school maken we een lijst met alle studenten die deze school in hun voorkeuren hebben opgenomen, ongeacht de plaats daarin. 2. Elk van die lijsten plaatsen we in een random volgorde. 3. We bekijken nu voor elke student de plaats op de lijst voor elk van zijn voorkeuren. - Als zijn positie op de lijst hoger is dan het aantal plaatsen in die school, dan heeft hij die plaats verworven. - We kunnen de student bijgevolg schrappen van alle lijsten van scholen waarvoor hij een lagere voorkeur had. 4. We herhalen stap 3 tot we geen studenten meer van (wacht)lijsten kunnen schrappen. 5. Op basis van de volgorde op de uiteindelijke lijsten worden de tickets verdeeld. Dit algoritme lijkt goed te werken, maar heeft 1, ogenschijnlijk bizar, nadeel: **het kan voorkomen dat 2 studenten elkaars primaire voorkeur toegewezen krijgen**, wat we een gekruiste toewijs nemen. Deze 2 studenten laten wisselen zou een optimalere oplossing betekenen, maar mag blijkbaar niet volgens de regels met ongenoegen tot gevolg. ### Kiezen per student Een alternatief algoritme dat ook aan alle voorwaarden voldoet, is om de loting per student te laten gebeuren: 1. We plaatsen alle studenten in een lijst 2. We verwijderen een random student uit de lijst en kijken naar zijn voorkeur - Als er nog plaatsen beschikbaar zijn in die school, dan krijgt de student een ticket voor die school - Als er geen plaatsen meer beschikbaar zijn, dan wordt de student terug in de lijst geplaatst met zijn volgende keuze als voorkeur. - Als de student geen voorkeuren meer over heeft, dan kunnen we helaas geen plaats voor hem voorzien. 3. We blijven stap 2 herhalen tot de lijst leeg is Het voordeel van dit algoritme is dat het **onmogelijk** is dat er in het eindresultaat **gekruiste toewijzen** optreden en dat **meer studenten** hun **primaire keuze** zouden moeten krijgen. `33:T54b,md`## Simulaties Om de 2 algoritmen te vergelijken, kunnen we enkele simulaties laten lopen. Voor deze simulaties zijn een aantal aannames gedaan: - Er is geen rekening gehouden met voorrang op basis van familieleden. Dit kan beschouw worden als een voorafname op het aantal plaatsen en is niet van belang. - Er is geen rekening gehouden met de dubbele contingentering/sociale mix wegens gebrek aan gegevens. - Iedereen heeft exact 3 keuzes opgegeven (al is deze parameter aanpasbaar). - Ik heb geen zicht op het verband tussen grootte van een school en de populariteit ervan. In de simulatie zijn alle scholen even groot, maar kan het verschil in populariteit ingesteld worden met een parameter. Bij de standaardinstellingen is de populairste school 50% populairder dan de minst populaire, gecorrigeerd voor de grootte. **Deze cijfers kunnen niet gebruikt worden om definitieve conclusies te trekken, dit kan enkel op basis van de echte data. Ze geven enkel een indicatie over eventuele mogelijke verbeteringen.** In een eerste stap heb ik geprobeerd om de huidige gerapporteerde cijfers te benaderen voor het in de praktijk gebruikte algoritme (gemiddelde uit 100 runs): Selectie per school |**Percentage**|**Cumulatief** :-----|-----:|-----: eerste keuze|86.41%|86.41% tweede keuze|11.73%|98.14% derde keuze|1.52%|99.66% geen toewijs|0.34%|100.00% `34:T662,class School { constructor(capacity, popularity) { this.capacity = capacity; this.popularity = popularity; this.students = []; this.waitingList = []; } reset() { this.students = []; this.waitingList = []; } registerStudent(student) { this.students.push(student); student.setSchool(this); } atCapacity() { return this.students.length >= this.capacity; } isSelected(student) { return this.waitingList.indexOf(student) < this.capacity; } addToWaitingList(student) { this.waitingList.push(student); } removeFromWaitingList(student) { const i = this.waitingList.indexOf(student); if (i !== -1) { this.waitingList.splice(i, 1); return true; } return false; } shuffleWaitingList() { this.waitingList.shuffle(); } assignStudents() { for (let i = 0; i < this.capacity && i < this.waitingList.length; i++) { this.registerStudent(this.waitingList[i]); } } static generateSchools(amount, capacity) { const schools = []; for (let i = 0; i < amount; i++) { schools.push(new School(capacity, 0.8 + Math.random() / 2.5)); } return schools; } static pickRandomSchool(schools) { let sum = 0; for (let school of schools) { sum += school.popularity; } let rm = Math.random() * sum; for (let school of schools) { rm -= school.popularity; if (rm <= 0) { return school; } } throw "random school error" } static resetSchools(schools) { for (let school of schools) { school.reset(); } } }35:Tc6a,class Simulator { static generateChoices(students, schools, picks) { for (const student of students) { const choices = []; while (choices.length < picks) { const newPick = School.pickRandomSchool(schools); if (!choices.includes(newPick)) { choices.push(newPick); } } student.setChoices(choices); } } static assignSchoolBased(students, schools) { School.resetSchools(schools); Student.resetStudents(students); // add students to waiting lists for (let student of students) { for (let school of student.getChoices()) { school.addToWaitingList(student); } } // shuffle all waiting lists for (let school of schools) { school.shuffleWaitingList(); } // removeObsoletePositions let changesMade = true; while(changesMade) { console.log("starting new iteration"); let removals = 0; changesMade = false; for (let student of students) { let removeMode = false; for (let choice of student.getChoices()) { if (removeMode) { let removed = choice.removeFromWaitingList(student); if (removed) { removals ++; changesMade = true; } } else { if (choice.isSelected(student)) { removeMode = true; } } } } console.log("removals: " + removals); } // assign schools for (let school of schools) { school.assignStudents(); } return Simulator.analyze(students); } static assignStudentBased(students, schools) { School.resetSchools(schools); Student.resetStudents(students); const studentsToAssign = Array.from(students); studentsToAssign.shuffle(); while (studentsToAssign.length > 0) { const student = studentsToAssign.pop(); const choice = student.getNextChoice(); if (choice === null) { continue; } else if (!choice.atCapacity()) { choice.registerStudent(student); } else { studentsToAssign.push(student); studentsToAssign.shuffle(); } } return Simulator.analyze(students); } static analyze(students) { let histogram = []; for (let student of students) { let pick = student.pick; if (histogram[pick]) { histogram[pick]++; } else { histogram[pick] = 1; } } return histogram; } static multiSchoolRun(steps) { const results = []; results.push(Simulator.assignSchoolBased(students, schools)); return Simulator.average(results, students.length); } static multiStudentRun(steps) { const results = []; results.push(Simulator.assignStudentBased(students, schools)); return Simulator.average(results, students.length); } static average(results, numOfStudents) { const result = []; for (let i = 0; i < results[0].length; i++) { let k = 0; for (let j = 0; j < results.length; j++) { k += results[j][i]; } result[i] = k / numOfStudents; } return result; } }36:[] 2f:{"title":"Analyse 'Meld je aan' Gent","cells":[{"id":0,"value":"md`# Analyse 'Meld je aan' Gent`","pinned":false,"hidden":false,"mode":"ojs"},{"id":146,"value":"$31","pinned":false,"hidden":false,"mode":"ojs"},{"id":157,"value":"$32","pinned":false,"hidden":false,"mode":"ojs"},{"id":178,"value":"$33","pinned":false,"hidden":false,"mode":"ojs"},{"id":247,"value":"md`\nAls we met dezelfde data het alternatieve algoritme gebruiken, dan krijgen we:\n\nSelectie per student |**Percentage**|**Cumulatief**\n-----|-----:|-----:\neerste keuze|94.58%|94.58%\ntweede keuze|2.50%|97.08%\nderde keuze|1.10%|98.18%\ngeen toewijs|1.82%|100.00%\n\nDit is een merkelijk beter resultaat voor eerste keuze, maar we zien dat er voor de andere gevallen iets slechter gescoord wordt.\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":288,"value":"md`\n## Beleidskeuzes in de algoritmes\nDe beleidskeuzes waarvan sprake in de eerste sectie kunnen in beide algoritmes geïmplementeerd worden. Bij het in de praktijk gebruikte algoritme kan dit door de lijst per school op een alternatieve manier te sorteren. Voorkeuren met hogere prioriteit zouden daar eerder of later kunnen komen.\n\nBij het student-gebaseerde algoritme kan dit door een alternatieve stap uit te voeren als de voorkeursschool niet meer beschikbaar is. In geval van strategie 1 komt de student dan in een tweede lijst terecht die pas behandeld zal worden na de primaire; in geval van strategie 2 proberen we die student direct te plaatsen door naar zijn volgende keuzes te kijken.\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":13,"value":"schools = School.generateSchools(18, 227)","pinned":false,"hidden":false,"mode":"ojs"},{"id":23,"value":"students = Student.generateStudents(4076)","pinned":false,"hidden":false,"mode":"ojs"},{"id":41,"value":"choices = Simulator.generateChoices(students, schools, 3)","pinned":false,"hidden":false,"mode":"ojs"},{"id":63,"value":"schoolSim = {\n choices;\n return Simulator.assignSchoolBased(students, schools);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":107,"value":"studentSim = {\n choices;\n return Simulator.assignStudentBased(students, schools);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":230,"value":"Simulator.multiSchoolRun(100)","pinned":false,"hidden":false,"mode":"ojs"},{"id":239,"value":"Simulator.multiStudentRun(100)","pinned":false,"hidden":false,"mode":"ojs"},{"id":5,"value":"$34","pinned":false,"hidden":false,"mode":"ojs"},{"id":9,"value":"class Student {\n constructor() {\n this.choices = [];\n this.nextChoice = 0;\n }\n \n reset() {\n this.nextChoice = 0;\n this.mySchool = undefined;\n this.pick = undefined;\n }\n \n setSchool(school) {\n if (this.mySchool != null) throw \"Already assigned!\";\n this.mySchool = school;\n this.pick = this.choices.indexOf(school) + 1;\n }\n \n setChoices(choices) {\n this.choices = choices;\n }\n \n getChoices() {\n return this.choices;\n }\n \n getNextChoice() {\n \tif (this.nextChoice < this.choices.length) {\n const c = this.choices[this.nextChoice];\n this.nextChoice++;\n return c;\n } else {\n return null;\n }\n }\n \n static generateStudents(amount) {\n const students = [];\n for (let i = 0; i < amount; i++) {\n students.push(new Student());\n }\n return students;\n }\n static resetStudents(students) {\n for (let student of students) {\n student.reset();\n }\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":32,"value":"$35","pinned":false,"hidden":false,"mode":"ojs"},{"id":36,"value":"Array.prototype.shuffle = function() {\n let i = this.length;\n while (i) {\n\tconst j = Math.floor(Math.random() * i);\n\tconst t = this[--i];\n\tthis[i] = this[j];\n\tthis[j] = t;\n }\n return this;\n}","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W36","stdlib":"1","titling":"auto"}