Het is de bedoeling een eenvoudig Genetisch algoritme (GA) dat zo goed mogelijk een ongerichte graaf zodanig inkleurt dat zo weinig mogelijk aangrenzende knopen dezelfde kleur hebben.
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.
Deadline: maandag 2 mei 2005.
Vragen en/of opmerkingen kunnen worden gestuurd naar: kosters@liacs.nl.
6 april 2005 — http://www.liacs.nl/home/kosters/AI/ga05.html