Tree search hyper-heuristic with application to combinatorial optimization

Francisco Javier Gil-Gala (), Marko Ɖurasevic (), Maria R. Sierra () and Ramiro Varela ()
Additional contact information
Francisco Javier Gil-Gala: University of Oviedo
Marko Ɖurasevic: University of Zagreb
Maria R. Sierra: University of Oviedo
Ramiro Varela: University of Oviedo

Journal of Heuristics, 2025, vol. 31, issue 2, No 8, 42 pages

Abstract: 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)$$ ( 1 , C a p ( t ) | | ∑ 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.

Keywords: Heuristic search; Priority rules; Hyper–heuristics; One machine scheduling problem; Travelling salesman problem (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10732-025-09560-7 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joheur:v:31:y:2025:i:2:d:10.1007_s10732-025-09560-7

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10732

DOI: 10.1007/s10732-025-09560-7

Access Statistics for this article

Journal of Heuristics is currently edited by Manuel Laguna

More articles in Journal of Heuristics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().