ThesisWiki : ExpAS4

ThesisHome :: Categories :: PageIndex :: RecentChanges :: RecentlyCommented :: Login/Register
Most recent edit on 2007-05-02 06:16:10 by MerelVeracx

Deletions:
We zien dus dat hoe groter het verschil tussen alfa en beta, hoe beter het algoritme presteert. Hierbij is het belangrijk dat alfa kleiner is dan beta. Dit zou te verklaren kunnen zijn door het grote verschil tussen de waarden van theta en eta (het totaal aantal feromonen op een pad en de heuristiek van een pad).
Deze experimenten laten uitschijnen dat een toenemende alfa GEEN goede rol speelt in het algoritme.
  1. Indien we de heuristiek van een pad scaleren (betere verspreiding van de waarden tussen 0 en 1 ipv tussen 0 en 0.01) ?
  2. Indien we de globale verdamping verminderen ?



    Edited on 2007-03-21 10:11:37 by MerelVeracx

    Deletions:

    Doel

Keuze van een pad

image als j N^k_i ; anders 0
Als boog J nog bezocht moet worden:
(de sterkte van het feromonenspoor)^ALFA * (heuristic desirability van IJ)^BETA
en dit gedeeld door totale kost van alle uitgaande bogen uit knoop I (som van alle feromonen en heuristic desirabilities)

Heuristic desirability van IJ

image
Hierbij is $\psi$ de extra kost die per schending geteld wordt en $nbv(game_j)$ het aantal schendingen van de constaints wanneer de wedstrijd $j$ toegevoegd zou worden aan de kalender. Indien wedstrijd $j$ A-B is, zal de kost afhankelijk zijn van de kalender die de mier al opgesteld heeft. Als geweten is van A dat ze eerder uit speelde tegen C, dan is $travelingdistance(A) = distance(C, A)$. Als A thuis speelde is dit 0. Dezelfde redenering voor B: indien ze eerder uitspeelde tegen D, dan is $travelingdistance(B) = distance(D, A)$. Als hij thuis speelde is dit $distance(B, A)$.

Feromoon evoluering

image
Hierbij is het versterken van het feromonenspoor gelijk aan:
(optimale kost kalender)/(kost kalender)

Numerieke resultaten (maxima en minima)

Zie hiervoor een overzicht (vergeleken met de numerieke waarden zoals beschreven in Swarm Intelligence, Bonnabeau) op numerieke resultaten van Ant System

Afstellen parameters

1. alfa:
2. beta:
3. globale evaporatie:




Edited on 2007-03-21 10:11:06 by MerelVeracx

Additions:

Experiment AS: vier ploegen

Zie voor gebruikte formules bij
Ant System experiments


Deletions:

Experiment AS: parameter optimalisatie





Oldest known version of this page was edited on 2007-03-21 09:47:11 by MerelVeracx [Cloned from ExpAB]
Page view:

Experiment AS: parameter optimalisatie


Doel

Keuze van een pad

image als j N^k_i ; anders 0

Als boog J nog bezocht moet worden:
(de sterkte van het feromonenspoor)^ALFA * (heuristic desirability van IJ)^BETA
en dit gedeeld door totale kost van alle uitgaande bogen uit knoop I (som van alle feromonen en heuristic desirabilities)

Heuristic desirability van IJ

image
Hierbij is $\psi$ de extra kost die per schending geteld wordt en $nbv(game_j)$ het aantal schendingen van de constaints wanneer de wedstrijd $j$ toegevoegd zou worden aan de kalender. Indien wedstrijd $j$ A-B is, zal de kost afhankelijk zijn van de kalender die de mier al opgesteld heeft. Als geweten is van A dat ze eerder uit speelde tegen C, dan is $travelingdistance(A) = distance(C, A)$. Als A thuis speelde is dit 0. Dezelfde redenering voor B: indien ze eerder uitspeelde tegen D, dan is $travelingdistance(B) = distance(D, A)$. Als hij thuis speelde is dit $distance(B, A)$.

