A hyper-heuristic based framework for dynamic optimization problems


APPLIED SOFT COMPUTING, vol.19, pp.236-251, 2014 (Journal Indexed in SCI) identifier identifier

  • Publication Type: Article / Article
  • Volume: 19
  • Publication Date: 2014
  • Doi Number: 10.1016/j.asoc.2014.01.037
  • Title of Journal : APPLIED SOFT COMPUTING
  • Page Numbers: pp.236-251
  • Keywords: Dynamic optimization problems, Hyper-heuristics, Generalized assignment problem, Moving peaks benchmark, Memory search technique, GENETIC ALGORITHM


Most of the real world problems have dynamic characteristics, where one or more elements of the underlying model for a given problem including the objective, constraints or even environmental parameters may change over time. Hyper-heuristics are problem-independent meta-heuristic techniques that are automating the process of selecting and generating multiple low-level heuristics to solve static combinatorial optimization problems. In this paper, we present a novel hybrid strategy for applicability of hyper-heuristic techniques on dynamic environments by integrating them with the memory/search algorithm. The memory/search algorithm is an important evolutionary technique that have applied on various dynamic optimization problems. We validate performance of our method by considering both the dynamic generalized assignment problem and the moving peaks benchmark. The former problem is extended from the generalized assignment problem by changing resource consumptions, capacity constraints and costs of jobs over time; and the latter one is a well-known synthetic problem that generates and updates a multidimensional landscape consisting of several peaks. Experimental evaluation performed on various instances of the given two problems validates that our hyper-heuristic integrated framework significantly outperforms the memory/search algorithm. (C) 2014 Elsevier B.V. All rights reserved.