Voronoi Intelligence

Voronoi-based seed management for evolutionary algorithms, multi-agent systems, and population diversity control.

A Voronoi diagram partitions space into cells, each governed by one seed (black point). This library uses seeds as the core primitive for population structuring, diversity maintenance, and territory-aware evolutionary operators.

---

What This Library Does

A Voronoi diagram partitions a space into regions where every point is closer to its region's seed than to any other seed. This geometric structure maps naturally onto several problems in evolutionary computation:

Problem	Approach
Maintaining population diversity	One individual per cell guarantees spacing without explicit niching parameters
Adaptive mutation step sizes	Cell area controls mutation magnitude; sparse regions get larger exploratory steps
Multi-agent territory assignment	Each agent owns a cell; re-tessellate when agents move or die
Novelty search	Sparsity = inverse cell area, combined with behavioural distance to archive
Crossover locality	Restrict crossover to neighbouring cells to preserve spatial structure

Modules

Module	Description
seeds	Seed sampling strategies (uniform, Poisson-disk, Sobol, Gaussian, spherical)
population	Voronoi-structured population with cell area/density/neighbor queries
evolution	Territory-aware GA operators: selection, mutation, crossover, novelty search
agents	Multi-agent coverage control with dynamic Voronoi territories and centroidal tessellation
visualization	2D plots, heatmaps, population animation
utils	Normalisation, point-in-polygon, random sampling within cells

Installation

git clone git@github.com:NullLabTests/voronoi_intelligence.git
cd voronoi_intelligence
pip install -e .
pip install -e ".[dev]"    # with test dependencies
pip install -e ".[dev,viz,ml]"  # full install

Quick Start

import numpy as np
from voronoi_agi import (
    UniformSeedSampler,
    VoronoiPopulation,
    VoronoiGA,
    plot_voronoi_2d,
)

sampler = UniformSeedSampler(n_seeds=50, dim=2)
seeds = sampler.sample()

def fitness(x):
    return -np.sum((x - 0.5) ** 2)

pop = VoronoiPopulation.from_sampler(
    sampler,
    individual_factory=lambda s: s,
    fitness_fn=fitness,
)

ga = VoronoiGA(population=pop, mutation_rate=0.15)
history = ga.run(n_generations=50)
plot_voronoi_2d(seeds)

Examples

Example	File	What It Shows
Seed distribution strategies	examples/01_seed_distribution.py	Side-by-side comparison of sampling methods
Voronoi-enhanced GA	examples/02_voronoi_ga.py	Continuous optimisation (Rastrigin, Ackley) with territory-aware operators
Multi-agent coverage	examples/03_multiagent_coverage.py	Agents partitioning a 2D domain with density field
Prompt evolution	examples/04_prompt_evolution.py	Structuring LLM prompt populations with Voronoi seeds

python examples/02_voronoi_ga.py

Benchmarks

The library includes three GA implementations for comparison:

• StandardGA — canonical real-valued GA (SBX crossover, polynomial mutation)
• FitnessSharingGA — GA with Deb & Goldberg fitness sharing
• VoronoiGA — territory-aware GA with cell-size-adaptive mutation and neighbour-restricted crossover

Tests verify that VoronoiGA maintains higher population diversity and competitive convergence on standard benchmarks.

Related Work

• Deb & Goldberg (1989) — Fitness sharing in genetic algorithms
• Cortés et al. (2004) — Coverage control for multi-agent systems via Voronoi partitions
• Lehman & Stanley (2011) — Novelty search
• Lloyd (1982) — Least squares quantization (centroidal Voronoi tessellation)
• Okabe et al. (2000) — Spatial Tessellations (comprehensive reference)

License

MIT — see LICENSE.