ThesisWiki : EnvironmentDesign

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

Additions:

Wedstrijdgrafe

Teamgrafe

Feromonengrafe

Vertrekkende van omgeving 3 probeerde ik de omgeving nog 'compacter' te krijgen. We werken opnieuw met verschillende soorten feromonen om een onderscheid te kunnen maken tussen de rondes, maar we hebben geen rondenaanduidingen meer. Elke mier begint zijn kalender door speeldag 1 in te vullen en werkt achtereenvolgens de andere speeldagen af.
Voor een illustratie en meer uitleg kunt u hier terecht.

Complexiteitoverzicht

image


Deletions:

Omgeving 1

Omgeving 2

Omgeving 4

TODO
Per ploeg wordt er een grafe uitgetekend waar zijn tegenstanders thuis en zijn tegenstanders uit in staan.
Elke mier moet nu voor zijn ploeg een gesloten pad zoeken, rekening houdend met de wensen van andere mieren.
Deze configuratie kan een tussenstap zijn tussen louter reactieve mieren en onderhandelende agenten (zie tweede semester).




Edited on 2007-04-07 07:13:27 by MerelVeracx

Deletions:
Tenslotte stelde Koen voor om nog een 4de omgeving uit te werken waarbij mieren een kalender proberen op te stellen voor "hun eigen' ploeg door in een omgeving rond te lopen, terwijl ze communiceren met andere mieren die hetzelfde proberen te doen. Dit zou een tussenstap zijn tussen een zuiver reactief algoritme en een zuiver intelligent/onderhandelend algoritme.
Er is nog veel werk te doen.




Edited on 2006-12-07 07:53:46 by MerelVeracx

Additions:
In mijn onderzoek was het dus nodig om goed na te denken over mogelijke grafeconfiguraties die geschikt zouden zijn. In een week brainstorming bedacht ik een drietal omgevingen. De eerste omgeving vertrekt van een omschrijving in de paper An Agent Based Metaheuristic for the TTP, dewelke ik geanalyseerd en geÔmplementeerd heb. De tweede omgeving is volledig eigen makelij, waarbij ik probeerde de grootte van de grafe naar beneden te krijgen. De derde omgeving tenslotte is een verder gezette poging, waarbij de grafe tot een minimum herleid is, maar waar er nood is aan 2(n-1) 'soorten' feromonen. We verwachten dus dat de complexiteit van de tweede en de derde vergelijkbaar is.

Deletions:
In mijn onderzoek was het dus nodig om goed na te denken over mogelijke grafeconfiguraties die geschikt zouden zijn. In een week brainstorming bedacht ik een drietal omgevingen. De eerste omgeving vertrekt van een omschrijving in de paper An Agent Based Metaheuristic for the TTP, dewelke ik geanalyseerd en geÔmplementeerd heb. De tweede omgeving is volledig eigen makelij, waarbij ik probeerde de grote van de grafe naar beneden te krijgen. De derde omgeving tenslotte is een verder gezette poging, waarbij de grafe tot een minimum herleid is, maar waar er nood is aan 2(n-1) 'soorten' feromonen. We verwachten dus dat de complexiteit van de tweede en de derde vergelijkbaar is.



Edited on 2006-12-07 07:50:06 by MerelVeracx

Additions:

Mijn omgevingen





Edited on 2006-12-07 07:48:06 by MerelVeracx

Additions:
Het ontwerp van een omgeving is een van dť belangrijkste stappen om een goed werkend mierenalgoritme te bekomen. Hierbij moeten we rekening houden dat een pad in de omgeving moet toelaten om een goede kalender op te stellen. Hoe strikter (hoe kleiner) een omgeving, hoe meer kans dat bepaalde oplossingen niet gevonden kunnen worden.. Hoe minder strikt (hoe groter), tjah, hoe minder kans dat mieren ooit eens een oplossing vinden.

