🤖 AI

Teacher-Aware Evolution of Heuristic Programs from Learned Optimization Policies

This paper proposes a teacher-aware evolutionary framework that leverages independently trained learned optimization policies as behavioral teachers to guide the automatic discovery of static, executable heuristics for combinatorial optimization, achieving superior performance over purely performance-driven LLM baselines without requiring neural inference at deployment.

Original authors: Minyu Chen, Song Qin, Ling-I Wu, Jianxin Xue, Guoqiang Li

Published 2026-05-12

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Minyu Chen, Song Qin, Ling-I Wu, Jianxin Xue, Guoqiang Li

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach a robot how to solve a complex puzzle, like organizing a factory schedule or planning the most efficient delivery route. You want the robot to learn a set of simple, written rules (a "heuristic") that it can follow quickly without needing a supercomputer.

The Problem with Old Methods
Previously, researchers used a "trial and error" approach with Large Language Models (LLMs). They would generate a rule, test it, and if the final result was bad, they would tell the LLM, "Try again." It's like a student taking a final exam, getting a failing grade, and then being told, "You failed, go study harder," without ever knowing which specific questions they got wrong or why. The feedback was delayed and vague.

The New Idea: The "Teacher" Coach
This paper introduces a new way to train these rules using a "Teacher-Aware" system.

Think of it like a sports coach training a rookie player:

The Rookie (The Candidate Program): This is the new set of rules the computer is trying to invent. It plays the game (solves the puzzle).
The Coach (The Learned Policy): This is a highly trained AI that already knows how to play the game very well. However, we aren't asking the Coach to play the game for us. We aren't trying to copy the Coach's brain directly.
The Interaction: As the Rookie plays, the Coach watches every single move the Rookie makes in real-time.
- If the Rookie makes a move the Coach thinks is good, the Coach nods.
- If the Rookie makes a move the Coach thinks is bad, the Coach shakes their head and says, "I would have chosen a different path here."

How the System Works
Instead of waiting until the end of the game to see if the Rookie won or lost, the system uses the Coach's immediate reactions as "local feedback."

The "Reflection" Step: An AI "Analyzer" looks at the Coach's reactions. It summarizes the Rookie's mistakes: "Hey, every time you faced a busy machine, you chose the wrong one. The Coach always picks the one with the shortest wait time."
The "Revision" Step: The system gives the Rookie three specific ways to improve, based on the Coach's feedback:
- Structural Rewrite: "Your whole strategy is wrong; let's change the main rule."
- Parameter Calibration: "Your strategy is good, but you're being too aggressive. Let's tweak the numbers."
- Mechanism Fusion: "You have a great speed rule, but you're missing the Coach's smart selection rule. Let's combine them."

The Result
The system evolves these rules over several generations. The final product is a static, simple set of instructions (like a recipe) that is fast to run and easy for humans to understand.

Why This Matters

Better Performance: The paper tested this on four difficult puzzles (scheduling jobs, traveling salesmen, delivery routes, and cutting graphs). The new method consistently found better rules than previous methods that only looked at the final score.
Generalization: The rules learned on small puzzles worked surprisingly well on much larger, unseen puzzles.
No Heavy Lifting at the End: Once the rules are learned, you don't need the "Coach" (the complex AI) anymore. You just run the simple, fast rules. This is crucial for real-world use where speed and low cost matter.

In Summary
This paper teaches computers to invent their own simple, fast rules by letting them practice against a "smart coach" that gives instant, specific feedback on every move, rather than just grading them at the end of the game. The result is a smarter, faster, and more reliable set of instructions for solving complex problems.

Technical Summary: Teacher-Aware Evolution of Heuristic Programs from Learned Optimization Policies

1. Problem Statement

Combinatorial optimization problems (e.g., scheduling, routing, graph optimization) often rely on compact, interpretable heuristic rules. While these rules are fast and easy to deploy, designing them typically requires significant domain expertise and empirical tuning. Recent Large Language Model (LLM)-based Automatic Heuristic Design (AHD) methods have shown promise in generating executable heuristics through evolutionary search. However, existing approaches primarily rely on delayed endpoint performance (the final objective value after a full rollout) or internal LLM feedback (textual reflections, population statistics) to guide evolution.

This reliance on endpoint feedback limits the granularity of the search signal. The paper posits that Learned Optimization Policies (trained via Deep Reinforcement Learning or Neural Combinatorial Optimization) contain rich, action-level behavioral information that is currently underutilized. While these neural policies are typically used as solvers, they can serve as "behavioral teachers" that provide preferences over candidate decisions at specific states. The challenge is to leverage these learned policies to guide the evolution of static, executable heuristic programs without requiring the final program to imitate the teacher or perform neural inference at deployment.

2. Methodology

The authors propose a Teacher-Aware Evolutionary Framework that integrates independently trained black-box optimization policies as external behavioral teachers into the LLM-based heuristic search loop.

