ThesisWiki : ReferenceForm

ThesisHome :: Categories :: PageIndex :: RecentChanges :: RecentlyCommented :: Login/Register
Most recent edit on 2007-04-07 07:04:54 by MerelVeracx

Additions:
1) Het is mogelijk om kalenders van verschillende problemen met elkaar te vergelijken omdat het 'relatief' tov de optimal afstand berekend wordt.

Deletions:
1) Het is mogelijk om kalenders van verschillende problemen met elkaar te vergelijken omdat het 'relatief' tov de optimal afstand berekent wordt.



Edited on 2007-01-26 15:06:13 by MerelVeracx

Additions:
imageimage

Deletions:
image
image




Edited on 2007-01-26 15:06:00 by MerelVeracx

Additions:
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.
image


Deletions:
Hieronder 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.
ter vergelijking randommieren resultaten:




Edited on 2007-01-26 14:57:04 by MerelVeracx

Additions:
image
ter vergelijking randommieren resultaten:




Edited on 2007-01-26 14:38:44 by MerelVeracx

Additions:
Hieronder 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.



Edited on 2007-01-26 14:37:07 by MerelVeracx

Additions:
image



Edited on 2007-01-24 15:42:25 by MerelVeracx

Additions:
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.

Deletions:
Ik heb snel een greedy ant 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.



Edited on 2007-01-24 15:41:42 by MerelVeracx

No differences.


Edited on 2007-01-24 15:40:09 by MerelVeracx

Additions:
Ik heb snel een greedy ant 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




Edited on 2007-01-24 14:07:43 by MerelVeracx

Additions:





Edited on 2007-01-24 14:06:58 by MerelVeracx

Additions:
imageimage

Deletions:
image image



Edited on 2007-01-24 14:06:32 by MerelVeracx

Additions:

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.
image
image
image




Edited on 2007-01-12 12:50:11 by MerelVeracx

Additions:

Reference-kalender-evaluatie



Deletions:

Reference-kalender-evaluatie





Edited on 2007-01-12 10:16:32 by MerelVeracx

Additions:

Verloop functie

Eigenschappen functie



Deletions:

Verloop functie

Eigenschappen functie





Edited on 2007-01-12 10:16:02 by MerelVeracx

Additions:
1) 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.



Edited on 2007-01-12 10:13:13 by MerelVeracx

Additions:
1) Constraints worden lineair beboet: een extra constraint kost evenveel wanneer het de eerste fout is, dan wanneer het de 50ste fout is.



Edited on 2007-01-12 10:08:52 by MerelVeracx

Additions:

Reference-kalender-evaluatie



Deletions:

Referency-kalender-evaluatie





Edited on 2007-01-12 10:08:40 by MerelVeracx

Additions:

Verloop functie





Edited on 2007-01-12 10:07:26 by MerelVeracx

Additions:
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.

Definitie





Oldest known version of this page was edited on 2007-01-11 17:39:53 by MerelVeracx []
Page view:

Referency-kalender-evaluatie

Of kortweg: de refkost.

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

Eigenschappen 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.

  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. Het is mogelijk om kalenders van dode mieren onderling te vergelijken (gedeelte in rode achtergrond)
  4. Het is mogelijk om kalenders in opbouw met elkaar te vergelijken (groene achtergrond)
  5. Het is mogelijk om kalenders van verschillende problemen met elkaar te vergelijken omdat het 'relatief' tov de optimal afstand berekent wordt.
Valid XHTML 1.0 Transitional :: Valid CSS :: Powered by Wikka Wakka Wiki 1.1.6.2
Page was generated in 0.0622 seconds