GeneticAlgorithms 1.0.0

Genetic Algorithms

GeneticAlgorithms is a small F# library for experimenting with genetic algorithms. It provides a compact, generic execution pipeline for evolving chromosomes and includes example projects that demonstrate both binary and character-based optimization problems.

The repository is structured as an educational, easy-to-read implementation rather than a feature-complete optimization framework. The core abstractions are intentionally small so you can understand how the algorithm works and adapt it for your own problems.

Inspiration

This library is heavily influenced by the ideas and teaching approach in Genetic Algorithms in Elixir: Solve Problems Using Evolution by Sean Moriarity. If you want a practical introduction to evolutionary algorithms and how to structure them in code, it is a strong companion resource for this repository.

Installation

The library is published on nuget.org:

dotnet add package GeneticAlgorithms

Features

• Generic chromosome representation with support for any gene type
• Problem definition through pluggable genotype, fitness, and termination functions
• Population evaluation with age tracking and fitness sorting
• Configurable parent selection: elite, random, tournament, tournament without duplicates, roulette-wheel, Boltzmann, stochastic universal sampling, or rank-based
• Configurable crossover: single-point by default, or order-one crossover for permutation genotypes
• Configurable mutation: rate and strategy, gene-shuffling by default
• A Distance module with reusable string-similarity functions (currently Jaro similarity) for building fitness functions that compare a candidate string against a target
• Included examples and automated tests

Project Structure

src/GeneticAlgorithms                Core library
examples/                            Example problems, each with F# and/or C# variants - see examples/README.md
tests/GeneticAlgorithms.Tests         Automated tests with Expecto
tests/GeneticAlgorithms.CSharpSmoke   Minimal C# consumer validating the interop layer
tests/GeneticAlgorithms.NuGetSmoke    Verifies a published NuGet release installs and runs correctly

Core Concepts

The library revolves around three types:

Chromosome<'T>

Represents a candidate solution. Size is derived from Genes rather than stored separately.

type Chromosome<'T> =
    { Genes: 'T array
      Fitness: float
      Age: int }

    member this.Size = this.Genes.Length

Age counts the number of generations a chromosome has existed, incremented once per generation by Genetic.evaluate. It resets to 0 when a chromosome is "born" - by Crossover (which always produces a genuinely new individual from two parents) or by a freshly generated genotype (the initial population, or padding a shortfall back to PopulationSize). Mutation does not reset it - a mutated chromosome is still the same individual, one generation older, with modified genes, the same way a Reinsertion-carried-over survivor keeps aging without being "reborn". Because evaluate always runs before Options.Probe/Problem.Terminate see a generation, the minimum Age ever observable is 1, not 0, for both the very first generation and any chromosome born since.

Problem<'Gene>

Defines how a specific optimization problem behaves.

