Revolutionizing Heuristic Design: Monte Carlo Tree Search Meets Large Language Models
www.marktechpost.com
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,dont forget to follow us onTwitter and join ourTelegram Channel andLinkedIn Group. Dont Forget to join our70k+ ML SubReddit. Afeerah Naseem+ postsAfeerah Naseem is a consulting intern at Marktechpost. She is pursuing her B.tech from the Indian Institute of Technology(IIT), Kharagpur. She is passionate about Data Science and fascinated by the role of artificial intelligence in solving real-world problems. She loves discovering new technologies and exploring how they can make everyday tasks easier and more efficient. Meet 'Height':The only autonomous project management tool (Sponsored)
0 Comments
·0 Shares
·34 Views