Tree search hyper-heuristic with application to combinatorial optimization

Abstract In this study, we investigate using the state space search paradigm to construct heuristics in the form of Priority Rules for combinatorial optimisation problems. This is an alternative to Genetic Programming (GP) and other hyper–heuristics, which represent the most common approach currently used. To do that, we define the problem of designing heuristics as a Constraint Satisfaction Problem and then exploit Any-Time Depth-First Search to solve it. To limit the effective size of the search space, we introduced a set of powerful pruning mechanisms, some embedded into the problem definition as constraints, while others by means of constraint propagation procedures. To further reduce the search space, we propose a heuristic procedure that allows the algorithm to discard some non-promising PRs, at low computational cost. The proposed approach, termed Systematic Search and Heuristic Evaluation (SSHE), was evaluated on two hard combinatorial optimisation problems, namely the One Machine Scheduling Problem with time-varying capacity (denoted by $$(1,Cap(t)||\sum T_j)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>(</mml:mo> <mml:mn>1</mml:mn> <mml:mo>,</mml:mo> <mml:mi>C</mml:mi> <mml:mi>a</mml:mi> <mml:mi>p</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>t</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>|</mml:mo> <mml:mo>|</mml:mo> <mml:mo>∑</mml:mo> <mml:msub> <mml:mi>T</mml:mi> <mml:mi>j</mml:mi> </mml:msub> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> ) and the classic Travelling Salesman Problem. The results of the experimental study show that SSHE is quite competitive with GP in building PRs; in particular, the PRs obtained by SSHE and GP showcase similar performance, but the ones produced by SSHE have generally lower size and so better readability than the PRs produced by GP.