type Problem<'Gene> =
    { Genotype: System.Random -> Chromosome<'Gene>
      FitnessFunction: Chromosome<'Gene> -> float
      Terminate: seq<Chromosome<'Gene>> -> int -> float -> bool }

Options<'Gene>

Controls runtime configuration.

type Options<'Gene> =
    { PopulationSize: int
      SelectionRate: float
      SelectionFn: System.Random -> Chromosome<'Gene> array -> int -> Chromosome<'Gene> array
      CrossoverFn: System.Random -> Chromosome<'Gene> -> Chromosome<'Gene> -> Chromosome<'Gene> * Chromosome<'Gene>
      MutationRate: float
      MutationFn: System.Random -> Chromosome<'Gene> -> Chromosome<'Gene>
      ReinsertionFn:
          System.Random -> Chromosome<'Gene> array -> Chromosome<'Gene> array -> Chromosome<'Gene> array -> Chromosome<'Gene> array
      Probe: GenerationInfo<'Gene> -> unit
      Random: System.Random }

SelectionFn picks from the Selection module (Selection.elite, Selection.random, Selection.tournament, Selection.tournamentNoDuplicates, Selection.roulette, Selection.boltzmann, Selection.stochasticUniversalSampling, Selection.rank) or a custom function of the same shape.

CrossoverFn picks from the Crossover module (Crossover.singlePoint for any gene array, or Crossover.orderOneCrossover for permutation genotypes such as NQueens) or a custom function of the same shape.

MutationFn picks from the Mutation module (Mutation.scramble/Mutation.scrambleSlice for any gene array, Mutation.flip/Mutation.flipEachGene for binary genotypes, or Mutation.gaussian for real-valued genotypes) or a custom function of the same shape; Genetic.mutation decides, via MutationRate, how many chromosomes to sample from the population as mutants each generation.

ReinsertionFn picks from the Reinsertion module (Reinsertion.`pure` to replace the population outright with this generation's offspring, or Reinsertion.elitist/Reinsertion.uniform to carry over a fraction of the previous generation's fittest or randomly chosen survivors alongside it) or a custom function of the same shape - it decides how parents, offspring, and leftover chromosomes combine into the next population.

Probe is called with a GenerationInfo<'Gene> snapshot after every evaluation. It's a generic injection point - the library only decides when it fires and what it carries; what a probe does with that snapshot (print it, collect it in memory, write it to a file or database, push it to a monitoring service) is entirely up to whoever plugs one in. The default is Probes.noop - probing is opt-in, not imposed. Probes.printProgress is a ready-made probe that prints the best fitness; Probes.combine runs several probes together, and Probes.everyNth throttles one to fire only every n generations.

Random is the single source of randomness for an entire run - every SelectionFn/CrossoverFn/MutationFn/ReinsertionFn, and Problem.Genotype, are called with this same instance rather than reaching for System.Random.Shared, so seeding it ({ Options.create 100 with Random = System.Random(42) }) makes an otherwise-identical run fully reproducible.

GenerationInfo<'Gene>

A snapshot of one generation's state, passed to Options.Probe.

type GenerationInfo<'Gene> =
    { Generation: int
      Population: Chromosome<'Gene> array
      Best: Chromosome<'Gene>
      Temperature: float }

Population is this generation's full population, already evaluated and sorted by descending fitness. Best is Population.[0]. Temperature is the same value passed to Problem.Terminate for this generation.

Algorithm Flow

Genetic.run executes the following loop:

1. Initialize a population using the supplied genotype function.
2. Evaluate all chromosomes with the fitness function and sort by descending fitness.
3. Report progress via Probe.
4. Stop if the termination function returns true for the current population, generation, and temperature.
5. Otherwise, select parents using SelectionFn and SelectionRate, keeping any unselected chromosomes as leftover.
6. Produce children from the selected parents using CrossoverFn.
7. Sample a subset of the population, sized by MutationRate, and apply MutationFn to each to produce mutants.
8. Combine the children and mutants into this generation's offspring, and let ReinsertionFn decide how parents, offspring, and leftover chromosomes combine into the next population.
9. Repeat from step 2 with the resulting population.

The termination callback receives the evaluated population, the current generation number, and a temperature value computed from recent fitness progress, so problems can stop either on solution quality, a generation cap, temperature behavior, or a combination of those signals.

Getting Started

Requirements

• .NET 10 SDK

Build the solution

From the repository root:

dotnet build genetic-algorithms.sln

Run the tests

dotnet run --project tests/GeneticAlgorithms.Tests/GeneticAlgorithms.Tests.fsproj

Basic Usage

Define a genotype function, a fitness function, and a termination condition, then call Genetic.run.

open GeneticAlgorithms

let genotype (rng: System.Random) =
    let genes = Array.init 10 (fun _ -> rng.Next(0, 2))

    { Genes = genes
      Fitness = 0.0
      Age = 0 }

let fitness_function (chromosome: Chromosome<int>) =
    chromosome.Genes |> Array.sum |> float

let terminate (population: seq<Chromosome<int>>) (_generation: int) (_temperature: float) =
    population |> Seq.exists (fun chromosome -> chromosome.Fitness >= 10.0)

let problem: Problem<int> =
    { Genotype = genotype
      FitnessFunction = fitness_function
      Terminate = terminate }

// Options.create fills in every field except PopulationSize with sensible defaults -
// SelectionRate 0.8 + MutationRate 0.05 + Reinsertion.elitist's survivalRate 0.15 sum to
// 1.0, which keeps population size stable across generations (`` Reinsertion.`pure` ``, the
// simplest strategy, would discard SelectionRate's 20% leftover with nothing to replace it
// beyond this generation's mutants, shrinking the population by ~15% every generation).
// Override only what you need via ordinary record-update syntax.
let options =
    { Options.create 100 with
        Probe = Probes.printProgress }

let solution = Genetic.run problem options

Building the record from scratch, field by field, works just as well if you'd rather not rely on Options.create's defaults:

let options =
    { PopulationSize = 100
      SelectionRate = 0.8
      SelectionFn = Selection.elite
      CrossoverFn = Crossover.singlePoint
      MutationRate = 0.05
      MutationFn = Mutation.scramble
      ReinsertionFn = Reinsertion.elitist 0.15
      Probe = Probes.printProgress
      Random = System.Random() }

Every strategy function draws its randomness from Options.Random instead of System.Random.Shared, so seeding it makes an otherwise-identical run fully reproducible:

let options =
    { Options.create 100 with
        Random = System.Random(42) }

C# Interop

The core API is implemented in idiomatic F#, but the library also exposes a small C#-friendly facade through GeneticAlgorithms.GeneticAlgorithm. This avoids forcing C# examples to construct F# records with curried function fields directly.

using GeneticAlgorithms;

var solution = GeneticAlgorithm.Run(
  genotype: rng => GeneticAlgorithm.CreateChromosome(new[] { rng.Next(0, 2) }),
  fitnessFunction: chromosome => chromosome.Genes[0],
  terminate: (population, generation, temperature) =>
    population.Any(chromosome => chromosome.Fitness >= 1.0) || generation >= 10,
  populationSize: 8);

Every Func<...> strategy parameter (selectionFn, crossoverFn, mutationFn, reinsertionFn, and genotype) is passed the run's System.Random as its first argument. For a reproducible run from C#, use the CreateOptions overload that takes an explicit random: Random parameter instead of the populationSize-only convenience overloads.

The populationSize-only overloads (this one and CreateOptions(populationSize)) default to SelectionRate = 0.8, MutationRate = 0.05, and Reinsertion.elitist 0.15 - the same population-stable combination used throughout this library's own examples, so population size stays constant across generations without any further configuration.

To use a non-default selection, crossover, or mutation strategy, build Options<'Gene> with GeneticAlgorithm.CreateOptions(populationSize, selectionFn, crossoverFn, mutationFn) instead - the library's own Selection/Crossover/Mutation module functions can be passed directly as method groups, since they compile to ordinary multi-argument static methods:

var options = GeneticAlgorithm.CreateOptions<int>(
  populationSize: 100,
  selectionFn: Selection.elite,
  crossoverFn: Crossover.orderOneCrossover,
  mutationFn: Mutation.scramble);

var solution = GeneticAlgorithm.Run(genotype, fitnessFunction, terminate, options);

The older Interop type remains available as a compatibility wrapper, but new C# examples should prefer GeneticAlgorithm.

The smoke project in tests/GeneticAlgorithms.CSharpSmoke exists specifically to validate that this API stays straightforward to consume from C#.

Examples

See examples/README.md for the full index of example projects, what each one demonstrates, and their available language variants.

Test Coverage

The test project verifies the main building blocks of the algorithm:

• Genetic.evaluate applies fitness, increments age, and sorts by descending fitness
• Genetic.crossover preserves chromosome size and recombines parent genes using the supplied CrossoverFn
• Genetic.mutation preserves population size and gene membership, applying MutationFn per chromosome at MutationRate
• Genetic.initialize creates the requested number of chromosomes
• Genetic.run returns the fittest chromosome when termination is reached
• Genetic.run forwards generation and temperature values to the termination callback
• Selection.elite, Selection.random, Selection.tournament, Selection.tournamentNoDuplicates, Selection.roulette, Selection.boltzmann, Selection.stochasticUniversalSampling, and Selection.rank each return the requested number of chromosomes under their respective selection rules
• Selection.select splits a population into parent pairs, the chromosomes consumed as parents, and leftover chromosomes according to SelectionRate, rounding odd counts up to stay even - parents are counted per physically consumed population slot (never more than actually exist for a given value), so they add back up to the population size alongside leftover whether SelectionFn redraws the same individual more than once (as tournament, roulette, boltzmann, and stochasticUniversalSampling can) or elite selects several distinct slots that happen to share a value (common once a population has converged)
• Crossover.orderOneCrossover always produces children that are valid permutations of the parents' genes, with no duplicate or missing values
• Mutation.scramble and Mutation.scrambleSlice preserve the exact multiset of gene values (and, for scrambleSlice, the overall chromosome length), only reordering them
• Mutation.flip flips every gene, and Mutation.flipEachGene flips each gene independently at its own probability
• Mutation.gaussian preserves chromosome length and its resampled genes have approximately the same mean as the original genes
• Distance.jaroSimilarity matches known reference values (for example, the standard MARTHA/MARHTA example), and is symmetric
• Options.create fills every field but PopulationSize with the same defaults as GeneticAlgorithm.CreateOptions, and every field can still be overridden via ordinary record-update syntax
• Genetic.run keeps every generation's population at exactly PopulationSize, even though Selection.select, Genetic.mutation, and Reinsertion.elitist/Reinsertion.uniform each round their own fractional share of it independently and can drift by a chromosome or two on their own (for example, PopulationSize = 8 with the library's own default rates produces 6 crossover children + 0 mutants + 1 survivor = 7)
• Genetic.run rejects a null Options.Random, and every public rate-shaped parameter (Options.SelectionRate/MutationRate, Reinsertion.elitist/Reinsertion.uniform's survivalRate, Mutation.flipEachGene/Mutation.randomReset's rate, and Crossover.uniform's rate) rejects a value outside [0, 1]
• Every Crossover strategy resets both children's Age and Fitness to 0/0.0, regardless of either parent's values - and, end to end, Genetic.run keeps every chromosome at Age = 1 (the first generation a freshly born individual is observed) rather than letting it accumulate with the generation count
• An empty chromosome (Genes = [||]) is a no-op for every Crossover and Mutation strategy - producing another empty chromosome (or, for mutation, the same chromosome unchanged) rather than crashing or being rejected
• Every Crossover strategy that assumes equal-length parents validates that assumption explicitly and consistently, via one shared internal helper, rather than relying on an incidental failure from whatever array operation it happens to call first: singlePoint, multiPoint, uniform, and wholeArithmeticCrossover all raise the same clear error naming the actual problem. multiPoint's pointCount is validated the same way, against the number of interior cut positions the parents' length actually has

Design Notes

This implementation is intentionally minimal. A few design choices to be aware of:

• Mutation.scramble is the default strategy, scrambling the genes within a chromosome rather than replacing individual genes with newly generated values; Mutation.scrambleSlice scrambles only a random window instead of the whole chromosome, Mutation.flip/Mutation.flipEachGene are binary-genotype alternatives, and Mutation.gaussian is a real-valued alternative that resamples every gene from a normal distribution fitted to the chromosome's own genes
• There is no configurable crossover rate; CrossoverFn always runs on every selected parent pair
• Every strategy function draws its randomness from the single System.Random instance in Options.Random, rather than System.Random.Shared, so seeding it ({ Options.create 100 with Random = System.Random(42) } in F#, or the random-taking CreateOptions overload in C#) makes an otherwise-identical run fully reproducible
• Selection.select identifies which population slots were used as parents by comparing Chromosome values, not by tracking population indices - correct (see Selection.partitionSelected's remarks for why), but it means every 'Gene needs a meaningful equality, and multiple physically distinct chromosomes that happen to be value-identical are indistinguishable by design. A future major version could have SelectionFn return indices instead of values, sidestepping both the equality constraint and the identity ambiguity entirely - a breaking change to Options.SelectionFn's shape, not attempted here
• PopulationSize is enforced by padding or truncating each generation's combined selection/crossover/mutation/reinsertion output back to the exact target size, rather than by making that combination round exactly on its own (which isn't possible in general - see the Test Coverage bullet above). A shortfall is padded with freshly generated genotypes, the same mechanism the first generation uses, rather than by duplicating existing survivors - a deliberate small diversity injection, not just a size fix
• Every public rate-shaped parameter - a probability, meant to be a value in [0, 1] - is validated the same way through one shared, internal helper, so the range check and its error message stay consistent everywhere instead of being re-implemented per call site: Options.SelectionRate and Options.MutationRate are checked centrally in Genetic.run (which also rejects a null Options.Random), while Reinsertion.elitist/Reinsertion.uniform's survivalRate, Mutation.flipEachGene/Mutation.randomReset's rate, and Crossover.uniform's rate each validate themselves the moment they're curried, since - unlike SelectionRate/MutationRate - there is no single call site that can see those values. Crossover.wholeArithmeticCrossover's alpha is deliberately excluded: it is a blend weight, not a probability, and values outside [0, 1] extrapolate rather than misbehave
• An empty chromosome is treated as a valid, if degenerate, value everywhere rather than being rejected as invalid input - matching Chromosome.Size's own contract, which is explicitly 0 for one. This was a deliberate policy choice: most Crossover/Mutation strategies already no-op correctly for empty input on their own (an operation over an empty array is usually itself a no-op), so treating emptiness as valid needed far less code than the alternative of adding new rejection checks to every strategy that already worked - only Crossover.singlePoint/messySinglePoint/orderOneCrossover (each of which drew a random cut point via a range derived from Genes.Length, invalid when it's 0) and Mutation.gaussian (which fits a mean/variance to the genes, undefined for zero genes) needed an explicit guard to fall in line with the rest

Those constraints keep the code simple, but they also make the project a good starting point for extending the algorithm with richer mutation operators or alternative crossover strategies.

Repository Goals

This project is a good fit if you want to:

• Learn how a genetic algorithm can be implemented in F#
• Experiment with generic chromosome representations
• Build on a small codebase instead of adopting a large framework
• Add new example problems and compare evolutionary behavior

License

This repository is licensed under the terms of the LICENSE file in the project root.