Genetic Algorithm Framework

A reusable genetic algorithm (GA) framework for combinatorial and continuous optimization, applied to seven classic operations-research problems.

The core idea is a clean separation of concerns. A single, problem-agnostic engine drives the evolutionary loop (selection, recombination, survival). The parts that depend on the problem — how a solution is represented and how it is recombined and mutated — live behind a small Encoding interface. Adding a new problem means writing a cost function and choosing an encoding; the engine is never touched.

Design

GeneticAlgorithm(cost_function, encoding, config) ── run() ──▶ best solution
        │                           │
        │                           └── Encoding: initialize / crossover / mutate
        └── elitist loop: selection ▶ crossover ▶ mutation ▶ survival

• Engine (ga/engine.py) — elitist GA with roulette-wheel and tournament parent selection. Reproducible through an injected NumPy random generator.

• Encodings (ga/encodings/) — pluggable solution representations:

  Encoding	Genome	Crossover	Mutation
  BinaryEncoding	bit string	single / double point, uniform	bit flip
  RealEncoding	bounded floats	blended (BLX)	clipped Gaussian
  PermutationEncoding	permutation	order crossover with repair	swap / reversion / insertion
  MixedEncoding	dict of parts	per-part crossover	per-part mutation

• Config (ga/config.py) — one validated parameter set for every problem.

Problems

Problem	Encoding	Summary
Sphere	real	Minimize a convex test function; validates the real operators.
Min-one	binary	Minimize the number of ones; validates the binary operators.
Knapsack (0/1)	binary	Maximize packed value under a weight capacity.
Quadratic assignment	permutation	Assign facilities to locations to minimize flow-weighted distance.
Transportation	real	Ship customer demand from suppliers at least cost under capacity.
Transportation with fixed cost	mixed (real + binary)	Choose which suppliers to open and how much to ship.
Hub location-allocation	binary	Choose which hubs to open and route each customer to the nearest one.

Project layout

ga/                     reusable framework (engine, config, selection, plotting)
ga/encodings/           binary, real, permutation and mixed encodings
problems/               one package per problem (data, cost function, runner)
data/                   sample instances, ready to run
results/                generated convergence plots (created at run time)

Installation

pip install -e .

This installs NumPy and matplotlib and makes both ga and problems importable from anywhere.

Usage

Run any problem as a module:

python -m problems.sphere.main
python -m problems.knapsack.main
python -m problems.hub_location.main

Or use the installed console scripts:

ga-sphere
ga-quadratic-assignment
ga-transportation-fixed-cost

Each run prints the best cost and runtime and saves a convergence plot under results/. To recreate a problem's data instance with a fixed seed:

python -m problems.knapsack.data --seed 0

Using the framework directly

import numpy as np
from ga import GAConfig, GeneticAlgorithm, RealEncoding
from problems.sphere.cost_function import sphere

encoding = RealEncoding(shape=(1, 20), low=-10, high=10)
config = GAConfig(max_iteration=500, population_size=20)
result = GeneticAlgorithm(sphere, encoding, config,
                          rng=np.random.default_rng(0)).run()
print(result.best.cost)

License

Released under the MIT License. See LICENSE.