AU kursuskatalog arkiv

Meta-heuristikker til løsning af kombinaoriske optimeringsproblemer (Q3+Q4) ( forår 2010 - 10 ECTS )

Rammer for udbud

• Uddannelsessprog: engelsk
• Niveau: Kandidatkursus.  
• Semester/kvarter: 3. + 4. kvarter, forår 2010.
• Timer per uge: 4.  
• Deltagerbegrænsning:
• Undervisningssted: Århus
• Hovedområde: Det Naturvidenskabelige Fakultet
• Udbud ID: 18446

Formål

Heltalsprogrammering og kombinatorisk optimering er en vigtig del af perationsanalysen. Kombinatorisk optimering beskæftiger sig med løsning af beslutningsproblemer med en endelig mængde af brugbare løsninger som, f.eks., at bestemme en optimal delmængde eller partitionering af en given grundmængde, en optimal sekvens eller tildeling. Kombinatoriske optimeringsproblemer og metoder fremviser mangfoldige anvendelsesmuligheder og har været succesrigt anvendt i forskellige områder som, f.eks., personlig planægning, logistik, transportplanlægning, produktionsplanlægning, supply chain management, o.s.v.

De fleste kombinatoriske optimeringsproblemer er dog desværre NP-hårde og meget svare at løse til optimalitet. Heuristiske metoder er derfor tit nødvendige til at kunne løse praktiske problemstillinger. Især meta-heuristiske løsningsmetoder, hvilke koordinerer underordnete heuristikker, har sig vist at være velfungerende metoder. Kurset giver et overblik over de vigtigste metoder inden for disse områder,
hvilke er egnet til at løse praktiske problemstillinger.

Indhold

Begreb, formål og anvendelses af heuristikker; komplexitætsteori; greedy metoder; lokalesøgning; simulated annealing og varianter; guided local search; variabel naboskab søge; variabel dybe søgning og meget store naboskaber; greedy randomiserede søge; myrekolonier; genetiske og evolutionære algoritmer; scatter search og path relinking; tabu search; attribute-based hill climbing.

Faglige forudsætninger

Matematisk programmering.

Underviser

Andreas Klose.

Undervisnings- og arbejdsform

2 x 2 timers forelæsninger pr. uge.

Engelsk.

Litteratur

Aarts EH, Lenstra JK (1997) Local Search in Combinatorial Optimization. Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley, New York.

Glover F, Kochenberger GA (2003) Handbook of Metaheuristics.
Kluwer International Series in Operations Research and Management Science,
Kluwer, London.

Reeves CB (1993) Modern Heuristic Techniques for Combinatorial Problems. Advanced Topics in Computer Science, Blackwell, Cambridge MA and Oxford UK.

Notater.

Udbyder

Institut for Matematiske Fag.

Tilmelding til undervisning

Tilmelding på selvbetjeningen https://mit.au.dk fra d. 1.-15. november 2009. Eftertilmeldinger: Kontakt Oddbjørg Wethelund, oddbjorg@imf.au.dk

Læringsmål

Ved kursets afslutning forventes den studerende inden for kursets emneområde at kunne:

• anvende vigtige meta-heuristiske løsningsmetoder til et givet kombinatoriske optimeringsproblem;
• analysere og diskutere fordele og ulemper ved forskellige alternative meta-heuristiske metoder for at l\o{}se specifikke optimeringsproblemer;
• anlysere den mulige nytte af bestemte meta-heuristikke metode med hensigten til løsningskvalitet, beregningstid, implementeringstid, generaliserbarheden;
• kombinere og integrere forskellige meta-heuristikker;
• anvende kombinerede metoder til at l\o{}se nye optimeringsproblemer.

Bedømmelse

• Mundtlig, bedømt efter 7-skala med ekstern censur
5 xxxxx

Eksamen består af to afleveringsopgaver, en efter hvert kvarter, og en mundlig eksamen af 20 minutter efter det fjerde kvarter. Hver afleringsopgave har en arbejdsomfang af cirka 20 timer. Mundlig eksamen er uden forberedelsestid. Alle eksamensdele er med en ekstern censor. En enkelt karakter gives efter den danske 7-trin karakterskala baseret på de skriftlige afleveringsopgaver og den mundlige eksamen.