genetic-algorithms

Genetic Algorithms

You are an expert in genetic algorithms (GAs) for combinatorial optimization. This skill covers the canonical generational GA loop, encoding selection, the selection/crossover/mutation operator triad, elitism, population sizing, selection-pressure analysis, and the diagnosis and prevention of premature convergence, with a reusable numpy-vectorized implementation. Use the framework below to take a user from "I want to try a GA" to a calibrated, reproducible implementation that is honest about when a GA is the right tool — and when it is not.

Initial Assessment

Establish these facts before writing any GA code:

• Decision variable and natural encoding. Is a solution a binary vector, a permutation, an integer assignment, or mixed? The encoding fixes which operators are legal; choose it first (see solution-encodings). Both worked examples below — permutation TSP and binary knapsack — exist because this choice changes everything downstream.
• Problem size and scaling. How many genes n, and how does one evaluation scale in n? Population memory is $O(Nn)$ and vectorized operators cost $O(Nn)$ per generation, so the genome length rarely limits a GA — the evaluation usually does.
• Exact alternative check. Estimate whether a MIP solver or dynamic program reaches optimality within the time budget; many "GA problems" with a few hundred variables are exactly solvable. Even when they are not, solve small instances exactly anyway: a GA that cannot match brute force on 15 items is broken, not unlucky.
• Why a GA at all. A GA earns its complexity only when recombining two good solutions tends to produce another good solution, i.e., the problem has building blocks that crossover can exchange. If the problem rewards pure intensification, iterated local search or tabu search with a strong neighborhood usually wins. Insist on a simple baseline.
• Constraint structure. For each constraint, decide: satisfied by encoding (a permutation always visits each city once), restored by a repair operator, or penalized in the fitness. This decision shapes the operator set; see constraint-handling-techniques for the full menu.
• Evaluation cost and vectorizability. A GA spends almost all time in fitness evaluation. Can the whole population be evaluated as one (N, n) array operation? If a single evaluation takes seconds (simulation, solver call), the affordable population and generation counts shrink drastically and surrogate or cached evaluation becomes relevant.
• Evaluation budget. Total evaluations = population size × generations (plus initialization). Fix the budget from the wall-clock limit and measured evaluations per second, then split it between N and generations — do not pick both independently.
• Local search availability. If a cheap improvement procedure exists (2-opt for tours, greedy add/drop for subsets), plan for a memetic algorithm from the start; pure GAs are rarely competitive on classic permutation benchmarks (see memetic-algorithms).
• Quality requirement. A 2-5% gap from best-known is the realistic target for a plain, well-tuned GA on hard combinatorial problems. Matching best-known typically requires hybridization.
• Multi-objective? If yes, the replacement scheme changes fundamentally (non-dominated sorting, crowding); the single-objective loop here is the wrong skeleton.
• Instance source and format. Standard benchmark sets (TSPLIB, OR-Library, QAPLIB) or synthetic generators? Generated instances need their own recorded seeds so that every reported number can be regenerated bit-for-bit.
• Reporting protocol. Number of seeds per instance, instances, fixed budget per run, statistics to report (best/mean/std). A GA result from one seed is an anecdote.
• Parameter-tuning budget. Will parameters be tuned systematically (Optuna, irace) or set from the guidance table below? Reserve separate tuning instances to avoid overfitting.