Heuristic selection in a multi-phase hybrid approach for dynamic environments

Abstract

An iterative selection hyper-heuristic method controls and mixes a set of low-level heuristics while solving a given problem. A low-level heuristic is selected and employed for improving a (set of) solution(s) at each step. This study investigates the influence of different heuristic selection methods within a population based incremental learning algorithm and hyper-heuristic based hybrid multiphase framework for solving dynamic environment problems. Even though the hybrid method delivers a good overall performance, it is superior in cyclic environments. The empirical results show that a heuristic selection method that relies on a fixed permutation of the underlying low-level heuristics, combined with a strategy that guarantees diversity when the environment changes is more successful than the learning approaches across different dynamic environments produced using a well known benchmark generator.