HeuristicInventor: Enabling Large Language Models to Automatically Invent Combinatorial Optimization Algorithms

HeuristicInventor is an innovative automated discovery engine that uses large language models (LLMs) to automatically invent algorithms for solving combinatorial optimization problems (e.g., Traveling Salesman Problem, TSP) through an iterative "novelty search" loop. Its core idea is to enable LLMs to generate, test, and refine Python code, continuously introducing new state variables and search dynamics to accelerate the algorithm discovery process. This project provides a new paradigm for AI-assisted algorithm design in the field of combinatorial optimization.

Combinatorial optimization problems (e.g., TSP, VRP) are NP-hard and widely used in fields like logistics and manufacturing. However, traditional heuristic algorithms require manual design and tuning by domain experts, which is time-consuming and labor-intensive. HeuristicInventor proposes a disruptive idea: letting large language models become algorithm inventors, using an automated loop to understand problem structures and propose innovative strategies to address the pain points of traditional methods.

HeuristicInventor's core architecture consists of three key components:

1. Novelty Search Loop: Inspired by biological evolution, it prioritizes retaining candidate solutions with large behavioral differences to avoid premature convergence and maintain diversity in the solution space;
2. LLM-Driven Code Generation: Supports models like Google Gemini and DeepSeek, which take problem descriptions, analyze bottlenecks, and generate modular Python code;
3. Automated Testing and Evaluation: Runs algorithms on TSP benchmark instances, records quality, efficiency, and behavioral characteristics, and uses feedback results to guide the next round of generation.

HeuristicInventor's technical highlights include:

• Dynamic State Variable Discovery: LLMs freely invent new variables such as node visit frequency and edge heat to capture the deep structure of the problem;
• Adaptive Search Dynamics: Adjust the exploration/exploitation ratio based on progress, modify neighborhood size, and implement multi-strategy mixing and memory mechanisms;
• Cross-Instance Generalization: Maintains competitiveness even on unseen types of TSP instances.

The project validated its effectiveness on multiple TSP benchmark datasets:

• TSPLIB standard instances: Achieved or approached known optimal solutions;
• Large-scale random instances: Can handle problems with thousands of nodes, showing good scalability;
• Special structure instances: Performed outstandingly on clustered or grid-structured instances. Interesting findings: LLMs sometimes reinvent variants of classic algorithms (e.g., simulated annealing) and also propose innovative strategies not considered by human experts.

HeuristicInventor has broad application prospects:

• Other Combinatorial Optimization Problems: Can be migrated to VRP, job scheduling, knapsack problems, etc.;
• Technology Integration: Combine with neural combinatorial optimization, Bayesian hyperparameter optimization, and multi-objective optimization;
• Educational and Research Value: Serve as an experimental platform for studying LLM creativity, helping to understand their reasoning patterns and innovation boundaries.

HeuristicInventor has the following limitations:

• Computational Cost: High cost of LLM API calls limits large-scale searches;
• Code Reliability: Automatically generated code occasionally contains syntax or logical flaws;
• Interpretability: Some algorithms lack intuitive explanations;
• Theoretical Guarantees: Lack of theoretical analysis on the performance of generated algorithms.

HeuristicInventor represents a new direction for AI-assisted algorithm design, combining LLM creativity with automated evaluation to bring a new paradigm to the field of combinatorial optimization. Future directions include:

1. Efficient code generation strategies to reduce API call costs;
2. Automatic code repair mechanisms to improve reliability;
3. Establishing a theoretical analysis framework for generated algorithms;
4. Expanding to a wider range of optimization problem categories. This project provides open-source tools and an experimental platform for developers and researchers.