ThesisWiki : Literatuurstudie

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

Literatuur

Op deze pagina

Books
Papers (en samenvattingen)
Internetlinks

Literatuurstudie

Het fascinerende aan het probleem is dat het een verschrikkelijk grote oplossingsverzameling heeft. De computer kan niet domweg alle mogelijkheden afgaan en bijhouden welke kalender de kortste totale reisweg geeft.. Het probleem is pas in 2001 in de belangstelling gekomen. Er wel interessante oplossingsmethoden voorgesteld, maar er valt nog veel te onderzoeken. Zo zijn er al algoritmes met simulated annealing (oplossingsverzameling willekeurig laten onderzoeken, waarbij meer of minder 'straf' wordt gegeven voor slechte(re) oplossingen, waarbij het de bedoeling is dat er naar een globale, optimale oplossing geconvergeerd wordt. Zie Anagnostopoulos, 2003) en met Tabu Search (oplossingsverzameling zo eng mogelijk proberen te maken, en de computer dan laten zoeken, terwijl er een geheugen van recent onderzochte oplossingen bijgehouden wordt. Zie Gaspero, 2006) die redelijk goede resultaten geven.

Books

Introducing Game Theory and Its Applications
2004 - Elliott Mendelson (ISBN 1-58488-300-6)
Inleiding tot spelstrategieŽn. Analyse van verschillende spelcategorieŽn doorspekt met voorbeelden en 'goede oefening voor thuis'-oefeningen.

Navigatie

Beginpagina
Samenvatting 5 papers
Samenvatting ant papers
Samenvatting rest papers

Swarm Intelligence - From Natural to Artificial Systems
1999 - Eric Bonabeau / Marco Dorigo (Belg!) / Guy Theraulaz (ISBN 0-19-513159-2)
Een 270 blz tellende samenvatting van de vooruitgang die geboekt is op vlak van swarm intelligence. Foraging behaviour, Task Allocation, Data Analysis, Graph Partitioning, Self-Assembling en Cooperative Transport worden behandeld.
Prey
2002 - Michael Crichton (ISBN 0066214122)
Cool fictie boek over nanopartikel robotjes die zich weten te organiseren in zwermen en gefilosofeer over hoe zo'n nieuwe wezens zouden jagen, nadenken, zichzelf zouden voortplanten, ...

Papers

Reeds behaalde resultaten in de literatuur

Neighborhood Search Algorithm for the Combined Through and Fleet Assignment Model
december 2001 Ė Ahuja / Goodstein / Mukherjee (Florida / Chicago / Cambridge)
Samenvatting
Het Combined Through and Fleet Assignment Problem is het constraint/optimalisatieprobleem waarbij je een reeks van aangeboden vluchttrips zo moet combineren tot vluchten zodat er een minimale inzet van resources nodig is, en er tevens voldaan wordt aan verscheidene kwaliteitsvoorwaarden.
[ETdescrip] The Traveling Tournament Problem: Description And Benchmarks
2001 Ė Easton / Nemhauser / Trick (USA) Download
Samenvatting
Eerste artikel over het Traveling Tournament Probleem.
Solving The Traveling Tournament Problem: a combined integer programming and constraint programming approach.
2003 Ė Easton / Nemhauser / Trick (USA)
Samenvatting
Er werd hier een implementatie gedaan gebaseerd op integer en constraint programming, waardoor ze de optimale oplossing hebben gevonden voor het probleem tot 8 ploegen. Belangrijkste conclusie uit het artikel vind ik dat ze voor het probleem van 8 ploegen een oplossing vinden binnen de vier dagen. Als ze tenminste 20 parallelle processoren erop laten stampen.
A Simulated Annealing Approach to the TTP
2003 Ė Anagnostopoulos / Michel / Hentenryck / Vergados (USA)
Samenvatting
Vertrekkende van de definitie van een omgeving van een kalender, laten ze het algoritme een geleide zoektocht doorheen omgevingen doen. Afhankelijk van de 'temperatuur' zal het algoritme nu en dan de omgevingen van minder goede kalenders ook verkennen. Hoewel het nooit zeker is dat dit algoritme een optimale (of bijna optimale) oplossing gevonden heeft, blijkt het in de praktijk zeer goed te werken. Ze verbeterden de best gekende resultaten tot 16 ploegen. Dit gebeurde voor het probleem van 12 ploegen al na ongeveer 17 minuten.
A Composite-Neighborhood Tabu Search Approach to the TTP
mei 2006 Ė Gaspero / Schaerf (Italie)
Samenvatting
Dit artikel onderzoekt de mogelijkheden van een 'Taboe geleidde zoektocht', hierbij herinnert het algoritme welke kalenders hij best niet kan onderzoeken (bv omdat hij al ervaren heeft dat ze niet goed zijn). Ze gebruiken dezelfde definitie van omgevingen als Anagnostopoulos, waarbij ze omgevingen die equivalent zijn aan elkaar, er zogezegd uitfilteren. De resultaten benaderen de best gekende resultaten, maar zijn altijd minder goed. De belangrijkste bijdrage van dit artikel is (vermoed ik) de analyse van kalenderomgevingen en de TODO experimentele analyse.
A Tiling Approach for Fast Implementation of the TTP
2006 Ė Bar-Noy / Moody (New York) Download PATAT 06
Via een minimale opspannende boom per ploeg krijg je een overzicht in welke volgorde een ploeg de andere ploegen het best kan bezoeken. Er worden kettingen van achtereenvolgende ploegen gevormd die men dan tiles noemt. Vervolgens wordt het tiling algo erop losgelaten om kalenders te zoeken die aan de TTP constraints voldoen.

