ThesisWiki : ThesisHome

ThesisHome :: Categories :: PageIndex :: RecentChanges :: RecentlyCommented :: Login/Register

Thesis: Agenten voor het 'Traveling Tournament Problem'

.: Menu :.

Old
The story of the kangaroo

Probleemomschrijving

Experimentendata
Presentations
Thesistekst (1.8MB)
Verrassing:


Zoeken op deze site
Admin



Thesisomschrijving

This site was set-up during my final year (2007) at the university while working on my master thesis. Here you can find snippets of everything that crossed my mind in that year. I researched the possibilities of using Ant Algorithms for the Traveling Tournament Problem, a non-trivial, combinatorical optimization problem. The Jos Schepens Memorial organization awarded my thesis with their annual prize, stating that they found it had a scientific value above average and represented non-orthodox thinking with creative values. Also, the prize-winner is selected for her open minded personality and interest in practical applications of the research performed. Hooray for me!

Deze thesis onderzoekt de toepassingsmogelijkheden van mierenalgoritmes op een niet triviaal, combinatorisch optimalisatieprobleem.

Traveling Tournament Problem

Het Traveling Tournament Problem werd het eerst beschreven vanuit de sportwereld (bv Major League Baseball). In elke sporttak wordt er per seizoen een tornooi georganiseerd. Daarbij moeten alle ploegen elkaar 2 keer ontmoeten, 1 maal uit (op verplaatsing) en eenmaal thuis. Geen enkele ploeg mag meer dan drie keer uit spelen, of meer dan drie keer na elkaar thuis. Ook mag een wedstrijd van A tegen B niet gevolgd worden door de wedstrijd B-A. Als je een groot land hebt (zoals Amerika, of gans Europa) zijn de verplaatsingskosten van elke ploeg niet meer te verwaarlozen. Daarom moet er een kalender gevonden worden waarbij elke ploeg zo weinig mogelijk moet reizen. Dus ipv ploeg BelgiŽ eerst uit gaat spelen in Spanje en dan thuis spelen tegen Frankrijk om dan uit te spelen in Portugal, heeft de kalender BelgiŽ uit tegen Spanje, vervolgens uit tegen Portugal en uiteindelijk thuis tegen Frankrijk een kortere reisweg voor de Belgische ploeg.

Mijn algemene opdracht

We ontwerpen een uitbreidbare applicatie waarbij de performantie van agentgeorienteerde algoritmes onderzocht wordt. (Biologisch gedrag nabootsen, zie ook uitleg mieren en uitleg feromonen).

Mijn Conclusie

Ik heb een JAVA applicatie ontwikkeld die oplossingen zoekt voor TTP problemen, volledig configureerbaar met verschillende oplossingsmethodes. Het is mogelijk om twee soorten grafes te ontwerpen die bij een bepaald probleem horen. Als agenten heb ik mieren die in deze omgevingen kunnen rondlopen en zodoende hun kalender samenstellen. Om de verschillende variatiepunten samen te brengen, heb ik experimentmodules ontworpen. Hierbij is het mogelijk om random mieren, deterministische greedy mieren, Antsystem mieren en DYNCOAA mieren rond te laten lopen. Verder zijn alle parameters van de verschillende experimenten te specifiŽren via de commandline of via een vraag-en-antwoord opzetmodule (waarbij defaultwaarden te kiezen zijn).
Verder heb ik een analyse gemaakt van een goede kalenderkostfunctie, waarbij de kwaliteit van onvolledige kalenders onderling vergeleken moest worden.
Mieren kunnen ongelooflijk veel data genereren, dus heb ik een geweldige gegevensbank ontwikkeld. Deze laat toe om de berg gegevens die de kwaliteit van de gevonden oplossing (en dus het algoritme) laten gegevens gestructureerd en eenvoudig te evalueren via grafiekjes (Data! Data!).

In deze thesis hebben we onderzocht of mierenalgoritmes waarbij de mieren niet van een volledige kalender vertrekken geschikt zijn voor een niet-triviaal optimalisatieprobleem. We hebben verschillende varianten succesvol kunnen implementeren en testen. Voor probleem NL06 vinden de Ant System mieren snel resultaten zonder constraintfouten maar met een gemiddelde afstandsfout van 11%. De beste resultaten van DynCOAA mieren hebben een afstandkost van
20% boven de afstandskost van de optimale kalender. Bij het probleem van acht ploegen vinden ze ook kalenders zonder constraintfouten, maar de afstandskost schommelt daar rond de 23%.
Voor het probleem van 14 ploegen vinden ze met moeite een volledige kalender die aan de DRR constraint voldoet.

We hebben ook resultaten behaald op het vlak van software-ontwikkeling. De resulterende applicatie is eenvoudig uit te breiden en zeer configureerbaar:
- Er kunnen op een eenvoudige wijze nieuwe methodes en tactieken ingevoerd worden. Dit hebben we met de structuur van de verschillende experimenten aangetoond.
- Een selectie van verschillende methodes kunnen gebruikt worden om andere experimenten op te zetten. Het experiment Willekeurig is immers een experiment waarbij er niets gedaan wordt in de verschillende taktieken die we besproken hebben. Ant System gebruikt ander feromonengedrag en keuzegedrag dan DynCOAA.
- Van elk experiment wordt er op een gestructureerde manier informatie bijgehouden. We hebben reeds aangehaald dat het wegschrijven van deze informatie de werking van het algoritme vertraagde, maar er moet rekening gehouden worden dat de gegevensbank en de applicatie op verschillende locaties uitgevoerd werden. Deze vertraging is aanzienlijk kleiner indien de gegevensbank en de applicatie op dezelfde machine draaien.
- De ontwikkeling van een externe gegevensbank was belangrijk om de grote hoeveelheid gegevens gestructureerd te bewaren en snel te kunnen analyseren. Het evalueren van experimenten verliep beduidend sneller dan wanneer de gegevens in een tekstbestand opgeslagen werden.

Na een heel jaar enthousiast en met plezier bezig geweest te zijn met dit onderwerp, waren de resultaten niet opzienbarend. De stille droom om met een oplossing op een groot probleem een eervolle vermelding te krijgen op de webpagina van Trick, bleek al snel niet haalbaar.
Desalniettemin mag men niet uit het oog verliezen dat het een zeer moeilijk probleem is, wat we hebben proberen op te lossen met een íeenvoudigeí heuristiek. Mierenalgoritmes zijn relatief gemakkelijk te begrijpen, maar ik geloof dat de kracht van deze technieken erin ligt om ze te combineren met andere heuristieken.

Bedankt voor uw interesse,
Merel Veracx


Useful pages: FormattingRules, WikkaDocumentation, OrphanedPages, WantedPages, TextSearch.
Valid XHTML 1.0 Transitional :: Valid CSS :: Powered by Wikka Wakka Wiki 1.1.6.2
Page was generated in 0.0220 seconds