Selection Hyper-heuristics for Population-based Meta-heuristics in Continuous Dynamic Environments

Abstract

Dynamic optimization problems provide a challenge in that optima have to be tracked as the environment changes. The complexity of a dynamic optimization problem is determined by the severity and frequency of changes, as well as the behavior of the values and trajectory of optima. While many efficient algorithms have been developed to solve these types of problems, the choice of the best algorithm is highly dependent on the type of change present in the environment. This thesis analyzes the ability of popular selection operators used in a hyper-heuristic framework to continuously select the most appropriate optimization method over time to solve a DOP better than the individual optimization methods can. A contradictory situation faced by DOP-focused meta-heuristics is identified from literature: statically tuning meta-heuristic parameters for DOPs is impossible, yet dynamically adapting multiple meta-heuristic parameters in an ad hoc fashion produces poor results. The no free lunch (NFL) theorems for optimization are discussed, along with reasoning from literature as to why the conditions that are required for the NFL theorem to hold are practically impossible to find in real-world continuous-valued optimization problems. Hyper-heuristics are positioned as meta-search methods that can therefor raise performance in practical DOPs. The heterogeneous meta-hyper-heuristic (HMHH) framework was originally devised for static environments. This thesis extends the HMHH framework by establishing the criteria needed to identify appropriate meta-heuristics that enable HMHHs to solve DOPs, introduces global and island neighborhoods that govern heuristic visibility of the population of candidate solutions, and introduces different heuristic selection triggering mechanisms beyond time-based triggers. The HMHH framework is extended further to handle a mix of population-based meta-heuristics and single-solution methods under the same population-based paradigm. A new performance measure for DOPs, namely the relative error distance, or Pr, is proposed that does not assume normally distributed performance data across an algorithm run, is resilient against fitness landscape scale changes, better incorporates performance variance across multiple fitness landscape changes, and allows easier algorithm comparisons using established nonparametric statistical methods. A new measure for heuristic diversity in population-based meta-heuristics, namely N (t), is introduced that is derived from Shannon’s normalized entropy measure. Additional measures are pro- posed that consider the heuristic reassignment frequency, or δ, and heuristic reassignment volume, or φ, of a multi-population-based hyper-heuristic over the entire course of an algorithm run. Empirical studies examine the performance and behavioral differences between var- ious hyper-heuristic selection operators. The proposed experimental procedures for all algorithm evaluations, comparisons, and parameter sensitivity analysis rely entirely on nonparametric statistical procedures. Twenty-seven unique environments, based on the holistic classification of Duhain and Engelbrecht, are systematically created using the moving peaks benchmark function (MPB) generator. Parameter values are compliant with the generally accepted scenario 2 settings for the MPB. The results show that these hyper-heuristic approaches can yield higher performance more consistently across different types of environments.