DM63: Heuristikker til løsning af kombinatoriske optimeringsproblemer (7.5 ECTS)

STADS: 1502541

Niveau


Undervisningsperiode


Ansvarlige undervisere
Email: jbj@imada.sdu.dk

Skemaoplysninger
Der er ingen skemaoplysninger for den valgte periode.

Indgangskrav:
Ingen

Faglige forudsætninger:
Stoffet fra DM02 og MM02 anbefales.

Kursusintroduktion
At give de studerende et kendskab til flere heuristiske metoder, såkaldte meta-heuristikker, som har vist sig nyttige til at finde næroptimale løsninger til mange optimeringsproblemer der optræder i praktiske anvendelser. Fælles for disse metoder er at de ofte er meget nemme at implementere, og at man kan anvende dem (med større eller mindre held) til at finde rimeligt gode (dvs næroptimale) løsninger til optimeringsproblemer som er NP-komplette (læs: svære). Eksempler er skedulering, hamilton kredse, ruteplanlægning, udskærings- og pakningsproblemer. Da metoderne bygger på meget generelle principper, der ikke er problemafhængige, er det en naturlig konsekvens at de ikke er lige gode for alle typer af optimeringsproblemer. Et af målene med kurset er at de studerende får mulighed for at vurdere hvilke af metoderne (om nogen) der vil kunne bruges på et specifikt problem. Endelig vil vi også komme ind på Branch and bound, som er en metode til at finde en optimal løsning til et givet (endeligt) kombinatorisk optimeringsproblem. Vi skal se på det generelle princip i metoden og studere dens anvendelighed på udvalgte problemer. Metoden er meget afhængig af éns evne til at producere et rimeligt estimat for værdien af en optimal løsning. Kurset henvender sig til alle der ønsker at studere teknikker med stor praktisk anvendelighed fremfor teori. Vi vil ikke lægge vægt på teorien bag metoderne, men prøve at samle praktisk erfaring med metoderne.

Forventet læringsudbytte


Emneoversigt
Simuleret nedkøling, Tabu søgning, genetiske algoritmer, guided lokal søging, noisingmetoden, Branch and bound metoden.

Litteratur

• Meddeles ved kursets start: .

Kursets hjemmeside
Dette kursus benytter e-learn (blackboard).

Forudsætningsprøver
Ingen

Eksamen- og censurform:
Projekt der bedømmes efter 13-skalaen med ekstern censur. Projektet vil være en naturlig forlængelse af de ting vi har set på i semestrets forløb. Typisk består projektet i en sammenligning af flere meta-heuristikker for det samme optimeringsproblem.

Vejledende timetal
På naturvidenskab er undervisningen tilrettelagt efter trefasemodellen dvs. intro, trænings- og studiefasen.

Vi starter med en 7-9 forelæsninger hvor formålet er at belyse de enkelte teknikker. Herefter er det planen at de studerende implementerer nogle af metoderne og eksperimenterer med disse. De skal så fremlægge deres resultater for de øvrige deltagere og i fællesskab drager vi konklusioner ud fra de eksperimentelle data (herunder om vi kan reproducere den opførsel som litteraturen beskriver for en given metode).
Aktiviteter i studiefasen

Sprog
Dette kursus undervises på engelsk, hvis der deltager internationale studerende, ellers undervises på dansk.

Bemærkninger
Der må påregnes et ret stort programmeringsarbejde. Dette kompenseres ved at antallet af konfrontationstimer er mindre end normalt.

Kursustilmelding
Se tilmeldingsfrister.

Pris for åben uddannelse
Se priser for enkeltkurser.

Denne kursusbeskrivelse var gyldig fra 1. September 2005 til 31. August 2006.