Feromoon evoluering

image

Hierbij is het versterken van het feromonenspoor gelijk aan:
(optimale kost kalender)/(kost kalender)

Numerieke resultaten (maxima en minima)

Zie hiervoor een overzicht (vergeleken met de numerieke waarden zoals beschreven in Swarm Intelligence, Bonnabeau) op numerieke resultaten van Ant System

Afstellen parameters


1. alfa:
2. beta:
3. globale evaporatie:

Uitgevoerde experimenten

Alle experimenten werden 3 keer herhaald, uitgevoerd op omgeving 1 voor het probleem van 4 ploegen met telkens 6 mieren.

TacticNameTacticMethodParamNameValue
AntDiedPheromoneTacticAnt_died_is_linear_moremin_amount0.01
AntDiedPheromoneTacticAnt_died_is_linear_moremax_amount0.3
AntEnhancePheromoneTacticPheromone_enh_ASnear_optimal8276
CalenderCostTotalTacticVARIABLE (cost)--
EdgeSelectionTacticEdgeselection_ASalfaVARIABLE (a)
EdgeSelectionTacticEdgeselection_ASbetaVARIABLE (b)
ElitePheromoneTacticMax_m_times_enhancingmax_elite5
GlobalEvaporationTacticAS_global_evaporationglobal_evaporation_rateVARIABLE (p)

Experiment voor het te bestuderen van de feromonen in de omgeving.

Voor feromonengedrag analoog aan experiment 184 zie experiment 252, grafiek te bekijken op deze pagina.

Voor feromonengedrag analoog aan experiment 195 zie experiment 253, grafiek te bekijken op deze pagina.

4 teams         100 iteraties        
Expn ants a b p cost gem optimal all optimal? optimal in run improvementstop
184 6 1 5 0.5 R 1.000564 2 / 3 4 / 5 5 / 4 / 17
185 6 0 5 0.5 R 1.000564 2 / 3 5 / 34 14 / 5 / 34
186 6 3 1 0.5 R 1.018407 0 / 3 0 1 / 1 / 1
195 6 3 2 0.5 R 1.038465 0 / 3 0 2 / 1 / 6
196 6 2 3 0.5 R 1.009062 0 / 3 0 9 / 4 / 1
205 6 1 5 0.2 R 1.001692 0 / 3 0 34 / 30 / 3
206 6 1 5 0.4 R 1.000564 0 / 3 0 5 / 1 / 3
207 6 1 5 0.6 R 1.001128 1 / 3 22 22 / 8 / 30
208 6 1 5 0.7 R 1.000564 2 / 3 3 / 6 3 / 6 / 12
231 6 2 4 0.5 SR 1.021236 0 / 4 0 5 / 6 / 11 / 7

CalenderCostTotalTacticR = Totalcost_refdead_penalty 30
CalenderCostTotalTacticR = Totalcost_refconstraint_penalty 0.3
Edgeselection scaledR = no scalingscalingfactor 1
Edgeselection scaledSR = scalingscalingfactor 0.001

We zien dus dat hoe groter het verschil tussen alfa en beta, hoe beter het algoritme presteert. Hierbij is het belangrijk dat alfa kleiner is dan beta. Dit zou te verklaren kunnen zijn door het grote verschil tussen de waarden van theta en eta (het totaal aantal feromonen op een pad en de heuristiek van een pad).

Deze experimenten laten uitschijnen dat een toenemende alfa GEEN goede rol speelt in het algoritme.
  1. Indien we de heuristiek van een pad scaleren (betere verspreiding van de waarden tussen 0 en 1 ipv tussen 0 en 0.01) ?
  2. Indien we de globale verdamping verminderen ?
Valid XHTML 1.0 Transitional :: Valid CSS :: Powered by Wikka Wakka Wiki 1.1.6.2
Page was generated in 0.0431 seconds