De vierde programmeeropgave (in het voorjaar van 2011) behorende bij het vak
Kunstmatige intelligentie gaat over
Genetische algoritmen.
Het is de bedoeling een eenvoudig
Genetisch algoritme (GA) te ontwerpen
dat een inpak-probleem ("bin packing")
zo goed mogelijk oplost.
Er zijn n pakketjes, ieder met een eigen grootte
(gewicht). Deze moeten verdeeld worden over een m-tal vrachtwagens.
Ieder pakketje moet in precies één vrachtwagen komen.
De vrachtwagens hebben alle dezelfde maximum capaciteit Q.
We nemen in ieder geval aan dat het totale gewicht van de pakketjes
maximaal m keer Q is, anders past het zeker niet.
Lees allereerst een eenvoudige representatie van het probleem in,
bijvoorbeeld zoiets als:
2
10
4
3
4
5
6
De eerste regels bevatten het aantal vrachtwagens en de maximum
capaciteit (2 respectievelijk 10).
Daarna komt een regel met het aantal pakketjes (in het voorbeeld slechts
4, maximaal zeg 100), gevolgd door de gewichten.
Er zijn in dit geval trouwens in essentie twee verschillende oplossingen:
3-5 en 4-6, of 3-6 en 4-5.
De oplossingen zijn individuen, bijvoorbeeld rijtjes van n
getallen, waarbij het i-de getal het nummer van de vrachtwagen voor
het i-de
pakketje aangeeft.
Bedenk eenvoudige genetische operatoren, zie ook de
sheets
van het college.
Zo kan een mutatie één nummer wijzigen, of
misschien twee pakketjes van vrachtauto wisselen
Denk zelf na over crossover.
Probeer niet het ultieme programma te schrijven!
Haal ook eens een echt probleem van internet, en kijk hoe goed het Genetisch
Algoritme erop werkt.
Hier
zijn een aantal datasets te vinden waarop je je genetische algoritme kunt
testen.
Deze datasets geven niet van te voren het aantal benodigde vrachtwagens,
maar deze waarden kun je wel vinden in de tabel op de site (kolom getiteld
"m*"), en zelf toevoegen aan de datasets.
Deze datasets zijn vrij lastig, en je kunt ook een iets hogere "m*"-waarde
meegeven om tot een oplossing te komen.
We nemen soms (?) aan dat er een oplossing bestaat.
(In ons voorbeeld boven zouden de pakketjes wellicht ook
3, 4, 4 en 8 als gewicht kunnen hebben?)
Beschrijf in het verslag in ieder geval kort de werking van genetische
algoritmen en het bin packing probleem in het algemeen.
Geef duidelijk aan welke representatie van individuen en welke genetische
operatoren je hebt gebruikt in je algoritme. Hielp crossover?
Vergelijk ook eens hoe het algoritme presteert op instanties met
verschillende waarden van de "tightness": de verhouding tussen het gewicht van
alle n pakketjes, en de totale maximum-capaciteit m*Q.
Geef duidelijk aan welke instanties met welke eigenschappen (m, n, Q,
tightness) je hebt gebruikt, inclusief bronvermelding.
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 3 mei 2011.
Vragen en/of opmerkingen kunnen worden gestuurd naar: kosters@liacs.nl.
30 maart 2011 — http://www.liacs.nl/home/kosters/AI/ga11.html