Deletions:
Het ontwerp van een omgeving is een van dť belangrijkste stappen om een goed werkend mierenalgoritme te bekomen. Hierbij moeten we rekening houden dat een pad in de omgeving moet toelaten om een goede kalender op te stellen. Hoe strikter een omgeving, hoe meer kans dat bepaalde oplossingen niet gevonden kunnen worden.. Hoe minder strikt, tjah, hoe minder kans dat mieren ooit eens een oplossing vinden.



Edited on 2006-12-07 07:47:49 by MerelVeracx

Additions:
Het ontwerp van een omgeving is een van dť belangrijkste stappen om een goed werkend mierenalgoritme te bekomen. Hierbij moeten we rekening houden dat een pad in de omgeving moet toelaten om een goede kalender op te stellen. Hoe strikter een omgeving, hoe meer kans dat bepaalde oplossingen niet gevonden kunnen worden.. Hoe minder strikt, tjah, hoe minder kans dat mieren ooit eens een oplossing vinden.

Deletions:
Het ontwerp van een omgeving is een van dť belangrijkste stappen voor een goed werkend mierenalgoritme te bekomen. Hierbij moeten we rekening houden dat een pad in de omgeving moet toelaten om een goede kalender op te stellen. Hoe strikter een omgeving, hoe meer kans dat bepaalde oplossingen niet gevonden kunnen worden.. Hoe minder strikt, tjah, hoe minder kans dat mieren ooit eens een oplossing vinden.



Edited on 2006-12-07 07:46:58 by MerelVeracx

Additions:
Het ontwerp van een omgeving is een van dť belangrijkste stappen voor een goed werkend mierenalgoritme te bekomen. Hierbij moeten we rekening houden dat een pad in de omgeving moet toelaten om een goede kalender op te stellen. Hoe strikter een omgeving, hoe meer kans dat bepaalde oplossingen niet gevonden kunnen worden.. Hoe minder strikt, tjah, hoe minder kans dat mieren ooit eens een oplossing vinden. In mijn onderzoek was het dus nodig om goed na te denken over mogelijke grafeconfiguraties die geschikt zouden zijn. In een week brainstorming bedacht ik een drietal omgevingen. De eerste omgeving vertrekt van een omschrijving in de paper An Agent Based Metaheuristic for the TTP, dewelke ik geanalyseerd en geÔmplementeerd heb. De tweede omgeving is volledig eigen makelij, waarbij ik probeerde de grote van de grafe naar beneden te krijgen. De derde omgeving tenslotte is een verder gezette poging, waarbij de grafe tot een minimum herleid is, maar waar er nood is aan 2(n-1) 'soorten' feromonen. We verwachten dus dat de complexiteit van de tweede en de derde vergelijkbaar is.
Tenslotte stelde Koen voor om nog een 4de omgeving uit te werken waarbij mieren een kalender proberen op te stellen voor "hun eigen' ploeg door in een omgeving rond te lopen, terwijl ze communiceren met andere mieren die hetzelfde proberen te doen. Dit zou een tussenstap zijn tussen een zuiver reactief algoritme en een zuiver intelligent/onderhandelend algoritme.
Er is nog veel werk te doen.




Edited on 2006-11-15 05:37:20 by MerelVeracx

