Lees een eenvoudige representatie van een graaf in,
bijvoorbeeld zoiets als:
4
0 8 0 3
8 0 2 5
0 2 0 0
3 5 0 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 getal x ongelijk 0 in de
i-de rij / j-de kolom
een tak tussen knopen i en j betekent,
met gewicht x, een geheel getal; als er 0 staat is er geen tak tussen
de twee knopen.
De matrix is symmetrisch: tussen i en j
gebeurt hetzelfde als tussen j en i.
Een tekening van de graaf geeft voor
iedere knoop een geheeltallig coordinatenpaar,
met coordinaten tussen (zeg) 0 en 1000.
Zonodig kunnen de takken ook worden ingetekend.
Hierbij zijn twee zaken belangrijk:
takken mogen zo min mogelijk elkaar snijden;
en afstanden moeten evenredig zijn aan die in de gegeven representatie.
De afstanden in de tekening worden uitgerekend via
d((x1,y1),(x2,y2))=SQRT((x1-x2)2+(y1-y2)2) (voor punten (x1,y1) en (x2,y2)), waarbij SQRT worteltrekken betekent.
En hoe bepaal je of twee getekende takken snijden?
Schrijf daartoe eerst de twee vergelijkingen van de (oneindig lange) lijnen op,
in de vorm Ax+By=C,
bijvoorbeeld via A=y2-y1,
B=x1-x2 en C=x1 y2-x2 y1, voor de lijn door (x1,y1) en (x2,y2).
Los dan het stelsel van twee vergelijkingen op.
Je hebt dan het snijpunt van de twee lijnen.
Maar ligt dat op de twee lijn-segmenten, de takken?
Verifieer dus tot slot of het eventuele snijpunt tussen de knopen in ligt,
door te kijken of dit voor x- en y-coordinaten geldt.
Zie bijvoorbeeld hier voor meer informatie.
Het Genetisch algoritme heeft dus eigenlijk twee doelen ("multi-objective"): zo weinig mogelijk snijpunten, en zo weinig mogelijk afwijking voor de afstanden. Experimenteer een beetje met parameters voor een fitness-functie die beide zaken weegt.
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 tekening" die gevonden is voor een enkele voorbeeldgraaf. Geen
grafische hoogstandjes svp.
Zie hier voor meer
informatie over gnuplot.
Andere tip: Graphviz.
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 6 mei 2008.
Vragen en/of opmerkingen kunnen worden gestuurd naar: kosters@liacs.nl.
7 april 2008 — http://www.liacs.nl/home/kosters/AI/ga08.html