Het is de bedoeling een eenvoudig Genetisch algoritme (GA) te ontwerpen dat zo goed mogelijk een ongerichte graaf zodanig inkleurt dat zo weinig mogelijk aangrenzende knopen dezelfde kleur hebben, terwijl nummers van buren met dezelfde kleur zoveel mogelijk in waarde verschillen. Bedenk zelf een redelijke manier om hier één fitness-functie uit te halen.
De invoer (het probleem) ziet er uit als:
4 2
0 1 0 1
1 0 1 1
0 1 0 0
1 1 0 0
De eerste regel bevat het aantal knopen van de graaf (in het voorbeeld
4, maximaal zeg 50) en het aantal kleuren (in het voorbeeld 2,
maximaal zeg 10). Daarna staat de adjacency-matrix representatie
van de graaf: in ons voorbeeld 4 rijen met 4 getallen (0 of 1),
waarbij een 1 in de i-de rij / j-de kolom
een tak tussen knopen i en j betekent.
Beschrijf in het verslag (niet te lang, niet te kort!)
duidelijk representatie, fitness-functie, genetische operatoren, experimenten.
De uitvoer van het programma geeft een kleuring van de invoergraaf,
met daarbij de conflicten (buren met dezelfde kleur). Geen
grafische hoogstandjes svp.
Zie hier voor meer
informatie over gnuplot.
In te leveren: geprint verslag (in LaTeX gemaakt; de C++-code als Appendix, zie verder hier voor opmerkingen over het verslag), en per email: de C++-code. Stuur ook enkele gebruikte voorbeeldgrafen (in het verslag ook genoemd!) mee. Stuur svp geen emails met LaTeX/PS/PDF/executables.
Deadline: maandag 8 mei 2006.
Vragen en/of opmerkingen kunnen worden gestuurd naar: kosters@liacs.nl.
28 maart 2006 — http://www.liacs.nl/home/kosters/AI/ga06.html