Ant Algorithm Approach

Solving Dynamic constraint optimization problems (Dyn COAA)
heden Ė Mertens (Belgie) Download
Samenvatting
Een doctoraat die een algemene dynamic constraint satification solver voorstelt, door gebruik te maken van een antgerichte aanpak.
Ant Colony Optimization: The Traveling Salesman Problem
(1999) Bonabeau / Dorigo/ Theraulaz, Swarm Intelligence ISBN 0-19-513159-2 - p39-56
Samenvatting
An Agent Based Metaheuristic for the TTP
(?) - Adriaen / Custers / Vandenberghe (BelgiŽ)
Samenvatting
Toepassing van de ACO approach op het TTP. Redelijk korte paper.
Antalgorithms voor exaamkalenders
2006 - Michael Eley (Duitsland) - Download PATAT 06
Zowel een AS als een MMAS approach voor het opstellen van examenkalenders waarin het de bedoeling is een conflictvrij verdeling van examens te krijgen. Zowel de toegewezen lokalen, beschikbaarheid van de professoren en belasting van de studenten worden in rekening gebracht.
An Ant based hyper-heuristic for the TTP
(2006) - Pai-Chun Chen / Graham Kendall / Vandenberghe (BelgiŽ)
Artikel
Hier vertrekken de mieren met een geldige double round-robin kalender. In hun omgeving bevatten de knopen transitieregels die ze moeten toepassen op hun kalender als ze die knoop passeren. Op die manier kan een bepaalde toer een kalender zodanig wijzigen dat er een zeer goede (optimale) kalender bereikt wordt. De mieren kunnen opnieuw andere mieren beÔnvloeden door geursporen. Mieren mogen de omgeving op een willekeurige manier doorkruisen (cirkels zijn dus toegestaan). Ze bereiken goede resultaten.
How Swarms build cognitive Maps.
(1995) - Chialvo, Millonas
download

Algemeen

