ThesisWiki : ReferenceForm

ThesisHome :: Categories :: PageIndex :: RecentChanges :: RecentlyCommented :: Login/Register

Reference-kalender-evaluatie

Terug naar

het algoritme overzicht

Zie ook

Evaluatie Anagnostopoulos

Aangezien het in deze implementatie mogelijk is dat mieren op verschillende wijzen bepaalde kalenders gaan prefereren en, in het geval van de evaluatie van anagnostopoulus, bepaalde kenmerken van de kalenders niet gekwantificeerd kunnen worden (onvolledig zijn, ongeldig zijn, ..) heb ik besloten om een onafhankelijke evaluatiefunctie te schrijven.

Of kortweg: de refkost.

Definitie

De refkost van een kalender S wordt als volgt berekent:
laat # het aantal atmost + no repeat fouten zijn en
distance de totale afstand afgelegd door alle ploegen volgens S
en optimal de (benadering van de) afstand van de beste (constraint-vrije) kalender voor het specifieke probleem
met (parameters) dead-penalty = 30 en constraint = 0.3.

Dan is refkost(S) =
als mier dood
cost = optimal * dead-penalty + optimal * constraint * # + distance
anders
cost = optimal * constraint * # + distance

Als de mier niet dood is, en er geen constraints geschonden zijn, is de kost (dan natuurlijk) gelijk aan
cost = distance

Tenslotte is gebeurt er nog een scalering:
refkost(S) = cost / optimal

Verloop functie

image

Hier ziet u de kost van een aantal "type" kalenders geplot. Van links naar rechts wordt er telkens de kost berekend van kalenders van levende mieren met 0 constraintfouten tot 50 constraintfouten (stapjes van 10) en een afstand van 100 tot 5* optimal in 10 stappen; hetzelfde voor dode mieren.

Eigenschappen functie

  1. Een lege kalender van een dode mier heeft een hogere kost dan elke andere (redelijke) kalender van een levende mier (rode achtergrond tov witte achtergrond in grafiek)
  2. Een kalender met minder constraints heeft altijd een lagere kost dan een kalender met meer constraints (op kalenders met véél constraints en een héle lage kost na (oranje achtergrond in de grafiek)
  3. Constraints worden lineair beboet: een extra constraint kost evenveel wanneer het de eerste fout is, dan wanneer het de 50ste fout is.
  4. Het is mogelijk om kalenders van dode mieren onderling te vergelijken (gedeelte in rode achtergrond)
  5. Het is mogelijk om kalenders in opbouw met elkaar te vergelijken (groene achtergrond)
  6. Het is mogelijk om kalenders van verschillende problemen met elkaar te vergelijken omdat het 'relatief' tov de optimal afstand berekend wordt.
  7. Dit impliceert dat kalenders met hetzelfde aantal constraintfouten en die ongeveer dezelfde afstandsfout maken tov het optimale (welke afhankelijk is van het probleem) dezelfde reference cost zullen hebben.

Illustraties

Achtereenvolgens heb ik een aantal mieren met een zuiver random gedrag kalenders laten samenstellen en de (strikte) toename in hun kalenderkost bijgehouden. Telkens is er ook te zien hoeveel constraintfouten er gemaakt werden.
imageimage

image


Ik heb snel een deterministische greedy mier geïmplementeerd: hij verkiest altijd de boog die hem de kleine cost oplevert. We zien dat dit kortzichtige 'kortste pad eerst' helemaal niet goed werkt voor het ttp; meer zelfs, het doet voor grotere problemen alleen in het begin beter dan random. Deze experimenten werden gedaan voor omgeving 1.

image

Hieronder links zit u de resultaten van een greedy implementatie met een random element: wanneer er meer dan 5 keuzes zijn, geeft hij de 5 beste bogen (deze met de laagste kost) evenveel kans om gekozen te worden. Wanneer er geen 5 bogen meer zijn, krijgt enkel de beste boog kans om gekozen te worden. Rechts is ter vergelijking de resultaten van random ants gegeven. Daaronder het besluit.
imageimage
image
Valid XHTML 1.0 Transitional :: Valid CSS :: Powered by Wikka Wakka Wiki 1.1.6.2
Page was generated in 0.0225 seconds