Full Text Available
Note: Clicking the button above will open the full text document at the original institutional repository in a new window.
A fitness landscape-integrated metaheuristic selection & configuration framework for binary programming problems.
Thesis (PhD)--Stellenbosch University, 2024.
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Published: |
Stellenbosch : Stellenbosch University
2025
|
| Subjects: | |
| Tags: |
No Tags, Be the first to tag this record!
|
| _version_ | 1867613740783894528 |
|---|---|
| access_status_str | Open Access |
| author | Van der Westhuyzen, Nathan Jan |
| author2 | Van Vuuren, J. H. |
| author_browse | Van Vuuren, J. H. Van der Westhuyzen, Nathan Jan |
| author_facet | Van Vuuren, J. H. Van der Westhuyzen, Nathan Jan |
| author_sort | Van der Westhuyzen, Nathan Jan |
| collection | Thesis |
| dc_rights_str_mv | Stellenbosch University |
| description |
Thesis (PhD)--Stellenbosch University, 2024. |
| format | Thesis |
| id | oai:scholar.sun.ac.za:10019.1/131952 |
| institution | Stellenbosch University (South Africa) |
| last_indexed | 2026-06-10T12:40:57.522Z |
| license_str | Other — see source repository |
| provenance_str_mv | Harvested via OAI-PMH from SUNScholar — Stellenbosch University Repository |
| publishDate | 2025 |
| publishDateRange | 2025 |
| publishDateSort | 2025 |
| publisher | Stellenbosch : Stellenbosch University |
| publisherStr | Stellenbosch : Stellenbosch University |
| record_format | dspace |
| source_str | SUNScholar — Stellenbosch University Repository |
| spelling | oai:scholar.sun.ac.za:10019.1/131952 A fitness landscape-integrated metaheuristic selection & configuration framework for binary programming problems. Van der Westhuyzen, Nathan Jan Van Vuuren, J. H. Colmant, A. Stellenbosch University. Faculty of Engineering. Dept. of Industrial Engineering. Binary system (Mathematics) Metaheuristics Mathematical optimization UCTD Thesis (PhD)--Stellenbosch University, 2024. ENGLISH ABSTRACT: The research field of optimisation has witnessed a surge in the number of metaheuristic solution methodologies available in the literature since the 1970s. As a result, analysts are faced with the challenging task of having to select a metaheuristic from this wide range of approximate optimisation techniques that is best suited to each optimisation problem instance considered. This selection problem is made more difficult by the phenomenon of performance complementarity, according to which no algorithm typically dominates all other algorithms for all optimisation problem instances. Instead, different algorithms perform better in respect of different types of optimisation problem instances. Moreover, even a single metaheuristic may perform differently in respect of solving the same optimisation problem instance if it is configured differently and/or assigned different hyperparameter values. The difficulty of choosing an appropriate metaheuristic (which is properly configured) calls for the development of an automated algorithm selection framework capable of decision support in aid of these selection decisions. A metaheuristic selection and configuration framework is therefore proposed in this dissertation for reducing the effects of performance complementarity by integrating solutions to the problems of algorithm selection and algorithm configuration in a simple and efficient manner within the application context of binary programming. This framework operates in two phases — an offline phase and an online phase. The offline phase takes as input a set of optimisation problem instances and a user-specified algorithm portfolio, and guides the user through the process of constructing a comprehensive and coherent meta-learning database. Building on the output of the offline phase, the online phase is tailored to take as input unseen binary programming problem instances and produce as output valuable metaheuristic design decision support for these instances. The operational phases of the framework are executed asynchronously and iteratively, in alternating fashion, with the offline phase initially preceding the online phase. The offline phase may be re-executed to include information on new, unseen optimisation problem instances in a batch-wise fashion with a view to enhance the representativeness of the meta- learning database over time. The offline phase is the computational foundation of the framework, while its online phase is the consulting house built upon that computational foundation. The framework is verified in the context of four classical binary programming problem classes. This verification process is performed at the framework component level (that is, each component is implemented and verified individually). Inter-component interactions are also meticulously examined in order to verify the correct working of the framework implementation as an integrated system. The working of the framework is finally demonstrated in the context of a real world-inspired case study conducted in collaboration with an industry partner attached to the dissertation. In this context, the verified framework is tested against a completely new binary programming problem class, allowing for an evaluation of the framework’s flexibility and adaptability, as well as its performance in respect of a novel real-world optimisation problem class. AFRIKAANSE OPSOMMING: Die navorsingsveld van optimering het sedert die 1970's 'n toename gesien in die aantal metaheuristiese oplossingsmetodologie e wat in die literatuur beskikbaar is. Gevolglik staar analiste die uitdagende taak in die gesig om 'n metaheuristiek uit hierdie wye verskeidenheid benaderde optimeringstegnieke te kies wat die beste geskik is vir elke optimeringsprobleemgeval wat oorweeg word. Hierdie seleksieprobleem word bemoeilik deur die verskynsel van prestasiekomplementariteit, waarvolgens geen algoritme tipies alle ander algoritmes vir alle optimeringsprobleemgevalle uitstof nie. In plaas daarvan presteer verskillende algoritmes beter ten opsigte van verskillende tipes optimeringsprobleemgevalle. Boonop kan selfs 'n enkele metaheuristiek anders presteer tydens die oplossing van dieselfde optimeringsprobleemgeval as dit anders gekon_gureer is en/of verskillende hiperparameterwaardes toegeken word. Die uitdaging om 'n toepaslike metaheuristiek (wat behoorlik gekon_gureer is) te kies, vereis die ontwikkeling van 'n geoutomatiseerde algoritme-seleksieraamwerk wat in staat is om besluitsteun ten bate van hierdie seleksiebesluite te bied. 'n Metaheuristiese seleksie- en kon_gurasieraamwerk word dus in hierdie proefskrif daargestel om die e_ekte van prestasiekomplementariteit te verminder deur oplossings vir die probleme van algoritmeseleksie en algoritmekon_gurasie op 'n eenvoudige en doeltre_ende wyse binne die toepassingskonteks van bin^ere programmering te integreer. Hierdie raamwerk werk in twee fases | 'n aynfase en 'n aanlynfase. Die aynfase neem as toevoer 'n versameling optimeringsprobleemgevalle en 'n gebruikersgespesi_seerde algoritmeportefeulje, en lei die gebruiker deur die proses om 'n omvattende en samehangende meta-leerdatabasis op te stel. Die aanlynfase bou voort op die aynfase deur die afvoer van laasgenoemde fase as toevoer te neem, tesame met ongesiene bin^ere programmeringsprobleemgevalle, en lewer waardevolle metaheuristiese ontwerp besluitsteun as afvoer vir hierdie gevalle. Die operasionele fases van die raamwerk word opeenvolgend en iteratief op afwisselende wyse uitgevoer, met die aynfase aanvanklik voor die aanlynfase. Die aynfase kan herhaaldelik uitgevoer word om inligting oor nuwe, ongesiene optimeringsprobleemgevalle in bondels in ag te neem met die oog daarop om die verteenwoordigendheid van die meta-leerdatabasis oor tyd te verbeter. Die aynfase is die berekeningsgrondslag waarop die raamwerk berus, terwyl die aanlynfase die konsultasiehuis is wat op daardie berekeningsgrondslag gebou is. Die raamwerk word in die konteks van vier klassieke bin^ere programmeringsprobleemklasse gedemonstreer. Hierdie veri_kasieproses word op die raamwerkkomponentvlak uitgevoer (dit wil s^e, elke komponent word individueel ge _mplementeer en geveri_eer). Inter-komponent interaksies word ook noukeurig ondersoek om die korrekte werking van die raamwerkimplementering as 'n ge _ntegreerde stelsel te veri_eer. Die werking van die raamwerk word uiteindelik in die konteks van 'n werklike w^ereld-ge _nspireerde gevallestudie gedemonstreer wat in samewerking met 'n bedryfsvennoot verbonde aan die proefskrif uitgevoer word. In hierdie konteks word die raamwerk teen 'n heeltemal nuwe bin^ere rogrammeringsprobleemklas getoets om sodoende die buigsaamheid en aanpasbaarheid van die raamwerk, sowel as die prestasie daarvan ten opsigte van 'n nuwe optimeringsprobleemklas in die bedryf, te bevestig. Doctoral 2025-04-30T12:50:39Z 2025-04-30T12:50:39Z 2024-12 Thesis https://scholar.sun.ac.za/handle/10019.1/131952 Stellenbosch University xxvi, 242 pages : illustrations application/pdf Stellenbosch : Stellenbosch University |
| spellingShingle | Binary system (Mathematics) Metaheuristics Mathematical optimization UCTD Van der Westhuyzen, Nathan Jan A fitness landscape-integrated metaheuristic selection & configuration framework for binary programming problems. |
| title | A fitness landscape-integrated metaheuristic selection & configuration framework for binary programming problems. |
| title_full | A fitness landscape-integrated metaheuristic selection & configuration framework for binary programming problems. |
| title_fullStr | A fitness landscape-integrated metaheuristic selection & configuration framework for binary programming problems. |
| title_full_unstemmed | A fitness landscape-integrated metaheuristic selection & configuration framework for binary programming problems. |
| title_short | A fitness landscape-integrated metaheuristic selection & configuration framework for binary programming problems. |
| title_sort | fitness landscape integrated metaheuristic selection configuration framework for binary programming problems |
| topic | Binary system (Mathematics) Metaheuristics Mathematical optimization UCTD |
| url | https://scholar.sun.ac.za/handle/10019.1/131952 |
| work_keys_str_mv | AT vanderwesthuyzennathanjan afitnesslandscapeintegratedmetaheuristicselectionconfigurationframeworkforbinaryprogrammingproblems AT vanderwesthuyzennathanjan fitnesslandscapeintegratedmetaheuristicselectionconfigurationframeworkforbinaryprogrammingproblems |