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:
Deletions:
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.
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:
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:
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.
Edited on 2007-01-24 14:07:43 by MerelVeracx
Additions:
Edited on 2007-01-24 14:06:58 by MerelVeracx
Additions:
Deletions:
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.
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
anderscost = 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
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.
- 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)
- 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)
- Het is mogelijk om kalenders van dode mieren onderling te vergelijken (gedeelte in rode achtergrond)
- Het is mogelijk om kalenders in opbouw met elkaar te vergelijken (groene achtergrond)
- Het is mogelijk om kalenders van verschillende problemen met elkaar te vergelijken omdat het 'relatief' tov de optimal afstand berekent wordt.