De vierde programmeeropgave (in het voorjaar van 2010) behorende bij het vak
Kunstmatige intelligentie gaat over
Genetische algoritmen.
Het is de bedoeling een eenvoudig
Genetisch algoritme (GA) te ontwerpen
dat een handelsreiziger-probleem
zo goed mogelijk oplost.
Lees allereerst een eenvoudige representatie van een graaf in,
bijvoorbeeld zoiets als:
4
0 8 2 3
8 0 2 5
2 2 0 7
3 5 7 0
De eerste regel bevat het aantal knopen van de graaf (in het voorbeeld
4, maximaal zeg 50). Daarna staat de adjacency-matrix representatie
van de graaf: in ons voorbeeld 4 rijen met 4 getallen,
waarbij een geheel getal x ongelijk 0 in de
i-de rij / j-de kolom
een tak met gewicht (afstand) x tussen knopen i en j voorstelt.
De matrix is symmetrisch: tussen i en j
gebeurt hetzelfde als tussen j en i.
De bedoeling is een een rondrit voor de handelsreiziger te maken
met zo kort mogelijke totaalafstand. Alle knopen worden precies
één maal bezocht. De beginknoop en eindknoop zijn
hetzelfde.
De oplossingen zijn individuen, in dit geval permutaties van
1,2,...,n (met n het aantal knopen in de graaf).
Bedenk eenvoudige genetische operatoren, zie ook de
sheets
van het college.
Probeer niet het ultieme programma te schrijven!
Haal ook eens een echt probleem van internet, en kijk hoe goed het Genetisch
Algoritme erop werkt. Gebruik bijvoorbeeld
TSPLIB.
Beschrijf in het verslag (niet te lang, niet te kort!)
duidelijk representatie, fitness-functie, genetische operatoren, experimenten.
De uitvoer van het programma geeft de
"beste oplossing" die gevonden is voor een enkele voorbeeldgraaf.
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 svp geen emails met LaTeX/PS/PDF/executables.
Deadline: dinsdag 4 mei 2010.
Vragen en/of opmerkingen kunnen worden gestuurd naar: kosters@liacs.nl.
30 maart 2010 — http://www.liacs.nl/home/kosters/AI/ga10.html