Research & Engineering Report: From Mathematical Optimization to LLM-Augmented Evolutionary Algorithms1. Portfolio Executive Summary & Recruiter ProfileResearch Title: Automated Metaheuristic Design via LLM-Augmented Evolutionary Algorithms: Theory, Hybridization, and Application to NP-Hard Constraint Satisfaction Problems   Overview for Recruiters & Hiring Managers:
This research project bridges classical Operations Research (OR) and modern Generative Artificial Intelligence. It establishes a complete theoretical and applied progression from exact mathematical optimization and complexity theory to advanced hybrid metaheuristics and LLM-Augmented Evolutionary Algorithms (LLaMEA / EVOLER). Rather than relying on manual human trial-and-error to design optimization operators, this research investigates how Large Language Models (LLMs) act as automated algorithm designers—generating, mutating, and refining Python-based metaheuristics in a closed feedback loop to solve NP-hard scheduling problems such as the University Course Timetabling Problem (UCTP).   Ready-to-Use CV / Portfolio Bullet Points:Algorithmic Research & Synthesis: Conducted an in-depth literature and architectural review of LLM-Augmented Evolutionary Algorithms (specifically LLaMEA and EVOLER frameworks), analyzing how models like GPT automate the generation and refinement of optimization algorithms.   Hybrid Metaheuristic Architecture: Designed a hybrid metaheuristic framework combining Genetic Algorithms (GA) for global search-space exploration with Simulated Annealing (SA) and Iterated Local Search (ILS) for local exploitation.   Constraint Satisfaction Modeling: Formulated discrete combinatorial models for the University Course Timetabling Problem (UCTP), translating complex institutional scheduling rules into mathematical objective functions with mandatory hard constraints and penalizable soft constraints evaluated against ITC and PATAT benchmark standards.   Closed-Loop Evaluative Pipelines: Engineered mathematical simulation landscapes to test thermodynamic cooling schedules and Metropolis acceptance criteria ($e^{-\Delta f/T}$), establishing the evaluation bedrock required to sandbox and score LLM-generated heuristics.   2. Step 1: Mathematical Optimization Bedrock (Exact Methods)The first phase of the research established the mathematical rules of optimization before introducing heuristic approximations. Optimization is formally defined as searching a feasible space for a set of decision variables $x^*$ that minimizes or maximizes an objective function $f(x)$.   Linear Programming & Continuous SpacesTo verify how exact methods operate in continuous, smooth spaces, a resource-allocation Linear Programming (LP) model was formulated and solved geometrically:Decision Variables: $x$ (units of Product Alpha) and $y$ (units of Product Beta).Objective Function: Maximize total profit:
   $$\max f(x,y) = 3000x + 2000y$$System Constraints: Bounded by machine capacity ($3x + 2y \le 150$), component supply limits ($x \le 40$), and non-negativity boundaries ($x, y \ge 0$).   By mapping these inequalities onto a 2D coordinate plane, the feasible region (search space) is bounded by the corner vertices $B(0,0)$, $C(0,75)$, $D(40,0)$, and the constraint intersection point $A(40,15)$. Evaluating $f(x,y)$ across the vertices yielded:   $f(40, 0) = 120,000$$f(0, 75) = 150,000$$f(40, 15) = 150,000$Because the objective function slope is parallel to the active constraint boundary $3x + 2y = 150$, both $A(40,15)$ and $C(0,75)$ achieve the exact global maximum, proving that every continuous point along the line segment $\overline{AC}$ (such as the midpoint $(20, 45)$) represents a valid global optimum.   3. Step 2: The Complexity Wall & Combinatorial OptimizationThe second phase of the study examined why exact calculus (gradients/Hessians) and Linear Programming (Simplex) collapse when transitioning from continuous variables to discrete, real-world scheduling problems.   Combinatorial Explosion & NP-HardnessIn discrete combinatorial optimization—such as the Traveling Salesman Problem (TSP) or Timetabling—variables must be integers. Time cannot be divided into arbitrary continuous fractions; it must be discretized into fixed integer Time Slots (e.g., mapping 5 days of 4 periods into discrete slots $0$ through $19$).   When assigning $N$ discrete events to $N$ discrete slots, the search space grows factorially ($N!$):For a trivial system of $5$ classes and $5$ time slots, the search space is $5! = 120$ permutations, which a computer can evaluate exhaustively in microseconds.For a realistic university system of $500$ classes, the search space explodes to $500!$ (over $1,100$ digits).In Complexity Theory (P vs. NP), this places the problem squarely in the NP-Hard class. Because no polynomial-time exact algorithm exists to traverse this space, exact mathematical methods hit a computational wall, necessitating intelligent approximation algorithms.   Constraint Satisfaction Problem (CSP) FormulationApplied to the University Course Timetabling Problem (UCTP), the combinatorial space is governed by two distinct classes of rules:   Hard Constraints (Mandatory): Strict physical or logical boundaries (e.g., a professor or student group cannot occupy two rooms during the same time slot; room capacity cannot be exceeded). Any violation renders a timetable invalid ($H_{violations} > 0$).   Soft Constraints (Penalizable): Quality-of-life preferences (e.g., minimizing isolated gaps between lectures for students or avoiding late Friday slots). Violations do not invalidate the schedule but add penalty weights to the objective fitness function:
   $$\min f(x) = W_{hard} \sum H_i(x) + W_{soft} \sum S_j(x)$$where $W_{hard} \gg W_{soft}$.4. Step 3: Heuristics, Metaheuristics, and HybridizationTo navigate NP-hard landscapes without exhaustive brute force, the research progressed through constructive heuristics, local search, and overarching metaheuristic frameworks.   Algorithmic TierCore MechanismStrengthsPrimary LimitationConstructive HeuristicsBuilds a solution step-by-step using a greedy rule-of-thumb (e.g., scheduling the most constrained 300-student auditorium lecture first).Extremely fast execution; guarantees a strong initial structure.Rigid and myopic; early greedy choices can lock the schedule into unresolvable conflicts later.Local Search (Hill Climbing)Iteratively alters a single solution via neighborhood operators (e.g., swapping two classes) and only accepts strictly better scores.   Rapidly converges to the nearest optimal peak or valley.   Permanently trapped in Local Optima (local minima/maxima), failing to reach the Global Optimum.   MetaheuristicsHigh-level algorithmic frameworks that orchestrate heuristics using memory, stochasticity, or populations to escape local optima.   Balances Global Exploration (diversification) and Local Exploitation (intensification).   Requires intensive hyperparameter tuning and expert operator design.Trajectory Methods: Simulated Annealing (SA) & Tabu Search (TS)To understand how a single-solution metaheuristic escapes a local minimum, Simulated Annealing (SA) was modeled and simulated using its statistical mechanics and metallurgical foundations:   Physical Analogy to Math: A timetable configuration $x$ represents the atomic structure of steel, and its penalty score $E(x)$ represents internal thermodynamic energy.The Metropolis Criterion: When a neighborhood perturbation generates a better schedule ($\Delta E = E_{new} - E_{current} < 0$), the move is always accepted. Crucially, if the move produces a worse schedule ($\Delta E > 0$), SA can still accept it stochastically to climb out of a local valley according to the Boltzmann probability distribution:
   $$P(\text{accept}) = e^{-\frac{\Delta E}{T}}$$Cooling Schedule Verification: At high initial temperatures (e.g., $T = 1000, \Delta E = 10$), the acceptance probability is $e^{-0.01} \approx 0.99005$ (99%), inducing chaotic global exploration. As temperature cools geometrically ($T_{k+1} = \alpha T_k$), $P \to 0$, transitioning the algorithm into pure exploitation so the system settles into a low-energy crystalline state (Global Minimum) rather than quenching into a disordered local trap.   Complementary Trajectory & Swarm Methods: The research scope also mapped Tabu Search (TS) (which utilizes short-term memory structures/tabu lists to forbid cycling back to recently visited states), Iterated Local Search (ILS), Variable Neighborhood Search (VNS), and Swarm Intelligence frameworks including Particle Swarm Optimization (PSO) (velocity updates) and Ant Colony Optimization (ACO) (pheromone trail reinforcement).   Hybrid Metaheuristics (GA + SA / ILS)Single metaheuristics often struggle to simultaneously explore massive combinatorial spaces and fine-tune local constraints. Modern operations research relies on Hybrid Metaheuristics (such as 2026 GA-SA architectures and GAILS exploration-exploitation frameworks):   Global Exploration via Genetic Algorithms (GA): Maintains a population of candidate timetables encoded as chromosomes, applying fitness selection, crossover (recombining parent schedules), and mutation to identify promising regions of the search space.   Local Exploitation via SA or ILS: Rather than relying on blind random mutation to fix granular scheduling collisions, the hybrid architecture applies Simulated Annealing or Iterated Local Search directly to top offspring chromosomes, systematically repairing hard/soft constraint violations.   5. Step 4: Core Research — LLM-Augmented Evolutionary AlgorithmsThe culmination of the research investigated Project 20: LLM-Augmented Evolutionary Algorithms, analyzing how generative AI resolves the biggest bottleneck in classical metaheuristics: manual algorithm engineering.   The Bottleneck of Classical Evolutionary ComputationIn standard Evolutionary Algorithms (EA) and Genetic Algorithms (GA), human researchers must manually invent and hardcode the genetic operators (crossover logic, mutation step-sizes, neighborhood swap heuristics, and cooling schedules). Designing an operator that respects complex domain rules—such as UCTP disruptions—requires months of human trial-and-error.   The Paradigm Shift: LLaMEA and EVOLERLLM-Augmented Evolutionary Algorithms integrate Large Language Models (such as GPT-based architectures or open-weight coding models) directly into the evolutionary loop. Using state-of-the-art frameworks like LLaMEA (Large Language Model Evolutionary Algorithm) and EVOLER, the search space is no longer a set of numbers—the search space is the space of executable Python algorithms itself.   +-----------------------------------------------------------------------+
