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

Het onderzoeksplan

Probleemstelling

Onderzoeksvraag: Kan met behulp van hill climbing een programma gemaakt worden dat betere roosters maakt?

Verantwoording

Het maken van roosters is iets wat tegenwoordig vaak nog niet goed wordt gedaan. Vaak worden deze bijvoorbeeld nog met de hand gemaakt, wat uiteraard erg arbeidsintensief en tijdrovend is. Gelukkig zijn er ook programma's op de markt die dit werk flink kunnen verlichten. Toch merken we vaak dat bij beide manieren we geen roosters krijgen waar we tevreden mee kunnen zijn: roosters met (een groot aantal) tussenuren bijvoorbeeld.
Uit ons pilotonderzoek konden we al constateren dat willekeurige, automatisch gegenereerde roosters zijn te verbeteren met genetische algoritmen: telkens kleine willekeurige mutaties toe te passen en de beste roosters te selecteren, zodat à la Survival of the Fittest de betere roosters overblijven. Commerciële (en enkele vrije) software doet dat vaak nog beter. Omdat de bron van vrije software [vaak] te bekijken is, willen wij ons nu ook daar op richten.
Het gaat hier in feite om een optimalisatieprobleem; dat wil zeggen dat door verbeterde roostergeneratie-algoritmes niet alleen roosters kunnen worden gemaakt die zoveel mogelijk aan onze eisen voldoen, maar dat bijvoorbeeld ook reisschema's van vervoersbedrijven verbeterd kunnen worden door iets andere constraints te nemen.

Theoretisch kader

Enkele belangrijke begrippen uit onze onderzoeksvraag zijn 'mutaties', 'fitness', 'random', 'genetic algorithms' en 'hill climbing'.

Mutaties
Een kleine wijziging aan - in dit geval - het rooster, waardoor we een net iets ander rooster krijgen, maar welke nog wel een goed rooster is. Bijvoorbeeld: we verwisselen het eerste en het tweede uur op maandag met elkaar.

Fitness
Een score die een rooster krijgt, die een indicatie is van hoe goed dit rooster is.

Random
Hier wordt er willekeurig een rooster gegenereerd die waarschijnlijk niet zo goed is. Dit wordt gebruikt om de eerste roosters te maken.

Genetic algorithms
Een optimalisatiemethode,
Bij genetic algorithms hebben we allereerst een een selectie (als eerste dus de random roosters).
Hierop laten we twee typen veranderingen los om zo een grotere groep roosters te krijgen.
mutaties (gebaseerd op een van de rooster uit de selectie)
crossover (gebaseerd op twee van de roosters uit de selectie)
bij crossover proberen we een gedeelte van het eerste rooster een gedeelte van het tweede rooster te (laten?) gebruiken.
bijvoorbeeld rooster drie (gegenereerd) heeft de maandag en dinsdag van rooster 1 (uit de selectie) en de woensdag tot vrijfdag van rooster 2 (ook uit de selectie).
Vervolgen kiezen we de roosters met de hoogste fitness en maken hiervan de nieuwe selectie.
Dit proces wordt steeds herhaald, tot een bepaalde eis is gehaald (generatie,fitness,tijd)

Hill-Climbing
Een optimalisatiemethode
We beginnen met een random rooster.
vervolgens maken we meerdere opvolgers met mutaties.
vervolgens kiezen we degene uit met de hoogste fitness.
dit word nu het nieuwe rooster.
we herhalen nu het kiezen van nieuwe roosters, totdat er geen betere meer worden gemaakt.

Over het algemeen wordt er bij het genereren van rooster gebruik gemaakt van genetic algorithms, wij zijn van plan rooster te genereren met behulp van Hill-Climbing.

Methode

We schrijven een nieuw programma dat zo goed mogelijke roosters kan genereren; ditmaal in Java. Deze taal leren we bij de cursus Object-Oriëntatie. Het voordeel van het gebruik van Java, is dat we objectgeörienteerd kunnen werken. Iedereen kan bijvoorbeeld afzonderlijk aan eigen onderdelen werken. Een ander voordeel van Java is dat we simpel modules kunnen toevoegen en verwijderen.
Ook in deze fase van ons onderzoeksproject willen we weer gebruikmaken van genetische algoritmen om betere roosters als eindresultaat te krijgen; in plaats van ons te beperken tot mutaties, gaan we deze keer ook actief crossover implementeren. Dit is ongeveer hetzelfde als wat veel huidige roostergeneratie-software doet. Naast genetische algoritmen, gaan we ook kijken in hoeverre het gebruik van een andere zoekmethode, hill climbing bijdraagt aan een beter resultaat. Of een gegenereerd rooster 'goed' is en 'hoe goed' het is, bepalen we door de fitness ervan vast te stellen. Voor vaststelling van de fitness wordt gekeken naar de volgende punten:

• Het aantal tussenuren dat het rooster bevat
• De frequentie waarmee het laatste uur gevuld is

Het resultaat en de methode waarmee dat resultaat verkregen is, willen wij vergelijken met de optimaliseermethoden en de daarbijhorende resultaten van vrije software. Een voorbeeld van dat soort software is Tablix . Na de resultaten van verschillende programma's een redelijk aantal maal vergeleken te hebben, zouden we een redelijk betrouwbare conclusie moeten kunnen trekken over welk algoritme het best presteert.

Deelvragen en onderzoeksmethode

Om onze onderzoeksvraag te kunnen beantwoorden, delen we deze op in enkele deelvragen die ons daarbij kunnen helpen:

• Wat is een 'goed rooster'?
• Hoe kunnen genetic algorithms ons helpen bij het verbeteren van roosters?
• Met welke andere algoritmen kunnen roosters verbeterd worden?

Wij willen dit ook ditmaal weer doen door zelf een programma te schrijven dat roosters genereert, en ze vervolgens verbetert met behulp van genetische algoritmen; deze keer niet alleen met mutaties, maar ook door gebruik te maken van cross-overs. Net als in de pilot gaan we weer controleren op de fitness van de gegenereerde roosters. Echter maken we de eisen waaraan de roosters moeten voldoen voor een hoge score strenger, waardoor ook kleine veranderingen in de roosters duidelijkere veranderingen zou moeten opleveren in de score. De score zetten we nu ook weer uit tegen het aantal generaties in een grafiek. Ook willen wij de fitness bepalen van roosters die door vrije (open source) programma's worden gegenereerd. Vervolgens vergelijken we die met de fitness van onze 'eigen' roosters.

Globale activiteitenplanning

Ons uiteindelijke onderzoeksplan wordt daarmee als volgt:

• Onderzoeken welke andere roosterprogramma's met een vrij beschikbare bron er bestaan
• Zelf een programma schrijven dat roosters genereert, met de kennis die we hebben (en gebaseerd op AI: A Modern Approach)
• Fitness controleren van onze eigen roosters
• Bekijken hoe anderen het roosterprobleem aangepakt hebben
• Vergelijken
• Conclusie trekken

Literatuur

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

Samenvatting tussenresultaat

Het is ons gelukt om een timetable swapper te maken, die al wel roosters kan (proberen te) verbeteren. Helaas is onze fitness-functie nog niet optimaal, wat ervoor zorgt dat de vrijdagen veelal leeg worden gelaten. Tussenuren worden ook niet altijd even goed weggewerkt. Wat hierna nog moet gebeuren is o.a. het resultaat (de uiteindelijke geoptimaliseerde roosters) van 'ons' algoritme vergelijken met het resultaat van (commerciële en) vrije softwarepakketten die ook roosters optimaliseren.