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

STADS: 15004601

Niveau
Kandidatkursus

Undervisningsperiode

Udbydes efter behov.

Ansvarlige undervisere
Email: marco@imada.sdu.dk

Skemaoplysninger
Der er ingen skemaoplysninger for den valgte periode.

Kommentar:
Ubegrænset deltagerantal. 1. kvartal.

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

Meddeles ved kursets start.

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

Forudsætningsprøver
Ingen

Eksamen- og censurform:
Projektopgave der bedømmes med karakter efter 7-skalaen og intern censur.
Projektopgaven består i at implementere og analysere et antal heuristikker og lokalsøgningsalgoritmer, og at beskrive det udførte arbejde i en skriftlig rapport.

Reeksamen følger terminerne vedtaget af studienævnet.

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

Forelæsninger: 20 timer
Laboratorieøvelser: 14 timer
Aktiviteter i studiefasen

Sprog
Dette kursus undervises på engelsk.

Kursustilmelding
Se tilmeldingsfrister.

Pris for åben uddannelse
Se priser for enkeltkurser.

Denne kursusbeskrivelse var gyldig fra 1. september 2008 til 31. august 2010.