DM812: Metaheuristikker (5 ECTS)

STADS: 15004701

Niveau
Kandidatkursus

Undervisningsperiode
Kurset er placeret i efterårssemesteret.
Udbydes efter behov

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 kurset DM811 Heuristikker og lokalsøgningsalgoritmer for kombinatorisk optimering skal være kendt.

Kursusintroduktion
Kurset vil introducere de studerende til et antal generelle søgningsmetoder, såkaldte metaheuristikker, som har vist sig nyttige til at finde næroptimale løsninger til mange optimeringsproblemer der optræder i praktiske anvendelser. Disse metoder hjælper delprocedurer, såsom konstruktionsheuristikker og lokalsøgningsmetoder, til at undslippe fra lokale optima og variere søgningen, således at løsningkvaliteten kan forbedres. De endelige algoritmer giver de bedste approksimationresultater i praksis for NP-hårde optimeringsproblemer, for hvilke en eksakt løsning ofte er umulig. Metoderne inspireres ofte af naturen, som for eksempel evolutionære algoritmer og myrekoloni-optimering, eller baseres på perturbering af søgeretningen, som for tabu søgning og iterativ lokal søgning. I løbet af kurset vil metoderne blive anvendt på eksempelproblemer, som f.eks. den handelsrejsendes problem, graffarving, skedulering, ruteplanlægning, udskærings- og pakningsproblemer. Et meget vigtigt aspekt ved succesfuld anvendelse af metaheuristikker er en effektiv konfiguration og indstillingen af parametre. Vi vil lære racing-metoder for at foretage disse beslutninger på et videnskabligt grundlag. Endeligt er det i større projekter nyttigt at anvendelse et programmeringsframework til at dele og genbruge programkoden. Derfor vil vi give et overblik over nogle af de eksisterende metaheuristik-frameworks, og gennemgå et af dem i detaljer.

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 vil prøve at samle praktisk erfaring med metoderne.

Forventet læringsudbytte
Ved kursets afslutning 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 også ved brug af pseudokode;
- anvende disse metoder på nye kombinatoriske optimeringsproblemer, som i natur minder om problemer fra kurset, herunder give en præcis skriftlig beskrivelse af, hvorledes algoritmen vil se ud i denne anvendelse;
- designe nye algoritmer baseret på metoder fra kurset (hybride algoritmer);
- implementere de designede algoritmer i et passende valgt programmeringssprog;
- 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 metaheuristikker;
- diskutere resultaterne opnået i forbindelse med de to sidste punkter.

Emneoversigt
Tabu søgning, gentaget lokalsøgning, evolutionære algoritmer, iterativ lokalsøgning, myrekoloni-optimering, simuleret nedkøling, samt andre metaheuristikker. Racing-algoritmer, programmeringsframework.

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-skala og ekstern censur.
Projektopgaven består i at implementere og konfigurere et antal af metaheuristik-algoritmer og at beskrive det udførte arbejde i en skriftligt 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å 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 2008.