Additions:
Deze grafe omvat n(n-1)+2(n-1) knopen minder dan (# knopen)*(# knopen - 1) bogen. De knopen vallen uiteen in 2 categoriŽn: een ronde knoop wordt gezien als het begin van een nieuwe ronde (en heeft dus een volgnummer); een wedstrijdknoop stelt een bepaalde wedstrijd voor waarbij er een thuisspelende ploeg is en een uitspelende ploeg.

Deletions:
Deze grafe omvat n(n-1)+2(n-1) knopen en (# knopen)*(# knopen - 1) bogen. De knopen vallen uiteen in 2 categoriŽn: een ronde knoop wordt gezien als het begin van een nieuwe ronde (en heeft dus een volgnummer); een wedstrijdknoop stelt een bepaalde wedstrijd voor waarbij er een thuisspelende ploeg is en een uitspelende ploeg.



Edited on 2006-10-06 12:39:37 by MerelVeracx

Additions:

Omgeving 1

Omgeving 3

Voor een illustratie en meer uitleg kunt u hier terecht.


Deletions:

Omgeving 1

Omgeving 3

Algemeen

De verkregen structuur ziet er zo uit:
image
Ik verkoos ervoor om alle 'ronde'-knopen te vervangen door een grote 'ronde'-knoop.
We hebben nu veel minder knopen (en dus minder bogen) om informatie in bij te houden.Een mier kan een kalender opstellen door ELKE BOOG MINSTENS EEN KEER te bezoeken, en op zo'n manier dat hij begint met de 'ronde'-knoop (de rode knop in 't midden) vervolgens een toer maakt doorheen de ploegen en opnieuw naar de 'ronde'-knoop uitwijkt.
Opgelet: een kalender niet niet alle 'NAAR ronde-knoop' of 'VAN ronde knoop' is ook een goede kalender!
Op die manier zal de mier bv de deeloplossing ROOD-PHI-NYM-MON-ATL-ROOD-ATL-PHI-MON-NYM-ROOD krijgen, welke we kunnen interpreteren als: in de 1ste ronde speelt PHI thuis tegen NYM en MON thuis tegen ATL. In de 2de ronde speelt ATL thuis tegen PHI enzo.
Aangezien we nu bepaalde bogen meerdere keren zullen opnemen in een (goede) oplossing, gaan we meer informatie moeten kunnen opslagen in de grafe.
Een eventuele oplossing is om 2(n-1) feromonen te voorzien. Wanneer een mier toegestaan wordt feromonen te droppen, zal hij op ROOD-PHI, PHI-NYM, MON-ATL en ATL-ROOD 'ronde 1'-feromonen droppen. Op ROOD-ATL, ATL-PHI, ... dropt hij 'ronde 2'-feromonen.
Het nadeel hier is dat de boog MON-ATL eigenlijk geen wedstrijd in ronde 1 voorstelt. Experimenten zullen moeten uitwijzen of dit een probleem vormt, en hoe het vermeden kan worden.
De optimale kalender werd ook hier eens uitgewerkt:
image




Edited on 2006-10-06 12:36:57 by MerelVeracx

Additions:

Omgeving 2

Deze grafe omvat 2n(n-1)+2(n-1) knopen en n*(n-1)*2(n-1) + 2n*2(n-1) bogen. Opnieuw zijn er twee categoriŽn bogen: rondeknopen en ploegknopen. Elke ronde wordt verbonden met een subgrafe waarin alle de ploegen staan.
Voor een illustratie en meer uitleg kunt u hier terecht.


Deletions:

Omgeving 2

Hier zetten we de ploegen en de rondes centraal ipv de wedstrijden en de rondes. Elke ronde wordt verbonden met een subgrafe waarin de ploegen staan. In die subgroep wordt er de wedstrijden voor die ronde gemodeleerd. Van de ene subroep ga je over naar de volgende ronde. De mier moet een toer vinden in de grafe waarbij ALLE KNOPEN JUIST EEN KEER bezocht worden.
De grafe zal er zo uitzien:
image
En de optimale oplossing ziet er als volgt uit:
image




Edited on 2006-10-06 12:31:50 by MerelVeracx

Additions:

Deelpagina's

Omgeving 1
Omgeving 2
Omgeving 3




Edited on 2006-10-06 12:30:10 by MerelVeracx

Additions:

Omgeving 1

Deze grafe omvat n(n-1)+2(n-1) knopen en (# knopen)*(# knopen - 1) bogen. De knopen vallen uiteen in 2 categoriŽn: een ronde knoop wordt gezien als het begin van een nieuwe ronde (en heeft dus een volgnummer); een wedstrijdknoop stelt een bepaalde wedstrijd voor waarbij er een thuisspelende ploeg is en een uitspelende ploeg.
Voor een illustratie en meer uitleg kunt u hier terecht.


Deletions:

Omgeving 1

Deze omgeving kenmerkt zich door de keuze van de knopen. Elke wedstrijd die in de kalender opgenomen moet worden, wordt voorgesteld door een knoop.
De rode knoppen in het midden stellen de rondes voor.
Een toer die alle KNOPEN (zowel de wedstrijd als de rode) JUIST EENMAAL aandoet, heeft een geldige kalender gevonden voor het probleem.
Het grote nadeel van deze aanpak is de grootte van de omgeving. Tel alle knopen en bogen op die je moet voorstellen, en je krijgt O(n^4) objecten.
Alle knopen worden met elkaar verbonden. Het weergeven van deze structuur zou niet meer overzichtelijk zijn, waardoor ik de optimale oplossing gewoon aangeduid heb.
De mieren beginnen hun toer in de knoop ronde 1, aangezien je de kalender niet kunt beginnen opbouwen in 't midden (er zou niets zinnig gezegd kunnen worden over de kost van de bekomen kalender). Let me rephrase that: geen enkel idee of er geen kosten kunnen berekend worden voor een willekeurig opgevulde kalender. Daarom gaan we nu eerst eens over tot het berekenen van de kosten voor een kalender: op deze pagina.
image

Opmerkingen

Visualisatie in matrixvorm van de feromonen die bijgehouden moeten worden:

image




Edited on 2006-09-30 18:34:18 by MerelVeracx

Additions:
Berekenen van de kost van een kalender
De mieren beginnen hun toer in de knoop ronde 1, aangezien je de kalender niet kunt beginnen opbouwen in 't midden (er zou niets zinnig gezegd kunnen worden over de kost van de bekomen kalender). Let me rephrase that: geen enkel idee of er geen kosten kunnen berekend worden voor een willekeurig opgevulde kalender. Daarom gaan we nu eerst eens over tot het berekenen van de kosten voor een kalender: op deze pagina.


Deletions:
De mieren beginnen hun toer in de knoop ronde 1, aangezien je de kalender niet kunt beginnen opbouwen in 't midden (er zou niets zinnig gezegd kunnen worden over de kost van de bekomen kalender). Let me rephrase that: geen enkel idee of er geen kosten kunnen berekend worden voor een willekeurig opgevulde kalender. Daarom gaan we nu eerst eens over tot het berekenen van de kosten voor een kalender.



Edited on 2006-09-30 18:33:31 by MerelVeracx

Additions:
De mieren beginnen hun toer in de knoop ronde 1, aangezien je de kalender niet kunt beginnen opbouwen in 't midden (er zou niets zinnig gezegd kunnen worden over de kost van de bekomen kalender). Let me rephrase that: geen enkel idee of er geen kosten kunnen berekend worden voor een willekeurig opgevulde kalender. Daarom gaan we nu eerst eens over tot het berekenen van de kosten voor een kalender.



Edited on 2006-09-20 21:31:36 by MerelVeracx

Additions:


Deletions:
 




Edited on 2006-09-20 21:14:39 by MerelVeracx

Additions:
CategoryRequirements

Deletions:
CategoryDesign - CategoryRequirements



Edited on 2006-09-20 21:13:01 by MerelVeracx

Additions:
 


Deletions:




Edited on 2006-09-20 21:12:52 by MerelVeracx

Additions:


Deletions:
Terug



Edited on 2006-09-20 20:51:30 by MerelVeracx

Additions:
CategoryDesign - CategoryRequirements

Deletions:
CategoryDesign



Oldest known version of this page was edited on 2006-09-20 20:51:04 by MerelVeracx []
Page view:
Terug

Non-functional Requirements: de omgeving

Random Talk


Omgeving 1

Algemeen

Deze omgeving kenmerkt zich door de keuze van de knopen. Elke wedstrijd die in de kalender opgenomen moet worden, wordt voorgesteld door een knoop.
De rode knoppen in het midden stellen de rondes voor.
Een toer die alle KNOPEN (zowel de wedstrijd als de rode) JUIST EENMAAL aandoet, heeft een geldige kalender gevonden voor het probleem.
Het grote nadeel van deze aanpak is de grootte van de omgeving. Tel alle knopen en bogen op die je moet voorstellen, en je krijgt O(n^4) objecten.

Alle knopen worden met elkaar verbonden. Het weergeven van deze structuur zou niet meer overzichtelijk zijn, waardoor ik de optimale oplossing gewoon aangeduid heb.

image

Opmerkingen


Visualisatie in matrixvorm van de feromonen die bijgehouden moeten worden:

image

Omgeving 2

Hier zetten we de ploegen en de rondes centraal ipv de wedstrijden en de rondes. Elke ronde wordt verbonden met een subgrafe waarin de ploegen staan. In die subgroep wordt er de wedstrijden voor die ronde gemodeleerd. Van de ene subroep ga je over naar de volgende ronde. De mier moet een toer vinden in de grafe waarbij ALLE KNOPEN JUIST EEN KEER bezocht worden.

De grafe zal er zo uitzien:

image

En de optimale oplossing ziet er als volgt uit:

image

Omgeving 3

Algemeen

Vertrekkende van omgeving 2 probeerde ik de omgeving nog 'compacter' te krijgen. Ipv subgrafes te definiŽren, zullen we hier werken met verschillende soorten feromonen om een onderscheid te kunnen maken tussen de rondes.

De verkregen structuur ziet er zo uit:

image

Ik verkoos ervoor om alle 'ronde'-knopen te vervangen door een grote 'ronde'-knoop.
We hebben nu veel minder knopen (en dus minder bogen) om informatie in bij te houden.Een mier kan een kalender opstellen door ELKE BOOG MINSTENS EEN KEER te bezoeken, en op zo'n manier dat hij begint met de 'ronde'-knoop (de rode knop in 't midden) vervolgens een toer maakt doorheen de ploegen en opnieuw naar de 'ronde'-knoop uitwijkt.
Opgelet: een kalender niet niet alle 'NAAR ronde-knoop' of 'VAN ronde knoop' is ook een goede kalender!

Op die manier zal de mier bv de deeloplossing ROOD-PHI-NYM-MON-ATL-ROOD-ATL-PHI-MON-NYM-ROOD krijgen, welke we kunnen interpreteren als: in de 1ste ronde speelt PHI thuis tegen NYM en MON thuis tegen ATL. In de 2de ronde speelt ATL thuis tegen PHI enzo.

Aangezien we nu bepaalde bogen meerdere keren zullen opnemen in een (goede) oplossing, gaan we meer informatie moeten kunnen opslagen in de grafe.

Een eventuele oplossing is om 2(n-1) feromonen te voorzien. Wanneer een mier toegestaan wordt feromonen te droppen, zal hij op ROOD-PHI, PHI-NYM, MON-ATL en ATL-ROOD 'ronde 1'-feromonen droppen. Op ROOD-ATL, ATL-PHI, ... dropt hij 'ronde 2'-feromonen.

Het nadeel hier is dat de boog MON-ATL eigenlijk geen wedstrijd in ronde 1 voorstelt. Experimenten zullen moeten uitwijzen of dit een probleem vormt, en hoe het vermeden kan worden.

De optimale kalender werd ook hier eens uitgewerkt:

image

Omgeving 4


TODO

Per ploeg wordt er een grafe uitgetekend waar zijn tegenstanders thuis en zijn tegenstanders uit in staan.

Elke mier moet nu voor zijn ploeg een gesloten pad zoeken, rekening houdend met de wensen van andere mieren.

Deze configuratie kan een tussenstap zijn tussen louter reactieve mieren en onderhandelende agenten (zie tweede semester).



CategoryDesign
Valid XHTML 1.0 Transitional :: Valid CSS :: Powered by Wikka Wakka Wiki 1.1.6.2
Page was generated in 0.0787 seconds