Discovering optimisation heuristics with LLM-guided evolution

teaching

Motivation

FunSearch and AlphaEvolve use language models to propose programs within an evolutionary search. Candidate algorithms are evaluated, and successful candidates inform subsequent proposals. The generated code might decide which item to place next, which move to try, or how to initialise a numerical solver. Its decisions and performance can be compared with algorithms designed by hand.

Project goal

Choose an optimisation problem and use LLM-guided evolution to develop or improve an algorithm for solving it. Define the objective and constraints, implement comparison methods, and build or adapt a search procedure that generates and evaluates candidate programs. The editable part may be a decision rule within an existing algorithm or a larger procedure. Investigate the quality of the solutions, the computation required, and the features of the problem that explain success or failure. You may develop your own application or reproduce and extend an experiment from the literature.

Possible directions

  • Packing items into bins. Given items of different sizes and bins of fixed capacity, minimise the number of bins used. Compare with first fit or best fit, then evolve a bin-selection rule or, when all items are known in advance, their ordering.

  • Constructing and improving routes. Find a short tour visiting a collection of locations, starting from a nearest-neighbour construction followed by local improvement. Evolve a rule for inserting locations or changing a tour, and investigate its behaviour on different arrangements of locations.

  • Scheduling jobs on machines. Assign jobs with known processing times to identical machines to minimise the time until all jobs finish. Evolve an assignment or improvement rule and compare with scheduling jobs in decreasing order of duration on the least-loaded machine.

  • Finding geometric constructions. Arrange a fixed number of equal circles inside a unit square, without overlap, to maximise their common radius. Evolve programs that construct or perturb arrangements, optionally followed by numerical optimisation, and compare with simple initialisations using the same solver.

These examples are optional; choose any problem that interests you and permits repeated experiments within your resources.

Developing your investigation

Decide what information the heuristic may use and what part of its code can change. An online packing rule sees items as they arrive; an offline rule can use the entire list. Keep feasibility checks and final scoring outside the code being evolved. Use an existing language model to propose programs, evaluate them, retain promising candidates, and guide further proposals. Inspect and simplify successful programs to investigate why they work. For example, which patterns of item sizes explain an improvement in packing, and can you construct a case where the rule fails?

Experimental considerations

Compare the evolved algorithm with established methods for the chosen problem under comparable execution budgets. Report solution quality, running time, and failures to return a feasible solution. Exact solutions or bounds, when available, can indicate how much improvement remains possible.

For reusable heuristics, assess the final algorithm on instances held out from the search; changes in problem size or structure can reveal its limits. For a fixed construction, independently verify feasibility and objective value, and compare repeated searches under the same budget. Generalisation to other instances is then an optional extension.

Report the cost of discovering an algorithm separately from the cost of using it, including unsuccessful proposals and evaluations. Record the model, prompts, programs, and evaluation settings so that results can be reproduced. Rediscovering a known heuristic or failing to improve a baseline can also provide evidence about the problem and the search procedure.

Suggested reading