Experience-Driven Reflective Co-Evolution of Prompts and Heuristics for Autonomous Algorithm Design

Combinatorial optimization has long been dominated by manually engineered heuristics, a paradigm requiring substantial expert intuition and implementation overhead. The advent of Large Language Models has disrupted this landscape, enabling the autonomous synthesis and optimization of algorithms. Recent approaches typically iterate on heuristic populations using LLMs as mutators; however, these strategies often suffer from limited exploration, leading to stagnation in local optima. To overcome this, we present the Experience-Driven Reflective Co-Evolution of Prompt and Heuristics (EvoPH) for autonomous algorithm design, a novel framework that couples an island migration model with elite selection to maintain population diversity. Uniquely, EvoPH co-evolves both the guiding prompts and the heuristics themselves, using a feedback loop driven by past experience to refine the search process. We demonstrate EvoPH's efficacy on the Traveling Salesman and Bin Packing Problems. Our results show that EvoPH achieves superior accuracy compared to baselines, marking a significant step forward in LLM-aided algorithm design. You are a top expert in combinatorial optimization and algorithms. Your task is to iteratively evolve and refine an existing Python function, solve_tsp_approximate(dist_matrix), to solve the Traveling Salesperson Problem (TSP). ## Evolutionary Goal Your primary objective is to enhance the provided function in each evolutionary step, pushing it towards the optimal balance of solution quality and speed. Assume you are receiving a function that already exists and needs improvement. ## Key Optimization Metrics Your success is measured on a trade-off between two competing goals: 1. Minimize Relative Error (Solution Quality): The solution's path length must be as close to the known optimum as possible. This is the top priority. 2. Minimize Execution Time (Computational Efficiency): The function must execute extremely quickly within the evaluator's strict time limit. A faster solution is often better than a marginally more accurate but slower one. ## Your Evolutionary Directives In each round, you must analyze the function provided to you and then rewrite it to be better. Follow this process: 1. Analyze: Quickly understand the current function's strategy. What heuristic is it using? What are its potential weaknesses (e.g., slow loops, a simple heuristic that gets stuck)? 2. Strategize: Decide on the best evolutionary step. * Is the current algorithm good but implemented inefficiently? Refine it by optimizing loops or using better data structures. * Is the algorithm too basic? Replace it with a more powerful one from the toolbox. * Does the function already have a strong local search? Enhance it . * Can two ideas be combined? Hybridize different techniques for a better result. 3. Implement: Rewrite the function with your proposed improvements, ensuring it remains robust and efficient. ## Performance & Implementation Tips * NumPy is Your Friend: Always favor NumPyfor vectorized and matrix operations to maximize speed. * Smart Search: For local search, a "first improvement" strategy (find one good swap and restart the search) is often faster than "best improvement" (testing all possible swaps). * Time-Awareness: The best algorithms are useless if they time out. The function must return a solution within the time limit. * Complete provision:Provide complete and executable code, The input parsing of the main function and data needs to be completely consistent with the source code.