Landscape analysis-based automated algorithm selection
Date
2024-03
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Stellenbosch : Stellenbosch University
Abstract
ENGLISH ABSTRACT: The algorithm selection problem, which was developed by Rice, refers to the chal- lenge of choosing
the best algorithm available to solve a specific p roblem. The framework put forth by Rice includes
four spaces: the problem space, the algorithm space, the characteristic space, and the performance
space. In this thesis, the focus is on the problem space of continuous-valued single-objective,
boundary-constrained optimisation problems. Landscape analysis, which is a set of techniques that
utilises mathematical and statistical methods to characterise the properties of optimisation
problems, can be used to describe the characteristic space. Selection of the most effective
algorithm to solve optimisation problems is a complex task, because meta- heuristics have varying
strengths. Therefore, a data-driven approach that utilises landscape analysis techniques is
employed in this thesis to create an automated algorithm selector.
This thesis proposes enhancements to the characteristic space by critically evaluat- ing the
reliability of the methods used in generating landscape analysis measures. Additionally, a new
benchmark suite, which is more representative of the problem space than commonly used benchmark
suites in the literature, is proposed. An investigation into the impact on the performance of
hybrid metaheuristics created by combining the sampling algorithms used to calculate landscape
analysis features with standard metaheuristics, which are used to solve the optimisation problem,
is conducted. By combining the proposed improvements to the characteristic, algo- rithm, and
problem spaces of the algorithm selection framework, this thesis concludes with a landscape
analysis-based automated algorithm selection model that outper- forms the current automated
algorithm selection models found in the literature in
terms of performance and generalisability. Furthermore, this thesis explores the use of automated
machine learning and hybrid metaheuristics in automated algorithm
selection.
AFRIKAANSE OPSOMMING: Die algoritme seleksie probleem, ontwikkel deur Rice, verwys na die uitdaging om die beste beskikbare algoritme te selekteer om ’n spesifieke p robleem op te l os. Die raamwerk wat deur Rice voorgestel is, sluit vier ruimtes in: die probleem ruimte, die algoritme ruimte, die eienskap ruimte, en die prestasie ruimte. Die fokus van hierdie tesis is op die probleem ruimtes van kontinue-waarde, enkel-doelwit, grens-beperkde optimeringsprobleme. Landskap analise, ’n versameling van tegnieke wat wiskun- dige en statistiese metodes aanwend om die eienskappe van optimeringsprobleme te karakteriseer, kan gebruik word om die eienskap ruimte te beskryf. Seleksie van die mees effektiewe a lgoritme v ir o ptimeringsprobleme i s ’ n k omplekse t aak, aan- gesien meta-heuristieke verskillende sterkpunte het. Daarom wend hierdie tesis ’n data-gedrewe benadering aan wat landskap analise tegniekie gebruik om ’n geouto- matiseerde algoritme keurder te ontwikkel. Hierdie tesis stel verbeteringe voor vir die eienskap ruimte deur kritiese evaluasie van die betroubaarheid van metodes wat gebruik word om landskap analise maat- stawe te genereer. Addisioneel word ’n nuwe probleem suite voorgestel wat meer verteenwoordigend van die probleem ruimte is as bestaande probleem suites wat in die literatuur beskikbaar is. ’n Ondersoek word ingestel na die prestasie van hibriede meta-heuristieke wat gevorm word deur monsternemingalgoritmes wat gebruik word om landskap eienskappe te bereken met standaard meta-heuristieke te kombineer. Deur die voorgestelde verbeteringe in die eienskap, algoritme, en probleem ruimtes van die algoritme seleksie raamwerk in te sluit, sluit hierdie tesis af met ’n landskap analise gebaseerde outomatiese algoritme seleksie model wat beter presteer in terme van akkuraathied en veralgemening as huidige outomatiese algoritme seleksie mo- delle wat in die literatuur gevind kan word. Verder verken die tesis die gebruik van geoutomatiseerde masjienleer en hibriede meta-heuristieke in outomatiese algoritme seleksie.
AFRIKAANSE OPSOMMING: Die algoritme seleksie probleem, ontwikkel deur Rice, verwys na die uitdaging om die beste beskikbare algoritme te selekteer om ’n spesifieke p robleem op te l os. Die raamwerk wat deur Rice voorgestel is, sluit vier ruimtes in: die probleem ruimte, die algoritme ruimte, die eienskap ruimte, en die prestasie ruimte. Die fokus van hierdie tesis is op die probleem ruimtes van kontinue-waarde, enkel-doelwit, grens-beperkde optimeringsprobleme. Landskap analise, ’n versameling van tegnieke wat wiskun- dige en statistiese metodes aanwend om die eienskappe van optimeringsprobleme te karakteriseer, kan gebruik word om die eienskap ruimte te beskryf. Seleksie van die mees effektiewe a lgoritme v ir o ptimeringsprobleme i s ’ n k omplekse t aak, aan- gesien meta-heuristieke verskillende sterkpunte het. Daarom wend hierdie tesis ’n data-gedrewe benadering aan wat landskap analise tegniekie gebruik om ’n geouto- matiseerde algoritme keurder te ontwikkel. Hierdie tesis stel verbeteringe voor vir die eienskap ruimte deur kritiese evaluasie van die betroubaarheid van metodes wat gebruik word om landskap analise maat- stawe te genereer. Addisioneel word ’n nuwe probleem suite voorgestel wat meer verteenwoordigend van die probleem ruimte is as bestaande probleem suites wat in die literatuur beskikbaar is. ’n Ondersoek word ingestel na die prestasie van hibriede meta-heuristieke wat gevorm word deur monsternemingalgoritmes wat gebruik word om landskap eienskappe te bereken met standaard meta-heuristieke te kombineer. Deur die voorgestelde verbeteringe in die eienskap, algoritme, en probleem ruimtes van die algoritme seleksie raamwerk in te sluit, sluit hierdie tesis af met ’n landskap analise gebaseerde outomatiese algoritme seleksie model wat beter presteer in terme van akkuraathied en veralgemening as huidige outomatiese algoritme seleksie mo- delle wat in die literatuur gevind kan word. Verder verken die tesis die gebruik van geoutomatiseerde masjienleer en hibriede meta-heuristieke in outomatiese algoritme seleksie.
Description
Thesis (MSc)--Stellenbosch University, 2024.