🧬 Genetic Algorithm Framework

Evolutionary computation with functors, selection, crossover, and mutation

Overview

A full-featured genetic algorithm framework using OCaml's module system. Defines a PROBLEM signature and a Make functor that builds a complete GA solver for any conforming problem. Includes tournament/roulette/rank selection, multiple crossover and mutation operators, island model parallelism, fitness sharing, and adaptive parameter control.

Concepts Demonstrated

Module signatures & functors — abstract problem interface with generic solver
Selection strategies — tournament, roulette wheel, rank-based, elitist
Crossover operators — single-point, two-point, uniform
Mutation operators — per-gene, swap, scramble
Island model — parallel subpopulations with migration
Fitness sharing — niching for diversity maintenance
Adaptive control — self-adjusting mutation/crossover rates
Convergence detection — stagnation restart mechanism

Key Components

Component	Description
`PROBLEM` signature	Define gene type, fitness, init, crossover, mutate
`Make(P)` functor	Build a GA solver from any PROBLEM implementation
`evolve`	Run the GA for N generations with given config
`island_evolve`	Multi-island GA with periodic migration
`OneMax / TSP / Knapsack`	Three complete example problem implementations

Usage Pattern

(* 1. Define a problem module *)
module MyProblem : PROBLEM = struct
  type gene = ...
  let fitness individual = ...
  let random_individual () = ...
  let crossover a b = ...
  let mutate rate individual = ...
end

(* 2. Build a solver via the functor *)
module Solver = Make(MyProblem)

(* 3. Configure and run *)
let config = {
  pop_size = 100;
  generations = 500;
  mutation_rate = 0.01;
  crossover_rate = 0.8;
  selection = Tournament 3;
  elitism = 2;
}
let best = Solver.evolve config

Example Problems

Problem	Description	Gene Type
OneMax	Maximize 1-bits in a bitstring	`bool array`
TSP	Travelling salesman — minimize route distance	`int array` (permutation)
Knapsack	Maximize value under weight constraint	`bool array` (inclusion mask)