Welcome back to OR-Path!
GenAI + OR Radar explores research connecting generative AI and Operations Research. After FunSearch, this edition looks at Evolution of Heuristics (EoH), published at ICML 2024: a way to evolve a heuristic’s description alongside its executable code.
The authors developed it independently of FunSearch. We are following a research theme, rather than a direct succession of inventions.
So let’s get straight to it.
1. Give each rule an idea and an implementation
Imagine a small competition for packing rules. Each contestant brings a recipe card and a program. The card explains the strategy; the program lets us try it.
For example, a best-fit rule places an incoming item in the box that leaves the least unused space. An item of size 4 fits exactly into a box with 4 units free, rather than boxes with 7 or 9 units free.
The figure shows that simple rule in words and code. It is our teaching example, not a heuristic discovered by EoH.
One idea, two representations. The blue item fills box 2 exactly. Original OR-Path best-fit teaching example; not a heuristic discovered by EoH or an experimental result. Click to enlarge.
2. Let the candidates compete
EoH keeps a population of descriptions and implementations. The LLM proposes variations, executable candidates are evaluated, and stronger heuristics survive. Its prompts can explore ideas, combine features, adjust parameters or simplify code.
Here is the search loop in plain-language pseudocode. Candidates are tested on design instances; detailed operators are omitted for readability.
Create idea + code pairs
Test the initial pool
Repeat while budget remains:
Select parent heuristics
LLM varies ideas and code
Test valid candidates
Keep the best in the pool
Return the best heuristic
Test it on unseen instances3. Read the results at the right scale
The paper evaluates online bin packing, the traveling salesman problem and flow shop scheduling. The illustrated bin-packing search uses 2,000 LLM queries and compares the resulting rule with established baselines and the published FunSearch heuristic.
These are benchmark results. They do not establish universal superiority, and the query counts are not a controlled cost comparison between identical models and setups.
A packing rule also faces a practical tension: a good fit now may leave awkward space for later arrivals. Testing across instances matters because one attractive example cannot tell us how the rule behaves over an entire sequence.
Why I chose this paper
EoH makes the design process easier to discuss: propose a rule, express it, measure it, then revise it. The description gives us something to inspect; the evaluation gives us something to challenge.
For me, the question worth following is how much these generated rules retain their usefulness when the instances change. That is where an appealing idea has to earn its place.
Read further
Fei Liu et al. — Evolution of Heuristics, ICML 2024.
Until next time 👋
Ricardo
OR-Path
