DM811: Heuristikker og lokalsøgningsalgoritmer for kombinatorisk optimering (5 ECTS)

STADS: 15013601

Niveau
Kandidatkursus

Undervisningsperiode
Kurset udbydes efter behov.

Ansvarlige undervisere
Email: marco@imada.sdu.dk

Skemaoplysninger
Vis hele skemaet
Vis personligt skema for dette kursus.

Indgangskrav:
Ingen

Faglige forudsætninger:
Stoffet fra DM507 Algoritmer og datastrukturer skal være kendt.

Kursusintroduktion
De studerende vil lære at implementere effektive heuristikker og lokalsøgningsalgoritmer for at finde næroptimale løsninger til diskrete optimeringsproblemer. Disse metoder bruges til i realistisk tid at finde gode approksimationer til NP-hårde kombinatoriske problemer, for hvilke der ikke kendes effektive eksakte metoder. I dag bruges sådanne heuristikker til at løse de fleste større optimeringsproblemer der optræder i praktiske anvendelser.
Eksempler er grådige heuristikker, træbaserede søgningsheuristikker, iterativ forbedring, probabilistisk iterativ forbedring og nabolagssøgning i stor skala. I løbet af kurset vil vi bruge eksempelproblemer som den handelsrejsendes problem, boolean satisfiability, graffarving, skedulering, ruteplanlægning, udskærings- og pakningsproblemer for at lære de grundlæggende principper som ligger bag de mest velfungerende heuristikker for sådanne problemer.

Kurset henvender sig til alle der ønsker at studere teknikker med stor praktisk anvendelighed. Vi vil ikke lægge vægt på teorien bag metoderne, men prøve at samle praktisk erfaring med dem

Forventet læringsudbytte
Ved kursets afslutning forventes den studerende at kunne:

- gengive skriftligt, i et præcist og klart sprog, de algoritmiske metoder som er en del af pensum, herunder også ved brug af 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;
- implementere de designede algoritmer i et passende valgt programmeringssprog;
- analysere de anvendte heuristikker mht. løsningskvalitet, tid- og pladsforbrug og andre karakteristiker ved metoderne;
- foretage empiriske afprøvninger af de anvendte metoder, og uddrage konklusioner om de kvalitative og kvantitative aspekter af de undersøgte metoder;
- diskutere resultaterne opnået i forbindelse med de to sidste punkter.

Emneoversigt
Konstruktionsheuristikker, grådige heuristikker, lokalsøgning, iterativ forbedring. Adskillige eksempelproblemer, herunder den handelsrejsendes problem, boolean satisfiability og graffarvning.

Litteratur
Der er i øjeblikket ikke angivet nogle materialer for kurset.

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

Forudsætningsprøver
Ingen

Eksamen- og censurform:
Tre opgaver der bedømmes samlet med karakter efter 7-trinsskalaen og ekstern censur. (15013602)

Reeksamen i samme eksamenstermin eller i umiddelbar forlængelse heraf

 

Vejledende timetal
På naturvidenskab er undervisningen tilrettelagt efter trefasemodellen dvs. intro, trænings- og studiefasen.
Introfase: 20 timer
Træningsfase: 14 timer

Aktiviteter i studiefasen

Sprog
Dette kursus undervises på dansk eller engelsk, afhængigt af underviseren. Dog altid på Engelsk ved deltagelse af internationale studerende.

Kursustilmelding
Se tilmeldingsfrister.

Pris for åben uddannelse
Se priser for enkeltkurser.

Dette er den nyeste version af en kursusbeskrivelse, som trådte i kraft den 1. sep 2013.