Promotie Ashkan Safari

Trefwoorden: Lokaal zoeken, k-swap, Machineplanning, Mierenkolonie-optimalisatie

"Theory of Local Search and Ant Colony Optimization in Combinatorial Problems"

Dit proefschrift onderzoekt hoe complexe beslissingsproblemen efficiënt kunnen worden aangepakt wanneer het vinden van een exacte oplossing simpelweg niet realistisch is. Dergelijke problemen doen zich in veel alledaagse situaties voor, waaronder planning, roostering en routering, waarbij het aantal mogelijke keuzes extreem snel toeneemt. In de praktijk vertrouwen mensen vaak op eenvoudige, op verbetering gebaseerde methoden die een oplossing geleidelijk beter maken, ook al suggereert de theorie soms dat deze methoden slecht zouden kunnen presteren.

Dit proefschrift legt uit waarom deze methoden in de praktijk meestal goed werken. Eerst wordt een machineplanningsprobleem bestudeerd en wordt aangetoond dat, hoewel in theorie zeer traag gedrag mogelijk is, dit in de praktijk onwaarschijnlijk is. Een meer realistische analyse helpt deze kloof tussen theorie en praktijkprestaties te overbruggen.

Vervolgens onderzoekt het proefschrift algoritmen die zijn geïnspireerd op het gedrag van mieren, die leren van ervaringen uit het verleden. Het laat zien hoe kleine veranderingen in hun leervoorwaarden een grote invloed kunnen hebben op hun betrouwbaarheid en snelheid. Al met al helpt het proefschrift te verduidelijken waarom praktische algoritmen vaak succesvol zijn, ondanks beperkte theoretische garanties.

Klik hier voor het volledige proefschrift.

Klik hier voor de livestream.