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

STADS: 1502541

Niveau


Undervisningsperiode

Efterårssemestret.

Ansvarlige undervisere
Email: marco@imada.sdu.dk

Skemaoplysninger
Der er ingen skemaoplysninger for den valgte periode.

Kommentar:
Ubegrænset deltagerantal.

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
Efter kurset forventes den studerende at kunne:

• gengive skriftligt, i et præcist og klart sprog, de generelle algoritmiske metoder (metaheuristiker) som er en del af pensum, herunder ved brug af pseudokode
• anvende disse metoder på konkrete nye kombinatoriske optimeringsproblemer, som i natur minder om problemer fra kurset. Herunder give en præcis beskrivelse af, hvorledes algoritmen vil se ud i denne anvendelse, f.eks. vha. pseudokode
• tilpasse specifikke algoritmer (konstruktionsheuristikker og lokalsøgningsheuristikker) til specialtilfælde af kendte problemer, og til nye problemer
• designe nye algoritmer baseret på metoder fra kurset (hybride algoritmer)
• implementere de designede algoritmer i et passende valgt programmeringssprog
• analysere de anvendte heuristikker (mht. tid- og pladsforbrug og andre kvaliteter ved metoderne)
• foretage empiriske afprøvninger af de anvendte metoder, og uddrage konklusioner om de kvalitative og kvantitative aspekter af de undersøgte metoder
• foretage en praktisk løsning af de konfigurations- og tuningsproblemer, som er en del af alle heuristikker
• sammenligne kvaliteten af forskellige algoritmer for det samme problem, og herudfra foretage et begrundet valg af endelig algoritme
• diskutere resultaterne opnået i forbindelse med de tre sidste punkter

Emneoversigt
Heuristiske algoritmer, Simuleret nedkøling, Tabu søgning, Gentaget lokal søging, Evolutionære algoritmer, Backtracking.

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 7-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. Dette kursus undervises på engelsk, hvis der deltager internationale studerende, ellers undervises på dansk.

Kursustilmelding
Se tilmeldingsfrister.

Pris for åben uddannelse
Se priser for enkeltkurser.

Denne kursusbeskrivelse var gyldig fra 1. September 2006 til 31. January 2011.