Genetic Algorithms: Evolution as Optimization

Some optimization problems don’t have gradients. Some have landscapes so rugged that gradient descent would get stuck immediately. Some have search spaces so vast that exhaustive search is impossible. For these problems, genetic algorithms offer a different approach: let evolution do the work.

ParGA implements genetic algorithms in Rust. Before diving into the implementation details, let’s understand what we’re actually computing.

The Core Idea

Genetic algorithms borrow from biology. You have a population of candidate solutions, each encoded as a “genome.” Better solutions are more likely to reproduce. Offspring inherit traits from their parents, with occasional random mutations. Over generations, the population evolves toward better solutions.

The key components:

1. Representation: How you encode solutions as genomes
2. Fitness function: How you measure solution quality
3. Selection: How you choose parents for reproduction
4. Crossover: How you combine parent genomes to create offspring
5. Mutation: How you introduce random variation

That’s it. The algorithm is simple, and it can still solve problems that defeat other methods.

Representation

The most common genome types:

Real-valued genomes: A vector of floating-point numbers. Good for continuous optimization problems like function minimization. Each gene represents a parameter to optimize.

# Genome: [x1, x2, x3, x4, x5]
# Each gene is a float within some bounds
genome = [0.5, -1.2, 3.4, 0.0, -0.8]

Binary genomes: A string of bits. Good for combinatorial problems or when you need discrete choices.

# Genome: [1, 0, 1, 1, 0, 0, 1, 0]
# Can represent feature selection, yes/no decisions
genome = [1, 0, 1, 1, 0, 0, 1, 0]

Permutation genomes: An ordering of elements. Good for sequencing problems like the traveling salesman.

# Genome: [3, 1, 4, 2, 5]
# Represents an ordering: visit city 3, then 1, then 4, etc.
genome = [3, 1, 4, 2, 5]

ParGA supports all three, but real-valued genomes are most common for scientific optimization.

Fitness Functions

The fitness function is where domain knowledge enters. It takes a genome and returns a number: how good is this solution?

# Minimize the sphere function
def fitness(genes):
    return -sum(x**2 for x in genes)  # Higher is better, so negate

# Or maximize something
def fitness(genes):
    return calculate_profit(genes)

The fitness function is the only part of a genetic algorithm that “knows” anything about the problem. Everything else is generic.

Crucially, fitness functions don’t need to be differentiable. They don’t even need to be continuous. They can call external simulators, query databases, or involve human judgment. This flexibility is why genetic algorithms are useful for problems where gradient-based methods fail.

Selection

Once you’ve evaluated fitness for the whole population, you need to choose which individuals reproduce. Common methods:

Tournament selection: Randomly pick k individuals, select the best. Repeat. The parameter k controls selection pressure. With k=2, you’re comparing pairs. With k=10, you’re selecting from the top 10% of random samples.

Roulette wheel: Probability of selection is proportional to fitness. Fitter individuals get bigger slices of the wheel. Simple but can be dominated by a few very fit individuals.

Rank-based: Sort by fitness, then assign selection probability based on rank rather than absolute fitness. More stable than roulette when fitness values have large variance.

Truncation: Just take the top N%. Simple and aggressive. Used when you want fast convergence but risk premature convergence.

ParGA defaults to tournament selection with k=3, which balances selection pressure with diversity preservation.

Crossover

Selected parents create offspring by combining their genomes. For real-valued genomes:

Single-point crossover: Pick a random point, take genes from parent A before it and parent B after.

Parent A: [1.0, 2.0, | 3.0, 4.0]
Parent B: [5.0, 6.0, | 7.0, 8.0]
Child:    [1.0, 2.0, | 7.0, 8.0]

Two-point crossover: Pick two points, swap the middle segment.

Uniform crossover: For each gene, randomly pick from parent A or B.

Blend crossover (BLX-α): Create offspring in the range between parents, extended by α on each side. This explores beyond the current population’s boundaries.

Simulated Binary Crossover (SBX): Mimics single-point crossover behavior but for real-valued genomes. Used in NSGA-II and other modern algorithms.

Mutation

After crossover, offspring undergo mutation with some probability. For real-valued genomes:

Gaussian mutation: Add random noise from a normal distribution. The standard deviation controls step size.

Uniform mutation: Replace a gene with a random value within bounds.

Polynomial mutation: Non-uniform mutation that concentrates small changes, occasionally making larger jumps.

