Additions:
Mierensystemen in de computerwereld
Zie voor een uitgebreide beschrijving de literatuur:
Swarm-Intelligence, from natural to artificial systems, Dorigo et al, p. 40-56. Meer informatie∞
Solving Dynamic constraint optimization problems (Dyn COAA) p33-38 Download hier∞
DynCOAA
Pheromone weighting formula [CM95]:
Waarbij de r de hoeveelheid feromonen op een bepaalde boog is
Betha de osmotropotaxic sensitivity;
en 1/delta de sensory capacity.
Indien we gebruik maken van het bovenstaande gewicht van een boog, kan men de kans dat een boog i gekozen wordt omschrijven met:
waarbij k een mier aanduidt, A een node, i de boog die je kiest;
De kans om boog i te kiezen is zijn gewicht / totale gewicht van de boog. Hoe hoger het gewicht, hoe meer kans dat de boog gekozen wordt.
In DynCOAA werkt men met 2 soorten pheromonen: positieve die aangeven hoe graag een boog tov een andere boog geprefereerd wordt; en negatieve die aangeven hoe meer je een andere boog kunt overwegen.
Hierbij zijn r+ en r- respectievelijk de hoeveelheid positieve en negatieve feromonen op boog i. Betha en Delta zijn hetzelfde als hierboven.
Tenslotte kan een mier zijn verleden bekijken en op basis van het verleden de andere bogen evalueren (constraint checking, distance, ..). De uiteindelijke formule ziet er als volgt uit:
Hierbij is de gamma de geaccumuleerde kost van het verleden met de i-de boog.
Vastgestelde parameters
# mieren = # knopenbeta (osmotropotaxic capacity) = 3.5
1/delta (sensory capacity) = 0.2
eta_0 (weight cost vs pheromones) = 2
vee (decay of eta) = exp(ln(0.5)/total iterations)
roo (global evaporation) = 0.1
E (local evaporation) = 1 - sqrt(0.8)^(n)
Ant Systems
- alle mieren worden toegestaan feromonen te verspreiden
- de hoeveelheid feromonen is afhankelijk van de kwaliteit van het gevonden pad
- feromonen verdampen voordat de mieren opnieuw feromonen leggen (nadat elke mier een pad gevonden heeft)
De keuze van de mier wordt bepaald door de sterkte van het feromonenspoor op dat pad en hoe goed dat het pad bijdraagt tot de oplossing (cost van het pad minimaal).
Formullekes:
Keuze van een pad:
als j € N^k_i ; anders 0In woorden: de kans van mier K om van knoop I naar knoop J te gaan (en dus boog IJ te kiezen) in iteratie T is gelijk aan:
ALS J nog bezocht moet worden:
(de sterkte van het feromonenspoor)^ALFA * (heuristic desirability van IJ)^BETHA
en dit gedeeld door
totale kost van alle uitgaande bogen uit knoop I (som van alle feromonen en heuristic desirabilitys)
Vastgestelde parameters
In SI (Bonabeau) kiezen ze in algoritme AS-TSP op p 45 alfa = 1 en beta = 5. De beginferomoonwaarden voor elke boog wordt gelijk gesteld aan 10^(-6). Het aantal mieren wordt gelijkgesteld aan het aantal steden respectievelijk aantal knopen in de grafe.Ant Max-Min System (Stützle en Hoos)
- enkel de mier die het beste pad gevonden heeft, mag feromonen verspreiden
- de hoeveelheid feromonen wordt beperkt: er wordt zowel een minimumwaarde als een maximumwaarde afgedwongen.
- de feromonen op alle bogen wordt bij initialisatie op max_feromoon gezet
Experimenten hebben aangetoond [] dat de resultaten beter zijn wanneer er ook het pad met de gemiddelde beste weg regelmatig feromonen krijgt. (Trail smoothing mechanism, p55 in boek Swarm Intelligence, Dorigo en co).
Formullekes:
Ant Colony Systems
- heeft een andere manier voor het kiezen van een bepaald pad (voor details, zie literatuur)
- enkel de feromonen op het gemiddelde beste pad worden versterkt
- feromonen verdampen enkel wanneer er een mier overloopt en nadat een mier een feromonenupdate gedaan heeft.
Formullekes:
Referentie
[]: Thomas St¨utzle. Local search algorithms for combinatorial problems: Analysis, improvements and new applications. PhD thesis, Fachbereich Informatik, TU Darmstadt, Germany, 1998.Deletions:
Mierensystemen in de computerwereld
Zie voor een uitgebreide beschrijving de literatuur:
Swarm-Intelligence, from natural to artificial systems, Dorigo et al, p. 40-56. Meer informatie∞
Solving Dynamic constraint optimization problems (Dyn COAA) p33-38 Download hier∞
DynCOAA
Pheromone weighting formula [CM95]:Waarbij de r de hoeveelheid feromonen op een bepaalde boog is
Betha de osmotropotaxic sensitivity;
en 1/delta de sensory capacity.
Indien we gebruik maken van het bovenstaande gewicht van een boog, kan men de kans dat een boog i gekozen wordt omschrijven met:
waarbij k een mier aanduidt, A een node, i de boog die je kiest;
De kans om boog i te kiezen is zijn gewicht / totale gewicht van de boog. Hoe hoger het gewicht, hoe meer kans dat de boog gekozen wordt.
In DynCOAA werkt men met 2 soorten pheromonen: positieve die aangeven hoe graag een boog tov een andere boog geprefereerd wordt; en negatieve die aangeven hoe meer je een andere boog kunt overwegen.
Hierbij zijn r+ en r- respectievelijk de hoeveelheid positieve en negatieve feromonen op boog i. Betha en Delta zijn hetzelfde als hierboven.
Tenslotte kan een mier zijn verleden bekijken en op basis van het verleden de andere bogen evalueren (constraint checking, distance, ..). De uiteindelijke formule ziet er als volgt uit:
Hierbij is de gamma de geaccumuleerde kost van het verleden met de i-de boog.
Vastgestelde parameters
# mieren = # knopenbeta (osmotropotaxic capacity) = 3.5
1/delta (sensory capacity) = 0.2
eta_0 (weight cost vs pheromones) = 2
vee (decay of eta) = exp(ln(0.5)/total iterations)
roo (global evaporation) = 0.1
E (local evaporation) = 1 - sqrt(0.8)^(n)
Ant Systems
- alle mieren worden toegestaan feromonen te verspreiden
- de hoeveelheid feromonen is afhankelijk van de kwaliteit van het gevonden pad
- feromonen verdampen voordat de mieren opnieuw feromonen leggen (nadat elke mier een pad gevonden heeft)
De keuze van de mier wordt bepaald door de sterkte van het feromonenspoor op dat pad en hoe goed dat het pad bijdraagt tot de oplossing (cost van het pad minimaal).
Formullekes:
Keuze van een pad: als j € N^k_i ; anders 0In woorden: de kans van mier K om van knoop I naar knoop J te gaan (en dus boog IJ te kiezen) in iteratie T is gelijk aan:
ALS J nog bezocht moet worden:
(de sterkte van het feromonenspoor)^ALFA * (kost van het pad waarin IJ inzit)^BETHA
en dit gedeeld door
totale kost van alle uitgaande bogen uit knoop I (som van alle feromonen en kosten)
Vastgestelde parameters
In SI (Bonabeau) kiezen ze in algoritme AS-TSP op p 45 alfa = 1 en beta = 5. De beginferomoonwaarden voor elke boog wordt gelijk gesteld aan 10^(-6). Het aantal mieren wordt gelijkgesteld aan het aantal steden respectievelijk aantal knopen in de grafe.Ant Max-Min System (Stützle en Hoos)
- enkel de mier die het beste pad gevonden heeft, mag feromonen verspreiden
- de hoeveelheid feromonen wordt beperkt: er wordt zowel een minimumwaarde als een maximumwaarde afgedwongen.
- de feromonen op alle bogen wordt bij initialisatie op max_feromoon gezet
Experimenten hebben aangetoond [] dat de resultaten beter zijn wanneer er ook het pad met de gemiddelde beste weg regelmatig feromonen krijgt. (Trail smoothing mechanism, p55 in boek Swarm Intelligence, Dorigo en co).
Formullekes:
Ant Colony Systems
- heeft een andere manier voor het kiezen van een bepaald pad (voor details, zie literatuur)
- enkel de feromonen op het gemiddelde beste pad worden versterkt
- feromonen verdampen enkel wanneer er een mier overloopt en nadat een mier een feromonenupdate gedaan heeft.
Formullekes:
Referentie
[]: Thomas St¨utzle. Local search algorithms for combinatorial problems: Analysis, improvements and new applications. PhD thesis, Fachbereich Informatik, TU Darmstadt, Germany, 1998.Edited on 2006-12-10 14:38:48 by MerelVeracx
Deletions:
Goed, aangezien wij niet werken met negatieve feromonen (aka feromonen die iets vertellen over hoe slecht een boog het gedaan heeft in 't verleden), gaan we de formule een beetje aanpassen.
Neem het aantal negatieve feromonen constant gelijk aan 0:
dan blijft er over
Edited on 2006-12-10 14:37:03 by MerelVeracx
Additions:
Goed, aangezien wij niet werken met negatieve feromonen (aka feromonen die iets vertellen over hoe slecht een boog het gedaan heeft in 't verleden), gaan we de formule een beetje aanpassen.
Neem het aantal negatieve feromonen constant gelijk aan 0:
dan blijft er over
Edited on 2006-12-10 08:04:57 by MerelVeracx
Additions:
Ant Max-Min System (Stützle en Hoos)
- de feromonen op alle bogen wordt bij initialisatie op max_feromoon gezet
Deletions:
Ant Max-Min System
Experimenten hebben aangetoond [] dat de resultaten beter zijn wanneer er ook het pad met de gemiddelde beste weg regelmatig feromonen krijgt.Edited on 2006-11-13 08:32:48 by MerelVeracx
Additions:
Vastgestelde parameters
# mieren = # knopenbeta (osmotropotaxic capacity) = 3.5
1/delta (sensory capacity) = 0.2
eta_0 (weight cost vs pheromones) = 2
vee (decay of eta) = exp(ln(0.5)/total iterations)
roo (global evaporation) = 0.1
E (local evaporation) = 1 - sqrt(0.8)^(n)
Vastgestelde parameters
Edited on 2006-11-13 08:29:12 by MerelVeracx
Additions:
In SI (Bonabeau) kiezen ze in algoritme AS-TSP op p 45 alfa = 1 en beta = 5. De beginferomoonwaarden voor elke boog wordt gelijk gesteld aan 10^(-6). Het aantal mieren wordt gelijkgesteld aan het aantal steden respectievelijk aantal knopen in de grafe.
Edited on 2006-11-01 13:12:04 by MerelVeracx
Additions:
Tenslotte kan een mier zijn verleden bekijken en op basis van het verleden de andere bogen evalueren (constraint checking, distance, ..). De uiteindelijke formule ziet er als volgt uit:
Hierbij is de gamma de geaccumuleerde kost van het verleden met de i-de boog.
Edited on 2006-11-01 09:50:42 by MerelVeracx
Additions:
Waarbij de r de hoeveelheid feromonen op een bepaalde boog is
Betha de osmotropotaxic sensitivity;
en 1/delta de sensory capacity.
Indien we gebruik maken van het bovenstaande gewicht van een boog, kan men de kans dat een boog i gekozen wordt omschrijven met:
waarbij k een mier aanduidt, A een node, i de boog die je kiest;
De kans om boog i te kiezen is zijn gewicht / totale gewicht van de boog. Hoe hoger het gewicht, hoe meer kans dat de boog gekozen wordt.
In DynCOAA werkt men met 2 soorten pheromonen: positieve die aangeven hoe graag een boog tov een andere boog geprefereerd wordt; en negatieve die aangeven hoe meer je een andere boog kunt overwegen.
Hierbij zijn r+ en r- respectievelijk de hoeveelheid positieve en negatieve feromonen op boog i. Betha en Delta zijn hetzelfde als hierboven.
Edited on 2006-11-01 09:44:42 by MerelVeracx
Additions:
DynCOAA
Pheromone weighting formula [CM95]:Edited on 2006-10-17 15:03:03 by MerelVeracx
Additions:
totale kost van alle uitgaande bogen uit knoop I (som van alle feromonen en kosten)
Deletions:
de kost van het pad en de sterkte van het feromonenspoor erop voordat je IJ zou toevoegen.
Edited on 2006-10-17 14:23:01 by MerelVeracx
Additions:
In woorden: de kans van mier K om van knoop I naar knoop J te gaan (en dus boog IJ te kiezen) in iteratie T is gelijk aan:
ALS J nog bezocht moet worden:
(de sterkte van het feromonenspoor)^ALFA * (kost van het pad waarin IJ inzit)^BETHA
en dit gedeeld door
de kost van het pad en de sterkte van het feromonenspoor erop voordat je IJ zou toevoegen.
Edited on 2006-10-17 13:58:35 by MerelVeracx
Additions:
Deletions:
Edited on 2006-10-17 13:56:22 by MerelVeracx
Additions:
Formullekes:
Keuze van een pad:Formullekes:
Formullekes:
Deletions:
Keuze van een pad:
Edited on 2006-10-17 13:52:05 by MerelVeracx
Additions:
Edited on 2006-10-17 13:49:26 by MerelVeracx
Additions:
als j € N^k_i ; anders 0Deletions:
Edited on 2006-10-17 13:48:02 by MerelVeracx
Additions:
Keuze van een pad:
Edited on 2006-10-17 13:39:35 by MerelVeracx
Additions:
Referentie
CategoryRequirementsEdited on 2006-10-17 13:37:45 by MerelVeracx
Additions:
- heeft een andere manier voor het kiezen van een bepaald pad (voor details, zie literatuur)
- enkel de feromonen op het gemiddelde beste pad worden versterkt
- feromonen verdampen enkel wanneer er een mier overloopt en nadat een mier een feromonenupdate gedaan heeft.
Edited on 2006-10-17 13:33:44 by MerelVeracx
Additions:
Zie voor een uitgebreide beschrijving de literatuur:
Deletions:
Zie voor een uitgebreide beschrijving de literatuur:
Oldest known version of this page was edited on 2006-10-17 13:33:26 by MerelVeracx []
Page view:
Mierensystemen in de computerwereld
Zie voor een uitgebreide beschrijving de literatuur:
Swarm-Intelligence, from natural to artificial systems, Dorigo et al, p. 40-56. Meer informatie∞
Solving Dynamic constraint optimization problems (Dyn COAA) p33-38 Download hier∞
Ant Systems
- alle mieren worden toegestaan feromonen te verspreiden
- de hoeveelheid feromonen is afhankelijk van de kwaliteit van het gevonden pad
- feromonen verdampen voordat de mieren opnieuw feromonen leggen (nadat elke mier een pad gevonden heeft)
De keuze van de mier wordt bepaald door de sterkte van het feromonenspoor op dat pad en hoe goed dat het pad bijdraagt tot de oplossing (cost van het pad minimaal).
Ant Max-Min System
- enkel de mier die het beste pad gevonden heeft, mag feromonen verspreiden
- de hoeveelheid feromonen wordt beperkt: er wordt zowel een minimumwaarde als een maximumwaarde afgedwongen.
Experimenten hebben aangetoond [] dat de resultaten beter zijn wanneer er ook het pad met de gemiddelde beste weg regelmatig feromonen krijgt.
Ant Colony Systems
[]: Thomas St¨utzle. Local search algorithms for combinatorial problems: Analysis, improvements and new applications. PhD thesis, Fachbereich Informatik, TU Darmstadt, Germany, 1998.