Experience-Guided Reflective Co-Evolution of Prompts and Heuristics for Automatic Algorithm Design
This addresses the challenge of reducing manual effort in algorithm design for combinatorial optimization, though it appears incremental as it builds on existing LLM-based methods.
The paper tackled the problem of automatic heuristic design for combinatorial optimization using LLMs, which often stagnates in local optima, by proposing the EvoPH framework that co-evolves prompts and heuristics with performance feedback, achieving the lowest relative error against optimal solutions on the Traveling Salesman and Bin Packing problems.
Combinatorial optimization problems are traditionally tackled with handcrafted heuristic algorithms, which demand extensive domain expertise and significant implementation effort. Recent progress has highlighted the potential of automatic heuristics design powered by large language models (LLMs), enabling the automatic generation and refinement of heuristics. These approaches typically maintain a population of heuristics and employ LLMs as mutation operators to evolve them across generations. While effective, such methods often risk stagnating in local optima. To address this issue, we propose the Experience-Guided Reflective Co-Evolution of Prompt and Heuristics (EvoPH) for automatic algorithm design, a novel framework that integrates the island migration model with the elites selection algorithm to simulate diverse heuristics populations. In EvoPH, prompts are co-evolved with heuristic algorithms, guided by performance feedback. We evaluate our framework on two problems, i.e., Traveling Salesman Problem and Bin Packing Problem. Experimental results demonstrate that EvoPH achieves the lowest relative error against optimal solutions across both datasets, advancing the field of automatic algorithm design with LLMs.