|                LLM-AUGMENTED EVOLUTIONARY LOOP                        |
|                                                                       |
|  1. Seed Initialization -> Naive Metaheuristic (Python Code)          |
|          |                                                            |
|          v                                                            |
|  2. Sandboxed Evaluator -> Tests Code on ITC / PATAT Benchmarks       |
|          |                 Computes Fitness Curve & Constraint Score  |
|          v                                                            |
|  3. Feedback Construction -> Bundles Code + Score + Error Tracebacks  |
|          |                                                            |
|          v                                                            |
|  4. LLM Operator (GPT / LLaMEA / EVOLER)                              |
|     "Mutate/Refine the local search & crossover logic to escape       |
|      the local minimum observed at generation 40."                    |
|          |                                                            |
|          +---> Generates Refined Hybrid Algorithm (Next Generation) --+
+-----------------------------------------------------------------------+
Step-by-Step Mechanics of the Research ArchitecturePopulation of Algorithms: Instead of evolving a population of schedules, the framework initializes a population of heuristic algorithms written in code.   LLM as the Variation Operator (Mutation & Crossover): Through structured meta-prompting, the LLM reads parent algorithms and their historical performance metrics. It performs algorithmic crossover (blending the global selection mechanism of Algorithm A with the local neighborhood repair of Algorithm B) and algorithmic mutation (rewriting a Simulated Annealing cooling schedule or inventing a domain-specific UCTP swap operator).   Automated Benchmarking & Grounding: Each newly generated algorithm is compiled in a sandboxed environment and executed against standardized scheduling datasets, specifically the ITC (International Timetabling Competition) and PATAT benchmark archives.   Iterative Self-Refinement: The evaluator extracts the resulting fitness score, execution runtime, and convergence stagnation metrics, feeding them back into the LLM context window. Over successive generations, the LLM autonomously discovers high-performing hybrid architectures (e.g., adaptive GA-ILS or GA-SA variants) tailored to the exact mathematical topology of the dataset.   Engineering Safeguards & Limitations Analyzed: The research accounted for critical failure modes in automated algorithm generation, including LLM syntax hallucinations, infinite loops in generated local-search operators, and computational evaluation overhead, mitigated via strict AST (Abstract Syntax Tree) code validation, execution timeouts, and automated traceback recovery prompts.