Core Mechanism: On-Policy Teacher Diagnostics

Instead of deploying the teacher or using it for direct imitation, the framework queries the teacher on the states visited by candidate heuristic programs during their execution.

State Sampling: For a candidate heuristic $h$ , the system rolls it out to generate a trajectory of states $S_h$ .
Teacher Querying: The teacher policy $T$ is queried on these specific states to determine its preferred action $a_T(s)$ or action scores $Q_T(s, a)$ .
Alignment Signals: The system computes:
- Top-1 Agreement: The frequency with which the candidate's action matches the teacher's preferred action.
- Normalized Teacher Value: If scores are available, the normalized value of the candidate's chosen action relative to the feasible action set.
- Percentile Rank: The rank of the candidate's action under the teacher's ordering.

Teacher-Guided Reflection and Revision

These diagnostic signals are converted into actionable feedback for the LLM analyzer. A lightweight task interface adapter ensures the feedback is contextually relevant. The analyzer LLM generates revision briefs based on three specific teacher-guided operators:

Structural Rewrite: Modifies high-level decision components when disagreements reveal recurring structural failures.
Parameter Calibration: Adjusts weights, thresholds, or gates when the program selects reasonable actions but is locally miscalibrated relative to the teacher.
Mechanism-Level Fusion: Combines an objective-strong mechanism with an alignment-strong mechanism to preserve performance while incorporating teacher-derived behavioral biases.

Population Management

The framework employs a multi-objective selection strategy using Pareto-style nondominated sorting. Each candidate is evaluated on a vector $z(h) = (F(h), -Align(h))$, where $F(h)$ is the task objective (minimized) and $Align(h)$ is the teacher alignment (minimized).

Selection: The final heuristic is selected based on task performance, not teacher fidelity. This ensures the output remains a static, efficient program optimized for the specific task, rather than a compressed version of the teacher.

3. Key Contributions

The paper claims four primary contributions:

Formulation: It introduces the concept of using independently trained black-box optimization policies as external behavioral teachers for LLM-based heuristic evolution.
Sampled On-Policy Teacher Alignment: A method to query teachers on candidate-induced states and convert their preferences into local behavioral search signals, distinct from standard imitation learning.
Teacher-Aware Reflective Evolution: A framework that utilizes teacher-alignment summaries and disagreement cases to guide structural and parametric revisions of heuristic programs.
Empirical Validation: Demonstration across four sequential combinatorial optimization domains (JSSP, TSP, CVRP, MaxCut) that learned policies can effectively guide the discovery of static, interpretable, and efficient heuristics.

4. Experimental Results

The method was evaluated on four benchmarks: Job-Shop Scheduling (JSSP), Traveling Salesman Problem (TSP), Capacitated Vehicle Routing Problem (CVRP), and MaxCut.

Performance: The proposed method consistently outperformed performance-driven LLM baselines (EoH, ReEvo) and classical dispatching rules across in-distribution and out-of-distribution (OOD) settings.
- JSSP: Achieved the best makespan on 10x10, 15x15, and 20x20 instances, and demonstrated superior generalization to larger random instances and Taillard benchmarks.
- Routing (TSP/CVRP): Produced the best solution quality among LLM-evolved heuristics, narrowing the gap to specialized solvers (like LKH) while maintaining the speed of static programs.
- MaxCut: Showed competitive performance on training distributions and strong transferability to different graph distributions (e.g., from Barabási–Albert to Erdős–Rényi) and scales.
Efficiency: The resulting heuristics are static executable programs, requiring no neural inference at deployment. They are substantially faster than the learned neural policies (teachers) used for guidance.
Ablation Studies: Removing teacher-derived feedback ("Performance-only") consistently degraded results, confirming the value of behavioral signals. Removing specific components (analyzer guidance, teacher-guided operators, or Pareto updates) also led to performance drops, particularly in OOD generalization.

5. Significance and Claims

The paper argues that learned optimization policies can be repurposed as behavioral feedback sources for automatic heuristic discovery. The significance lies in shifting the role of neural policies from being the final solver to being a source of local decision-level feedback.

Complementarity: Teacher preferences provide a signal complementary to endpoint fitness, guiding the search toward heuristics that preserve useful learned biases while correcting specific weaknesses.
Static vs. Neural: The framework successfully bridges the gap between the high performance of learned neural policies and the interpretability/efficiency of static heuristics.
Modesty: The authors acknowledge limitations, noting the method requires an alignable learned teacher, task-specific interface adapters, and analyzer calls. They do not claim to replace all solvers but rather to improve the discovery process of static heuristics.

In summary, the work demonstrates that by treating learned policies as "behavioral teachers" rather than "solvers to be imitated," one can evolve static heuristics that are both high-performing and efficient, leveraging the rich local decision signals of deep learning without inheriting its computational overhead.