Kunstmatige intelligentie — Programmeeropgave 4, 2012 — Genetische algoritmen

plaatje De vierde programmeeropgave (in het voorjaar van 2012) behorende bij het vak Kunstmatige intelligentie gaat over Genetische algoritmen. Het is de bedoeling een eenvoudig Genetisch algoritme (GA) te ontwerpen dat een eenvoudige versie van het Vehicle Routing Probleem (VRP) zo goed mogelijk oplost.

Probleem

Er zijn n klanten verspreid over het land, en iedere klant wil een pakketje hebben. De beschikbare pakketjes moeten daartoe verdeeld worden over een m-tal vrachtwagens met capaciteit Q, die deze pakketjes verspreiden over de klanten. We nemen aan dat alle pakketjes gewicht 1 hebben, en dat klant 1 het zogenaamde "depot" voorstelt waar alle vrachtwagens vertrekken en uiteindelijk terugkomen.
Iedere vrachtwagen bedient minimaal 1 klant, en iedere vrachtwagen rijdt precies 1 route (van depot naar depot via zijn klanten). Het depot heeft geen pakketje nodig (maar bezit juist een oneindige hoeveelheid pakketjes).

De vraag is nu, gegeven n, m, Q en de locatie van de klanten, welke routes de vrachtwagens moeten rijden zodanig dat iedere klant een pakketje krijgt, de capaciteit van geen enkele vrachtwagen wordt overschreden, en de totale lengte van de routes minimaal is.

Een oplossing van het probleem bestaat uit m rijtjes van in een bepaalde volgorde bezochte klanten. De lengte van de oplossing is gelijk aan de som van de lengtes van de routes. Een oplossing is een individu van de populatie waarop het genetische algoritme gaat werken.

Datasets

Voor je experimenten kun je gebruik maken van de volgende datasets, afgeleid van de datasets uit de VRPLIB:

Op de eerste regel van een bestand staan achtereenvolgens n, m, en Q, alle integers gescheiden door spaties. Op de volgende n regels staat telkens het getal van de klant, gevolgd door zijn x- en y-coordinaten. Je kunt deze coordinaten, nadat je ze hebt ingelezen, het beste direct omschrijven naar afstanden, en deze opslaan in een double array. De uiteindelijke lengte van een oplossing is ook een double.

Opdracht

Ontwerp een eenvoudig genetisch algoritme dat het vehicle routing probleem (zo goed mogelijk) oplost.
Bedenk en beschrijf eerst een goede representatie voor individuen, waarop de genetische operatoren makkelijk toepasbaar zijn.
Hoe initialiseer je de populatie? Welke vormen van selectie, mutatie en cross-over ga je toepassen?
Hoe beoordeel je een individu op zijn fitness? Een lange route is niet zo erg, maar een te volle vrachtwagen is verboden.
Leg ook eens de link met de theorie. Wat voor soort genetisch algoritme gebruik je?
Experimenteer met minimaal twee parameters (bijvoorbeeld de mutatiekans en de populatiegrootte) en rapporteer over je bevindingen.
Heeft cross-over effect? Wat is de beste mutatiekans? Na hoe veel generaties convergeert de oplossing? Hoe ver zit je van de beste oplossing af?

Probeer niet het ultieme programma te schrijven. Beschrijf in het verslag in ieder geval naast bovenstaande zaken ook kort de werking van genetische algoritmen en het vehicle routing probleem in het algemeen. Geef duidelijk aan welke instanties met welke eigenschappen je hebt gebruikt, inclusief bronvermelding.

Voor de liefhebbers: vergelijk ook eens hoe het algoritme presteert op instanties met verschillende waarden van de "tightness" (in ons geval n/(m*Q)): de verhouding tussen het gewicht van alle pakketjes en de totale maximum-capaciteit. Verhoog of verlaag daartoe de waarde van Q in de verschillende testfiles.

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 8 mei 2012; Den Haag: woensdag 23 mei 2012.


Vragen en/of opmerkingen kunnen worden gestuurd naar: kosters@liacs.nl.

10 april 2012 — http://www.liacs.nl/home/kosters/AI/ga12.html