Toepassing van Simulated Annealing

Mijn vrouw heeft een terugkerend probleem. Ze werkt aan een universiteit waar ze ieder jaar zo’n 200 studenten moet toewijzen aan 20 scriptiebegeleiders. Met Excel als haar enige instrument en vele combinaties, een ondankbare taak. Tijd voor het schrijven van een Machine Learning programma.

Elke student krijgt twee keuzes van twintig scriptiebegeleiders. De totalen van de eerste keuzes van alle studenten (blauwe balken) en tweede keuze (oranje balken) worden getoond in de bovenste rij figuren. De twintig scriptiebegeleiders worden aangeduid met de letters A tot en T.

Matching-SupplyAndDemand-700x400

Sommige scriptiebegeleiders zijn erg populair, maar hebben slechts een paar plaatsen. De beschikbaarheid van scriptiebegeleiders wordt getoond door de groene lijn. De totalen onder de groene lijn komen overeen met de totalen van de blauwe en oranje balken.

De discrepantie tussen de groene lijn en de blauwe of oranje tellingen toont de onevenwichtigheid tussen de vraag (door de studenten) en het aanbod (door de scriptiebegeleiders). Hoe kan men een eerlijke toewijzing maken?

Een naïeve poging is om bovenaan de lijst van studenten te beginnen en hen toewijzen aan de scriptiebegeleiders van de eerste keuze. Na een aantal toewijzingen hebben sommige scriptiebegeleiders geen plaats meer. En de eerste keus de volgende student kan niet meer worden gehonoreerd. Deze student wordt vervolgens gekoppeld met haar / zijn tweede keuze.

Op een gegeven moment kan ook geen tweede keuze meer toegewezen worden. Dan wordt deze student toegewezen aan een willekeurige scriptiebegeleider. Deze naïeve wijze van matching is nogal oneerlijk voor de studenten aan de onderkant van de lijst. Ze zullen vrijwel zeker slecht worden gematcht. En dat is onnodig.

De Simulated Annealing is ideaal voor deze taak. Deze vroege voorbeeld van Machine Learning werd uitgevonden door Nicholas Metropolis en andere wetenschappers in de jaren 1950. Hun idee was om het toewijzingsprobleem te randomizen.

Het programma begint met iedere student willekeurig toe te wijzen aan een scriptiebegeleider. Elke toewijzing wordt gemeten door een afstand. Een eerste keus matching krijgt een afstand van 1, een tweede keus een afstand van 2 en een mismatch krijgt een afstand van 7. De totale som van alle afstanden geven algehele kwaliteit van de matching. Hoe kleiner de som, hoe beter de matching.

Vervolgens worden willekeurig twee student-scriptiebegeleider combinaties gekozen, de twee scriptiebegeleiders worden verwisseld en de nieuwe student-scriptiebegeleider afstanden worden vergeleken met de oude. Wanneer de som van beide afstanden kleiner is is het een verbetering en wordt de nieuwe combinatie geaccepteerd. Wanneer de som van de afstanden groter is is het een verslechtering en wordt deze gewoonlijk verworpen. Echter, het geheim van de smid in Machine Learning is dat een kleine fractie van de verslechteringen toch wordt geaccepteerd. In tegenstelling tot wat je intuïtie je zegt, verbetert dit het algehele resultaat op de lange termijn. Dankzij Metropolis en collega’s.

Matching-Metropolis-700x400

Nicholas Metropolis bekijkt onze oplossing.

In ons geval, deze lange termijn is zo’n zestigduizend verwisselingen. In de eerste paar duizend verwisselingen zijn de verbeteringen er in overvloed, maar later worden ze meer zeldzaam. Wanneer de som van de afstanden niet meer afneemt, is een “dichtste pakking” van student-scriptiebegeleider combinaties verkregen.

De beste matching staat in de onderste figuur. De vraag en aanbod precies op elkaar afgestemd. Voor elke scriptiebegeleider kan de mix van student voorkeuren worden afgelezen. De blauwe segmenten zijn de eerste keuze, de oranje segmenten van de tweede keuze, en de rode segmenten de overigen. In totaal zijn 46% van de eerste keuzes toegewezen (totaal blauwe gebied), 28% van de tweede keuzes (totaal oranje gebied), en 26% als overigen (totaal rood gebied).

Door het programma een aantal malen te draaien blijkt dat betere oplossing zeer moeilijk te vinden zal zijn. Studenten en begeleiders moeten het doen met wat hier wordt gepresenteerd. Belangrijk is dat elke student dezelfde eerlijke kans kreeg om te worden toegewezen aan zijn / haar scriptiebegeleider keuze.