Adaptive challenge for algebraic and realistic dynamic optimisation benchmarks.

Alza Santos, Joan

Abstract

Dynamic optimisation focuses on finding the best possible solutions while continuously adapting to changing environments. One of the main challenges in academic dynamic optimisation is accurately representing the adaptive challenge of online algorithms to different dynamic features in benchmark generators, ensuring that only problems that obtain effective adaptation of online algorithms are classified as "dynamic". However, academic research often simulates changes in the problem by simply adjusting certain features of the dynamic process, such as the magnitude and frequency of problem changes. This thesis reviews academic research and practical applications to identify inconsistencies in defining dynamic optimisation problems, and replicates established methods to quantitatively evaluate how different dynamic features affect the adaptive advantage of algorithms. In particular, the study makes the following contributions. First, the thesis establishes a theoretical framework for the fitness landscape rotation as a dynamic benchmark generator in order to demonstrate its preserving nature. Contributions here include using the fitness landscape rotation as a tilting strategy to redirect the search for algorithms that are stuck in local optima. Second, the study introduces the concept of elusivity to differentiate dynamic optimisation problems from sequences of unrelated instances by quantifying the adaptive advantage of online algorithms over restart. The conducted empirical research shows that certain combinations of problems, algorithms and performance metrics indicate different degrees of elusivity, highlighting the importance of considering algorithmic performance in relation to problem dynamism. Third, in order to extend the analysis to a practical scenario, the thesis presents a thorough analysis and a robust methodology for generating synthetic instances from real-world data, provided by ARR Craib, introducing a novel approach to developing dynamic benchmark instances, especially for dynamic scheduling problems. The specific benchmark generator characterises realistic features, allowing for the evaluation of optimisation algorithms in practical dynamic contexts.

Citation

ALZA SANTOS, J. 2025. Adaptive challenge for algebraic and realistic dynamic optimisation benchmarks. Robert Gordon University, PhD thesis. Hosted on OpenAIR [online]. Available from: https://doi.org/10.48526/rgu-wt-2795469

• Thesis Type: Thesis
• Deposit Date: Apr 17, 2025
• Publicly Available Date: Apr 17, 2025
• DOI: https://doi.org/10.48526/rgu-wt-2795469
• Keywords: Dynamic optimisation; Combinatorial optimisation; Fitness landscape rotation; Group theory; Evolutionary algorithms; Truck and trailer scheduling; Logistics
• Public URL: https://rgu-repository.worktribe.com/output/2795469
• Award Date: Jan 31, 2025