<p>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 <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10732_2025_9560_Article_IEq1.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="128" /> </InlineMediaObject> <EquationSource Format="TEX">$(1,Cap(t)||\sum T_j)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <mn>1</mn> <mo>,</mo> <mi>C</mi> <mi>a</mi> <mi>p</mi> <mrow> <mo stretchy="false">(</mo> <mi>t</mi> <mo stretchy="false">)</mo> </mrow> <mo stretchy="false">|</mo> <mo stretchy="false">|</mo> <mo>∑</mo> <msub> <mi>T</mi> <mi>j</mi> </msub> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>) 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.</p>

Tree search hyper-heuristic with application to combinatorial optimization

期刊论文
出版模式：

开放获取
发表日期：

2025年5月17日

查看全文

Francisco Javier Gil-Gala,
Marko Ɖurasevic,
Maria R. Sierra,
Ramiro Varela

摘要

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)$ $(1, C a p (t) | | \sum T_{j})$ ) 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.