MISE - Research Program

Guiding Genetic Algorithms with Language Models for Combinatorial Optimization

Many real-world challenges - from routing packages to designing efficient schedules or layouts - are examples of combinatorial optimization problems: problems where we search over a vast space of possible configurations for the best solution.

This research project explores how to solve such problems using genetic algorithms (GAs) enhanced with large language models (LLMs). Students will learn the foundations of recursion, greedy heuristics, and local search, before building up to fully fledged genetic algorithm solvers. Then, students will explore how large language models (LLMs) can assist in solving combinatorial problems by helping generate or modify simple programs that define candidate solutions. Rather than relying on purely random changes, the algorithm can use the language model to suggest more promising variations - blending traditional evolutionary search with the learned patterns and generalization capabilities of modern AI tools.

This approach mirrors simplified versions of techniques used in recent state-of-the-art research on machine-assisted problem solving, where large language models are used to propose small programs that are evaluated and refined through search.