DM/DMP86: Lokalsøgningsmetoder: Anvendelse og Design (10 ECTS)
STADS: 1507001Niveau
PhD-kursus
Undervisningsperiode
Ansvarlige undervisere
Email: marco@imada.sdu.dkSkemaoplysninger
Der er ingen skemaoplysninger for den valgte periode.
Indgangskrav:
Ingen
Faglige forudsætninger:
Stoffet fra DM02 og DM63 skal være kendt.
Kursusintroduktion
Kurset er en fortsættelse af DM63 og formålet er at forøge kendskabet til lokalsøgningsmetoder og disses anvendelse i praksis til løsning af optimeringsproblemer. Der er tre hovedemner i kurset.
Problemer:
En lang række optimeringsproblemer fra forskellige anvendelser (f.eks. transport, skedulering, skemalægning, økonomi) vil blive diskuteret. Nogle af disse kan også være af en underholdningsnatur, som f.eks. Sudoku. Kurset vil også omhandle multi-objektiv og stokastiske optimeringsproblemer, samt hvorledes lokalsøgningsmetoder må tilpasses for at kunne anvendes i disse kontekster.
Algoritmer:
Den studerende vil blive introduceret for de oftest anvendte konstruktionsheuristikker, nabostrukturer og speed-up teknikker med henblik på hurtig undersøgelse af nabomængden for nogle af de typiske problemer der optræder i praktiske anvendelser af heuristikker. Derudover vil dækningen af metaheuristikker fra DM63 blive udbygget ved introduktionen af metoder såsom Variable Neighborhood Search, Scatter Search og Path Relinking. Algoritmer inspireret af sværmeopførsel, såsom Ant Colony Optimization eller adaptive metoder såsom GRASP og Memetic Algorithms vil også blive behandlet i kurset.
Empirisk Software Engineering:
Lokalsøgningsmetoder genererer stokastiske algoritmer hvis vurdering nødvendiggør empirisk analyse. Den studerende vil lære de relevante statistiske metoder til empirisk analyse af algoritmer. Disse teknikker, som mest baserer sig på sekventiel testning, bruges derefter til at løse konfigurationsproblematikken indenfor udvikling af høj kvalitets lokalsøgningsmetoder for det givne problem.
Forventet læringsudbytte
Emneoversigt
Stochastic Local Search, Heuristikker, Metaheuristikker, Optimering, Konfigurationsproblemet, Experimentel Algoritmik, Sekventiel Testning.
Litteratur
Der er i øjeblikket ikke angivet nogle materialer for kurset.
Pensum
Se pensumbeskrivelse.
Kursets hjemmeside
Dette kursus benytter e-learn (blackboard).
Forudsætningsprøver
Ingen
Eksamen- og censurform:
Mundtlig eksamen (30 minutter uden forberedelse) og bedømmelse af projektrapport. Den mundtlige eksamen og bedømmelse af rapport tæller hver 50% af den samlede karakter. Ekstern censur med bedømmelse efter 13 skala. Af hensyn til at opnå en rimelig arbejdsbyrde, kan projekter laves af op til 3 personer sammen. Projektet bedømmes intern censur ved underviser og vil inkludere en mundtlig præsentation for klassen ved hver gruppe. Censor får adgang til at se rapporterne ved eksamen. Der kan spørges i projektemnerne til den mundtlige eksamen. Der er kun eksamen, når faget er kørt. Eksamen i modfase terminer kun efter ansøgning til studienævnet.
Vejledende timetal
På naturvidenskab er undervisningen tilrettelagt efter trefasemodellen dvs. intro, trænings- og studiefasen.
De første 5-7 uger vil bestå af forelæsninger og øvelser (ca. 28 timer i alt). Ved forelæsningerne vil vi illustrere de forskellige metoder og teknikker, samt diskutere disses anvendelse på en bred vifte af problemer. Projektemnet kan vælges individuelt efter godkendelse af læreren.
Aktiviteter i studiefasen
Sprog
Der er ikke registreret nogle oplysninger om undervisningssproget.
Bemærkninger
Der vil være et betydeligt arbejde i form af programmering og eksperimenteren med metoderne. Dette kompenseres ved, at antallet af konfrontationstimer er mindre end normalt. Kurset vil også involvere en del arbejde med henblik på visualisering af resultaterne indenfor det såkaldte R environment – en gratis software pakke til statistisk databehandling. Kurset undervises på engelsk.
Kursustilmelding
Se tilmeldingsfrister.
Pris for åben uddannelse
Se priser for enkeltkurser.
Denne kursusbeskrivelse var gyldig fra 1. februar 2006 til 31. januar 2011.