Boundary mutation: Mutate a gene to exactly its lower or upper bound. Useful for problems where optimal solutions lie on boundaries.

Mutation rate is typically low (1-5% per gene). Too much mutation destroys good solutions. Too little causes premature convergence.

Putting It Together

A typical genetic algorithm:

import numpy as np
from parga import GA

def fitness(genes):
    return -float(np.sum(genes**2))   # GA maximizes, so negate to minimize

ga = GA(
    fitness,
    genome_length=10,
    population_size=100,
    generations=100,
    mutation_rate=0.01,
    crossover_rate=0.8,
)
result = ga.run()
print(result.best_fitness)

GA maximizes what you give it. minimize() and maximize() are thin wrappers that handle the sign for you, with a wrinkle covered further down.

Each generation:

1. Evaluate fitness for all individuals
2. Select parents based on fitness
3. Create offspring via crossover
4. Mutate offspring
5. Replace old population with new

Repeat until convergence or budget exhaustion.

Which landscape actually needs a GA

The usual advice is that GAs are for rugged landscapes and gradient methods are for smooth ones. That is testable, so I tested it. Four standard benchmark functions in ten dimensions, every method given the same budget of 10,000 function evaluations, 20 random seeds, median best value found. The global optimum is 0.0 in all four cases.

Two of those rows are exactly the advice. On the sphere, a gradient method is better by thirteen orders of magnitude, and it is not close: the GA is still wandering around the fourth decimal place while L-BFGS-B has hit machine precision. On Rastrigin, whose surface is a quadratic bowl covered in cosine ripples, the GA beats fifty restarts of a gradient method by a factor of fifteen. Ackley is the same story.

Griewank is the row that ruins the rule of thumb.

Griewank is the textbook multimodal function. It has an enormous number of local minima, it appears in every benchmark suite as the hard case, and a local optimizer beats the GA on it by a factor of thirty. That is the opposite of what “many local optima means use a GA” predicts.

The reason is that Griewank’s local minima come from a product of cosines whose amplitude does not grow with dimension, while the global structure comes from a quadratic term that does. In ten dimensions the ripples are already shallow relative to the bowl, so a gradient method rolls straight through them. Griewank gets easier as you add dimensions, which is a genuinely strange property for a function whose reputation is difficulty.

So the criterion is not “how many local optima are there”. It is whether local structure points at the global optimum. Rastrigin’s ripples are deep enough to trap you and tell you nothing about where to go next. Griewank’s are speed bumps on a slope that leads home. Counting optima does not distinguish those two cases, and it is the distinction that decides which tool to reach for.

The thing to actually do

Look again at what the GA gets on Rastrigin: 1.52, where the optimum is 0. It found the right basin and then failed to get to the bottom of it. That is the characteristic GA failure, and it is the mirror of the gradient method’s characteristic failure, which is getting to the bottom of the wrong basin very precisely.

So do both. ParGA has local_search_iters for exactly this, and you can also just hand the GA’s answer to a local optimizer afterwards:

Every row improves, and two of them spectacularly. Ackley goes from 1.57 to 2e-08, eight orders of magnitude, because the GA had already found the right funnel and all that remained was to fall down it. The sphere row now matches a pure gradient method exactly, so the hybrid costs nothing even on the problem where the GA was useless alone.

The hybrid also beats the 50-start gradient method on Rastrigin by a factor of 46, and on Ackley by nine orders of magnitude. Population search for the basin, derivative information for the last few decimal places. Neither half is doing the other’s job.

Sign conventions

GA maximizes whatever you hand it. minimize() and maximize() wrap it for the other direction, and minimize() works by negating your objective and maximizing that, which is also the scale its best_fitness is reported on:

result = minimize(sphere, genome_length=10, bounds=(-5, 5))
-result.best_fitness     # 0.0064, the minimum it found

Worth reading once, because a sum of squares reported as a negative number is otherwise a confusing thing to see.

Beyond Simple GAs

ParGA implements additional techniques that improve on the basic algorithm:

Elitism: Always keep the best individual(s) from the previous generation. Prevents losing good solutions to unlucky mutations.

Island models: Multiple populations evolving in parallel with occasional migration. Maintains diversity and avoids premature convergence. This is the focus of the next post.

Adaptive parameters: Mutation rate and crossover rate can change during evolution, starting aggressive and becoming conservative as the population converges.

The basic GA is simple. The variations are where the art lies.

Next: how island models and migration topologies turn a single population into a parallel exploration machine.