Combine and conquer an evolutionary hyperheurist

Authors: José Carlos OrtizBayliss Hugo TerashimaMarín Santiago Enrique ConantPablos

Publish Date: 2016/02/10

Volume: 46, Issue: 3, Pages: 327-349

PDF Link

Abstract

Selection hyperheuristics are a technology for optimization in which a highlevel mechanism controls lowlevel heuristics so as to be capable of solving a wide range of problem instances efficiently Hyperheuristics are used to generate a solution process rather than producing an immediate solution to a given problem This process is a reusable mechanism that can be applied both to seen and unseen problem instances In this paper we propose a selection hyperheuristic process with the intention to rise the level of generality and solve consistently well a wide range of constraint satisfaction problems The hyperheuristic technique is based on a messy genetic algorithm that generates highlevel heuristics formed by rules condition rightarrow  heuristic The highlevel heuristics produced are seen to be good at solving instances from certain parts of the parameterized space of problems producing results using effort comparable to the best single heuristic per instance This is beneficial as the choice of best heuristic varies from instance to instance so the highlevel heuristics are definitely preferable to selecting any one lowlevel heuristic for all instances The results confirm the robustness of the proposed approach and how highlevel heuristics trained for some specific classes of instances can also be applied to unseen classes without significant lost of efficiency This paper contributes to the understanding of heuristics and the way they can be used in a collaborative way to benefit from their combined strengths

Keywords: