Opdracht 4: Mierenkolonie voor TSP

Opdracht

Los het handelsreizigerprobleem op met een systeem van mieren in Netlogo. [Dit probleem is er uit gehaald, en vervangen door Mierenkolonie voor QAP.]

Randvoorwaarden voor de implementatie*

1. De volgende GUI parameters zijn instelbaar: aantal steden, aantal mieren, leerfactor α factor β (zie hieronder).
2. Een netwerk van steden wordt bij de setup automatisch gegenereerd. De afstand tussen elk tweetal steden is gelijk aan de afstand op het Netlogo canvas.
3. Tijdens elke ronde vindt er animatie plaats. (“Er moet wat te zien zijn.”) Het wordt vrijgelaten wat je precies animeert.
4. Na elke ronde wordt er een plot gemaakt van tenminste: de gemiddelde lengte van een toer, de lengte van de kortste toer.

Belangrijke formules

De eerste belangrijke formule gaat over het kiezen van een volgende stad. Mier k staat op stad i, en kiest de volgende stad j als volgt:

j   =	VolgendeStadDoorFeromoon(i)	als q ≤ q0,
	VolgendeStadDoorVerkennen(i)	anders.

• Het getal q is een random getal tussen 0 en 1 die bij elke keuze van een stad opnieuw gegenereerd wordt.
• q₀ is een constante, die de drempelwarde voor exploratie aangeeft. Als de drempelwaarde hoog is, wordt er vaker geëxploiteerd.
• VolgendeStadDoorFeromoon(i) is een stad die bij exploitatie gekozen wordt.
• VolgendeStadDoorVerkennen(i) is een stad die bij exploratie gekozen wordt.

Exploitatie

VolgendeStadDoorFeromoon(i) is de stad j die dichtbij ligt en waarvan de weg i-j er naar toe “uitgesleten” is door voorgangers:

VolgendeStadDoorFeromoon(i) = argmax_h∈Jk{ Aantrekkelijkheid(i,h) }

• J_k is k's lijst van onbezochte steden.
• Stad h is een kandidaat-volgende stad. (Eén van h wordt j.)

De aantrekkelijkheid van de weg van stad i naar stad h wordt gegeven door

Aantrekkelijkheid(i,h) = [m(i,h)] ⋅ [v(i,h)]^β

• v(i,h) is omgekeerd evenredig aan de afstand van i tot h
• m(i,h) is de hoeveelheid feromoon van i naar h
• β is een constante die aangeeft hoe belangrijk we de invloed van het feromoon achten in verhouding tot de afstand.

Exploratie

VolgendeStadDoorVerkennen(i) is de stad die door exploratie verkregen wordt, met de “gewogen roulettewiel formule”. Aantrekkelijke hebben een grotere kans om voor exploratie geselcteerd te worden dan minder aantrekkelijke steden:

VolgendeStadDoorVerkennen(i) = gewogen_roulettewiel_keuze{ j | p_i,j }

• Het getal p_i,j is de kans dat stad j bij exploratie bezocht zal worden door k vanuit i:

  pi,j   =	aantrekkelijkheid van pad i-j som van de aantrekkelijkheid van alle paden naar steden vanuit i, die in deze ronde nog niet bezocht waren door k.	als j nog niet door k bezocht was
  	0	anders.

Feromoon

De tweede belangrijke formule bepaalt hoeveel geurstof een mier k afscheidt als deze pad i-j neemt.

m(i,j)_nieuw = α m(i,j)_vorig + (1-α)Δm(i,j)

• Het getal m(i,j) is de hoeveelheid geurstof op pad i-j.
• Het getal Δm(i,j) is de hoeveelheid extra geurstof die een mier k achterlaat op pad i-j.
• Het getal α is een gedurende het hele experiment constante leerfactor, dicht onder 1.

Na elke ronde is er een winnaar. Dat is de mier k die de kortste toer heeft gemaakt. Alleen k heeft het recht om feromoon af te scheiden op zijn spoor. De verliezers niet.

De hoeveelheid extra geurstof die overwinnaar k achterlaat op pad i-j is

Δm(i,j)   =	1 / ( lengte van toer van overwinnaar )	als pad i-j op toer van overwinnaar ligt,
	0	anders.