{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T01:38:21Z","timestamp":1760060301929,"version":"build-2065373602"},"reference-count":41,"publisher":"MDPI AG","issue":"8","license":[{"start":{"date-parts":[[2025,8,15]],"date-time":"2025-08-15T00:00:00Z","timestamp":1755216000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>This study introduces a novel train-and-test approach referred to as apprenticeship learning (AL) for generating selection hyper-heuristics to solve the Quadratic Unconstrained Binary Optimisation (QUBO) problem. The primary goal is to automate the design of hyper-heuristics by learning from a state-of-the-art expert and to evaluate whether the apprentice can outperform that expert. The proposed method collects detailed search trace data from the expert and trains the apprentice based on the machine learning models to predict heuristic selection and parameter settings. Multiple data filtering and class balancing techniques are explored to enhance model performance. The empirical results on unseen QUBO instances show that indeed, \u201cstudent surpasses the teacher\u201d; the hyper-heuristic with the generated heuristic selection not only outperforms the expert but also generalises quite well by solving unseen QUBO instances larger than the ones on which the apprentice was trained. These findings highlight the potential of AL to generalise expert behaviour and improve heuristic search performance.<\/jats:p>","DOI":"10.3390\/a18080516","type":"journal-article","created":{"date-parts":[[2025,8,15]],"date-time":"2025-08-15T14:24:28Z","timestamp":1755267868000},"page":"516","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Student Surpasses the Teacher: Apprenticeship Learning for Quadratic Unconstrained Binary Optimisation"],"prefix":"10.3390","volume":"18","author":[{"given":"Jack","family":"Cakebread","sequence":"first","affiliation":[{"name":"School of Computer Science, University of Nottingham, Nottingham NG8 1DY, UK"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5416-4460","authenticated-orcid":false,"given":"Warren G.","family":"Jackson","sequence":"additional","affiliation":[{"name":"School of Computer Science, University of Nottingham, Nottingham NG8 1DY, UK"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4030-6525","authenticated-orcid":false,"given":"Daniel","family":"Karapetyan","sequence":"additional","affiliation":[{"name":"School of Computer Science, University of Nottingham, Nottingham NG8 1DY, UK"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8847-1856","authenticated-orcid":false,"given":"Andrew J.","family":"Parkes","sequence":"additional","affiliation":[{"name":"School of Computer Science, University of Nottingham, Nottingham NG8 1DY, UK"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0276-1391","authenticated-orcid":false,"given":"Ender","family":"\u00d6zcan","sequence":"additional","affiliation":[{"name":"School of Computer Science, University of Nottingham, Nottingham NG8 1DY, UK"}]}],"member":"1968","published-online":{"date-parts":[[2025,8,15]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Cowling, P., Kendall, G., and Soubeiga, E. (2001). A Hyperheuristic Approach to Scheduling a Sales Summit. Practice and Theory of Automated Timetabling III, Springer.","DOI":"10.1007\/3-540-44629-X_11"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1016\/j.ejor.2019.07.073","article-title":"Recent advances in selection hyper-heuristics","volume":"285","author":"Drake","year":"2020","journal-title":"Eur. J. Oper. Res."},{"key":"ref_3","unstructured":"Burke, E., Curtois, T., Graham, H., Gabriela, K., Sanja, O., and Jos, P. (2009, January 10\u201312). HyFlex: A Flexible Framework for the Design and Analysis of Hyper-heuristics. Proceedings of the Multidisciplinary International Scheduling Conference (MISTA 2009), Dublin, Ireland."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Burke, E., Gendreau, M., Hyde, M., Kendall, G., McCollum, B., Ochoa, G., Parkes, A., and Petrovic, S. (2011). The Cross-Domain Heuristic Search Challenge\u2013An International Research Competition. LION 2011: Learning and Intelligent Optimization, Springer.","DOI":"10.1007\/978-3-642-25566-3_49"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"M\u0131s\u0131r, M., Verbeeck, K., De Causmaecker, P., and Vanden Berghe, G. (2012, January 16\u201320). An Intelligent Hyper-Heuristic Framework for CHeSC 2011. Proceedings of the Learning and Intelligent OptimizatioN, Paris, France.","DOI":"10.1007\/978-3-642-34413-8_45"},{"key":"ref_6","unstructured":"Warren, J., Karapetyan, D., \u00d6zcan, E., and Parkes, A.J. (2022). Automated Algorithm Configuration for the Quadratic Unconstrained Binary Optimisation Problem (Presented at OR62), Technical Report."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"58","DOI":"10.1007\/s10878-014-9734-0","article-title":"The unconstrained binary quadratic programming problem: A survey","volume":"28","author":"Kochenberger","year":"2014","journal-title":"J. Comb. Optim."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1002\/net.21751","article-title":"Quadratic unconstrained binary optimization problem preprocessing: Theory and empirical analysis","volume":"70","author":"Lewis","year":"2017","journal-title":"Networks"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"McGeoch, C.C. (2014). The D-Wave Platform. Adiabatic Quantum Computation and Quantum Annealing: Theory and Practice, Springer International Publishing.","DOI":"10.1007\/978-3-031-02518-1"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"218","DOI":"10.1038\/nphys2900","article-title":"Evidence for quantum annealing with more than one hundred qubits","volume":"10","author":"Boixo","year":"2014","journal-title":"Nat. Phys."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Samuel, A.L. (1960). Programming Computers to Play Games. Advances in Computers, 1, Elsevier.","DOI":"10.1016\/S0065-2458(08)60608-7"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Abbeel, P., and Ng, A.Y. (2004, January 4\u20138). Apprenticeship Learning via Inverse Reinforcement Learning. Proceedings of the Twenty-First International Conference on Machine Learning, Banff, AB, Canada.","DOI":"10.1145\/1015330.1015430"},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Ochoa, G., Hyde, M., Curtois, T., Vazquez-Rodriguez, J.A., Walker, J., Gendreau, M., Kendall, G., McCollum, B., Parkes, A.J., and Petrovic, S. (2012, January 11\u201313). HyFlex A Benchmark Framew. Cross-Domain Heuristic Search. Proceedings of the European Conference on Evolutionary Computation in Combinatorial Optimization, M\u00e1laga, Spain.","DOI":"10.1007\/978-3-642-29124-1_12"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Adriaensen, S., Ochoa, G., and Now\u00e9, A. (2015, January 25\u201328). A benchmark set extension and comparative study for the HyFlex framework. Proceedings of the 2015 IEEE Congress on Evolutionary Computation (CEC), Sendai, Japan.","DOI":"10.1109\/CEC.2015.7256971"},{"key":"ref_15","unstructured":"Middendorf, M., and Blum, C. (2013, January 3\u20135). Generalizing Hyper-heuristics via Apprenticeship Learning. Proceedings of the Evolutionary Computation in Combinatorial Optimization, Vienna, Austria. Available online: https:\/\/www.researchgate.net\/publication\/259287080_Generalizing_Hyper-heuristics_via_Apprenticeship_Learning."},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Asta, S., and \u00d6zcan, E. (2014, January 9\u201312). An Apprenticeship Learning Hyper-Heuristic for Vehicle Routing in HyFlex. Proceedings of the 2014 IEEE Symposium on Evolving and Autonomous Learning Systems (EALS), Orlando, FL, USA.","DOI":"10.1109\/EALS.2014.7009505"},{"key":"ref_17","unstructured":"Tyasnurita, R., \u00d6zcan, E., Shahriar, A., and John, R. (2015, January 11\u201315). Improving performance of a hyper-heuristic using a multilayer perceptron for vehicle routing. Proceedings of the 15th Annual Workshop on Computational Intelligence, Madrid, Spain."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Ushijima-Mwesigwa, H., Negre, C.F.A., and Mniszewski, S.M. (2017, January 12). Graph Partitioning Using Quantum Annealing on the D-Wave System. Proceedings of the Second International Workshop on Post Moores Era Supercomputing, New York, NY, USA. PMES\u201917.","DOI":"10.1145\/3149526.3149531"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"595","DOI":"10.1016\/j.ejor.2012.07.012","article-title":"Path relinking for unconstrained binary quadratic programming","volume":"223","author":"Wang","year":"2012","journal-title":"Eur. J. Oper. Res."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Adriaensen, S., and Now\u2019e, A. (2016, January 24\u201329). Case Study: An Analysis of Accidental Complexity in a State-of-the-art Hyper-heuristic for HyFlex. Proceedings of the 2016 IEEE Congress on Evolutionary Computation (CEC), Vancouver, BC, Canada.","DOI":"10.1109\/CEC.2016.7743965"},{"key":"ref_21","unstructured":"Witten, I.H., Frank, E., Hall, M.A., and Pal, C.J. (2016). The WEKA Workbench. Online Appendix for \u201cData Mining: Practical Machine Learning Tools and Techniques\u201d, Morgan Kaufmann Publishers Inc.. [4th ed.]."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1007\/s13748-019-00185-z","article-title":"A review on the self and dual interactions between machine learning and optimisation","volume":"8","author":"Song","year":"2019","journal-title":"Prog. Artif. Intell."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"1093","DOI":"10.1016\/j.eswa.2006.12.018","article-title":"Mining the data from a hyperheuristic approach using associative classification","volume":"34","author":"Thabtah","year":"2008","journal-title":"Expert Syst. Appl."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"8348","DOI":"10.1109\/TITS.2023.3270334","article-title":"Frequent Itemset-Driven Search for Finding Minimal Node Separators and Its Application to Air Transportation Network Analysis","volume":"24","author":"Zhou","year":"2023","journal-title":"IEEE Trans. Intell. Transp. Syst."},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Tapia-Avitia, J.M., Cruz-Duarte, J.M., Amaya, I., Ortiz-Bayliss, J.C., Terashima-Marin, H., and Pillay, N. (2022, January 18\u201323). A Primary Study on Hyper-Heuristics Powered by Artificial Neural Networks for Customising Population-based Metaheuristics in Continuous Optimisation Problems. Proceedings of the 2022 IEEE Congress on Evolutionary Computation (CEC), Padua, Italy.","DOI":"10.1109\/CEC55065.2022.9870275"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"412","DOI":"10.1016\/j.ins.2014.12.020","article-title":"A tensor-based selection hyper-heuristic for cross-domain heuristic search","volume":"299","author":"Asta","year":"2015","journal-title":"Inf. Sci."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1016\/j.knosys.2016.01.031","article-title":"A tensor based hyper-heuristic for nurse rostering","volume":"98","author":"Asta","year":"2016","journal-title":"Knowl.-Based Syst."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"115978","DOI":"10.1016\/j.eswa.2021.115978","article-title":"Semiconductor final testing scheduling using Q-learning based hyper-heuristic","volume":"187","author":"Lin","year":"2022","journal-title":"Expert Syst. Appl."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"121050","DOI":"10.1016\/j.eswa.2023.121050","article-title":"A Q-learning-based hyper-heuristic evolutionary algorithm for the distributed flexible job-shop scheduling problem with crane transportation","volume":"234","author":"Zhang","year":"2023","journal-title":"Expert Syst. Appl."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1007\/s10710-017-9308-x","article-title":"A hyperheuristic approach based on low-level heuristics for the travelling thief problem","volume":"19","author":"Martins","year":"2018","journal-title":"Genet. Program. Evolvable Mach."},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Fontoura, V.D., Pozo, A.T., and Santana, R. (2017, January 5\u20138). Automated design of hyper-heuristics components to solve the PSP problem with HP model. Proceedings of the IEEE Congress on Evolutionary Computation (CEC 2017), Donostia, Spain.","DOI":"10.1109\/CEC.2017.7969526"},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1016\/j.ins.2014.10.045","article-title":"Population based Monte Carlo tree search hyper-heuristic for combinatorial optimization problems","volume":"314","author":"Sabar","year":"2015","journal-title":"Inf. Sci."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1109\/TEVC.2014.2319051","article-title":"Automatic design of a hyper-heuristic framework with gene expression programming for combinatorial optimization problems","volume":"19","author":"Sabar","year":"2015","journal-title":"IEEE Trans. Evol. Comput."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"494","DOI":"10.1016\/j.ejor.2017.01.001","article-title":"Markov Chain methods for the bipartite Boolean quadratic programming problem","volume":"260","author":"Karapetyan","year":"2017","journal-title":"Eur. J. Oper. Res."},{"key":"ref_35","unstructured":"MacQueen, J. (2025, May 08). Some Methods for Classification and Analysis of Multivariate Observations. Available online: https:\/\/www.scirp.org\/reference\/referencespapers?referenceid=2232949."},{"key":"ref_36","unstructured":"Haykin, S. (1994). Neural Networks: A Comprehensive Foundation, Prentice Hall PTR."},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Tyasnurita, R., \u00d6zcan, E., and John, R. (2017, January 5\u20138). Learning heuristic selection using a Time Delay Neural Network for Open Vehicle Routing. Proceedings of the 2017 IEEE Congress on Evolutionary Computation (CEC), Donostia, Spain.","DOI":"10.1109\/CEC.2017.7969477"},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"111731","DOI":"10.1016\/j.knosys.2024.111731","article-title":"Constructing selection hyper-heuristics for open vehicle routing with time delay neural networks using multiple experts","volume":"295","author":"Tyasnurita","year":"2024","journal-title":"Knowl.-Based Syst."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1016\/j.ejor.2015.09.003","article-title":"An iterated multi-stage selection hyper-heuristic","volume":"250","author":"Kheiri","year":"2016","journal-title":"Eur. J. Oper. Res."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1007\/s10732-007-9009-3","article-title":"Local search heuristics for Quadratic Unconstrained Binary Optimization (QUBO)","volume":"13","author":"Boros","year":"2007","journal-title":"J. Heuristics"},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"106760","DOI":"10.1016\/j.asoc.2020.106760","article-title":"Hyper-Heuristics based on Reinforcement Learning, Balanced Heuristic Selection and Group Decision Acceptance","volume":"97","year":"2020","journal-title":"Appl. Soft Comput."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/18\/8\/516\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T18:28:22Z","timestamp":1760034502000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/18\/8\/516"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,8,15]]},"references-count":41,"journal-issue":{"issue":"8","published-online":{"date-parts":[[2025,8]]}},"alternative-id":["a18080516"],"URL":"https:\/\/doi.org\/10.3390\/a18080516","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2025,8,15]]}}}