Hogeschool Gent Departement INWE
Eindwerk: Automatische Planning van Lesroosters
Peter Van den Daele Promotor: Rudy Stoop
Woord Vooraf Mijn dank gaat in eerste plaats uit naar mijn promotor, Rudy Stoop, die mij in moeilijke omstandigheden heeft moeten coachen. Hij heeft mij zeer begripvol gesteund en bij moeilijkheden veelal direct de juiste denkpistes aangegeven.
Daarnaast wil ik ook Phillippe Broekmeyer van Jeugd & Muziek Brussel danken voor het aanbrengen van dit onderwerp. Zonder zijn onbevangen enthousiasme en problemen met het manueel opstellen van lesroosters had dit eindwerk misschien een ander onderwerp behandeld.
Tot slot dank ik natuurlijk ook nog alle familie en vrienden die geduldig naar mij luisterden de vele keren dat ik mijn onderzoek voor hen uit de doeken deed waardoor ik een steeds betere kijk op het geheel kreeg. In het bijzonder wens ik hier nog mijn echtgenote, An Devos, te vermelden, die vele eenzame avonden en nachten heeft doorgebracht en mij emotioneel en logistiek zeer sterk heeft gesteund.
2
Abstract Dit eindwerk beschrijft één van de vele manieren om, uitgaande van een databank met gegevens over docenten, studenten, lokalen, vakken en richtingen via een computerprogramma een uurrooster te genereren. Met uurrooster bedoele n we de grote verscheidenheid van lessenroosters en examenroosters die bestaan. In het programma is het mogelijk om met een set regels het gewenste uurrooster aan te duiden. Het merendeel van de uurroosters worden nog altijd manueel opgesteld. Dit vergt zeer veel tijd en levert, gemiddeld genomen, slechts werkbare uurroosters op. De studies die over dit onderwerp verschenen zijn, beschrijven bijna allemaal het probleem in één enkele onderwijsinstelling en zorgen voor een, zo efficiënt en optimaal mogelijke, oplossing voor die specifieke school. Deze oplossingen zijn dan in regel kwalitatief beter dan hun manuele broeders en kosten minder tijd om op te stellen. In deze bundel wordt een programma beschreven dat zo breed mogelijk toepasbaar is, en een aanvaardbare oplossing creëert in een aanvaardbare tijdspanne.
This thesis uses one of the many possible algorithms to generate a timetable with a computer program starting from a database with the information about the professors, students, classrooms, courses and departments. Timetable here means the large variety of school timetables and examination schedules that can occur. In this program it is possible to select the desired timetable through a set of constraints. Most of the timetables are still composed with pencil and paper. This requires a lot of time and, averagely spoken, merely results in useable timetables. The case studies that have been conducted on this subject, all start from the problems of one institute and describe the best and most efficient solution for that school. Those solutions are, averagely spoken, of a better quality than there manual variants and require less time. In this article, a program is outlined that is widely useable and that creates a reasonable solution in a reasonable amount of time.
3
Inhoudsopgave
Woord Vooraf .......................................................................................................................2 Abstract .................................................................................................................................3 Inhoudsopgave .....................................................................................................................4 Hoofdstuk 1:
Mogelijke onderlinge verbanden in een lesrooster
........................................................... 8 1.
Voorbeschouwing ........................................................................................................9
2.
Relaties..........................................................................................................................9 2.1.
Docent – Tijd.........................................................................................................9
2.2.
Docent – Vak ......................................................................................................10
2.3.
Docent – Klasgroep ...........................................................................................10
2.4.
Klasgroep – Tijd .................................................................................................10
2.5.
Klasgroep – Vak.................................................................................................10
2.6.
Vak – Tijd ............................................................................................................11
2.7.
Lokaal – Tijd .......................................................................................................11
2.8.
Lokaal – Docent .................................................................................................11
2.9.
Lokaal – Klasgroep ............................................................................................11
2.10. 3.
Lokaal – Vak ...................................................................................................12
Groepering ..................................................................................................................12 3.1.
Bespreking ..........................................................................................................12
3.2.
Samenvattende regels ......................................................................................13
3.2.1.
Docent .........................................................................................................13
3.2.2.
Vak/klasgroep.............................................................................................14
3.2.3.
Lokaal ..........................................................................................................14
3.2.4.
Tijd................................................................................................................15
3.2.5.
Intrinsieke regels ........................................................................................15
Hoofdstuk 2: .............................................. 16 Kernalgoritme ............................................. 16 1.
Complexiteit ................................................................................................................17 1.1.
Tijdsbeschouwingen..........................................................................................17 4
2.
3.
4.
1.2.
P en NP ...............................................................................................................17
1.3.
NP Complete ......................................................................................................18
1.4.
Uurroosterprobleem...........................................................................................18
Voornaamste algoritmen...........................................................................................20 2.1.
Complete Enumeration.....................................................................................20
2.2.
Direct Heuristics .................................................................................................21
2.3.
Graph Colouring .................................................................................................22
2.4.
Network Flow......................................................................................................22
2.5.
Simulated Annealing (SA) ................................................................................22
2.6.
Tabu Search (TS) ..............................................................................................23
2.7.
Genetic Algorithms (GA)...................................................................................24
2.8.
Constraint Satisfaction (CSP)..........................................................................25
2.9.
Integer Lineair programmeren.........................................................................25
2.10.
Expert systemen ............................................................................................26
2.11.
Andere .............................................................................................................26
Genetic Algorithms ....................................................................................................27 3.1.
Motivatie ..............................................................................................................27
3.2.
Overzicht van het genetisch algoritme ...........................................................28
3.3.
Implementatiefacetten.......................................................................................30
3.3.1.
Codering ......................................................................................................30
3.3.2.
Reproductieproblemen..............................................................................31
3.3.3.
De eigenlijke voortplanting .......................................................................33
3.3.4.
Mutatie .........................................................................................................38
3.3.5.
Convergentie ..............................................................................................39
3.3.6.
Parameters .................................................................................................40
Toepassing van het GA ............................................................................................42 4.1.
De implementatie ...............................................................................................42
4.2.
Klassieke GA ......................................................................................................43
4.2.1.
Cyclus ..........................................................................................................43
4.2.2.
Parameters .................................................................................................44
4.3.
CHC GA...............................................................................................................44
4.3.1.
Cyclus ..........................................................................................................44
4.3.2.
Parameters .................................................................................................45
4.3.3.
Pseudocode................................................................................................45 5
4.4.
Genetische sequentie .......................................................................................46
4.4.1.
Doelstelling .................................................................................................46
4.4.2.
1e Ontwerp ..................................................................................................46
4.4.3.
2e Ontwerp ..................................................................................................47
4.4.4.
3e Ontwerp ..................................................................................................48
4.4.5.
4e Ontwerp ..................................................................................................49
4.4.6.
Vergelijking en keuze ................................................................................49
Hoofdstuk 3: Opbouw van het programma (UML) ................ 50 1.
Het Takendiagram .....................................................................................................51
2.
Het Klassenmodel......................................................................................................53 2.1.
3.
4.
Relaties:...............................................................................................................54
De Sequentiediagrammen........................................................................................55 3.1.
Haal de benodigde gegevens op ....................................................................55
3.2.
Definieer het lesrooster & Configureer het GA .............................................56
3.3.
Stel het lesrooster op ........................................................................................57
Woordenboek .............................................................................................................58
Hoofdstuk 4: Implementatieverloop .......................... 62 1.
2.
3.
4.
Studie...........................................................................................................................63 1.1.
Algemeen ............................................................................................................63
1.2.
GA ........................................................................................................................63
Onderzoek...................................................................................................................63 2.1.
Een goede GA implementatie..........................................................................63
2.2.
Lesroosters .........................................................................................................65
2.3.
Regels als definitietaal ......................................................................................65
2.4.
Een lesrooster in een klassemodel.................................................................66
Implementaties ...........................................................................................................66 3.1.
1e implementatie ................................................................................................66
3.2.
Gui en databanktoegang ..................................................................................67
3.3.
CHC GA...............................................................................................................67
3.4.
Definitief ontwerp ...............................................................................................67
3.5.
Laatste implementatie .......................................................................................67
Besluiten van de implementatie...............................................................................68
Hoofdstuk 5: Besluit ...................................... 69 1.
Besluit ..........................................................................................................................70 6
1.1.
Oplossingsmethode...........................................................................................70
1.2.
Klassieke GA of CHC GA .................................................................................71
1.3.
Het definiëren van lesroosters .........................................................................72
1.4.
Samenvatting ......................................................................................................73
2.
Mogelijke verbeteringen............................................................................................73
3.
Andere onderzoekspistes .........................................................................................74
Referenties..........................................................................................................................76
7
Hoofdstu k 1: Mogelijke onderlinge verbanden in een lesrooster
8
1.
Voorbeschouwing
Om een lesrooster in zoveel mogelijk omstandigheden bruikbaar te maken, is het nodig om alle mogelijke relaties tussen de verschillende facetten te voorzien en instelbaar te maken. Facetten die vergeten zijn, maken direct bepaalde soorten roosters onmogelijk. Het is niet de bedoeling om alles te voorzien, dit zou te ver leiden, maar wel om zoveel mogelijk te voorzien. Er zullen steeds speciale lesroosters bestaan die niet in het geïmplementeerde keurslijf passen. Zo zullen speciale relaties die enkel nuttig zijn voor uurroosters voor individueel onderwijs, niet opgenomen worden in de mogelijkheden van het programma. De bedoeling van dit hoofdstuk is om alle regels te verzamelen die uit de relaties voortvloeien. Deze regels zullen het mogelijk maken om met één bepaalde groep gegevens verschillende roosters te bouwen, naargelang de omstandigheden dat vereisen. Alle regels worden beschouwd vanuit de invalshoek van de ‘speler’. De ‘spelers’ zijn ‘docenten’, ‘studenten/klasgroepen’, ‘vakken’ en ‘lokalen’. Behalve deze gebruikersset aan regels, worden ook de verborgen voorwaarden opgesomd zodat een student enkel die vakken volgt waarvoor hij ingeschreven is.
2.
2.1.
Relaties
Docent – Tijd
• gewenste lesdagen (lesuren) • ongewenste lesdagen (lesuren) • onmogelijke lesdagen (lesuren) • spreiding lestijden (in blok of met pauzes) • moet vastgesteld aantal lesuren hebben (maximum ? minimum) • moet vastgesteld aantal labo-uren hebben (maximum ? minimum) • middagpauze 9
2.2.
Docent – Vak
• docent assisteert in vak • docent geeft enkel les in vakken waarin aangesteld • docent moet minstens één keer toegewezen zijn aan vak • 1 docent meerdere vakken op hetzelfde moment • vak moet docent hebben • 1 vak meerdere docenten op hetzelfde moment
2.3.
Docent – Klasgroep
• 1 docent meerdere klassen op hetzelfde moment • docent moet klas hebben om les aan te geven • 1 klas meerdere docenten op hetzelfde moment • klas moet docent hebben
2.4.
Klasgroep – Tijd
• spreiding van de lessen (wenselijkheid springuren – examens niet te dicht opeen) • meerdere keren les op hetzelfde moment (normaal nooit) • middagpauze
2.5.
Klasgroep – Vak
• klas moet vak hebben (in het juiste aantal lesuren) • 1 klas meerdere vakken op hetzelfde moment • vak moet gevolgd worden door klas • 1 vak meerdere klassen op hetzelfde moment • meerdere klasgroepen samen voor dat vak • klas volgt enkel vakken waarvoor ingeschreven • maximaal aantal studenten voor het vak
10
2.6.
Vak – Tijd
• vak moet doorgaan • mag meerdere keren op hetzelfde moment • moet meerdere keren op hetzelfde moment • tijdsduur gerespecteerd
2.7.
Lokaal – Tijd
• lokaal moet bezet zijn • simultaan gebruikt voor meerdere lessen • onmogelijke tijdstippen (dag – uur)
2.8.
Lokaal – Docent
• docent aanwezig in verschillende lokalen op hetzelfde moment • docent moet lokaal hebben • docent steeds zelfde lokaal / verdieping / gebouw / site • meerdere docenten in 1 lokaal • voldoende tijd bij lokaaltransities
2.9.
Lokaal – Klasgroep
• klas moet lokaal hebben • 1 klas meerdere lokalen op hetzelfde moment • lokaal moet klas bevatten • 1 lokaal meerdere klassen op hetzelfde moment • maximale bezetting / bezettingsgraad • minimale bezetting / bezettingsgraad • voldoende tijd bij lokaaltransities • klas steeds zelfde lokaal / verdieping / gebouw / site
11
2.10. Lokaal – Vak • vak moet lokaal hebben • 1 vak meerdere lokalen op hetzelfde moment • in lokaal moet vak doorgaan • 1 lokaal meerdere vakken • benodigd audiovisueel materiaal • vak steeds zelfde lokaal / verdieping / gebouw / site
3.
3.1.
Groepering
Bespreking
Uit de opsomming blijkt dat er een aantal types van voorwaarden opduiken. Een steeds opduikend duo is: “moet voorkomen – mag meerdere keren voorkomen”. Dit kan het best beschreven worden door een multipliciteit toe te kennen en dan aan te duiden of de multipliciteit maximaal, minimaal of exact is. De relaties zijn gericht; er is een duidelijk verschil in de relatie docent-klasgroep en de relatie klasgroep-docent. Het is mogelijk dat een docent op bepaalde tijdstippen aan meerdere klasgroepen lesgeeft, terwijl de klasgroepen op elk moment slechts mogen voorzien zijn van één docent. Als we de vakken en klassen algemeen beschouwen dan zien we dat sommige kunnen samengevoegd worden tot één geheel. Elke klas zit in een bepaalde richting en heeft een vastgesteld pakket aan vakken. Dit geeft echter een zekere beperking aan het algoritme. Als meerdere klassen les hebben in éénzelfde vak, is het logisch dat die gegroepeerd worden. Deze groepering niet automatisch laten verlopen, zorgt voor een beperkt aantal mogelijke combinaties.
12
Een dynamische benadering bestaat erin dat de klassen bij hun vak gegroepeerd zitten, eventueel in monstergroepen, en dat deze klassen dynamisch gesplitst worden. Een eerste probleem dat hierbij opduikt, is de gelijkheid van de verdeling. En een volgend probleem is het aantal uren dat de docent ervoor toegewezen krijgt. Het kan zijn dat een bepaald vak in vier keer gegeven moet worden, maar dat het programma een auditorium toekent waarin de les in één keer gegeven kan worden. Een andere mogelijkheid is de klas in mini-klasgroepen opdelen die elk een vak vo lgen en bij deze klas/vakcombinaties aanduiden dat deze simultaan in hetzelfde lokaal mogen. Het voor de hand liggende probleem dat dan opduikt, is dat het programma de neiging zal vertonen enorm veel groeperingen te vormen en zo een docent veel te veel uren te laten presteren. Om de vakken en klasgroepen als één geheel te kunnen beschouwen, moeten er dus nog drie extra voorwaarden opgelegd worden. De eerste twee passen het gemakkelijkst in de relatie docent-vak/klasgroep; we hebben hier als extra een ‘splitsingsmultipliciteit’ of ‘groeperingsmultipliciteit’ en een ‘evenwicht in verdeling’ voorwaarde. De derde voorwaarde is intern in de vak/klasgroep. Het gaat om de ‘mag gegroepeerd worden met’ voorwaarde. Deze voorwaarde kan intrinsiek vastgelegd worden. Twee vak/klasgroepen mogen dan gegroepeerd worden als de vakken he tzelfde zijn. Om deze relaties praktisch te kunnen toepassen, vatten we alle mogelijkheden samen in enkele eenvoudige regels die een lesrooster kunnen definiëren. Deze regels zijn letterlijk terug te vinden in het programma.
3.2.
Samenvattende regels
3.2.1. •
Docent
Gewenste lesmomenten (weekdag en ochtend, voormiddag, namiddag of avond)
•
Ongewenste lesmomenten (weekdag en ochtend, voormiddag, namiddag of avond)
•
Lessen spreiden of lessen groeperen tot blokken
13
•
Maximum, minimum of exact aantal lesuren of labo-uren, algemeen of per vak, als docent of als assistent
•
Maximum, minimum of exact aantal vakken simultaan
•
Maximum, minimum of exact aantal klasgroepen simultaan
•
Maximum, minimum of exact aantal lokalen toegewezen op hetzelfde moment
•
Lessen gegeven in zelfde lokaal, zelfde verdieping, zelfde gebouw, zelfde site
•
Voldoende tijd bij lokaaltransities
3.2.2. •
Vak/klasgroep
Altijd of nooit groeperen van vak/klasgroepen met dezelfde klasgroep maar met verschille nd vak
•
Altijd of nooit groeperen van vak/klasgroepen met hetzelfde vak maar met een verschillende klasgroep
•
Maximum,
minimum
of
exact
aantal
studenten
bij
groeperen
van
vak/klasgroepen met hetzelfde vak maar met een verschillende groep •
Maximum, minimum of exact aantal docenten simultaan
•
Maximum, minimum of exact aantal lokalen toegewezen op hetzelfde moment
•
Lessen spreiden of lessen groeperen tot blokken
•
Lessen aan klasgroep in zelfde lokaal, zelfde verdieping, zelfde gebouw, zelfde site
•
Voldoende tijd bij lokaaltransities
•
Audiovisueel materiaal is vereist, is niet vereist of is bij voorkeur aanwezig
3.2.3. •
Lokaal
Gewenste bezettingsmomenten (weekdag en ochtend, voormiddag, namiddag of avond)
•
Ongewenste bezettingsmomenten (weekdag en ochtend, voormiddag, namiddag of avond)
•
Maximale, minimale of exacte bezettingsgraad
•
Maximum, minimum of exact aantal klasgroepen (studenten) simultaan
•
Maximum, minimum of exact aantal docenten simultaan
•
Maximum, minimum of exact aantal vakken simultaan 14
3.2.4.
Tijd
Dit zit niet in regels, maar in een schema vervat. De gebruiker moet dit tijdschema, waarin het lesrooster moet passen, definiëren. Het standaard schema is een week bestaande uit vijf dagen. Elke dag bestaat dan weer uit een ochtend, een voormiddag, een middagpauze, een namiddag en een avond. Elk dagonderdeel, behalve de middagpauze, bestaat uit twee lesperiodes. Op elk niveau, in elk blokje kan een begin en eindtijd vastgelegd worden. Het programma kijkt enkel naar de laagst gedefinieerde tijden. Als een dag loopt tussen 8u en 17u en het avondblokje is vastgelegd als liggende tussen 16u en 20u, dan zal het programma uitgaan van dagen die gaan van 8u tot 20u. Natuurlijk is de gebruiker niet gebonden aan een schema bestaande uit 5 werkdagen. Dit is, net als het aantal periodes in een dag en het aantal lessen in een periode, naar eigen wens aanpasbaar. De middagpauze is een speciaal blokje dat altijd moet voorkomen. Dit is eigenlijk gewoon een tijdsduur die bepaalt hoeveel tijd er minimum tussen de lessen van de voormiddag en de namiddag moet liggen. In het programma kunnen ook nog een stel regels opgenomen worden die deze tijden soms wel en soms niet afdwingbaar maken.
3.2.5.
Intrinsieke regels
•
Docenten geven enkel les in vakken waarvoor ze aangesteld zijn
•
Lesduur overschrijdt het opgestelde tijdschema niet
•
Alle vakken moeten gepland worden
•
Niet ingestelde regels worden ingesteld volgens standaard waarden indien nodig
15
Hoofdstu k 2: Ker nalgoritme
16
1.
1.1.
Complexiteit
Tijdsbeschouwingen
Een algoritme wordt beschouwd als “goed” als het efficiënt genoeg is om praktisch bruikbaar te zijn. Om de efficiëntie te meten, wordt de uitvoeringstijd in het slechtste geval bekeken. Een “goed” algoritme wordt uitgevoerd in polynomiale tijd. Dit betekent dat voor een probleem van grootte n, de uitvoeringstijd, in zijn slechtste geval, kan uitgedrukt worden als een polynomiale functie van n. Met tijd wordt hierbij niet het aantal seconden bedoeld, maar wel het aantal eenvoudige operaties (optelling, toewijzing, vergelijking,…) dat het algoritme nodig heeft om tot een oplossing te komen. Er zijn ook “slechte” algoritmen. Deze hebben een uitvoeringstijd die een exponentiële of meer dan exponentiële functie van n is. Als de grootte van het probleem (n) toeneemt, dan kan de uitvoeringstijd van het algoritme onbruikbaar lang worden. Afhankelijk van het probleem kan dit zeer snel problematische proporties aannemen. De problemen worden onderverdeeld in twee klassen: “gemakkelijk” (“easy”) en “moeilijk” (“hard”). Een “moeilijk” probleem is een probleem dat enkel met een “slecht” algoritme kan opgelost worden.
1.2.
P en NP
Het is soms mogelijk om een probleem te reduceren tot een ander (eenvoudiger) probleem. Als er nu voor probleem A een reductie bestaat die, in polynomiale tijd, probleem A omvormt tot probleem B, en als probleem B oplosbaar is in polynomiale tijd, dan is probleem A oplosbaar in polynomiale tijd. Dit geeft tot gevolg dat de problemen netjes onderverdeeld kunnen worden in twee klassen: P en NP. P bevat alle beslissingsproblemen die in polynomiale tijd oplosbaar zijn. NP bevat alle beslissingsproblemen die niet in polynomiale tijd oplosbaar zijn.
17
Er zijn nog andere mogelijke definities die dezelfde scheiding tussen N en NP aanbrengen.
1.3.
NP Complete
Een beslissingsprobleem A, behorende tot de klasse van NP problemen, wordt NP Complete genoemd als elk NP probleem op polynomiale wijze getransformeerd kan worden tot A. Men kan ook stellen als een probleem A op polynomiale wijze te transformeren is tot een NP Complete probleem B, dat A ook een probleem is dat tot de NP Complete klasse behoort. Dit geeft als gevolg dat als er ooit een oplossing in polynomiale tijd gevonden wordt voor een probleem dat NP Complete is, er geen klasse van NP problemen meer is. Er dient opgemerkt te worden dat er een verschil is tussen transformeren en reduceren. Reduceren vermindert de complexiteit van een probleem, terwijl een transformatie een reductie is die alle nuances van het originele probleem intact houdt. Een transformatie is een symmetrische relatie en een reductie is dit niet. Een probleem dat bekomen wordt door reductie van een NP Complete probleem is niet NP Complete. Dit betekent niet dat de oplossing hiervan eenvoudiger geworden is. Deze problemen noemt men “NP hard“. De verzameling van de problemen die NP hard zijn, is niet beperkt tot beslissingsproblemen.
1.4.
Uurroosterprobleem
Het is zeer moeilijk te bewijzen dat een probleem NP is. Voor de meeste problemen heeft men het vermoeden dat ze NP zijn, maar is men er nog niet in geslaagd om dit te bewijzen. Dit geldt ook voor het uurroosterprobleem. Het uurroosterprobleem kan op twee manieren opgelost worden : door benaderingsmethodes of exact. In het geval van NP problemen, zal men meestal niet kiezen voor de exacte oplossing omdat het onaanvaardbaar lang duurt om deze te vinden. Daarom zal men meestal proberen de oplossing te benaderen. De benaderingsmethodes leveren meestal goede resultaten en soms zelfs de exacte oplossing. Spijtig genoeg leveren de meeste heuristische algoritmen soms ook slechte oplossingen af. Bij deze methodes zal men meestal proberen om de situaties die tot een slechte oplossing leiden, op voorhand vast te stellen en te vermijden.
18
De heuristische methodes vallen over het algemeen uiteen in twee groepen: de deterministische methodes en de niet-deterministische. Bij deze laatste groep is, ofwel de tijd die nodig is om tot een oplossing te komen, ofwel de kwaliteit van de oplossing o nbekend. De meeste algoritmen kunnen op twee manieren geprogrammeerd worden. Dit geeft een opdeling in specifieke en algemeen toepasbare oplossingen. De algemene oplossingen vergen meer tijd om tot een goed resultaat te komen. Het voordeel is, dat bij een verandering van het probleem, enkel een paar parameters aangepast moeten worden of hier en daar een klein stukje code moet herbekeken worden. In extremis kan het programma zelfs doodgewoon uitgevoerd worden met de andere gegevens. De probleemspecifieke algoritmen zijn dan weer interessant om een betere performantie te bekomen, maar moeten grotendeels tot volledig herschreven worden bij een wijziging in het probleem. Bij enkele van de algemeen toepasbare algoritmen op combinatorische problemen is het niet alleen mogelijk om, met grotendeels dezelfde code, vele variaties van he tzelfde probleem op te lossen, maar ook andere combinatorische problemen. Heuristische methodes zijn veelal afgeleid uit een manier waarop in de werkelijke wereld een oplossing voor het probleem gevonden wordt. Het spreekt voor zich dat de manueel gebruikte methodes geen enkele garantie hebben tot het vinden van de oplossing. Omdat deze kritische noot veel vergeten wordt, wordt soms zeer veel tijd gestoken in het modelleren van oplossingsmethodes waar uiteindelijk geen betere garantie op een optimale oplossing gegeven wordt dan de garantie die de manuele methode gaf. Dit nadeel wordt dan meestal opgevangen door de gebruiker een grotere controle over het verloop van het programma te geven, waardoor er met eenvoudige methodes toch een zeer goed resultaat kan bereikt worden in aanzienlijk kortere tijd dan met de volledig manuele methoden.
19
2.
2.1.
Voornaamste algoritmen
Complete Enumeration
Dit is eigenlijk de gemakkelijkste en de meest perfecte oplossing voor het probleem. Alle andere, hierna besproken algoritmen zijn benaderi ngen. Het is mogelijk om alle oplossingen op te sommen, automatisch te evalueren, en het gewenste uurrooster eruit te filteren. Er is enkel één probleem : tijd ! Dit algoritme is namelijk ongelooflijk inefficiënt. Bij lesroosters heeft men vijf facetten: de tijd, de studenten, de docenten, de vakken en de lokalen. Het lesroosterprobleem is dus een vijfdimensioneel probleem. Dit zorgt ervoor dat het aantal mogelijke combinaties zeer sterk stijgt als één van de facetten toeneemt. Bij een school van gemiddelde omvang zou het berekenen van de oplossing via deze methode eigenlijk wel een tiental jaren kunnen duren.
Laten we eens ruwweg het aantal combinaties nagaan voor een school met een 100 klasgroepen, een 400 vakken en een 200 docenten. Aangezien de studenten in een richting inschrijven, en in die richting de vakken vastliggen, kunnen we de vakken aan de klasgroepen koppelen. Als we de klasgroepen als een kleinste, ondeelbaar geheel beschouwen, dit wil zeggen dat een reële klas uit meerdere klasgroepen bestaat die, bijvoorbeeld, voor keuzevakken wel eens opsplitsen, en als we beschouwen dat elke klas 6 verschillende vakken volgt, dan komen we aan een 2400 bouwsteentjes. Nu zijn er nog docenten die aan een vak kunnen toegewezen worden. Stel dat gemiddeld gezien twee docenten per vak voorzien zijn. Dit brengt het totale aantal combinaties op 4800. Laten we veronderstellen dat er zich geen problemen kunnen voordoen met de lokalen en dat deze dus buiten beschouwing kunnen gelaten worden. Dan blijft nog enkel het plaatsen in een uurrooster over. Dit komt neer op alle intern mogelijke combinaties van de elementen van de verzameling. De complete enumeration zou in dit voorbeeld dus een slordige 4800 faculteit aan mogelijkheden moeten overlopen. 20
Dit is ongeveer 3,8 x 1015587. Zelfs met de snelste processoren is het ondoenlijk om dit probleem op deze wijze op te lossen binnen de levensspanne van de aarde.
2.2.
Direct Heuristics
Deze methode probeert volgens een vastgesteld schema alle lesuren te plaatsen in een lesrooster. Eigenlijk probeert men hier de computer een vereenvoudigde en formelere variant van de manueel gebruikte methode op te leggen. Door een aantal vuistregels op voorhand vast te leggen en daarna efficiënt te implementeren, kan de computer een goed uurrooster samenstellen. De snelheid van het programma kan niet gegarandeerd worden. In het beste geval: zeer snel O(n) – in het slechtste geval: zéér traag (jaren). Het programma is zeer sterk afhankelijk van de situatie waarin het gebruikt wordt. Als er een oplossing bestaat, en er wordt voldoende tijd uitgetrokken, dan wordt deze doorgaans gevonden. Het is wel zo dat als er zich situaties voordoen waar de heuristieken niet tegen opgewassen zijn, het algoritme meestal op zeer grondige wijze zal falen. In regel moeten alle mogelijke situaties voorzien zijn in de vuistregels. Een voorbeeld van een set vuistregels: -
Wijs het meest beperkte vak toe aan de meest geschikte periode
-
Als voor een periode slechts één vak in aanmerking komt, wijs dit vak toe aan die periode
-
Als een vak in een bezette periode moet toegewezen worden, verplaats dan het reeds tot die periode toegewezen vak naar een andere periode
Deze eenvoudige vuistregels voorzien alle omstandigheden. Ze wijzen een vak toe volgens een bepaald systeem en als de plaats bezet is, dan gebeurt een soort backtracking, die in extremis tot aan de eerst geplaatste les kan teruggaan en al het gedane werk nog eens herbegint. De vermelde verzameling heuristieken zal slechts in eenvoudige problemen soelaas bieden. Zo zal er voor grotere problemen zeker een vuistregel moeten voorzien zijn die belet dat de backtracking te ver gaat en die een alternatief biedt in dergelijke situaties.
21
2.3.
Graph Colouring
Bij deze methode wordt het uurroosterprobleem herleid tot het inkleuren van een graaf. Dit is een uitgebreid onderzocht probleem met goed gekende oplossingsmethodes. In zijn meest algemene vorm is dit probleem NP Complete. Het is mogelijk om bij de reductie het probleem te beperken, zodat er niet langer sprake is van een zuivere Graph Colouring. Men kan door voldoende kennis van het probleem vermijden dat de slechtste performantie optreedt en een polynomiale uitvoeringstijd mogelijk maakt. Deze reductie zelf is niet in alle omstandigheden mogelijk en er is voorkennis van het probleem nodig. Doordat de reductie sterk probleemspecifiek beschreve n moet worden, is dit geen flexibele oplossingsmethode.
2.4.
Network Flow
Het opstellen van een lesrooster kan ook herleid worden tot het berekenen van de stroom doorheen een stroomnetwerk. Het oplossen van stroomnetwerken bekomen door de reductie van de lesroosters is nauwelijks een verbetering in complexiteit. Eén van de beschreven oplossingsmethodes voor een stroomnetwerk is een verdere reductie tot Graph Colouring. De kritieken ten overstaan van Graph Colo uring gelden ook voor de Network Flow. De uitgedachte oplossingen met het Network Flow algoritme worden in de praktijk bijna niet meer toegepast.
2.5.
Simulated Annealing (SA)
Dit is een algemeen optimalisatie-algoritme bedoeld om goede oplossingen te vinden bij zeer moeilijke optimalisatieproblemen. Het is geïnspireerd op de tempering van metalen. Door het proces van tempering probeert men in de werkelijke wereld solide materialen te bekomen met een zeer lage potentiële energie. Deze methode probeert, bij elke ronde, lokaal, op willekeurige wijze, kleine wijzigingen door te voeren. Als deze wijziging geëvalueerd wordt als een verbetering van de huidige situatie, dan zal deze doorgevoerd worden. Als de wijziging het huidige “energieniveau” doet stijgen, dan zal de nieuwe toestand aanvaard worden met een kans die afhankelijk is van de huidige “temperatuur”.
22
De “temperatuur” daalt na elke ronde. Dit heeft twee gevolgen. Ten eerste is de SA beperkt in tijd; het algoritme wordt uitgevoerd totdat een vooraf vastgestelde “eindtemperatuur” bereikt wordt, of totdat de evaluatie van het resultaat onder een bepaalde waarde gaat. Vervolgens daalt bij het dalen van de temperatuur de kans dat slechte oplossingen aanvaard worden. Het grote nadeel van deze methode is dat het optimum slechts lokaal kan gegarandeerd worden. Door kennis van de zoekruimte kan het algoritme aangepast worden zodat het kan ontsnappen aan lokale optima. De kans op lokale optima wordt trouwens zeer sterk verkleind als de temperatuur op voldoende trage wijze daalt. Als de methode niet struikelt in een lokaal optimum, dan levert deze methode een goede oplossing in een goede tijd op.
2.6.
Tabu Search (TS)
Dit algoritme werd oorspronkelijk gedefinieerd als een gevorderde heuristische procedure voor optimalisatieproblemen, ontworpen om andere methoden (of compone nten ervan) te helpen ontsnappen aan de val in lokale optima. Er is veel onderzoek geweest naar dit principe en dit heeft ervoor gezorgd dat de Tabu Search een losstaande en waardevolle optimalisatieoplossing werd. Het doel van de Tabu Search is het minimaliseren (maximaliseren) van een functie onder bepaalde beperkingen. Om dit doel te bereiken wordt in de omgeving van de huidige oplossing naar een nieuwe oplossing gezocht. Deze wijziging gebeurt door een “move” die meestal symmetrisch van aard is (dit wil zeggen dat er een inverse “move” bestaat die van de nieuwe naar de oude oplossing terugkeert). Als een functie geoptimaliseerd wordt, dan kan het zijn dat de oplossing gevangen zit in een lokaal optimum. De enige manier om uit die val te ontsnappen, is een move naar een omgeving die minder optimaal is dan de huidige. Als dit zonder meer toegestaan wordt, dan zullen er lussen ontstaan. Om dit tegen te gaan wordt een Tabu-list gebruikt. De Tabu-list zorgt ervoor dat de omgeving van de huidige oplossing beperkt wordt zodat het algoritme steeds verder gaat met zoeken en niet op z’n schreden terugkeert. Als een move een belangrijke verbetering in de te minimaliseren functie teweegbrengt, dan wordt de Tabu-list leeggemaakt. 23
Het algoritme biedt ook de mogelijkheid om in deelgebieden van “goede” kwaliteit op een intensere wijze te zoeken. Ook kan er door gebruik te maken van de kennis van de zoekruimte op een gerichte wijze gezocht worden. Deze methode biedt een redelijke garantie op een goede oplossing. De optimale oplossing kan ook hier niet gegarandeerd worden. Als de methode tot een oplossing komt, dan is deze oplossing veelal het optimum. Deze methode is trager dan SA en heeft veel meer systeembronnen nodig. De oplossing kan met een veel hogere zekerheid gewaarborgd worden. Om de “random move” op zinvolle en efficiënte wijze te kunnen implementeren is kennis van de zoekruimte vereist, wat in het geval van lesroosters deels afhankelijk is van het soort lesrooster dat vereist wordt.
2.7.
Genetic Algorithms (GA)
GA stelt een intelligent gebruik van een willekeurig zoekmechanisme voor om optimalisatieproblemen op te lossen. Het maakt gebruik van historische informatie (vorige generaties) om gerichter te zoeken naar en in specifieke gebieden en zo efficiënter de zoekruimte te doorkruisen. Dit optimalisatie-algoritme is gebaseerd op de processen die de natuur gebruikt voor evolutie, meer bepaald de “survival of the fittest”. Er wordt gestart met een grote populatie van oplossingen. Deze worden elk volkomen geëvalueerd en gerangschikt volgens “fitness” toestand. De gezondste oplossingen worden dan op willekeurige wijze gekruist. De “offspring” die op deze wijze bekomen wordt, vormt dan de nieuwe populatie van waaruit dan nieuwe nakomelingen gegenereerd worden. De oplossing stopt als een telg een vooraf bepaalde “fitness” behaalt of na een maximaal aantal herhalingen. Het bereiken van de optimale oplossing kan niet gegarandeerd worden. In praktische simulaties echter, bereikt deze methode, indien op juiste wijze geïmplementeerd, een oplossing die altijd in de nabije omgeving van een algemeen optimum ligt. Het algoritme is grotendeels onafhankelijk van het probleem.
24
2.8.
Constraint Satisfaction (CSP)
Dit is een oplossingsmethode die sterk aanleunt bij de problematiek van de lesroosters. De oplossing wordt gedefinieerd door een set van beperkingen (Constraints) die aan de data opgelegd wordt. Er zijn twee grote opsplitsingen in de wijze van oplossen. De oudste methode is het toepassen van alle beperkingen terwijl de data stap voor stap toegevoegd worden, en indien het niet meer mogelijk is om data toe te voegen, de beperkingen één voor één te verzachten. De andere methode is starten met een beperkte set van beperkingen op de oplossing en vervolgens telkens een beperking toevoegen tot de oplossing onmogelijk is of alle beperkingen opgelegd zijn. Als nog niet alle beperkingen opgelegd zijn, probeert men de resterenden in versoepelde vorm op te leggen. De kracht van deze methode is dat er een oplossing kan worden bereikt, ook al bestaat er strikt genomen geen. De oplossing zal altijd dicht aanleunen bij de gewenste oplossing. Deze methode is een wijze om naar het probleem te kijken en een systeem om het probleem aan te pakken. De concrete invulling van het lesrooster kan dan met andere oplossingsmethoden. Veelal wordt een heuristische, incrementele methode gebruikt. Er zijn voor deze oplossing verschillende tools/solvers ontwikkeld en eveneens speciale hardware.
2.9.
Integer Lineair programmeren
Deze methode maakt gebruik van de reductie van het probleem tot een stelsel ongelijkheden. De variabelen in dit stelsel zijn doorgaans van het binaire type. Door toepassing van bestaande oplossingsmethodes op stelsels aangereikt door de algebra, worden de stelsels zeer snel opgelost. Deze methode is, gemiddeld genomen, potentieel de snelste. Het reduceren van verschillende soorten lesroosterproblemen op dynamische wijze, is uitermate complex en vereist een zeer groot wiskundig inzicht. Het is niet duidelijk of dit zelfs mogelijk is.
25
2.10. Expert systemen Dit zijn systemen waarbij men alle kennis en denkpatronen die een mens gebruikt om lesroosters op te stellen, samenvat in een verzameling regels. Deze regels worden dan toegepast op het probleem. Deze methode is sterk verwant aan de direct heuristics. Het grootste probleem van dit systeem is dat de kennis van een expert, of een groep experten, in het opstellen van lesroosters nodig is en dat echt alle uitzonderi ngen en mogelijke situaties beschreven moeten worden. Dit is praktisch zeer moeilijk te verwezenlijken. In mijn onderzoek heb ik enkele theoretische modellen ontdekt maar, in tegenstelling tot de voorgaande methodes, geen enkele aanwijzing dat dit systeem praktisch ooit werkbaar geïmplementeerd is. De kritiek die in het begin van dit hoofdstuk vermeld is, is hier zeer toepasbaar. Het is niet gegarandeerd dat methodes gebruikt bij het manueel opstellen van lesroosters tot het exacte optimum leiden. Anderzijds dient wel opgemerkt te worden dat een gebruiker waarschijnlijk nooit in een programma het lesrooster zal kunnen definiëren zoals hij het in zijn gedachten heeft, waardoor het resultaat waarschijnlijk nooit met zijn beeld van een ideaal lesrooster zal overeenstemmen.
2.11. Andere Op dit moment zijn er nog enkele andere oplossingsmethodes die onderzocht worden. De meeste hiervan zijn nog in het stadium van theoretisch onderzoek. Als belangrijkste kunnen we vermelden dat er een aantal ambitieuze projecten opgestart zijn om een oplossing te beschrijven met wat de onderzoekers omschrijven als “Meta Heuristics”. Deze methode ziet er veelbelovend uit, maar is tot nu toe nog niet praktisch toepasbaar gebleken. De “Meta Heuristics” draait om een systeem van heuristieken die heuristieken moet kiezen die het probleem te lijf gaan. Bij elke stap wordt opnieuw gekeken welke heuristiek de volgende in het rijtje is om de oplossing te vervolledigen.
26
3.
Genetic Algorithms
3.1.
Motivatie
Om een omnivalent aanpasbaar lesrooster op te stellen, is in deze studie een genetisch a lgoritme gekozen als kern. De hoofdreden hiervoor is de relatief grote onafhankelijkheid tussen het algoritme en het eigenlijke probleem. Een andere reden is dat, in de praktijk, dit algoritme goede resultaten haalt in een redelijke tijdspanne. De willekeurigheid van de selectie en de wijze waarop de volgende generaties samengesteld worden, maken het mogelijk dat, als er andere evenwaardige oplossingen bestaan, het programma deze kan vinden door eenvoudigweg nogmaals uitgevoerd te worden met dezelfde beperkingen en gegevens. Dit is zeer handig in situaties waarbij blijkt dat de voorziene beperkingen niet alle gewenste of noodzakelijke beperkingen kunnen beschrijven of in situaties waarbij de planner zich gevoelsmatig niet gelukkig voelt met een resultaat. Als het verschil tussen wat in het programma kan worden aangegeven en wat moet beschreven worden niet te groot is, dan zal het algoritme, mits enkele pogingen, toch een goed resultaat geven. Het algoritme is van niet-deterministische aard en zal altijd een benadering van de ideale oplossing vormen. Dit is zeer praktisch als er dermate veel beperkingen opgelegd zijn, dat er geen lesrooster meer op te stellen valt dat aan alle voorwaarden vo ldoet. Als duidelijk nadeel kan gesteld worden dat dé oplossing meestal net niet zal gevonden worden. Dit is echter een eigenschap van alle niet-deterministische algoritmen. De oplossing gegenereerd door het algoritme is meestal van een goede tot zeer goede kwaliteit als de populatie groot genoeg gekozen is, de kans op productie van kinderen en de kans op mutatie op verstandige wijze ingesteld is. Het algoritme kan geprogrammeerd worden met een generische kern, die zijn informatie (genetische sequentie) krijgt van een vertaalfunctie, en zijn fitheidscores van een eventueel externe fitheidfunctie
27
3.2.
Overzicht van het genetisch algoritme
GA’s zijn gebaseerd op de analogie met de genetische structuur en het gedrag van de chromosomen zoals deze in de natuur in een populatie voorkomt. Ze gebruiken hiervan de volgende basisprincipes: • Individuen in een populatie gaan in strijd met elkaar voor overleving en voortpla ntingspartners. • De meest succesvolle individuen zullen meer nageslacht voortbrengen dan de minder succesvolle. • Genen van ‘sterke’ individuen worden doorgegeven naar de volgende generatie, waardoor de kinderen veelal beter zijn dan hun ouders. • Elke volgende generatie is steeds beter “thuis” in zijn omgeving. Een GA houdt een populatie van individuen bij, waarbij elk individu een oplossing van het probleem voorstelt. Een individu wordt gecodeerd als een vector met eindige lengte, bestaande uit verschillende componenten of variabelen. Om de genetische analogie op te houden, worden de individuen chromosomen genoemd en hun bouwstenen genen. Een chromosoom is samengesteld uit verschillende genen. Een allel is een gen met een specifieke waarde. De positie van een gen in een chromosoom is de locus. De string die het chromosoom voorstelt, wordt het genotype genoemd en de interpretatie van het genotype naar het probleem toe, wordt het fenotype genoemd. De fitheidscore die aan elke oplossing wordt toegekend, drukt zijn mogelijkheid uit tot voortplanting. Het is de bedoeling om een individu te vinden met een optimale of bijna optimale fitheidscore. Het doel van het GA is om door een selectieve kweek van de oplossingen een nageslacht te produceren dat betere oplossingen voorstelt. Dit gebeurt door de recombinatie van de informatie in de chromosomen van de ouders.
28
Er wordt een populatie van n chromosomen (oplossingen) bijgehouden met hun respectievelijke fitheidscore. De ouders worden geselecteerd om zich voort te planten op basis van een voortplantingsschema. Logischerwijs wordt aan de ouders met een hoge fitheid meer kansen geboden kinderen te genereren. Er worden evenveel kinderen geproduceerd als er ouders zijn, waarna de ouders sterven. Hierdoor wordt bij elke ronde een nieuwe generatie gecreëerd telkens de voortplantingsmogelijkheden van de ouders uitgeput zijn. Op deze wijze hoopt men dat de gezondste oplossingen zullen blijven voortbestaan en zichzelf verbeteren, en dat de minst fitte oplossingen zullen uitsterven. Elke nieuwe generatie van oplossingen bevat, gemiddeld genomen, meer goede genen dan de vorige generatie. Er zullen steeds meer goede partiële oplossingen opduiken, totdat de populatie geconvergeerd is. Vanaf dat punt zullen er geen kinderen meer voortgebracht worden die veel verschillen van degene voortgebracht door de vorige generatie. Het algoritme is geconvergeerd naar een oplossing. Uit deze korte beschrijving kunnen we vier grote verschillen afleiden met de klassieke zoek- en optimalisatiemethodes: • GA’s werken op een codering van het probleem en niet op de eigenlijke variabelen van het probleem. Dit maakt het algoritme grotendeels probleemonafhankelijk. Een oplossing wordt voorgesteld door een tekenstring samengesteld uit een alfabet. Meestal wordt een binair alfabet gebruikt. • GA’s zoeken in een populatie van oplossingen, niet op één enkel punt. Dit zorgt ervoor dat er weinig kans is dat het algoritme vast komt te zitten in een lokaal optimum dat ver van de optimale oplossing ligt. • GA’s worden bestuurd door de fitheidscore en niets anders dan de fitheidscore. Vele andere methoden maken gebruik van randinformatie om bepaalde dingen te kunnen besluiten en zo verder te zoeken. Deze randinformatie kan vaak aanleiding zijn van foute zoekrichtingen en resultaten. GA’s maken deze veronderste llingen niet en zijn dus toepasbaar op een zeer brede waaier van problemen. Spijtig genoeg gaat dit dan ook veelal ten koste van de uitvoeringstijd en kan hierdoor ook niet met absolute zekerheid gesteld worden dat de juiste oplossing gevonden wordt.
29
• GA’s gebruiken eerder stochastische regels dan deterministische keuzes om het optimum te zoeken. Een willekeurige keuze wordt gebruikt om het algoritme naar de gebieden in de zoekruimte te leiden waar er een goede kans is op betere oplossingen. • Doordat vele oplossingen naast elkaar bestaan, en naast elkaar geëvalueerd en gebruikt worden, ontstaat er een soort impliciet parallellisme dat het algoritme een hoge efficiëntie kan geven.
Deze eigenschappen maken van GA’s een robuus te zoektechniek die oplossingen genereert van goede kwaliteit in een redelijke tijd en dit voor een zeer uiteenlopende klasse van problemen.
Het klassieke genetisch algoritme kan in pseudo-code als volgt geschreven worden: solve() { initial_pop=generate_initial_pop(); calc_fitnesses (initial_pop); curr_generation = initial_pop; while ( ! converged (curr_generation) ) { pool = make_matingpool (curr_generation); while ( ! full (next_generation) ) { random_select_two_parents (pool); offspring = produce_offspring (parents); offspring = mutate (offspring); put (next_generation, offspring); } calc_fitnesses (next_generation); curr_generation = next_generation; } return select_best_solution (curr_generation); }
3.3. 3.3.1.
Implementatiefacetten Codering
Een oplossing voor een probleem is volledig bepaald door een eindige collectie variabelen. De variabelen maken samen een vector van waarden. De oplossing is gecodeerd in een alfabet (veelal binair) dat doorgaans de reproductie probleemonafha nkelijk maakt.
30
De exacte codering die gebruikt wordt om een probleem te beschrijven is niet echt van vitaal belang. Het algoritme is robuust genoeg om geen last te hebben van onduidelijkheden in de codering. Er zijn twee principes die de keuze van een goede probleemcodering bepalen. Het principe van de betekenisvolle blokken en het principe van het minimale alfabet. Het principe van de betekenisvolle blokken bepaalt dat een codering gekozen moet worden zodat korte, lage-orde schemata relevant zijn voor het onderliggende probleem en dat deze relatief onafhankelijk zijn van schemata op vaste posities. Deze regel is niet echt praktisch en maakt goede coderingen zeer moeilijk om op te stellen. Het principe van het minimale alfabet zegt dat het kleinst mogelijke alfabet gekozen moet worden om het probleem op natuurlijke wijze voor te stellen. Dit is logisch omdat er genen doorgegeven worden naar volgende generaties. Fitte individuen hebben de neiging om gelijkaardige lage-orde schemata te bevatten. Doordat de reproductie een voorkeur vertoont voor fitte individuen, hebben deze schemata een goede kans om doorgegeven te worden. Een alfabet dat zo klein mogelijk is, maximaliseert de informatie in de schemata waardoor de goede informatie zo efficiënt mogelijk doorgegeven wo rdt.
3.3.2.
Reproductieproblemen
Tijdens de reproductie worden chromosomen gekozen om de ouders te zijn voor een volgende generatie. De ouders worden verkozen op basis van een schema dat een voorkeur wegdraagt voor de fitste individuen waardoor goede oplossingen een betere kans hebben om gekozen te worden dan slechte. Betere oplossingen zullen zich doorgaans meerdere keren voortplanten, terwijl de zwakke oplossingen soms niet eens aan bod zullen komen. Om dit mogelijk te maken wordt een “kweekvijver” gevormd. Alleen de oplossingen in de “kweekvijver” krijgen de kans om zich te reproduceren. De manier waarop de chromosomen geselecteerd worden, moet met de nodige zorg geïmplementeerd worden. Anders zal het algoritme niet op correcte wijze convergeren. Er zijn twee mogelijke problemen die kunnen opduiken: voortijdige convergentie en trage convergentie. In de volgende paragrafen worden enkele oplossingen voorgesteld om de reproductie efficiënter te maken.
31
3.3.2.1.
Voortijdige en trage convergentie
Voortijdige convergentie komt voor als in een populatie één of meerdere oplossingen duidelijk fitter is dan de andere. Deze “superfitte” individuen zullen dan de populatie overheersen en de oplossing tot een zwak lokaal optimum leiden. Het is heel moeilijk om hiertegen maatregelen te treffen. De beste methode is zeer zorgvuldig met de beginpopulatie omspringen zodat de fitheid van deze oer-individuen zeer dicht bij elkaar ligt. Op het einde, als het algoritme bijna klaar is, zijn er veel oplossingen met een gelijkaardige fitheidscore en zeer veel sterk op elkaar gelijkende deeloplossingen. Op dat moment kan het algoritme onvoldoende onderscheid maken tussen de oplossingen wat leidt tot trage convergentie. Dit is een onvermijdelijk en zeer natuurlijk verschijnsel. Dit gedrag kan enkel positief beïnvloed worden door een goede mutatiefunctie die de diversiteit hoog genoeg houdt. Het probleem zal daardoor enkel minder uitgesproken worden maar niet verdwijnen.
3.3.2.2.
Fitheidschaalverandering
Door de fitheidfunctie te veranderen tot een lineaire combinatie van factoren, worden de verschillen tussen de individuen duidelijker. Het toekennen van een gewicht (positief of negatief) aan bepaalde allellen maakt een juistere verdeling tussen de fitte chromosomen in de “kweekvijver” waarschijnlijker.
3.3.2.3.
Fitheidklassering
Individuen worden gerangschikt volgens fitheid waarna een waarschijnlijkheidsverdeling geassocieerd wordt met de gesorteerde lijst. De chromosomen worden dan gekozen volgens deze waarschijnlijkheidsverdeling.
3.3.2.4.
Wedstrijdselectie
Groepen van een vaste grootte worden op willekeurige wijze uit de populatie gekozen en de fitste van de groep gaat dan naar de kweekvijver. Alle individuen gaan dan terug naar de populatie en er wordt opnieuw een tornooi georganiseerd. Dit proces wordt herhaald tot de kweekvijver vol zit. Een binair tornooi geeft een gelijkaardig resultaat als de fitheidrankschikking-methode, zonder het tijdrovende sorteren en dergelijke.
32
3.3.3.
De eigenlijke voortplanting
Twee individuen, op willekeurige wijze geselecteerd uit de “kweekvijver”, kruisen door middel van een “crossover” operator tot een aantal kinderen. Er zijn een aantal operatoren die hiervoor gebruikt worden. De belangrijkste algemeen toepasbare operatoren zijn simple crossover, multi-point crossover, uniform crossover. Op een algemeen schema van binaire aard worden deze operatoren zeer eenvoudig en zeer efficiënt gebruikt. Het is echter zo dat bij combinatorische problemen waarbij een volgorde van belang is, deze operatoren falen. De redenen hiervoor zullen duidelijk worden bij de nadere bespreking van de operatoren in de volgende paragrafen. Daarom zullen we nog drie andere operatoren, specifiek voor volgordeproblemen, bespreken. Deze zijn de order crossover, de PMX crossover en de cyclic crossover. Als er twee ouders uit de “kweekvijver” gehaald worden voor voortplanting, dan bestaat er ook altijd de kans dat deze zich niet voortplanten. Als dit zich voortdoet dan worden de geselecteerde ouders integraal in de volgende generatie geplaatst. Op deze wijze krijgt men een soort generatie-overbrugging en een situatie waarbij kinderen naast de ouders leven.
3.3.3.1.
Simple Crossover of Single-point Crossover
Deze techniek vormt de ouders om tot twee kinderen. De schema’s van de ouders worden onder elkaar geplaatst. Daarna wordt er een crossover-punt op willekeurige wijze gekozen. De mogelijke plaatsen voor een crossover zijn beperkt tot de posities tussen de genen. Anders zou een voortplanting kunnen verworden tot een voortplanting en een mutatie. Om de twee kinderen te vormen, worden het schema van de ouders in twee gesneden bij het crossoverpunt. De staartschema’s worden dan onderling van plaats gewisseld zodat een kind altijd begint met de eerste helft van de genen van de ene ouder en eindigt met de laatste helft van de genen van de andere ouder.
Voorbeeld: O1: 2 3 7 4
1 6 9 8 5
K1: 2 3 7 4
7 3 2 4 8
Single-point Crossover O2: 5 9 1 6
7 3 2 4 8
K2: 5 9 1 6 33
1 6 9 8 5
3.3.3.2.
Multi-point Crossover
Dit is een direct uitvloeisel van de single-point crossover. De techniek is volkomen dezelfde, alleen worden er k crossover points gekozen. Deze operator is vooral nuttig als de building block theorie, die de basis vormt van de GA, niet volledig opgaat.
Voorbeeld: O1: 2 3
7 4
1 6 9 8
5
K1: 2 3
1 6
1 6 9 8
8
7 4
7 3 2 4
5
Multi-point Crossover O2: 5 9
1 6
7 3 2 4
8
3.3.3.3.
Uniform crossover
K2: 5 9
Dit is dan weer een uitbreiding van de multi-point crossover. Men genereert een bitstring even lang als de chromosomen met een Bernouilli-distributie. Daarna overloopt men de bitstring en als men een 0 tegenkomt, dan wordt de informatie van de eerste ouder in het eerste kind gekopieerd en van de tweede ouder in het tweede kind. Als in de bitstring een 1 voorkomt, dan worden de rollen omgedraaid. Deze methode heeft als effect dat er grotere stukken schema kunnen overleven in de volgende generatie maar ook dat op bepaalde plaatsen de genen op zeer grondige wijze door elkaar geschud kunnen worden. Als variatie hierop bestaat de HUX (Half Uniform Exchange), waarbij alle bits die identiek zijn in beide ouders, in de kinderen doorgegeven worden en van elke ouder exact de helft van de bits waar de ouders van elkaar verschillen. Op die manier verwezenlijkt men dat de kinderen maximaal verschillen van de o uders.
Voorbeeld: Bitstring: 0 0 1 0 1 1 1 1 0 O1: 2 3 7 4 1 6 9 8 5
K1: 2 3 1 4 7 3 2 4 5 Uniform crossover
O2: 5 9 1 6 7 3 2 4 8
K2: 5 9 7 6 1 6 9 8 8
34
3.3.3.4.
Order crossover
Veronderstel twee ouders die met single-point crossover kinderen genereren. Als de genen van de ouders een sortering van data voorstellen dan krijgen we de volgende situatie:
O1: 2 3 7 4
1 6 9 8 5
K1: 2 3 7 4
7 3 2 4 8
Single-point crossover O2: 5 9 1 6
7 3 2 4 8
K2: 5 9 1 6
1 6 9 8 5
De kinderen stellen geen sortering van de data meer voor. Immers, bij K1 komen data in 2, 3, 4 en 7 plots twee keer voor en zijn er een aantal andere gewoon verdwenen. Deze operator vernietigt dus oplossingen bij sorteringproblemen. De order crossover heeft dit probleem niet. Deze operator wordt verwezenlijkt door de ouders, op willekeurige wijze in drie delen op te splitsen. Het middelste deel van O1 wordt integraal gekopieerd naar K1 met dezelfde locus. Om K1 te vervolledigen worden waarden uit O2 gehaald. De waarden uit O2 worden herschreven; men neemt eerst het derde deel, dan het eerste deel en vervolgens het middelste deel. K1 wordt nu ingevuld door de waarden uit die getransformeerde O2 af te lopen, en de al gebruikte waarden over te slaan. K2 wordt op dezelfde wijze samengesteld door de rol van O1 en O2 om te draaien.
Voorbeeld: Order Crossover O1:
2 3 7
4 1 6
9 8 5
O2:
5 9 1
6 7 3
2 4 8
K1:
. . .
4 1 6
. . .
O2’: 2 4 8 5 9 1 6 7 3
K1:
2 8 5
4 1 6
9 7 3
K2:
9 8 5
6 7 3
2 4 1 (analoog)
35
3.3.3.5.
PMX crossover (Partially-mapped exchange crossover)
Deze techniek deelt de ouders ook in drie delen op. De middelste delen worden dan gezien als een uitwisselingsschema. De concrete invulling hiervan is het best te vo lgen in het onderstaande voorbeeld.
Voorbeeld: PMX Crossover O1:
2 3 7
4 1 6
9 8 5
O2:
5 9 1
6 7 3
2 4 8
Uitwisselingsschema: 4 ? 6 1 ? 7 6 ? 3
K1 gevormd uit O1: O1: 2
3?6
K1: 2 6 1
7?1
4?6?3
3 7 4
1?7
6?3?6?4
9
8
5
4?6?3?6?4
8
9 8 5
K2 gevormd uit O2: O2: 5
9
K2: 5 9 7
3.3.3.6.
1?7
6?3
3 1 6
7?1
3?6
2
2 4 8
Cycle crossover
Deze methode definieert een aantal cycli in de genen van de ouders om kinderen te genereren. Het uitschrijven van de verschillende cycli legt een patroon vast in de genen van de ouders. Om kinderen te genereren, zal men, op willekeurige wijze, een keuze maken tussen de genen van beide ouders voor elk verschillend patroonelement. Het onderstaande voorbeeld legt deze procedure in detail uit.
36
Gemiddeld de helft van de absolute posities van de genen in de ouders worden ongewijzigd overgenomen in de kinderen. Het sterke voordeel van deze methode is dat het schemata van grotere lengte “beschermt” doorheen de generaties. Dit maakt de compactheid van de schemata minder belangrijk. Deze operator is ook geschikt voor sorteringproblemen.
Voorbeeld: Cycle Crossover O1:
2 3 7 4 1 6 9 8 5 0
O2:
5 9 1 6 7 3 2 0 4 8
Deze ouders creëren volgende cycli: A: 2 ? 5 ? 4 ? 6 ? 3 ? 9 ? 2 B: 7 ? 1 ? 7 C: 8 ? 0 ? 8
De ouders voldoen dus aan het volgend patroon: P: A A B A B A A C A C
Kinderen genereren: K1 = A van O1, B van O2, C van O1 (willekeurig keuze) K2 = A van O2, B van O1, C van O1 (willekeurig keuze) K1: 2 3 1 4 7 6 9 8 5 0 K2: 5 9 7 6 1 3 2 8 4 0
3.3.3.7.
Behoud van schemata
Het grootste verschil in de verschillende reproductie-operatoren ligt in de informatie die doorgegeven wordt naar de volgende generatie. Er kan een opsplitsing gemaakt worden in twee grote soorten operatoren: operatoren die de neiging hebben tot het bewaren van kortere schemata en operatoren die eerder langere schemata bewaren.
37
Het voordeel van het bewaren van kortere schemata is dat er meer interne verscheidenheid behouden wordt en dat er meer kans is dat slechte schemata uitgeroeid worden. Er zal sneller convergentie optreden. Er zit echter een behoorlijk grote valstrik verborgen in het bevoordelen van korte schemata. Als bij de evaluatie van een oplossing korte schemata tot een hogere fitheidscore leiden dan grotere, goede schemata, dan leidt dit tot versnippering en dus vernietiging van de reeds gevonden grotere deeloplossingen. Het vinden van een goede oplossing zal gereduceerd worden tot louter toeval. Het is altijd mogelijk om dit uit te lokken, maar praktisch onmogelijk om dit verschijnsel te vermijden. Het enige dat gedaan kan worden is de kans hierop zo klein mogelijk houden. Voortplantingsoperatoren die langere schemata bevoordelen, helpen zeer goed in het vermijden van deze “decepti veness”, maar hebben andere eigen problemen die echter beter op te lossen zijn. Niet alle schemata zijn goed. Het doorgeven van langere, slechte schemata kan een volledige populatie aantasten. Als men de bevolking voldoende langzaam laat evolueren, dan worden deze slechte deeloplossingen er gemakkelijk uitgezift als men de bevolking divers genoeg houdt. Een mogelijkheid is een “overlevingsselectie” te ho uden waarbij elke derde generatie samengesteld wordt uit de fitste leden van de vorige twee generaties. Dit gecombineerd met een systeem die de diversheid van de generaties sterk bewaakt. Over het algemeen kan gesteld worden dat voortplantingsoperatoren die een voorkeur wegdragen voor het doorgeven van korte deeloplossingen, sneller zullen convergeren maar veel minder zeker een goed resultaat zullen bieden. Terwijl de andere soort gemiddeld een beter resultaat kan garanderen, maar dan met een langere convergentietijd.
3.3.4.
Mutatie
Deze operator moet ervoor zorgen dat een zekere vorm van diversiteit in de populatie gehandhaafd blijft. Een te veelvuldig toepassen van de mutatie vernietigt goede oplossingen op een storende manier. Daarom zal men de kans op mutatie zeer klein maken; typisch gebruikt men een kans van 1% op mutatie. De mutatie wordt toegepast na de crossover.
38
De meest eenvoudige manier van mutatie is het omklappen van een bit in de gecodeerde string. Het spreekt vanzelf dat coderingen die een zekere ordening moeten bepalen, de neiging hebben om sterk beschadigd te worden door deze techniek. Dit zou tot gevolg kunnen hebben dat een gemuteerde oplossing altijd zeer gehandicapt wordt en een zeer lage fitheidscore krijgt. Hierdoor heeft deze bijna geen kans om deel te nemen aan het kweekproces en heeft de mutatie, die de diversiteit moet bewaren, geen zin. Daarom bestaan er ook nog andere manieren van mutatie. Een eenvoudige en efficiente, alternatieve methode is gewoon twee genen in het chromosoom van plaats wisselen. Om een sterker effect te verkrijgen, kan men ook alle genen tussen twee loci door elkaar gooien. Een ander mechanisme dat niet echt mutatie is maar om dezelfde reden uitgevoerd wordt, is het vervangen van een deel van de bevolking als de bevolking begint te convergeren. Een deel van de populatie wordt door zichzelf in sterk verhaspelde vorm verva ngen. Dit proces treedt dan enkel op als de bevolking onder een bepaalde convergentiegrens duikt.
3.3.5.
Convergentie
Het is zeer duidelijk de bedoeling dat de populatie convergeert en aldus een optimale oplossing bevat. Een algemene definitie van convergentie, die echter zeer rekeni ntensief is, is de vo lgende: “Een gen is geconvergeerd als deze in 95% van de populatie in een generatie dezelfde waarde aanneemt. De populatie is geconvergeerd als alle genen geconvergeerd zijn.” Een eenvoudiger manier die meestal gebruikt wordt om convergentie te bepalen, is het verschil maken tussen de gemiddelde fitheidscore en de beste fitheidscore. Als dit beneden een bepaalde waarde ligt, besluit men dat de populatie geconvergeerd is. Een andere soms gebruikte methode is een steekproef nemen uit de populatie en de convergentie-definitie daarop toepassen. Om een GA te laten convergeren moet er een voldoende diversiteit behouden blijven doorheen de evolutie. Dit is vooral zeer belangrijk in het begin waar het risico bestaat op vroegtijdige convergentie naar een (meestal) lokaal optimum.
39
In de praktijk zal een GA bijna altijd convergeren. Er zijn een aantal onderzoeken geweest die bewezen hebben dat het mogelijk is om voor elke implementatie een probleem te construeren waarop het GA altijd faalt. Hieruit is ook gebleken dat het uiterst onwaarschijnlijk is dat dit zich in een reële situatie voordoet.
3.3.6.
Parameters
Er zijn een aantal parameters die in het oog gehouden moeten worden bij het construeren van een GA. Een eerste belangrijke parameter is de grootte van de bevolking. Een te kleine bevolking kan tot zeer wisselvallige resultaten leiden. Als er minder individuen zijn, is er potentieel een kleinere diversiteit en dus ook een grotere kans tot convergentie naar een lokaal optimum. In de meeste gevallen wordt een bevolking gehandhaafd van 50 tot 200 individuen. Theoretische studies over de bevolkingsgrootte hebben aangetoond dat de meest rendabele omvang tussen L en 2L liggen, met als L de lengte van het chromosoom van een individu in de populatie. Deze theoretische ideale omvang is veelal ondoenlijk omdat de populatie dan zo groot wordt dat het algoritme niet in een aanvaardbare tijd tot een oplossing kan komen. In dat geval zal men door empirische testen proberen een goed evenwicht te vinden of het mutatiemechanisme voldoende bewaken. Een volgende parameter is de initiële bevolking. De beginsituatie moet voldoende diversiteit bieden, wil er een reële mogelijkheid zijn dat het systeem convergeert naar het optimum. Als de verscheidenheid groot genoeg is, wordt zelfs de kans dat er geen convergentie naar een goede oplossing optreedt nagenoeg onbestaande. De kwaliteit van de initiële bevolking is enkel van invloed op de snelheid van uitvoering. Een hogere kwaliteit betekent doorgaans een sneller resultaat. Het grootste gevaar van een initiële oplossing van goede kwaliteit ligt in de diversiteit. Het is veel moeilijker om een grote verscheidenheid te handhaven bij een set van goede kwaliteit dan bij een willekeurig gegenereerde bevolking.
40
Een derde parameter die in het oog gehouden moet worden, is de kans op voortpla nting. Bij een operator die de keten niet al te fel door elkaar gooit, wordt deze kans redelijk hoog gezet, tussen de 90 à 95%. Bij een operator zoals uniform crossover, zal men eerder een kans hanteren tussen de 10 à 30%. Het belang van deze parameter ligt in de verbetering die per generatie zou moeten optreden. In alle oplossingen zitten kleine deeloplossingen. Sommige voortplantingsoperatoren zullen een grotere overlevingskans bieden aan kleinere, korte deeloplossingen, terwijl andere juist langere deeloplossingen bewaren. Methodes die langere deeloplossingen bewaren, hebben ook een grotere kans op het genereren van kwalitatief slechte oplossingen in een generatie zodat bij deze methodes gekozen wordt om een groter deel van de “goede” ouderbevolking te laten overleven. Deze operatoren zullen hierdoor een bevolking trager laten evolueren naar een goede oplossing en een grotere kans bieden een optimaal resultaat te bereiken omdat zij de valstrik van “deceptiveness” in korte schemata vermijden. Een laatste belangrijke parameter is de mutatiekans. In de meeste gevallen zal deze kans behoorlijk laag staan. Een percentage tussen 1% en 5% is gebruikelijk. Zoals al besproken, is de mutatie verantwoordelijk voor het behouden van de diversiteit in een populatie. Het is dan ook belangrijk om deze kans niet te laag te zetten. Anderzijds kan een te grote kans op mutatie hele reeksen goede oplossingen vernietigen. Omdat het belang van mutatie vooral in het begin van het proces ligt, namelijk om voortijdige convergentie te vermijden, zal men soms ook gebruik maken van een uitstervende kans op mutatie. Gelukkig zijn Genetische Algoritmen een robuuste oplossingsmethode. Het is mogelijk om bij elke implementatie een generische set parameters te definiëren die ongeacht het probleem een hoge kans op een goede oplossing in een snelle tijd garanderen. Er zal dan altijd wel een fijnere afstemming bestaan in elk specifiek geval die een hogere kans op een oplossing in snellere tijdspanne mogelijk maakt, maar die in andere gevallen juist een heel slechte performantie vertoont. Om de parameters te bepalen zijn er reeds vele studies uitgevoerd. De belangrijkste methoden die daarin aan bod komen zijn de volgende: •
Met een formule bepalen Het is mogelijk een relatie te bepalen tussen de probleemstelling, de implementatie en de parameters. De formule opstellen is behoorlijk moeilijk en in de meeste gevallen is het zelfs niet te bewijzen dat deze formule ook correct is. 41
•
Een GA voor het parameterprobleem bovenop het GA gebruiken Dit is een zeer tijdsrovende aanpak omdat het probleem vele keren opgelost moet worden om tot een oplossing te komen. De resultaten zijn doorgaans wel zeer goed.
•
Alle waarden uitproberen Zeer goede resultaten maar bijna ondoenlijk. Deze oplossing is nog erger dan een extra GA gebruiken.
•
Generische, robuuste parameters gebruiken Zoals reeds vermeld, biedt dit een oplossing. GA’s doen het redelijk goed met zulke parameters. Het nadeel is en blijft dat er bijna altijd een andere instelling van de parameters zal bestaan met betere resultaten en performantie.
•
Een GA construeren dat die parameters (bijna) niet nodig heeft Als men de bestaansredenen nagaat van de parameters, ziet men dat het mogelijk is om deze problemen grotendeels te vermijden. Dit leidt tot een iets tragere uitvoering van elke levenscyclus maar leidt meestal ook, door een gegarandeerde optimale werking, sneller tot een resultaat dat bovendien kwalitatief beter is. Een voorbeeld hiervan is het CHC GA. Dit algoritme wordt verderop beter toegelicht.
4.
4.1.
Toepassing van het GA
De implementatie
Het genetisch algoritme is vele keren tijdens deze studie op verschillende wijzen geimplementeerd. Sommige uitvoeringen waren enkel bedoeld als test, sommige waren pogingen tot vernieuwing, en de laatste, meest geschikte, groep uitvoeringen waren toepassingen van reeds onderzochte en uitgebreid gedocumenteerde methodes. Uiteindelijk zijn er twee kernmodules uitgevoerd, elk met hun specifieke eigenschappen en resultaten. De vergelijking volgt na de bespreking van beide modules.
42
De twee kernmodules die gemaakt werden, zijn enerzijds de klassieke GA methode en anderzijds de CHC GA methode. Ondanks dat beide methodes op de leest van het genetisch programmeren geschoeid zijn, zijn ze verschillend in gedragingen, evolutie en resultaten. Aan beide methodes werd dezelfde bevolking aangeboden om een betere vergelijking te kunnen maken. Beide methodes werden ook verschillende keren uitgevoerd om de invloed van het niet-deterministische karakter van het GA te minimaliseren. Desondanks moet opgemerkt worden dat beide methodes een andere set parameters hebben en er geen garantie kan gegeven worden dat de parameterinstellingen van gelijkwaardige kwaliteit waren. De bespreking van de opbouw van de aangeboden genetische keten wordt gevoerd in hoofdstuk 3, de Implementatie.
4.2.
Klassieke GA
4.2.1.
Cyclus
De cyclus van het klassieke genetische algoritme is gerealiseerd in classicGA.cc 1. Hier wordt volgende cyclus gebruikt: •
Willekeurige selectie van twee keer twee individuen. Deze worden per twee tegen elkaar uitgespeeld in een binary tournament, zodat er slechts één ouderpaar overblijft.
•
Dit ouderpaar produceert twee kinderen met behulp van een lichtjes aangepaste multipoint crossover of wordt ongewijzigd aan de volgende generatie toegevoegd.
•
Op de kinderen wordt, met lage kans, een swap-mutatie toegepast.
•
De kinderen worden in een nieuwe bevolking geplaatst en dit wordt herhaald tot de bevolking volledig is.
•
Het proces wordt gestopt, als de bevolking geconvergeerd is tot een oplossing of er een individu bestaat die een volkomen oplossing voor de probleemste lling vormt
1
Zie programmacode, bijlage A
43
4.2.2.
Parameters
Als parameters om dit geheel te besturen krijgen we dan: •
de bevolkingsgrootte
•
de reproductiekans
•
de mutatiekans
•
de minimale te bereiken convergentiewaarde
De bevolkingsgrootte is hier van belang om een voldoende grote keuze in oplossingen te bieden en de diversiteit voldoende groot te maken. De reproductiekans biedt de mogelijkheid om delen van de oudergeneratie in de volgende generatie te laten overleven. De mutatiekans moet de diversiteit in de evolutie bewaren. De convergentiewaarde bepaalt wanneer het algoritme mag stoppen.
CHC 2 GA
4.3. 4.3.1.
Cyclus
De cyclus van het CHC genetische algoritme is gerealiseerd in chcGA.cc 3. Hier wordt volgende cyclus gebruikt: •
Willekeurige selectie van het ouderpaar
•
Creatie van twee kinderen als de ouders verder van elkaar liggen dan de minimale Hamming-afstand 4 door middel van HUX
•
De gevormde kindgeneratie wordt bij de oudergeneratie gevoegd, alle chromosomen worden gerangschikt op fitheid en de besten worden gebruikt voor de volgende generatie
2
Cross generational elitist selection, Heterogeneous recombination, Cataclysmic mutation
3
Zie programmacode, bijlage A
4
Aantal bitposities waarin twee bitstrings van elkaar verschillen
44
•
Als er bijna geen nieuwe kinderen meer geproduceerd worden, wordt het minst fitte deel van de bevolking vervangen door een mutatie van de fitste.
4.3.2.
Parameters
Als parameters om dit geheel te besturen krijgen we dan: •
de bevolkingsgrootte
•
de minimale Hamming -afstand
•
het aantal iteraties dat de bevolking moet doorlopen
•
het vervangingspercentage bij convergentie (door theoretisch onderzoek is gebleken dat dit best 35% van de bevolking is)
De bevolkingsgrootte zorgt voor een voldoende keus aan diverse oplossingen. De minimale Hamming-afstand voorziet een bescherming tegen incest en dus verarming van de bevolking. Het aantal iteraties bepaalt wanneer het algoritme stopt. Deze parameter moet min of meer proefondervindelijk vastgelegd worden. Het vervangingspercentage is in principe ook een parameter maar wordt in deze implementatie vast gekozen op de, theoretisch gezien, meest optimale waarde.
4.3.3.
Pseudocode
Het CHC GA kan in pseudocode als volgt voorgesteld worden: solve () initial_pop = generate_initial_pop (); calc_fitnesses (initial_pop) generation = 0; threshold = min_hamming_distance; parent_pop=initial_pop; while ( generation<max_gen && best_fitness!=perfect ) do generation = generation+1; while ( ! full (child_pop) ) { random_select_two_parents (parent_pop); offspring = half_uniform_X (parents, threshold); put (child_pop, offspring) } calc_fitnesses (child_pop); next_generation = elite_of (parent_pop, child_pop); if ( parent_pop = next_generation ) decrease threshold; if ( threshold = 0 ) next_generation = external_mutation (next_generation);
45
parent_pop = next_generation; } return select_best_solution (parent_pop); }
4.4.
Genetische sequentie
4.4.1.
Doelstelling
De genetische sequentie moet een volledig lesrooster voorstellen van een volledige school. In de sequentie zitten volgende elementen vervat: •
Het tijdstip waarop een les doorgaat
•
De leraren die de les geven
•
Het vak dat gegeven wordt
•
De klasgroepen die deze les volgen
•
De lokalen waarin de les gegeven wordt
Deze voorstelling van het probleem gaat al direct uit van de verschillende lessen (vakken) die gegeven worden. Het is natuurlijk ook mogelijk om de sequentie vanuit andere standpunten te bekijken. Dit is een belangrijk facet voor het ontwerpen van de genetische voorstelling. Een doorgevoerde vereenvoudiging is het koppelen van de klasgroepen aan de vakken. Het is immers geweten welke lessen in welke klas (studiejaar) gegeven worden. Het enige dat nog min of meer variabel kan zijn, is het aantal studenten in de klasgroepen, maar dit kan eenvoudig opgevangen worden door uit te gaan van maximale of gemiddelde waarden.
4.4.2.
1e Ontwerp Tijdstip1
Vak/Klas A
Docent Y
Tijdstip2 Lokaal R
Vak/Klas U
Docent B
Tijdstip3 Lokaal L
Vak/Klas Q
Docent Z
… Lokaal J
In dit ontwerp wordt het probleem bekeken vanuit het standpunt van de tijd. Elke positie in de genetische sequentie stelt een volgend tijdstip voor. 46
Bij het doorlopen van de sequentie wordt deze opgesplitst in evenveel stukken als er klassen zijn. De klassen zitten willekeurig door elkaar vermengd in het chromosoom. Als het chromosoom opgesplitst is in klassen, worden deze overlopen en de reële tijdstippen waarop de lessen doorgaan berekend. Dit gebeurt aan de hand van een door de gebruiker ingevulde tabel met algemene dagschikkingen5. Hierdoor heeft men een lesrooster per klas en hieruit kan men dan een lesrooster per docent, per lokaal en per leerling puren.
4.4.3.
2e Ontwerp
Normaal Tijdstip1 Vak/Klas A
Docent Y
Tijdstip2 Lokaal R
Vak/Klas U
Docent B
Tijdstip3 Lokaal L
Vak/Klas Q
Docent Z
… Lokaal J
Groepering, de docenten Y, B en Z geven les op tijdstip 1 aan Vak/Klas A in Lokaal R Tijdstip1 Vak/Klas A
Docent Y
Lokaal R
Vak/Klas A
Docent B
… Lokaal R
Vak/Klas A
Docent Z
Lokaal R
Docent X bestaat niet, illegale waarde resulteert in mogelijke pauze Tijdstip1 Vak/Klas A
Docent Y
Tijdstip2 Lokaal R
Vak/Klas U
Docent X
Tijdstip3 Lokaal L
Vak/Klas Q
Docent Z
Lokaal J
…
Dit ontwerp is hetzelfde als het 1e ontwerp maar met een kleine wijziging. Doordat de verschillende loci tijdstippen uitdrukken waarop de lessen gegeven worden, is het onmogelijk om variabele rustpauzes in te lassen. Lessen gegeven door meerdere docenten passen zeer slecht in deze codering. De aanpassing bestaat eruit dat meerdere keren hetzelfde gen na elkaar maar met slechts één verandering (docent, vak/klasgroep, lokaal) in een groepering resulteert. Dit wordt dan een les gegeven door meerdere docenten, of een les die doorgaat in meerdere lokalen, enz. .
5
Voorbeeld: dag begint om 8u, middagpauze duurt 1 uur en ligt tussen 11u30 en 14u30, dag eindigt
om 18u
47
Om dynamische rustpauzes mogelijk te maken wordt in dit tweede ontwerp gebruik gemaakt van illegale informatie zoals een klasgroep die geplaatst is in een bezet lokaal. Als zo’n rustpauze in de middagperiode ligt dan wordt er een middagpauze gegenereerd. Dit ontwerp lost alle problemen van het vorige ontwerp op, maar is zeer moeilijk om te evalueren. Bij het berekenen van de fitheid van een chromosoom wordt zeer veel tijd verspild. Door het gebruik van de illegale informatie is het ook zeer moeilijk om dynamisch een chromosoom met gepaste lengte te voorzien.
4.4.4.
3e Ontwerp
Docent1 Vak/Klas 2^3
Tijdstip 4
Docent2 Lokaal R
Vak/Klas 2^5+2^8
Tijdstip 4
Docent3 Lokaal L
Vak/Klas 2^2
Tijdstip 2
… Lokaal J
Aangezien de tijd een groot probleem vormt bij de schikking van de genen, was het interessant één van de andere facetten als uitgangspunt te nemen. Dit resulteert inderdaad in een eenvoudigere oplossingsmethode. De docent als uitgangspunt lost alvast een aantal zoekproblemen naar de geldigheid van een oplossing op. Een docent wordt evenveel loci toebedeeld als het aantal uren dat hij aangesteld is. Dit is een gegeven dat toch berekend moet worden in het begin van het schooljaar. Het groeperen van docenten is dan geen enkel probleem meer. Wat wel een probleem is, is het gebruik van verschillende lokalen op hetzelfde moment door een docent (of een groep docenten) of het lesgeven aan meerdere klasgroepen. Dit kan opgevangen worden door de gebruiker op voorhand deze groeperingen te laten maken, maar dit gaat volledig tegen het opzet van dit eindwerk in. Als oplossing wordt een bitcode als groepeerfunctie gebruikt. Elke bit komt overeen met een vak/klasgroep die les kan hebben van die bepaalde docent. Als er meerdere bits geactiveerd zijn, dan heeft men een groepering.
48
Voor de tijdstippen wordt een beperkte tijdcode gebruikt die de dag van de week aanduidt en enkel een beperkt aantal mogelijke lesperiodes in de voormiddag en namiddag voorziet. Na vertaling kan men bijvoorbeeld periode 3 in de voormiddag op donderdag krijgen. Deze periode kan enkel als geldig beoordeeld worden als deze les, samen met de lessen in de periodes 1 en 2, de middagpauze niet in het gedrang brengt.
4.4.5.
4e Ontwerp
Aangezien er per docent veel meer vak/klasgroepen bestaan dan omgekeerd, is het slechts een kleine stap om de codering in voorgaand ontwerp om te klappen. Dit resulteert direct in kleinere genen. Het aantal lesuren toegewezen aan de docenten kan dan ook op een iets dynamischer wijze gebeuren. De vak/klasgroepen zijn een minder variabel gegeven dan de lesuren van de docenten. Om groeperingen te verwezenlijken wordt dezelfde bitcodering gebruikt als in het vorige ontwerp.
4.4.6.
Vergelijking en keuze
Als deze ontwerpen vergeleken worden, ziet men een duidelijke evolutie naar een eenvoudiger te controleren en efficiënter coderingssysteem. Het 2e ontwerp is het best voorziene van de codering uitgaande van de tijd en het 4e ontwerp is het efficientste en eenvoudigste ontwerp als men niet uitgaat van de tijd. Er had eventueel nog een vijfde ontwerp gemaakt kunnen worden uitgaande van de lokalen. Dit heeft niet veel zin aangezien men moeilijk op voorhand kan bepalen hoeveel en welke lokalen nodig zullen zijn. In eerste instantie is een implementatie met het 2e ontwerp aangevat maar dit leverde immense problemen op om de fitheid op een juiste relevante manier te definiëren en berekenen. Deze aanpak maakt het moeilijk en omslachtig om de mogelijke conflicten op te sporen en te bestraffen. Wegens de povere testresultaten en de (onnodige) complexiteit is dit ontwerp niet volledig werkend in de praktijk omgezet. Tot slot is er eerst een implementatie van het 3e ontwerp aangevat die in een vroeg stadium is aangepast tot een toepassing van het 4 e ontwerp.
49
Hoofdstu k 3 : Opbouw va n het p r o g r a mma (UML)
50
1.
Het Takendiagram
Haal de benodigde gegevens van de docenten, vakken, lokalen en studenten uit een bron. (1)
Definieer het gewenste lesrooster. (2)
Stel het lesrooster op. (3)
Gebruiker
Bekijk het opgestelde lesrooster en voer kleine wijzigingen uit. (4)
Bewaar het opgestelde lesrooster. (5)
Pas de configuratie van het algoritme aan. (6)
Toelichting: (1) Deze gegevens kunnen opgeslagen zijn in één of meerdere databanken die samen de bron vormen. Eve ntueel zou de gebruiker manueel extra gegevens moeten kunnen invoeren. Dit kan nodig zijn als niet alle benodigde gegevens in de beschikbare databanken te vinden zijn. Het begrip databank is zo breed mogelijk gebruikt : gaande van Oracle databanken tot sequentiële tekstbestanden. (2) Het lesrooster wordt gedefinieerd door het belang van de beperkingen, opgelegd door de ingelezen gegevens, aan te duiden. Zo kan men bijvoorbeeld geen belang hechten aan het benodigde audiovisueel materiaal voor de lessen. Een volledige lijst van de mogelijke op te leggen beperkingen zit in het “woordenboek”. Behalve de beperkingen wordt hier ook de tijdsonderverdeling van een lesweek vastgelegd.
51
(3) Het lesrooster opstellen gebeurt door het programma de opdracht te geven aan de berekening te beginnen (4) Het bekijken en veranderen van een lesrooster is onafhankelijk van de berekening en configuratiefacetten. Hier kan een lesrooster ingelezen worden, bekeken en aangepast. Het inlezen gebeurt enkel van bestanden met een vast gedefinieerd formaat. (Deze taak wordt voorlopig niet verwezenlijkt in dit programma.) (5) Het berekende of gewijzigde lesrooster kan opgeslagen worden in een databank, in tekstbestand of afgedrukt op papier. (Van deze taak wordt enkel een eenvoudige wijze van opslag naar een tekstbestand voorzien.) (6) Deze taak geeft de gebruiker de mogelijkheid om de prestaties van het programma te verbeteren indien nodig. Bij het opstarten van het programma zijn goede standaardwaarden voorzien. De gebruiker kan de ingestelde waarden altijd herstellen naar de standaardwaarden.
52
2.
Het Klassenmodel Bevolking - TournamentSelection() - RandomSelection() - ElitistSelect() - MutateCHC() + Constructor() + Destructor() + Generate() + ReproduceGA() + ReproduceCHC() + SetGAConfig() + GetSolution()
1
Chromosoom
GAConfig
+ HUX() + MPCrossover() + Mutate() + SetChromosoom() + GetChromosoom() + GetFitness() + SetFitness() + SetFitheidFtie()
- ConfigGA() - ConfigCHC()
- SetupDagSchema() + Add() + Remove() 18
3
4
Constraints + Add() + Remove() + GetConstraints()
Planner
GA + SetGAConfig() + HandleGA() + HandleCHC() + GetSolution() + Fitheid()
+ ConfigGA() + LeesData() + DefDagSchema() + DefConstraints() + Bereken() + Import() + Export()
5
8
9 11
14
DagSchema
2
6
LeesData 7
+ SetupDBConnectie() + LeesDocenten() + LeesKlassen() + LeesVakken() + LeesLokalen()
10 12
13
Lokaal
Klas/Vak
Docent
LokID : Long LokNaam : String Verdieping : Integer Gebouw : Integer Site : Integer Capaciteit : Integer AVM : AVMLijst
VakID : Long VakNaam : String KlasID : Long KlasNaam : String AantalStud : Integer Jaar : Integer Studierichting : Integer Specialisatie : Integer VakSoort : Integer
DocID : Long Naam : String DocentVakken : VakLijst AssistentVakken : VakLijst
GewLokMom : TijdLijst OnGewLokMom : TijdLijst Bezettingsgraad : MMInt AantKlasSim : MMInt AantVakSim : MMInt AantDocSim : MMInt
KlasGroeperen : Boolean VakGroeperen : Boolean GroepGrootte : MMInt AantDocentSim : MMInt AantLokSim : MMInt LesMomGroep : Boolean AVM : AVMLijst
Les lstDocenten lstDocentVolgendeLes lstKlas/Vak lstKlas/VakVolgendeLes lstLokalen lstLokaalVolgendeLes lstBeginTijd lstEindTijd
15
16
53
GewLesMom : TijdLijst OngewLesMom : TijdLijst LesMomGroep : Boolean AantUrenLes : MMInt AantUrenTheorie : MMInt AantUrenLabo : MMInt AantUrenDocent : MMInt AantUrenAssistent : MMInt AantVakSim : MMInt AantKlasSim : MMInt AantLokSim : MMInt
17
2.1. Nr
Relaties: Relatie
Beschrijving
Multipliciteit
1
Bevolking – Chromosoom
Bestaat uit
(1 op veel)
2
GAConfig – Planner
Bepaalt de configuratie van
(1 op 1)
3
GA – Bevolking
Laat evolueren
(1 op 1)
4
DagSchema – Planner
Bepaalt dagindeling
(1 op 1)
5
GA – Planner
Bepaalt de oplossing voor
(1 op 1)
6
Constraints – Planner
Bepaalt de beperkingen voor
(1 op 1)
7
LeesData – Planner
Bepaalt de gegevens voor
(1 op 1)
8
Lokaal – GA
Beperkt
(veel op 1)
9
Klas/Vak – GA
Beperkt
(veel op 1)
10
Docent – GA
Beperkt
(veel op 1)
11
LeesData – Lokaal
Vult de gegevens in van
(1 op veel)
12
LeesData – Klas/Vak
Vult de gegevens in van
(1 op veel)
13
LeesData – Docent
Vult de gegevens in van
(1 op veel)
14
Les – GA
Is een oplossing van
(veel op 1)
15
Les – Lokaal
Bevat
(1 op veel)
16
Les – Klas/Vak
Bevat
(1 op veel)
17
Les – Docent
Bevat
(1 op veel)
18
GA – Chromosoom
Bepaalt de fitheid van
(1 op veel)
Relaties tussen Lokaal, Klas/Vak en Docent
zie Woordenboek
54
3.
De Sequentiediagrammen
3.1.
Haal de benodigde gegevens op dePlanner
deLeesData
LeesData(Bestand) SetupDBConnection(Bestand) Gebruiker LeesDocenten() Create *
eenDocent
LeesLokalen() Create *
eenLokaal
LeesKlassen() LeesVakken() Create *
eenKlas/Vak
55
3.2.
Definieer het lesrooster & Configureer het GA dePlanner
deConstraints
hetDagSchema
DefConstraints() Gebruiker
Add()* / Remove()*
DefDagSchema()
ConfigGA() ConfigGA() / ConfigCHC()
56
hetGAConfig
3.3.
Stel het lesrooster op dePlanner Bereken()
hetGA
deBevolking
hetChromosoom
SetGAConfig()
SetGAConfig()
Gebruiker (d.m.v. CHC)
Generate()
SetChromosoom()*
RandomSelection()
[Stopvoorwaarde]
ReproduceCHC()
HUX()
GetFitness()* FitHeid()*
ElitistSelect()
GetSolution()
57
4.
Woordenboek
Lijst van beperkingen 0: 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35:
Gewenste lesmomenten Ongewenste lesmomenten Maximum aantal lesuren Minimum aantal lesuren Maximum aantal theorie-uren Minimum aantal theorie-uren Maximum aantal praktijk-uren Minimum aantal praktijk-uren Maximum aantal docent-uren Minimum aantal docent-uren Maximum aantal assistent-uren Minimum aantal assistent-uren Maximum aantal docenten op hetzelfde lesuur Minimum aantal docenten op hetzelfde lesuur Maximum aantal vakken op hetzelfde lesuur Minimum aantal vakken op hetzelfde lesuur Maximum aantal klassen op hetzelfde lesuur Minimum aantal klassen op hetzelfde lesuur Maximum aantal lokalen nodig hetzelfde lesuur Minimum aantal lokalen nodig hetzelfde lesuur Maximale bezettingsgraad Minimale bezettingsgraad Lessen steeds in hetzelfde lokaal Lessen in lokalen op dezelfde verdieping Lessen in lokalen in hetzelfde gebouw Lessen in lokalen op dezelfde site Lesuren groeperen of spreiden Klassen groeperen als zelfde vak Vakken groeperen als zelfde klas Maximum aantal leerlingen bij groeperen Minimum aantal leerlingen bij groeperen Audiovisueel materiaal beschikbaar Voldoende tijd bij verandering van lokaal Begintijdstip dag respecteren Eindtijdstip dag respecteren Ingestelde duur middagpauze respecteren
HUX Half Uniform Exchange crossover.
MPCrossover Multi Point Crossover.
Mutate Driedimensionale swap mutatie.
58
GetFitness / SetFitness De fitheid van het huidige chromosoom. De fitheid wordt op een illegale waarde (-MAX_INT) gezet als deze niet nog berekend is.
Generate Dit genereert een volkomen willekeurige bevolking. Voor het klassieke GA zitten hier ook ongeldige waarden in, voor het CHC GA zijn enkel geldige waarden aanwezig.
TournamentSelection Willekeurige selectie van een ouderpaar door twee wedstrijden waarbij telkens twee willekeurig gekozen ouders tegen elkaar uitkomen en de fitste, eerst gekozene de wedstrijd wint.
RandomSelection Willekeurige selectie van een ouderpaar.
ChildsMPC Creatie van twee kinderen door middel van Multi Point Crossover.
ChildsHUX Creatie van twee kinderen door middel van Half Uniform Exchange Crossover.
ElitistSelect Generatie van een nieuwe oudergeneratie uit de beste exemplaren van de huidige oudergeneratie en kindgeneratie.
ReproduceGA Reproductie via het klassieke genetische algoritme.
ReproduceCHC Reproductie via het CHC genetische algoritme.
GAConfig Grafische klasse die de gebruiker toestaat de twee types GA te configureren en de configuratie zelf bevat.
LeesData Interface naar een databank, opslag medium of grafisch venster. Verzorgt de functies om de gegevens voor de lesroosters in te lezen.
DagSchema – Constraints Grafische klassen die de gegevens voor de tijdsindeling van een lesweek en de beperkingen op een lesrooster inzamelen en bewaren.
59
Planner Basisklasse, hart van het programma. Deze (grafische) klasse geeft de gebruiker de mogelijkheid om de verschillende taken uit te voeren.
Planner : Bereken() De functie speelt alle noodzakelijke informatie door aan de klasse GA waarna deze een lesrooster begint op te stellen. Er wordt in een grafisch scherm getoond wat het algoritme op dat moment aan het doen is.
Planner : Import() Deze functie leest een reeds berekend lesrooster in. De bedoeling is dat de gebruiker het ingelezen lesrooster kan bewerken. Het bewerken van berekende lesroosters is in deze fase niet voorzien. Deze functie heeft nog geen nut en is dus niet geïmplementeerd.
Planner : Export() Toont het lesrooster op het scherm en/of schrijft het weg naar een bestand of databank. In de huidige fase wordt het lesrooster enkel naar een bestand weggeschreven.
GA Basisklasse voor het berekenen van het lesrooster. De onderliggende laag (Bevolking en Chromosoom) is in C++ geschreven om een hogere performantie te realiseren.
GA : Fitheid() Deze functie wordt door het chromosoom opgeroepen met de genetische sequentie als parameter. Deze functie geeft dan de berekende fitheid terug aan het chromosoom. In deze fase is deze functie geïmplementeerd in Delphi omdat alle informatie op deze wijze eenvoudiger op te zoeken is. Om de performantie te verbeteren zou dit naar C++ moeten omgezet worden.
LokID / VakID / DocID / KlasID Dit zijn de eigenlijke codeerwaarden die in het programma gebruikt worden.
AVMLijst Lijst van audiovisueel materiaal. Deze klasse bevat ook de beschrijving van de beschikbare materialen. Wordt gebruikt in de klasse Lokaal en in de klasse Klas/Vak.
TijdLijst Lijst met tijdspannen. Wordt gebruikt om bij Docenten en Lokalen aan te geven welke momenten zij wel of niet beschikbaar zijn.
VakLijst Lijst met vakken. Gebruikt om de docenten te beperken tot de vakken waarin zij aangesteld zijn.
60
MMInt Struct die een interval uitdrukt. Exacte waarden worden bekomen als het minimum gelijk is aan het maximum.
Lokaal : Bezettingsgraad Dit is een procentuele waarde (tussen 0 en 100). Dit interval drukt uit hoeveel percent van het lokaal bezet moet zijn.
Klas/Vak : Vaksoort Nog niet gebruikt. Is bedoeld voor latere versies. Deze bijkomende beperkingen te bepalen op het groeperen van vaksoort wordt de radius van het vak bedoeld, namelijk of gegeven wordt in één studiejaar, in één richting of in één
waarde laat toe klasgroepen. Met een vak identiek specialisatie.
Docent : AantUrenLes / AantUrenTheorie / AantUrenLabo / AantUrenDocent / AanturenAssistent De AantUrenLes is het aantal uren dat een docent algemeen met de studenten bezig is op school. Dit aantal uren kan opgesplitst worden in AantUrenTheorie en AantUrenLabo. Volkomen apart daarvan kunnen de AantUrenLes ook opgesplitst worden in AantUrenDocent en AanturenAssistent.
Les : lstLokalen / lstLokaalVolgendeLes lstLokalen is de lijst met lokalen in gebruik voor die les. lstLokaalVolgende les is een verwijzing naar de volgende les die in één van de lokalen in lstLokalen doorgaat. Op deze wijze kan men een lokaal volgen doorheen de tijd en zien welke lessen er doorgaan en wanneer. Dit is analoog voor de lstDocenten, lstDocentVolgendeLes, lstKlas/Vak, lstKlas/VakVolgendeLes
Relaties tussen Lokaal, Klas/Vak en Docent Dit is uitgebreid besproken in Hoofdstuk 1 §2 - Relaties.
61
Hoofdstu k 4: Implementatieverloop
62
1.
1.1.
Studie
Algemeen
Dit eindwerk is begonnen met een uitgebreide studie via internet naar alle mogelijke algoritmen die lesroosters kunnen opstellen. Het resultaat van dat onderzoek was een hele resem aan beschrijvingen van methodes die met wisselend succes op lesroosters losgelaten worden. Om een keuze uit deze algoritmen te kunnen maken, is elke methode apart onderzocht. Daaruit zijn dan een aantal methodes gekozen die een zeer goede indruk wisten te vestigen omtrent de toepasbaarheid op een lesrooster. De keuze tussen deze redelijk gelijkwaardige kandidaten is in het voordeel van het genetisch algoritme uitgedraaid.
1.2.
GA
Nadat de keuze gemaakt was, was het tijd om het algoritme tot in de details te analyseren en uit de diepen. In eerste instantie werd er gezocht naar een eenvoudig te begrijpen uitleg om het algoritme in een programma te kunnen uittestten. Het blijkt dat er zeer veel theoretische besprekingen bestaan maar zeer weinig praktische gidsen. Aan de hand van een aantal beschrijvingen in pseudocode en een beschrijving van de meest gebruikte operatoren werd een eerste testprogramma gemaakt. Uit dat testprogramma blijkt al snel dat de grote kracht van het GA het sterkst beperkt wordt door de fitheidfunctie.
2.
2.1.
Onderzoek
Een goede GA implementatie
Na enkele pogingen is er een kernprogramma gecodeerd dat een GA implementeert. Bij de creatie hiervan zijn we volgende problemen tegengekomen: 63
-
Memory Leaks
Het GA maakt gebruik van zeer dynamische structuren. Het is uitermate belangrijk om een goed geheugenbeheer te hebben. Hierbij dient zeer veel aandacht besteed te worden aan het juist toewijzen van pointers en zelfs nog meer aan het vrijgeven van geheugen dat niet meer gebruikt wordt. Een vervelende trek van C++ zorgde hier voor extra problemen. Als de instructie ‘delete’ op een reeds vrijgegeven array toegepast wordt, dan stopt het programma door een fatale fout. Er bestaat hier een eenvoudige oplossing voor, namelijk elke vrijgegeven pointer op nul initialiseren. Het commando ‘delete’ faalt niet als het opgeroepen wordt op een op nul geïnitialiseerde pointer. -
Uitvoersnelheid versus goede code
Om de snelheid van het algoritme te verhogen wordt het best gebruik gemaakt van globale variabelen. Het is goed mogelijk om een éénmalig te initialiseren set variabelen te definiëren waarop alle bewerkingen uitgevoerd worden. Anderzijds past een GA ook heel goed in een samenwerkende set Klassen. Uit voorliefde voor gestructureerd programmeren en vooral omdat foutopsporing in Klassen gemakkelijker is, werd gekozen voor deze laatste methode. -
Het belang van de parameters bij een GA
Dit komt in alle studies naar voren : de parameters van de GA zijn zeer belangrijk. Door het fout instellen van deze parameters is het mogelijk de uitvoertijd ruim te verdubbelen en het vinden van een oplossing te verhinderen. -
De genetische sequentie
Zoals uit het onderzoek blijkt, is het belang van de genetische sequentie behoorlijk hoog. Dit facet van het GA hangt zeer sterk samen met de fitheidfunctie. Een slechte keuze voor de genetische sequentie zorgt er direct voor dat een deel van de dynamische mogelijkheden voor het opstellen van de roosters de mist in gaat. Vervolgens kan een slecht gekozen sequentie er ook voor zorgen dat de perfo rmantie van de fitheidfunctie kritiek wordt.
64
2.2.
Lesroosters
Uit gesprekken met leraren en uit eigen ervaringen blijkt dat er niet veel lesroosters bestaan waar iedereen tevreden mee is. Elk jaar zit er wel ergens een onmogelijkheid verborgen in de grotere lesroosters. Een belangrijke vraag die zich stelt is : “Wanneer is een lesrooster goed?” en nog belangrijker : “Wat bepaalt een goed lesrooster?”. Vanuit deze twee vragen zijn we begonnen eisen en gegevens te verzamelen over goede lesroosters. Dit gecombineerd met gegevens uit bestaande studies, blijkt dat een lesrooster als goed wordt beschouwd als er geen onmogelijkheden in zitten en 95% van de gebruikers tevreden is. Bij manuele planning wordt dit bijna nooit gehaald, maar bij geautomatiseerde of half-geautomatiseerde planning soms wel. Dit werd meteen een doelstelling voor het programma. Een groot probleem bij lesroosters is hoe deze gedefinieerd moeten worden door een gebruiker. Het merendeel van de studies wees in de richting van het ontwikkelen van een taal specifiek voor dat doel. Na enkele korte pogingen daartoe heb ik besloten om dit niet te doen. Een taal heeft twee grote nadelen. Vooraleer een taal door een gebruiker kan toegepast worden om veel preciezer een goed lesrooster te beschrijven, moet deze eerst aangeleerd worden. Dit vormt voor veel gebruikers een hoge drempel. Vervolgens is een taal niet eenvoudig te ontwikkelen en is er niet genoeg tijd voorzien om dit te verwezenlijken. Om deze redenen heb ik besloten de lesroosters te laten beschrijven door een verzameling van regeltjes.
2.3.
Regels als definitietaal
Regels zijn een stuk minder flexibel dan een taal en zijn dus minder geschikt. Daartegenover staat de eenvoud in gebruik en de haalbaarheid voor de ontwikkeling. Als eerste stap heb ik alle facetten en mogelijkheden van een lesrooster met zijn ve rschillende partijen neergeschreven. Dit was een behoorlijk lange lijst. Al snel bleek dat er heel sterk aan groepering kon gedaan worden om een hanteerbare set regels over te houden. Eerst is er gegroepeerd door het neerschrijven van de relaties en vervolgens zijn deze relaties vereenvoudigd tot de invalshoeken van de verschillende belanghebbenden. De resultaten hiervan zijn gebundeld in het eerste hoofdstuk van dit eindwerk.
65
2.4.
Een lesrooster in een klassemodel
Voor de echte ontwikkeling van start kon gaan, moet eerst een degelijk ontwerp gemaakt worden. Het is echter niet zo eenvoudig om een lesrooster in een klassenmodel te vatten. De ogenschijnlijk duidelijk afgelijnde entiteiten klas, vak, docent, lokaal en tijd hebben zeer veel onderlinge verbanden. Ook zijn die entiteiten niet direct ha nteerbaar in een planningsprogramma. Om het aantal combinaties min of meer haalbaar te houden moet minstens één dimensie van het probleem uitgeschakeld wo rden. De combinatie Vak/Klas is hier de meest logische. Dit zorgt er wel voor dat de klassen in groepen verdeeld zijn volgens specialisatie. Deze onderverdelen veroorzaakt enkele doordenkertjes, maar geen onoverkomelijke problemen.
3.
3.1.
Implementaties
1e implementatie
Met een rudimentair klassenmodel en een beetje ervaring met genetische algoritmen door testen, kan een eerste implementatie aangevat worden. Deze implementatie gebeurde in Linux wegens de veel grotere stabiliteit van dit platform. Het is de bedoeling om het kernalgoritme in C/C++ te schrijven en de grafische verwerking aan Delphi over te laten. C/C++ is een zeer goed overzetbare code zolang enkel de ISO C++ standaard gehanteerd wordt. Uiteindelijk blijkt veel tijd te gaan naar het ontwikkelen van stukjes programma om snel en eenvoudig gegevens in het programma te kunnen inlezen. Na ongeveer een maand van tijdverlies hieraan, ben ik overgeschakeld op de databank- en bestandstoegang voorzien in Delphi. Dit gaf wel als implicatie dat eerst de GUI moet ontwikkeld worden.
66
3.2.
Gui en databanktoegang
Na een korte gewenperiode om over te schakelen naar het Object Pascal als programmeertaal, was een eenvoudig hanteerbare Gui snel gemaakt. De databanktoegang was ook snel in orde waardoor zich een volgend probleem stelde. Om gegevens te kunnen inlezen moeten deze, liefst op een gestructureerde manier, in de databank komen. Dit leidde tot een herbekijken van het ontwerp en het inbouwen van de voorzieningen om met kleine wijzigingen een databank aan het programma te hangen. Hierdoor wordt de applicatie ook ruimer toepasbaar.
3.3.
CHC GA
Nu er een bruikbare databanktoegang bestaat en er een kleine testdatabank gemaakt is, is het tijd om de C++ code vanuit Linux te halen en in een DLL te compileren. Na een paar problemen om uit te vissen hoe dit juist in zijn werk gaat, en een paar incompatibele interface probleempjes heb ik een paar tests gedaan. Uit deze tests bleek dat het GA goede lesroosters kan opstellen maar dat er ook een onaanvaardbare kans is op falen. Uit een bijkomende studie over de verschillende varianten van de GA blijkt een telg naar voren te komen met een uitgesproken voorkeur tot het oplossen van sterk beperkte combinatorische problemen. De ontwikkeling van een kerna lgoritme werd weer aangevat onder Linux.
3.4.
Definitief ontwerp
Door veel ervaringen en wijzigingen loopt het ontwerp van het programma sterk achter op de werkelijkheid. Het volledige ontwerp werd dan vanaf nul herbegonnen. In het vernieuwde ontwerp werd de fysieke gegevensstructuur afgeschermd van de door het programma gebruikte gegevensstructuur. Ook werden voorzieningen getroffen om de Gui in verschillende schermpjes onder te verdelen met elk hun specifieke verantwoordelijkheden.
3.5.
Laatste implementatie
Op takenlijst voor deze implementatie staat:
67
-
het opnieuw ontwikkelen van de Gui aangezien deze niet modulair genoeg opgebouwd was en de interfaces niet meer kloppen met het nieuwe ontwerp
-
Het afwe rken van de implementatie van het CHC algoritme
-
Het herschrijven van de databanktoegang
-
Het implementeren van de nieuwe interne gegevensstructuren
-
Het herschrijven van de fitheidfunctie en deze overhevelen naar een hoger niveau om deze functie dichter bij de data te brengen waarvan zijn resultaat afhankelijk is
-
Opnieuw koppelen van de C++ code aan de Object Pascal code.
-
Het uitvoeren van nieuwe tests met hopelijk betere resultaten
4.
Besluiten van de implementatie
Deze is nog lang niet af. Uit testen met een heel beperkte set gegevens onder Linux, gebruik makend van het oude stramien van de GA, blijkt het CHC GA veel betere resultaten te vertonen dan het klassieke GA. Deze verbetering doet zich zowel voor op vlak van performantie (niet veel) als op gebied van kwaliteit (zeer veel). Een enkele keer wordt geen goed resultaat bereikt maar dit wordt voor 100% opgelost door het aantal iteraties dat het programma uitvoert op te drijven. De invloed van de instelbare parameters blijkt bij het CHC GA veel lager te zijn dan bij het klassieke systeem. Het CHC GA zal vermoedelijk erin slagen, bij uitgebreide testen op grotere datasets, een zeer goede prestatie neer te zetten zonder de slechte kantjes van het klassieke GA. De gemiddelde performantie van het klassieke genetische algoritme kwam uit de eerste testen als goed, maar met een zeer brede spreiding van de resultaten.
68
Hoofdstu k 5: Besluit
69
1.
Besluit
Er zijn drie facetten aan dit eindwerk om een besluit te kunnen vormen. Enerzijds een evaluatie van de gekozen oplossingsmethode, vervolgens een evaluatie van de twee gevolgde pistes, daarna een beoordeling van het opstellen van een lesrooster en tot slot een samenvatting.
1.1.
Oplossingsmethode
De gekozen oplossingsmethode heeft geen rechtstreeks verband met het probleem. Dit is een duidelijk nadeel en voordeel. Doordat de methode geen veronderstellingen doet over het probleem, zullen er ook geen verborgen afhankelijkheden de oplossing bemoeilijken. Anderzijds is deze methode wel een omweg. Er bestaan geen vergelijkende testen met andere oplossingsmethodes. Hierdoor is het niet mogelijk om de kwaliteit en snelheid van dit algoritme te vergelijken met andere. Uit verschillende studies bestaat het vermoeden dat het GA gemiddeld trager werkt maar soms, per toeval, veel sneller. Het sterk niet-deterministische karakter van dit algoritme zorgt er inderdaad soms voor dat de berekening herbegonnen moet worden omdat het GA er echt niet uitkomt en convergeert naar een lokaal optimum dat een slechte oplossing vormt. Gelukkig zorgt het niet-deterministische karakter er ook voor dat de berekening gewoon met dezelfde gegevens opnieuw gedaan kan worden en dat dan bijna altijd wel een goed resultaat gevormd wordt. De berekende oplossingen waren, bij het testen en met een eventueel herberekenen, altijd voldoende conform de gestelde eisen om bruikbaar te zijn. Een echte noodzaak tot een “aanpasfunctionaliteit” om achteraf de foutjes te corrigeren, was er niet, al zou een dergelijke functie in sommige gevallen wel bruikbaar geweest zijn. De oplossingsmethode voldoet aan de gestelde eisen, maar er kan niet gesteld wo rden dat de gevolgde methode de beste of een slechte wijze is om tot een oplossing te komen.
70
1.2.
Klassieke GA of CHC GA
Het antwoord hierop is duidelijk. Hoewel de gemiddelde resultaten van beide implementaties zeer gelijklopend zijn, vertoont de CHC GA veel minder schommelingen in zijn prestaties. Bij een schaalvergroting van het te berekenen lesrooster, zal de rekentijd voor het CHC GA in mindere mate toenemen dan voor het klassieke GA. Dit komt natuurlijk omdat het CHC GA minder generaties nodig heeft om tot een resultaat te komen. De invloed van de fitheidfunctie is, in de tijdsdiscussie, zeer groot en speelt hier dus een doorslaggevende rol. Beide algoritmen hebben last van slechte resultaten, of het vast komen te zitten in lokale optima. Door de cataclysmische mutatie heeft het CHC GA veel minder last van dit gedrag. Alleen wordt het algoritme soms te vroeg afgebroken. Uit testen blijkt dat beter het aantal keren dat convergentie optreedt als maatstaf genomen wordt dan het aantal generaties. Met deze kleine wijziging gedraagt dit algoritme zich veel stabieler en logischerwijze ook minder voorspelbaar in uitvoeringstijd. De gemiddelde uitvoertijd wordt dan hoger dan het klassieke GA maar de oplossingen van het CHC GA worden, gemiddeld genomen, kwalitatief beter. Er zijn evenwel nog enorm veel variaties ontdekt, elk met hun specifiek gedrag, die niet uitgetest werden. De geïmplementeerde en uitgeteste oplossingen waren wel de methodes die het sterkste vermoeden op goede resultaten wekten. In dit probleem is het CHC GA de beste oplossing van de uitgeprobeerde varianten van het GA. Uit het theoretisch onderzoek kon dit verwacht worden.
71
1.3.
Het definiëren van lesroosters
Dit is een probleem dat niet echt goed aan bod is gekomen in deze studie. Om een lesrooster op degelijke wijze te kunnen definiëren is een volledige taal nodig. Dit wordt in deze studie gerealiseerd door een set regels aan de gebruiker te tonen die hij dan kan gebruiken om een lesrooster samen te stellen. De bruikbaarheid van deze methode is beperkt. Deze werkwijze gaat goed en is praktisch, zolang er niet al te veel gevarieerde eisen worden gesteld, en er geen lange lijsten met individuele uitzonderingen optreden. Bij grotere, complexe lesroosters zal dit systeem dus soms tekort schieten omdat de gebruiker zeer moeilijk een overzicht kan behouden over het uurrooster dat hij aan het opstellen is. Dan zijn er echt wel de uitgebreidere mogelijkheden van een taal nodig. Dit is eigenlijk ook het uiterst moeilijke punt om te overbruggen als men een programma wil maken dat meer soorten uurroosters kan opstellen, dan enkel de lesroosters. Het vinden van een kernalgoritme dat de uurroosters kan opstellen is dan de eenvoudige taak. Het definiëren van een uurrooster en het controleren van een berekend rooster in een programma is het grote struikelblok. Dit veronderstelt een probleemonafhankelijke uurroostertaal met dynamische gegevensstructuren die de taal implementeert en gebruikt. Het ontwikkelen van een dergelijke taal is een uitgebreide studie op zich. Een uurroostertaal toegespitst op lesroosters zal, in het concept van deze studie, een sterke impact hebben op de fitheidfunctie. Hoe complexer de eisen, hoe moeilijker het wordt om alle controles in een redelijke tijdspanne af te ronden en hoe moeilijker het wordt om relevante overtredingwaarden toe te kennen. Ook deze toegenomen complexiteit wordt uit de weg gegaan door de in deze studie gedefinieerde beperkte set aan mogelijke regeltjes. Alles bij elkaar genomen is het mogelijk om, mits enige handigheid en zorgvuldigheid, met eenvoudige regeltjes de gewenste lesroosters te bepalen. In sommige gevallen is dit geen vanzelfsprekende taak.
72
1.4.
Samenvatting
Het CHC GA is de betere oplossing voor het automatisch genereren van lesroosters. Vanuit de studie kunnen geen conclusies getrokken worden die dit algoritme vergelijken met andere werkwijzen. De verwezenlijkte oplossing heeft een paar tekortkomi ngen, die oplosbaar zijn als er bijkomende studie en programmeerwerk verricht wordt. Een betere GUI, het ontwikkelen van een constraint-definitie-taal, en het ontwikkelen van bijkomende databank-toegangmodules zijn hierbij de belangrijkste elementen. Het bekomen programma is academisch bruikbaar maar heeft nog enkele reeds vermelde aanpassingen nodig om in de prakti jk gebruikt te kunnen worden.
2.
Mogelijke verbeteringen
De laag die zorgt voor het inlezen van de juiste data uit een databank is beperkt tot Microsoft Access databanken. In de praktijk zal het bijna nooit voorkomen dat een dergelijk lichte databank voor de gegevens van een school gebruikt wordt. Deze laag is echter eenvoudig uit te breiden zodat gegevens uit zwaardere databanken gehaald kan worden. De gebruikersinterface is van het rudimentaire type en laat weinig mogelijkheden. Ook is het mogelijk om het programma te laten vastlopen door ongeldige waarden in de gegevensvelden op te geven. De mogelijkheden tot het definiëren van een lesrooster kunnen ook zeer sterk uitgebreid worden. Zo kan een grafische voorstelling van de gelegde verbanden de gebruiker een heel eind verder op weg helpen. De gegenereerde uitvoer vindt plaats in tabelvorm, wat niet echt uurroosterachtig is. Het is beter om de uitvoer naar een databank te sturen. Dit biedt meer mogelijkheden tot visualisatie. De fitheidfunctie en de GA’s zelf zijn vatbaar voor verregaande optimalisatie. Dit was niet het doel van deze studie maar heeft wel een grote impact op de prestaties.
73
Nog een handige uitbreiding is een aanpasfunctie. Dit zou de gebruiker moeten toelaten om veranderingen aan te brengen in een lesrooster. In extremis zou deze functie ook gebruikt kunnen worden als hulp om een rooster manueel samen te stellen. De aanpasfunctie zou dan drieledig moeten zijn. Bij een (ver)plaatsing van een les in het rooster zou de functie moeten aanduiden of er conflicten optreden en welke. De functie zou ook automatisch de conflicten moeten kunnen oplossen via een paar eenvoudige heuristische regels. En tot slot moet de functie een opsomming kunnen geven van welke lessen, docenten, studentengroepen of lokalen er nog niet geplaatst of gebruikt zijn.
3.
Andere onderzoekspistes
Er zijn nog veel andere algoritmen die het lesroosterprobleem op efficiënte wijze kunnen oplossen. Aangezien het lesroosterprobleem een volkomen Constraint Satisfaction Problem is, is het zeer interessant om dit probleem te proberen oplossen met de specifiek daarvoor geschreven algoritmen. Uit deze studie kan in ieder geval niet duidelijk besloten worden dat GA’s trager of sneller zijn dan een dergelijke oplossingsmethode.
Het ontwikkelde GA, is een redelijk generische methode voor lesroosterproblemen. Het is niet duidelijk of deze methode ook een goed resultaat zou opleveren bij algemene uurroosterproblemen. Er zijn zeer veel uurroosters denkbaar. Een mogelijk onderzoek zou kunnen zijn naar de gemeenschappelijke en de verschillende kenmerken van dit brede scala en naar een oplossingsmethode die dit brede scala aankan.
Behalve de samenstelling van de genetische sequentie die in deze studie gebruikt is, zijn er nog andere mogelijkheden. Een diepgaand onderzoek hierin kan efficiëntere, gemakkelijker bruikbare en ruimer toepasbare sequenties ontdekken. Het opbouwen van een dergelijke sequentie is een kunst waarvan de schoonheid wiskundig kan bewezen worden.
74
Een taal die toelaat aan de gebruiker om op nauwkeurige wijze het verlangde lesrooster te definiëren zal waarschijnlijk veel meer resultaat hebben op de kwaliteit van de oplossing dan het uitdenken van andere oplossingsalgoritmes voor dit probleem. Als in die taal ook een methode vervat zit om de oplossing te toetsen aan de geste lde eisen dan zou dit een grote stap betekenen in het opstellen van lesroosters.
75
Referenties Larry J. Eshelman (1991): The CHC Adaptive Search Algorithm: How to Have Save Search When Engaging in Non Traditional Genetic Recombination
David E. Goldberg (1987): Simple Genetic Programs and the Minimal, Deceptive Problem
J. Holland (1975): Adaptation In Natural and Artificial Systems
Darrel Whitley (1993): A genetic Algorithm Tutorial
Don Banks, Peter van Beek, Amnon Meisels : A Heuristic Incremental Modeling Approach to Course Timetabling
A. Schaerf (1996): A Survey of Automated Timetabling
A. Schaerf (1996): Tabu Search techniques for large high-school timetabling problems
W. Erben, J. Keppler : A Genetic Algorithm Solving a Weekly Course-Timetabling Problem
P. Ross, E. Hart (2001) An Investigation of Hyper-Heuristic Methods
W. E. Hart : A Theoretical Comparison of Evolutionary Algorithms and Simulated Annealing
H.J. Goltz, D Matzke : University Timetabling Using Constraint Logic Programming
E.K. Burke, D.G. Elliman, R. Weare : A University Timetabling System based on Graph Colouring and Constraint Manipulation 76
J. Stallaert (1997) : Automated Timetabling Improves Course Scheduling at UCLA
E.K. Burke, D.G. Elliman, R. Weare, P. Ford : Examination Timetabling in British Universities – A Survey
G. Telfar (1994) : Generally Applicable Heuristics for Global Optimisation: An Investigation of Algorithm Performance for the Euclidean Traveling Salesman Problem
77
