Evolution of Heuristics: Towards Efficient Automatic Algorithm Design Using Large Language Model

2024/01/04 by Fei Liu, Xialiang Tong, Liu, Fei +13 · 59 citations
Computer Science · #Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #Metaheuristic Optimization Algorithms Research #Multimodal Machine Learning Applications #Neural and Evolutionary Computing (cs.NE) #Speech and dialogue systems

paper · pdf · doi:10.48550/arxiv.2401.02051

openalex publication_date 2024/01/04 · openalex created_date 2024/01/10 · openalex updated_date 2026/07/28

Abstract

Heuristics are widely used for dealing with complex search and optimization problems. However, manual design of heuristics can be often very labour extensive and requires rich working experience and knowledge. This paper proposes Evolution of Heuristic (EoH), a novel evolutionary paradigm that leverages both Large Language Models (LLMs) and Evolutionary Computation (EC) methods for Automatic Heuristic Design (AHD). EoH represents the ideas of heuristics in natural language, termed thoughts. They are then translated into executable codes by LLMs. The evolution of both thoughts and codes in an evolutionary search framework makes it very effective and efficient for generating high-performance heuristics. Experiments on three widely studied combinatorial optimization benchmark problems demonstrate that EoH outperforms commonly used handcrafted heuristics and other recent AHD methods including FunSearch. Particularly, the heuristic produced by EoH with a low computational budget (in terms of the number of queries to LLMs) significantly outperforms widely-used human hand-crafted baseline algorithms for the online bin packing problem.

Cited by

• Benchmarking Zero-Shot LLM-Generated Parent Selection in Genetic Programming for Symbolic Regression
• TopoFE: topology-aware LLM-guided Automated Feature Engineering
• PortAgent: LLM-driven Vehicle Dispatching Agent for Port Terminals
• CogMCTS: A Novel Cognitive-Guided Monte Carlo Tree Search Framework for Iterative Heuristic Evolution with Large Language Models
• AutoICE: Automatically Synthesizing Verifiable C Code via LLM-driven Evolution
• Task-Specific Trust Evaluation for Multi-Hop Collaborator Selection via GNN-Aided Distributed Agentic AI
• Evolutionary Discovery of Heuristic Policies for Traffic Signal Control
• From Performance to Understanding: A Vision for Explainable Automated Algorithm Design
• Online Operator Design in Evolutionary Optimization for Flexible Job Shop Scheduling via Large Language Models
• Channel Ordering for Fairness in Elastic Optical Networks via a LLM-Guided Bottleneck TSP Solver
• irace-evo: Automatic Algorithm Configuration Extended With LLM-Based Code Evolution
• Using Multi-modal Large Language Model to Boost Fireworks Algorithm's Ability in Settling Challenging Optimization Tasks
• SOCRATES: Simulation Optimization with Correlated Replicas and Adaptive Trajectory Evaluations
• An In-depth Study of LLM Contributions to the Bin Packing Problem
• Glia: A Human-Inspired AI for Automated Systems Design and Optimization
• The FM Agent
• Discovering Heuristics with Large Language Models (LLMs) for Mixed-Integer Programs: Single-Machine Scheduling
• Structure-Aware Cooperative Ensemble Evolutionary Optimization on Combinatorial Problems with Multimodal Large Language Models
• AutoOpt: A Dataset and a Unified Framework for Automating Optimization Problem Solving
• REvolution: An Evolutionary Framework for RTL Generation driven by Large Language Models
• AlphaOPT: Formulating Optimization Programs with Self-Improving LLM Experience Library
• Automated Algorithm Design for Auto-Tuning Optimizers
• An Agentic Framework with LLMs for Solving Complex Vehicle Routing Problems
• EvoCAD: Evolutionary CAD Code Generation with Vision Language Models
• Refining Hybrid Genetic Search for CVRP via Reinforcement Learning-Finetuned LLM
• Hierarchical Optimization via LLM-Guided Objective Evolution for Mobility-on-Demand Systems
• VRPAgent: LLM-Driven Discovery of Heuristic Operators for Vehicle Routing Problems
• MCCE: A Framework for Multi-LLM Collaborative Co-Evolution
• MetaMuse: Algorithm Generation via Creative Ideation
• EvoEngineer: Mastering Automated CUDA Kernel Code Evolution with Large Language Models
• EvoSpeak: Large Language Models for Interpretable Genetic Programming-Evolved Heuristics
• Combining Large Language Models and Gradient-Free Optimization for Automatic Control Policy Synthesis
• Experience-Guided Reflective Co-Evolution of Prompts and Heuristics for Automatic Algorithm Design
• ViTSP: A Vision Language Models Guided Framework for Large-Scale Traveling Salesman Problems
• AutoEP: LLMs-Driven Automation of Hyperparameter Evolution for Metaheuristic Algorithms
• URS: A Unified Neural Routing Solver for Cross-Problem Zero-Shot Generalization
• StepORLM: A Self-Evolving Framework With Generative Process Supervision For Operations Research Language Models
• Structuring Collective Action with LLM-Guided Evolution: From Ill-Structured Problems to Executable Heuristics
• Guiding Large Language Models with Genetic Programming-Evolved Heuristic Knowledge for Dynamic Multi-Mode Project Scheduling
• Budget-Aware LLM Discovery via Cost-Calibrated Frontier Utility
• LM-GRASP: Instance-Specific Language Models for Combinatorial Construction via Online Imitation Learning
• Optimizing ground state preparation protocols with autoresearch
• Large Language Models as End-to-end Combinatorial Optimization Solvers
• Large Language Models in Operations Research: Methods, Applications, and Challenges
• Large Language Model Assisted Automated Algorithm Generation and Evolution via Meta-black-box optimization
• Evolution of Kernels: Automated RISC-V Kernel Optimization with Large Language Models
• Solve it with EASE
• LLM-Based Instance-Driven Heuristic Bias In the Context of a Biased Random Key Genetic Algorithm
• Re-evaluating LLM-based Heuristic Search: A Case Study on the 3D Packing Problem
• Deep Reinforcement Learning for Drone Route Optimization in Post-Disaster Road Assessment
• Language Models For Generalised PDDL Planning: Synthesising Sound and Programmatic Policies
• ELATE: Evolutionary Language model for Automated Time-series Engineering
• HiFo-Prompt: Prompting with Hindsight and Foresight for LLM-based Automatic Heuristic Design
• EvoCut: Strengthening Integer Programs via Evolution-Guided Language Models
• \(X\)-evolve: Solution space evolution powered by large language models
• Multimodal LLM-assisted Evolutionary Search for Programmatic Control Policies
• Collab-Solver: Collaborative Solving Policy Learning for Mixed-Integer Linear Programming
• Learning to Incentivize: LLM-Empowered Contract for AIGC Offloading in Teleoperation
• Automatically discovering heuristics in a complex SAT solver with large language models

Related

• Multi-objective Evolution of Heuristic Using Large Language Model
• Understanding the Importance of Evolutionary Search in Automated Heuristic Design with Large Language Models
• Leveraging Large Language Models to Develop Heuristics for Emerging Optimization Problems
• EoH-S: Evolution of Heuristic Set using LLMs for Automated Heuristic Design
• Experience-Guided Reflective Co-Evolution of Prompts and Heuristics for Automatic Algorithm Design