Measurability and reproducibility in Timetabling Research: state-of-the-art and discussion
(2006) A. Schaerf / Luca Di Gaspero (ItaliŽ). Download PATAT 06
Experimenten worden uitgevoerd om op een empirische manier bepaalde hypotheses te bevestigen, verwerpen. Belangrijk is het dat andere onderzoekers deze resultaten moeten kunnen vergelijken met andere resultaten. Dataformaat van de probleemdata, rekentijd formulering in functie van het systeem, statistische analyse en een open communicatie (bv uitgebreidere rapportering op een website) zijn zaken die hier besproken worden.
Designing and reporting on computational experiments with heuristic methods.
(1995) R.S. barr, Bruce Golden, J. Kelly, M.G.C. Resende, W.R. Steward (dallas, maryland,..).
Deze paper gaat uitgebreider in op het ontwerp van experimenten en de rapportering erover toegespitst op heuristische methodes. Aangezien dit onderwerp vrij belangrijk is in het tweede semester, heb ik hier een werkblad rond gemaakt op ontwerp van experimenten.
Scheduling a major college basketbal conference
1997 - Trick / Nemhauser - Download
Samenvatting
In deze paper werd er via een integer-constraint programming methode een kalender uitgewerkt voor de Atlantic Coast Conference, waarin 9 schoolploegen elkaar over een periode van 2 maanden, twee wedstrijden per week. Ze beschrijven zo'n 19 constraints waaraan hun kalender moest voldoen, zoals minstens 1 populaire wedstrijd per week voor de televisie constracten te kunnen naleven of ervoor zorgen dat zwakkere ploegen niet achtereenvolgens tegen de sterkste ploegen moesten spelen.
Scheduling the Brazilian Soccer Championship
2006 - Ribeiro / Urrutia - Download PATAT 06 p.481-483
Snel te lezen real life probleem waarbij ze voor 22 ploegen uit BraziliŽ een kalender opstellen waarbij er enerzijds het aantal opeenvolgende uit-thuis wedstrijden proberen te beperken, het aantal goed bekeken wedstrijden voor de televisie proberen te maximaliseren en te voldoen aan een aantal constraints waarbij bv. de belangrijkste ploegen van de belangrijkste steden niet tegelijk in ťťn stad mogen spelen. Ook is een bepaalde stad minder aantrekkelijk voor de media, waardoor wanneer er maar 1 favoriet buiten de belangrijkste steden speelt, dat die uitwedstrijd dan niet in de niet gewilde stad gebeurt... Op 10 minuten hebben ze op dezelfde manier als beschreven in Scheduling a major college basketbal conference een kalender gevonden die volgens hun beter was dan de kalenders die handmatig samengesteld werden.
Multithreaded Tests with JUnit
2003 - Alex Rupp - Today Java .Net Bron Artikel pdf
JUnit is the glue that holds many open source projects together. But JUnit has problems performing multithreaded unit tests. This creates considerable difficulty for middleware developers in the open source J2EE market. This article introduces GroboUtils, a JUnit extension library designed to address this problem and enable multithreaded unit testing in JUnit. A basic understanding of JUnit and threads is recommended but not necessary for readers of this article.

..Processing..

TODO MM05d MERKLE, D. and M. MIDDENDORF: Swarm Intelligence. In BURKE, E. and G. KENDALL (editors): Introductory Tutorials in Optimisation, Search and Decision Support Methodology. Kluwer, 2005. (mail send)

Internetlinks

J.L. Deneubourg
Onderzoek bij sociale insecten en hoe dit gedrag gebruikt kan worden in automatische systemen.
Greet Vanden Berghe
Vakgroep Informatietechnologie, Departement Industrieel Ingenieur aan het KaHo St.-Lieven. Heeft de volgende onderzoeksinteresses: Automatische Personeelsplanning, Nurse Rostering, Timetabling and Scheduling, Agent Technology, Optimisation, Meta-Heuristics, Artificial Intelligence.
Publicaties
Marco Dorigo (ACO)
In 1999, the Ant Colony Optimization metaheuristic was defined by Dorigo, Di Caro and Gambardella. The first ACO system was introduced by Marco Dorigo in his Ph.D. thesis (1992), and was called Ant System (AS).
Publicaties
PATAT
The International Series of Conferences on the Practice and Theory of Automated Timetabling (PATAT) is held bi-annually as a forum for both researchers and practioners of timetabling to exchange ideas.
IEEE TEC
Papers on application, design, and theory of evolutionary computation, with emphasis given to engineering systems and scientific applications. Evolutionary optimization, machine learning, intelligent systems design, image processing and machine vision, pattern recognition, evolutionary neurocomputing, evolutionary fuzzy systems, applications in biomedicine and biochemistry, robotics and control, mathematical modelling, civil, chemical, aeronautical, and industrial engineering applications.
Daniel Merkle
Parallelverarbeitung und Komplexe Systeme, Universitat Leipzig.
Andere publicaties met selected preview
Trick
TTP Description and Benchmarks.
TTP Validator
TTP Instance validator per benchmarks, met 4 standaard uitvoerformaten onderhouden door Andrea Schaerf en Luca Di Gaspero.
Java Implementation Van TTP
Online te gebruiken implementatie voor het berekenen van de TTP voor alle benchmarks. De auteur geeft zelf aan dat je een snelle computer nodig hebt om problemen van grootte groter dan 8 op te lossen. Implementatiedetails zijn percies niet gegeven.
Stigmergic Systems
Interessante site waarop informatie verzameld wordt of stigmergische systemen. Verschillende definities voor stigmergy worden gegeven.

Aanverwante problemen

TSPLIB95
TSPLIB is a library of sample instances for the TSP (and related problems) from various sources and of various types.
Valid XHTML 1.0 Transitional :: Valid CSS :: Powered by Wikka Wakka Wiki 1.1.6.2
Page was generated in 0.0219 seconds