prikaz prve stranice dokumenta Metaheuristics for problems with limited budget of evaluations
  Download
PDF 2.84 MB
doctoral thesis
Metaheuristics for problems with limited budget of evaluations
Zagreb: University of Zagreb, Faculty of Electrical Engineering and Computing, 2020. urn:nbn:hr:168:219792
Molnar, Goran
University of Zagreb
Faculty of Electrical Engineering and Computing
Department of Electronics, Microelectronics, Computer and Intelligent Systems

Institutional repository: FER Repository

Cite this document

Molnar, G. (2020). Metaheuristics for problems with limited budget of evaluations (Doctoral thesis). Zagreb: University of Zagreb, Faculty of Electrical Engineering and Computing. Retrieved from https://urn.nsk.hr/urn:nbn:hr:168:219792

Molnar, Goran. "Metaheuristics for problems with limited budget of evaluations." Doctoral thesis, University of Zagreb, Faculty of Electrical Engineering and Computing, 2020. https://urn.nsk.hr/urn:nbn:hr:168:219792

Molnar, Goran. "Metaheuristics for problems with limited budget of evaluations." Doctoral thesis, University of Zagreb, Faculty of Electrical Engineering and Computing, 2020. https://urn.nsk.hr/urn:nbn:hr:168:219792

Molnar, G. (2020). 'Metaheuristics for problems with limited budget of evaluations', Doctoral thesis, University of Zagreb, Faculty of Electrical Engineering and Computing, accessed 17 May 2024, https://urn.nsk.hr/urn:nbn:hr:168:219792

Molnar G. Metaheuristics for problems with limited budget of evaluations [Doctoral thesis]. Zagreb: University of Zagreb, Faculty of Electrical Engineering and Computing; 2020 [cited 2024 May 17] Available at: https://urn.nsk.hr/urn:nbn:hr:168:219792

G. Molnar, "Metaheuristics for problems with limited budget of evaluations", Doctoral thesis, University of Zagreb, Faculty of Electrical Engineering and Computing, Zagreb, 2020. Available at: https://urn.nsk.hr/urn:nbn:hr:168:219792

Metadata
TitleMetaheuristics for problems with limited budget of evaluations
Title (croatian)Metaheuristike za probleme s ograničenim brojem evaluacija
AuthorGoran Molnar
MentorDomagoj Jakobović (mentor)
Committee memberDomagoj Jakobović (član povjerenstva)
GranterUniversity of Zagreb
Faculty of Electrical Engineering and Computing
(Department of Electronics, Microelectronics, Computer and Intelligent Systems)
Zagreb
Defense date and country2020, 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
Keywords (croatian)
Languageenglish
URN:NBNurn:nbn:hr:168:219792
Study programmeTitle: Computer Science
Study programme type: university
Study level: postgraduate
Academic / professional title: Doktor znanosti (Doktor znanosti)
Catalog URLhttp://lib.fer.hr/cgi-bin/koha/opac-detail.pl?biblionumber=52198
Type of resourceText
Extentx, 249 str.
File originBorn digital
Access conditionsOpen access
Terms of useLicence In copyright icon
Created on2022-03-08 13:58:36