Heuristic designing is a practical and indispensable tool leveraged in standard fields like artificial intelligence and operations research to find satisfactory solutions to complex optimisation problems. Experts usually design them by hand, which makes the process expensive and slow. A simplification of heuristics design, without a reduction in performance, was subsequently achieved through the Automatic Heuristic Design (AHD) proposal. It relied on several human-defined parameters, thereby limiting its adaptability as well as its effectiveness. AHD was recently integrated with LLMs, employing a strong population-based framework. However, the framework was designed to pick the first solution it found and converged quickly, which prevented it from exploring much better options, resulting in less effective optimisation strategies. In order to tackle these obstacles, a team of researchers from National University of Singapore and Southern University of Science and Technology China have developed MCTS-AHD, the first tree search method for LLM-based AHD.
Current LLM-based methods have been efficient, yet they are in need of a more tailored approach so that they do not converge on the local optima but rather explore the vast array of opportunities available. These methods also have inadequate search mechanisms, leading to insufficient investigation of the possible heuristics. They are single-objective focused, limiting their adaptability in real-world scenarios where multiple objectives must be considered. These inefficiencies ultimately increase the cost of problem optimisation, prompting the need for a new method to ensure the full-fledged utilisation of LLMS.
The suggested method, MCTS-AHD, combines Monte Carlo Tree Search and large language models for better heuristic function exploration. This system generates high-quality heuristics applicable to a wide variety of applications. In addition, MCTS-AHD uses an evaluation metric. This metric continually evaluates and improves the heuristics. Consequently, the search tree pursues only the most promising of the candidates. The key mechanisms of the method are as follows:
- Integration of MCTS and LLMs: MCTS balances the exploration of new solutions and exploitation of the existing ones, ensuring that no time is wasted on unpromising paths. LLMs can understand the problems and generate excellent heuristics by leveraging MCTS. Structure of the Search Tree: The search tree consists of nodes and branches. Nodes represent a heuristic, and branches are the tweaks made in the heuristics. This tree mapping allows the framework to remember the explored solutions and focus on finding new ones. Simulation and Tree Expansion: The heuristics on each node have multiple branches that are simulated to evaluate their performance. This evaluation ensures that the search tree only expands on the promising branches, reducing time and overall cost.
MCTS-AHD was extensively tested on challenging datasets that included NP-hard combinatorial optimisation (CO) problems and Cost-aware Acquisition Function (CAF) design for Bayesian Optimization (BO). Its performance was compared to 4 baselines: manually designed heuristics, traditional automated heuristic design, neural combinatorial optimisation, and LLM-based AHD methods. MCTS-AHD consistently outperformed baseline methods in these benchmarks, demonstrating its robustness across different problem domains. Overall, there was a significant improvement in heuristic quality.
In conclusion, MCTS-AHD significantly improves using large language models to design heuristics automatically. MCTS-AHD uses a tree-based structure, progressive widening and revolutionary exploration strategies to explore more heuristic functions than existing methods. This approach improves the performance and diversity of the heuristics and offers a strong framework for dealing with a meaningful number of complex CO tasks. MCTS-AHD creates a meaningful benchmark in AHD research, providing a highly scalable and exceptionally flexible solution for various applications.
Check out the Paper and GitHub Page. All credit for this research goes to the researchers of this project. Also, don’t forget to follow us on Twitter and join our Telegram Channel and LinkedIn Group. Don’t Forget to join our 70k+ ML SubReddit.
The post Revolutionizing Heuristic Design: Monte Carlo Tree Search Meets Large Language Models appeared first on MarkTechPost.
