Research and Development 1/^Archief/2008-2009/Genetic algorithms/Pilot

Onderzoeksverslag

Wat onderzoeken we?

Onderzoeksvraag

Hoe efficient zijn genetic algorithms bij het in elkaar zetten van een rooster?
Oftewel:
Hoe verloopt de mate van verbetering, uitgezet tegen het aantal gebruikte generaties, bij het verbeteren van een rooster met behulp van genetic algorithms waarbij we ons beperken tot mutaties?

Product / Soort antwoord

Grafiek van fitness van het rooster uitgezet tegen het aantal generaties sinds het origineel.

Verantwoording

Wij maken een computerprogramma dat zelf roosters genereert en die vervolgens verbetert met behulp van mutaties.

Methode

Wij schrijven een C++-programma dat roosters genereert, muteert en de fitness ervan bepaalt. De code hiervan is terug te vinden op SVN. Hier is dan ook altijd de meest recente versie van dat programma te vinden.

Het onderzoek

Roosters genereren

We laten de roosters van 5 dagen x 8 uur door een C++-programma willekeurig samenstellen, en laten die ook door datzelfde programma controleren op fitness, de mutaties uitvoeren en op basis van de veranderingen in fitness grafieken laten maken. Die roosters worden geoutput in een html-bestand genaamd roosters.html. Dat levert dan bijvoorbeeld roosters op als deze:

Klas A

Docent H in L#0	Docent F in L#0	Docent F in L#0	Docent E in L#0	Docent E in L#0
tussenuur	Docent J in L#0	Docent G in L#0	tussenuur	Docent E in L#0
Docent D in L#0	tussenuur	Docent A in L#0	Docent F in L#0	tussenuur
Docent C in L#0	tussenuur	Docent B in L#0	Docent C in L#0	Docent I in L#0
Docent I in L#0	Docent A in L#0	Docent I in L#0	Docent G in L#0	Docent G in L#0
Docent C in L#0	Docent J in L#0	Docent D in L#0	tussenuur	Docent A in L#0
Docent H in L#0	Docent B in L#0	Docent B in L#0	tussenuur	tussenuur
Docent H in L#0	Docent D in L#0	Docent J in L#0	tussenuur	tussenuur

void dump_rooster (rooster)
{
	ver-HTML rooster
}

void genereer_rooster (rooster)
{
	vul rooster met tussenuren
	vul rooster systematisch
	randomizeer (?) rooster
	maak er HTML van (dump_rooster)
}

Fitness controleren

Nu we roosters hebben, kunnen we die gaan controleren op fitness. We controleren op de volgende punten:

1. Het aantal tussenuren dat het rooster bevat

2. Of er iets in het eerste uur ingeroosterd is

3. Dat het rooster geen extreme uitschieters bevat (d.w.z.: zo min mogelijk verschil in uren per dag van de week)

Aan de hand hiervan krijgt een gegenereerd rooster dan een bepaalde waarde. Deze waarde zegt iets over hoe optimaal een gegenereerd rooster is.

int fitness_dag(dagrooster)
{
	voor ieder uur
		tel het aantal lesuren en tussenuren
	return fitness voor deze dag
}

int fitness (roosters)
{
	controleer of het rooster correct is
	ga van alle klassen
		alle dagen af
			en bekijk de fitness voor die dag (fitness_dag)
	return de totale fitness
}

Mutaties uitvoeren

Na het bepalen van de initiële fitness kunnen we een poging doen om die initiële populatie roosters te verbeteren. We hebben, zoals in 'Onderzoeksvraag' te lezen is, ervoor gekozen om dit met genetic algorithms te doen. Dit is een soort zoekmethode waarbij successor states worden gegenereerd door het combineren van twee parent states, vergelijkbaar met biologische voortplanting. Genetic algorithms lenen zich met name goed voor optimalisatieproblemen, waar het maken van zo efficiënt mogelijke roosters ook tot behoort. Hoewel onder genetic algorithms meer verstaan wordt, dan mutaties, beperken we ons in de pilot slechts daartot. Bij mutaties wordt er at random iets in code gewijzigd. In ons geval betekent dat bijvoorbeeld dat er een uur wordt veranderd. Dit hoeft niet per se tot een verbetering te leiden, net zoals een mutatie in de natuur niet altijd positief uitpakt.

void muteer(rooster)
{
	controleer of het rooster correct is
	*produceer willekeurige getalletjes*
	gebruik die willekeurige getallen om een verandering aan te brengen
}

Grafiekjes

Na de mutaties kan dan nagegaan worden of die een positief effect hebben op de fitness van de roosters, en zo ja, in hoeverre. Wat de eindresultaten van ons onderzoek nu zijn, is in het volgende kopje te lezen.

Resultaten

We moeten helaas constateren dat de fitness weinig verbetert.

Voorlopige conclusie

In dit pilotonderzoek wilden wij onderzoeken of een rooster verbeterd kan worden met behulp van genetic algorithms. Wij namen hiervoor (door een zelfgeschreven programma) gegenereerde roosters voor een middelbare school, en voerden hierop mutaties uit. Voor en na het uitvoeren van die mutaties hebben we de fitness van het rooster gecontroleerd.
Uit het onderzoek blijkt helaas dat het uitvoeren van mutaties roosters weinig beïnvloedt (al is het resultaat nog wel positief).
Het pilotonderzoek bood weinig ruimte voor uitgebreider onderzoek. Na afloop hiervan zitten we dan ook nog met enkele (nieuwe,) onbeantwoorde vragen en gedachten, waar we ons in het vervolgonderzoek op kunnen richten.

• Het huidige geïmplementeerde algoritme is niet bijster efficiënt; kunnen we het verbeteren?
• Wij hebben enkel mutaties toegepast. Wat voor effect zullen cross-overs hebben?
• We zouden de eisen die aan gegenereerde roosters gesteld worden, kunnen verscherpen. Wat voor effect heeft dit?
• Kunnen we ook on the fly nieuwe, efficiënte(re) roosters genereren bij bijvoorbeeld lesuitval?

Wat had in ons pilotonderzoek beter gekund?

• De veranderingen waren te klein; hierdoor was veel verandering binnen roosters niet mogelijk.
• Wellicht was de planning niet altijd even optimaal. Hoewel deadlines - waar afgesproken - in het algemeen redelijk gevolgd zijn, ging het niet altijd (helemaal) goed.

Bronvermelding

• Stuart Russell & Peter Norvig, Artificial Intelligence: A Modern Approach, Prentice Hall/Pearson Education, USA, 2003

Presentatiemateriaal

(Voorstel voor) definitieve opzet

• Inleiding onderwerp
  • Wat zijn genetic algorithms?
  • Onderzoeksvraag

• Onderzoek
  • Methode van onderzoek
  • Resultaten

• Conclusie presentatie
  • Alles samengevat
  • Vervolgonderzoek
  • Reflectie

• Vragenminuutje

Prefab-uitziende Powerpointjes en dergelijke

Ding staat op SVN-ding