abstract
- This work explores how Cellular Automata can be used to produce hyper-heuristics to solve combinatorial optimization problems. By leveraging the inherent structure of Cellular Automata, we introduce a hyper-heuristic model that dynamically chooses heuristics to solve a famous NP-hard problem, the Knapsack Problem, where we test our approach. We implement and compare our approach against the heuristics and some popular classifiers such as k nearest neighbors, neural networks, and random forests. Our findings highlight the potential of our approach, which learns when to apply each particular heuristic from a pool as the search progresses to obtain competent performance. Our results suggest that Cellular Automata can indeed be used to produce hyper-heuristics and compete against other popular classifiers from the literature when also used as hyper-heuristics. © The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.