Metaheuristics for problems with limited budget of evaluations

doctoral thesis

• Title (croatian): Metaheuristike za probleme s ograničenim brojem evaluacija
• Author: Goran Molnar
• Mentor: Domagoj Jakobović (mentor)
• Committee member: Domagoj Jakobović (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; (Department of Electronics, Microelectronics, Computer and Intelligent Systems); Zagreb
• Defense date and country: 2020, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing
• Universal decimal classification (UDC): 004 - Computer science and technology. Computing. Data processing

Abstract

Metaheuristic techniques are an essential set of optimisation techniques with broad applications in numerous problems of great practical importance. Despite their success, using metaheuristics also has notable drawbacks: they are highly complex algorithms whose implementation process still lacks a formal development methodology. Their development is expensive as it requires highly trained experts, considerable time and computational resources. This work proposes a bottom-up development methodology for metaheuristic development, based on a component-based view of metaheuristics and gradual addition of more complex elements. The development methodology has the potential to reduce development time and costs while providing high-quality results. This development methodology was experimentally validated on three difficult problems: (1) call centre workforce scheduling, (2) carsharing reservations optimisations, (3) carsharing variable trip pricing problem. The second and third problems were especially difficult given their resource-intensive objective function, that requires long evaluation times, this way restricting the evaluations budget. Solutions to these two problems are to the best of the author's knowledge, the first applications of the iterated local search metaheuristic on problems with a limited budget of evaluations. Further, these solutions do not use surrogate modelling, which is common practice with such problems. The work concludes with a set of guidelines for surrogate-free solving of optimisation problems with a limited budget of evaluations, based on the experiences solving these two problems.

Abstract (croatian)

Metaheurističke tehnike važan su skup tehnika optimizacije sa širokom primjenom u brojnim problemima velike praktične važnosti. Unatoč njihovim uspješnim primjenama, korištenje metaheuristika nosi i neka nepoželjna svojstva: radi se prije svega o složenim algoritmima za čiju implementaciju još uvijek ne postoje formalne razvojne metodologije. Njihov je razvoj skup, traje dugo, zahtijeva visoko obrazovane stručnjake i znatne računalne resurse. Ovaj rad predlaže bottom-up metodologiju razvoja metaheuristika koja se temelji na rastavu metaheuristika na komponente i postupnom dodavanju složenijih elemenata. Primjena razvijene metodologije može smanjiti trajanje i troškove razvoja, ali i dalje može pružiti kvalitetne rezultate. Praktična primjenjivost je eksperimentalno provjerena prilikom implementacije optimizacijskih algoritama za tri teška problema: (1) izrada rasporeda rada djelatnika pozivnog centra, (2) optimizacija rezervacija carsharing sustava i (3) rješavanje problema određivanja varijabilnih cijena carsharing usluge. Drugi i treći problem bili su posebno teški s obzirom na njihovu ciljnu funkciju koja zahtijeva intenzivne resurse, te se zbog toga na računalu izvršava dugo. Rješenja ova dva problema su prema autoru dostupnim informacijama, prve primjene metaheuristike ponavljajuće lokalne pretrage (engl. iterated local search) na probleme s ograničenim brojem evaluacija. Nadalje, izgrađeni algoritmi ne koriste nadomjesno modeliranje, što je uobičajena praksa kod ovakvih problema. Rad završava nizom smjernica za rješavanje problema optimizacije s ograničenim brojem evaluacija bez nadomjesnog modela, temeljenih na iskustvima rješavanja ova dva problema.

• Keywords: metaheuristics; development methodology; Iterated local search; workforce scheduling; carsharing; transportation optimisation
• Keywords (croatian): metaheuristike; razvojne metodologije; ponavljajuća lokalna pretraga; rasporedi rada djelatnika; carsharing; optimizacija prometa
• Language: english
• URN:NBN: urn:nbn:hr:168:219792
• Study programme: Title: Computer Science; Study programme type: university; Study level: postgraduate; Academic / professional title: Doktor znanosti (Doktor znanosti)
• Catalog URL: http://lib.fer.hr/cgi-bin/koha/opac-detail.pl?biblionumber=52198
• Type of resource: Text
• Extent: x, 249 str.
• File origin: Born digital
• Access conditions: Open access
• Created on: 2022-03-08 13:58:36