Build a Genetic Algorithm TSP Solver
Build a test-driven genetic algorithm that solves the Travelling Salesman Problem.
Introduction
30 Second Summary
Think about the last time you needed to plan a route through multiple stops. Even with just 10 places to visit, the number of possible routes explodes into the millions.
In this project, you will build a genetic algorithm that evolves increasingly better solutions to the Travelling Salesman Problem, entirely driven by a pre-written test suite that acts as your specification.
What You'll Build
A modular genetic algorithm framework for the Travelling Salesman Problem that evolves a population of tours using tournament selection, Order Crossover, swap mutation, and elitism to find near-optimal routes through a set of cities.
By the end of this project, you'll have:
- A modular Python package with five GA components: chromosome encoding, selection, crossover, mutation, and evolution.
- A comprehensive test suite with 40+ tests that serve as your implementation specification, following a test-driven development workflow.
- A working genetic algorithm that finds near-optimal routes within 10% of the theoretical optimum on benchmark instances.
- Secret Mission: Extend your GA into a memetic algorithm with 2-opt local search that outperforms the base solver.
Are there any prerequisites?
This project assumes strong Python proficiency, comfort with object-oriented programming, and basic familiarity with probability and statistics. You should also have prior experience with pytest for writing and running tests.
Set Up the Project Structure
In test-driven development, you write the tests before the implementation. That means your project needs a clear structure from the start so pytest can discover your tests and your package imports resolve cleanly.
In this step, you will scaffold the entire project directory, configure your build metadata, and set up shared test fixtures that every future test file depends on.
In this step, get ready to:
- Create the project directory structure and pyproject.toml configuration.
- Set up a virtual environment and install dependencies.
- Add shared test fixtures in tests/conftest.py.
Create the project directory structure
Your genetic algorithm project has two main packages: tsp_ga/ for the implementation modules, and tests/ for the test specifications.
- Move to your Desktop by running this command:
cd ~/Desktop- Create your project folder and the two package directories by running these commands:
mkdir tsp-ga
cd tsp-ga
mkdir tsp_ga tests- Create the empty __init__.py files and empty test files by running:
touch tsp_ga/__init__.py tests/__init__.py
touch tests/test_chromosome.py tests/test_selection.py tests/test_crossover.py tests/test_mutation.py tests/test_evolution.py- Create stub modules with placeholder content in each implementation file by running:
echo "pass" > tsp_ga/chromosome.py
echo "pass" > tsp_ga/selection.py
echo "pass" > tsp_ga/crossover.py
echo "pass" > tsp_ga/mutation.py
echo "pass" > tsp_ga/evolution.py- Confirm the files exist by running:
ls tsp_ga/ tests/You should see __init__.py, chromosome.py, selection.py, crossover.py, mutation.py, and evolution.py under tsp_ga/.
Under tests/ you should see __init__.py and the five test files.
Seeing 'No such file or directory'?
Make sure you ran cd tsp-ga after creating the folder. All subsequent commands assume you are inside the tsp-ga directory.
help me debug my directory structure
Now open the tsp-ga folder in your code editor so you can edit the project files.
- Create a pyproject.toml file in the root of your tsp-ga folder and paste the following configuration:
[project]
name = "tsp-ga"
version = "0.1.0"
requires-python = ">=3.11"
dependencies = [
"numpy>=2.4.6",
]
[project.optional-dependencies]
dev = [
"pytest>=9.1.1",
]
[tool.pytest.ini_options]
testpaths = ["tests"]What does this configuration do?
- requires-python = ">=3.11" ensures the project only installs on Python 3.11 or higher, which NumPy 2.4.6 requires.
- [project.optional-dependencies] groups dev tools like pytest separately so production installs stay lean.
- [tool.pytest.ini_options] tells pytest to look in the tests/ directory for test files.
- Save pyproject.toml.
✔️ Awesome, I've got everything!
Great. Make sure you have saved pyproject.toml in the root of your tsp-ga folder.
ⓧ I'd like to double check the full code
[project]
name = "tsp-ga"
version = "0.1.0"
requires-python = ">=3.11"
dependencies = [
"numpy>=2.4.6",
]
[project.optional-dependencies]
dev = [
"pytest>=9.1.1",
]
[tool.pytest.ini_options]
testpaths = ["tests"]Create a virtual environment and install dependencies
A virtual environment isolates your project's packages from your system Python. This prevents version conflicts between projects.
- Create a virtual environment by running this command:
python3 -m venv .venv- Activate the virtual environment:
macOS
source .venv/bin/activateWindows
.venv\Scripts\activateLinux
source .venv/bin/activateYou should see (.venv) appear at the beginning of your terminal prompt.
- Install the project in editable mode with dev dependencies by running:
pip install -e ".[dev]"What does this command do?
The -e flag installs your package in editable mode. Changes to your source code take effect immediately without reinstalling.
The .[dev] suffix includes the optional dev dependencies (pytest) alongside the core dependency (numpy).
- Verify that pytest can discover your test directory by running:
pytest --collect-onlyYou should see a session header with no errors and a message like no tests collected. This is expected because your test files are still empty.
Seeing 'No module named tsp_ga'?
Make sure you ran pip install -e ".[dev]" from inside the tsp-ga folder (where pyproject.toml lives). Also confirm your virtual environment is active by checking for (.venv) in your prompt.
help me fix my pytest setup
Add shared test fixtures
Pytest fixtures provide reusable test data that multiple test files can share. The conftest.py file is a special location where pytest automatically discovers fixtures available to all tests in the same directory.
- Open tests/conftest.py in your editor and paste the following fixtures:
import numpy as np
import pytest
@pytest.fixture
def square_coords():
"""4 cities forming a unit square. Optimal tour length = 4.0."""
return np.array([
[0.0, 0.0],
[0.0, 1.0],
[1.0, 1.0],
[1.0, 0.0],
])
@pytest.fixture
def square_dist_matrix(square_coords):
"""Pre-computed distance matrix for the square."""
from tsp_ga.chromosome import create_distance_matrix
return create_distance_matrix(square_coords)
@pytest.fixture
def circle_coords():
"""10 cities equally spaced on a unit circle.
Optimal tour visits them in angular order with length ~6.18."""
angles = np.linspace(0, 2 * np.pi, 10, endpoint=False)
return np.column_stack([np.cos(angles), np.sin(angles)])
@pytest.fixture
def rng():
"""Deterministic random number generator for reproducible tests."""
return np.random.default_rng(12345)What do these fixtures provide?
- square_coords gives 4 cities at the corners of a unit square. The optimal tour visits them in order with total length 4.0.
- square_dist_matrix pre-computes distances for the square cities so tests run faster.
- circle_coords places 10 cities on a unit circle. The optimal tour length is approximately 6.18.
- rng provides a seeded random number generator so tests produce identical results every run.
- Save tests/conftest.py.
- Run pytest --collect-only again to confirm there are still no errors.
You should still see no tests collected with 0 errors. The fixtures load silently until a test actually requests them.
Seeing a syntax error in conftest.py?
Check that the np.array calls use matching brackets. Each coordinate pair is inside its own inner list, and the outer array uses square brackets.
help me fix my conftest.py
✔️ Awesome, I've got everything!
Great. Double check you have saved tests/conftest.py and that pytest --collect-only runs cleanly.
ⓧ I'd like to double check the full code
import numpy as np
import pytest
@pytest.fixture
def square_coords():
"""4 cities forming a unit square. Optimal tour length = 4.0."""
return np.array([
[0.0, 0.0],
[0.0, 1.0],
[1.0, 1.0],
[1.0, 0.0],
])
@pytest.fixture
def square_dist_matrix(square_coords):
"""Pre-computed distance matrix for the square."""
from tsp_ga.chromosome import create_distance_matrix
return create_distance_matrix(square_coords)
@pytest.fixture
def circle_coords():
"""10 cities equally spaced on a unit circle.
Optimal tour visits them in angular order with length ~6.18."""
angles = np.linspace(0, 2 * np.pi, 10, endpoint=False)
return np.column_stack([np.cos(angles), np.sin(angles)])
@pytest.fixture
def rng():
"""Deterministic random number generator for reproducible tests."""
return np.random.default_rng(12345)Your project skeleton is ready. Next up, you will drop in the full chromosome test specification and implement your first GA components against it.
Implement Chromosome Representation and Fitness
In test-driven development, you write the tests first and let them guide your implementation. The tests ARE your specification. They define exactly what each function must accept, return, and guarantee.
In this step, you will add a complete test file that specifies four chromosome functions, then implement each function until all 17 tests pass. This is the foundation layer of your genetic algorithm. Every other component depends on these four functions.
In this step, get ready to:
- Add the test specification for chromosome representation and fitness.
- Implement the four core chromosome functions against the test spec.
- Verify all 17 tests pass.
Add the test specification
In a test-first workflow, you write the tests before any implementation code exists. These tests define the exact function signatures, return types, and behavioral contracts your code must satisfy.
- Open tests/test_chromosome.py in your editor and replace its contents with the following test specification:
"""SPECIFICATION: Chromosome Representation and Fitness
=====================================================
A chromosome in our GA-TSP represents a tour as a permutation of city indices.
Requirements:
1. create_distance_matrix(coords) must return a symmetric (n, n) matrix where
entry [i, j] is the Euclidean distance between city i and city j. The diagonal
must be all zeros.
2. is_valid_tour(tour, n_cities) must return True if and only if the tour is
a permutation of [0, 1, ..., n_cities - 1]. It must reject duplicates,
missing cities, wrong lengths, and out-of-range values.
3. create_random_tour(n_cities, rng) must return a valid tour of the specified
size. Two calls with different rng states should (almost certainly) produce
different tours.
4. tour_length(tour, dist_matrix) must compute the total round-trip distance:
the sum of edges from tour[0]->tour[1]->...->tour[-1]->tour[0].
"""
import numpy as np
import pytest
from tsp_ga.chromosome import (
create_distance_matrix,
create_random_tour,
is_valid_tour,
tour_length,
)
class TestCreateDistanceMatrix:
"""Tests for the distance matrix computation."""
def test_shape(self, square_coords):
"""Distance matrix must be (n, n) for n cities."""
dm = create_distance_matrix(square_coords)
assert dm.shape == (4, 4)
def test_symmetric(self, square_coords):
"""Distance matrix must be symmetric: d(i,j) == d(j,i)."""
dm = create_distance_matrix(square_coords)
np.testing.assert_array_almost_equal(dm, dm.T)
def test_zero_diagonal(self, square_coords):
"""Distance from a city to itself must be zero."""
dm = create_distance_matrix(square_coords)
np.testing.assert_array_equal(np.diag(dm), 0.0)
def test_known_distances(self, square_coords):
"""Verify known distances for the unit square."""
dm = create_distance_matrix(square_coords)
assert dm[0, 1] == pytest.approx(1.0)
assert dm[1, 2] == pytest.approx(1.0)
assert dm[2, 3] == pytest.approx(1.0)
assert dm[3, 0] == pytest.approx(1.0)
assert dm[0, 2] == pytest.approx(np.sqrt(2))
assert dm[1, 3] == pytest.approx(np.sqrt(2))
def test_triangle_inequality(self, square_coords):
"""Triangle inequality must hold: d(i,k) <= d(i,j) + d(j,k)."""
dm = create_distance_matrix(square_coords)
n = len(dm)
for i in range(n):
for j in range(n):
for k in range(n):
assert dm[i, k] <= dm[i, j] + dm[j, k] + 1e-10
class TestIsValidTour:
"""Tests for tour validation."""
def test_valid_tour(self):
"""A proper permutation of [0, n) is valid."""
assert is_valid_tour(np.array([2, 0, 3, 1]), 4) is True
def test_identity_permutation(self):
"""The identity permutation [0, 1, ..., n-1] is valid."""
assert is_valid_tour(np.arange(5), 5) is True
def test_wrong_length(self):
"""A tour with wrong number of cities is invalid."""
assert is_valid_tour(np.array([0, 1, 2]), 4) is False
def test_duplicate_cities(self):
"""A tour with duplicate cities is invalid."""
assert is_valid_tour(np.array([0, 1, 1, 3]), 4) is False
def test_missing_city(self):
"""A tour missing a city is invalid."""
assert is_valid_tour(np.array([0, 1, 2, 4]), 4) is False
def test_empty_tour(self):
"""An empty tour for n=0 is valid; for n>0 is invalid."""
assert is_valid_tour(np.array([], dtype=int), 0) is True
assert is_valid_tour(np.array([], dtype=int), 1) is False
class TestCreateRandomTour:
"""Tests for random tour generation."""
def test_valid(self, rng):
"""Generated tour must be a valid permutation."""
tour = create_random_tour(10, rng)
assert is_valid_tour(tour, 10)
def test_correct_length(self, rng):
"""Generated tour must have exactly n_cities elements."""
tour = create_random_tour(20, rng)
assert len(tour) == 20
def test_randomness(self):
"""Different RNG states should produce different tours."""
rng1 = np.random.default_rng(1)
rng2 = np.random.default_rng(2)
tour1 = create_random_tour(50, rng1)
tour2 = create_random_tour(50, rng2)
assert not np.array_equal(tour1, tour2)
def test_dtype(self, rng):
"""Tour must contain integer indices."""
tour = create_random_tour(10, rng)
assert np.issubdtype(tour.dtype, np.integer)
class TestTourLength:
"""Tests for tour length computation."""
def test_square_optimal(self, square_dist_matrix):
"""The perimeter tour of a unit square has length 4.0."""
tour = np.array([0, 1, 2, 3])
assert tour_length(tour, square_dist_matrix) == pytest.approx(4.0)
def test_square_diagonal(self, square_dist_matrix):
"""A tour crossing the diagonal has length 2 + 2*sqrt(2)."""
tour = np.array([0, 2, 1, 3])
expected = 2 * np.sqrt(2) + 2.0
assert tour_length(tour, square_dist_matrix) == pytest.approx(expected)
def test_reverse_same_length(self, square_dist_matrix):
"""Reversing a tour does not change its length (symmetric TSP)."""
tour = np.array([0, 1, 2, 3])
reversed_tour = np.array([3, 2, 1, 0])
assert tour_length(tour, square_dist_matrix) == pytest.approx(
tour_length(reversed_tour, square_dist_matrix)
)
def test_rotation_invariant(self, square_dist_matrix):
"""Starting the tour at a different city does not change length."""
tour1 = np.array([0, 1, 2, 3])
tour2 = np.array([2, 3, 0, 1])
assert tour_length(tour1, square_dist_matrix) == pytest.approx(
tour_length(tour2, square_dist_matrix)
)
@pytest.mark.parametrize("n_cities", [3, 5, 10, 20])
def test_positive_length(self, n_cities):
"""Tour length must be positive for non-degenerate instances."""
rng = np.random.default_rng(42)
coords = rng.random((n_cities, 2))
dm = create_distance_matrix(coords)
tour = np.arange(n_cities)
assert tour_length(tour, dm) > 0What does this test file specify?
The file defines 17 tests across 4 classes, each specifying a function you must implement:
- TestCreateDistanceMatrix (5 tests): the distance matrix must be symmetric, have zero diagonal, satisfy known Euclidean distances, and obey the triangle inequality.
- TestIsValidTour (6 tests): a valid tour is a permutation of [0, n_cities). The function must reject duplicates, wrong lengths, and missing cities.
- TestCreateRandomTour (4 tests): random tours must be valid permutations with integer dtype, and different RNG states must produce different tours.
- TestTourLength (5 tests): tour length is the round-trip sum of edges. It must be rotation-invariant and reversal-invariant for symmetric TSP.
- Save tests/test_chromosome.py.
- Confirm pytest discovers all 17 tests by running:
pytest tests/test_chromosome.py --collect-only- You should see 17 tests collected. They will all fail if you run them now because the implementation is just a stub.
Seeing an import error?
If pytest reports an import error from tsp_ga.chromosome, make sure your tsp_ga/chromosome.py file still exists (even with just pass in it). The test imports will fail if the module file is missing or has a syntax error.
Also confirm your virtual environment is active and the package is installed in editable mode (you ran pip install -e ".[dev]" in Step 1).
Help me debug my pytest import error for tsp_ga.chromosome
Implement the chromosome functions
Now that you have a complete specification, your job is to write implementation code that satisfies every test. You will build up tsp_ga/chromosome.py function by function, running the tests after each addition.
- Open tsp_ga/chromosome.py and replace the pass stub with the following code for the import and first two functions:
import numpy as np
def create_distance_matrix(coords: np.ndarray) -> np.ndarray:
"""Compute the Euclidean distance matrix from an (n, 2) array of coordinates."""
# Broadcast subtraction to get pairwise differences
diff = coords[:, np.newaxis, :] - coords[np.newaxis, :, :]
return np.sqrt((diff**2).sum(axis=-1))
def is_valid_tour(tour: np.ndarray, n_cities: int) -> bool:
"""Check that a tour is a valid permutation of [0, n_cities)."""
# A valid tour must have exactly n_cities elements
if tour.shape != (n_cities,):
return False
# When sorted, a valid permutation equals [0, 1, ..., n_cities-1]
return np.array_equal(np.sort(tour), np.arange(n_cities))What does this code do?
- create_distance_matrix uses NumPy broadcasting to compute all pairwise Euclidean distances in one vectorized operation. The result is a symmetric matrix with zeros on the diagonal.
- is_valid_tour checks two things: is the array the right length, and when sorted, does it equal [0, 1, ..., n-1]? This catches duplicates, missing cities, and out-of-range values in one check.
- Save tsp_ga/chromosome.py.
- Run the tests for these two functions by running:
pytest tests/test_chromosome.py -v -k "TestCreateDistanceMatrix or TestIsValidTour"- You should see 11 tests passed (5 for distance matrix, 6 for tour validation).
Tests failing on distance values?
If test_known_distances fails, make sure you are computing Euclidean distance (square root of sum of squared differences), not Manhattan distance. The broadcasting must subtract along axis=-1 to get (x, y) differences per city pair.
Help me fix my create_distance_matrix function
- Add the remaining two functions below is_valid_tour in tsp_ga/chromosome.py:
def create_random_tour(n_cities: int, rng: np.random.Generator) -> np.ndarray:
"""Generate a random valid tour (permutation of [0, n_cities))."""
# Start with an ordered sequence and shuffle in place
tour = np.arange(n_cities)
rng.shuffle(tour)
return tour
def tour_length(tour: np.ndarray, dist_matrix: np.ndarray) -> float:
"""Calculate the total length of a tour (round trip)."""
# Sum distances along consecutive edges in the tour
edges = dist_matrix[tour[:-1], tour[1:]]
# Add the return edge from last city back to first
return float(edges.sum() + dist_matrix[tour[-1], tour[0]])What does this code do?
- create_random_tour creates [0, 1, ..., n-1] then shuffles it using the provided RNG. This guarantees the result is always a valid permutation.
- tour_length uses NumPy fancy indexing to gather all edge distances in one array operation. The dist_matrix[tour[-1], tour[0]] term adds the return-to-start edge, making it a round trip.
- Save tsp_ga/chromosome.py.
- Run the full chromosome test suite by running:
pytest tests/test_chromosome.py -v- You should see 17 passed in green. Every test across all 4 classes should pass.
Tour length tests failing?
If test_square_optimal reports a length other than 4.0, make sure you are including the return edge from the last city back to the first. The tour [0, 1, 2, 3] visits edges 0-1, 1-2, 2-3, AND 3-0.
If test_randomness fails, confirm you are using the rng parameter for shuffling (not np.random.shuffle which uses the global state).
Help me debug my failing chromosome tests
✔️ Awesome, I've got everything!
Great. Double check you have saved tsp_ga/chromosome.py and all 17 tests are passing.
ⓧ I'd like to double check the full code
Here is the complete tsp_ga/chromosome.py for comparison:
import numpy as np
def create_distance_matrix(coords: np.ndarray) -> np.ndarray:
"""Compute the Euclidean distance matrix from an (n, 2) array of coordinates."""
diff = coords[:, np.newaxis, :] - coords[np.newaxis, :, :]
return np.sqrt((diff**2).sum(axis=-1))
def is_valid_tour(tour: np.ndarray, n_cities: int) -> bool:
"""Check that a tour is a valid permutation of [0, n_cities)."""
if tour.shape != (n_cities,):
return False
return np.array_equal(np.sort(tour), np.arange(n_cities))
def create_random_tour(n_cities: int, rng: np.random.Generator) -> np.ndarray:
"""Generate a random valid tour (permutation of [0, n_cities))."""
tour = np.arange(n_cities)
rng.shuffle(tour)
return tour
def tour_length(tour: np.ndarray, dist_matrix: np.ndarray) -> float:
"""Calculate the total length of a tour (round trip)."""
edges = dist_matrix[tour[:-1], tour[1:]]
return float(edges.sum() + dist_matrix[tour[-1], tour[0]])You now have the entire foundation layer of your genetic algorithm working and verified. Every higher-level component (selection, crossover, mutation, evolution) depends on these four functions. Next up, you will implement tournament selection to give your GA a way to pick fit parents for reproduction.
Implement Tournament Selection
Your chromosome module is complete. You have functions that create distance matrices, validate tours, generate random permutations, and measure tour length. Now you need a way to choose which tours get to reproduce.
In nature, organisms compete for the right to pass on their genes. Tournament selection mimics this by pitting a random subset of the population against each other and letting the fittest individual win. In this step, you'll write the test specification first, then implement the selection function to pass all 6 tests.
In this step, get ready to:
- Add the complete test specification for tournament selection (6 tests).
- Implement the tournament_select function to pass all tests.
- Verify 6 tests pass with zero failures.
Add the selection test specification
The test file IS your specification. It defines the exact function signature, return type, and behavioral contract you must satisfy. Read through each test carefully before writing any implementation code.
- Open tests/test_selection.py and replace its contents with this test specification:
"""SPECIFICATION: Tournament Selection
=====================================
Tournament selection picks `tournament_size` random individuals from the
population and returns the one with the best (lowest) fitness.
Requirements:
1. The returned individual must be a member of the population (not invented).
2. The returned individual must be a valid tour.
3. With tournament_size == population_size, must always return the best
individual (deterministic extreme case).
4. Over many trials, fitter individuals should be selected more frequently
than less fit ones (selection pressure).
5. Must not modify the original population.
6. Must return a copy, not a view into the population array.
"""
import numpy as np
import pytest
from tsp_ga.chromosome import is_valid_tour
from tsp_ga.selection import tournament_select
class TestTournamentSelect:
"""Tests for tournament selection."""
@pytest.fixture
def population_and_fitness(self):
"""Create a population of 10 tours over 5 cities with known fitnesses."""
rng = np.random.default_rng(99)
pop = np.array([rng.permutation(5) for _ in range(10)])
fitnesses = np.array([10.0, 9.0, 8.0, 7.0, 6.0, 5.0, 4.0, 3.0, 2.0, 1.0])
return pop, fitnesses
def test_returns_valid_tour(self, population_and_fitness, rng):
"""Selected individual must be a valid tour."""
pop, fit = population_and_fitness
selected = tournament_select(pop, fit, tournament_size=3, rng=rng)
assert is_valid_tour(selected, 5)
def test_returns_population_member(self, population_and_fitness, rng):
"""Selected individual must exist in the original population."""
pop, fit = population_and_fitness
selected = tournament_select(pop, fit, tournament_size=3, rng=rng)
assert any(np.array_equal(selected, ind) for ind in pop)
def test_full_tournament_returns_best(self, population_and_fitness):
"""Tournament size == pop size must return the global best."""
pop, fit = population_and_fitness
rng = np.random.default_rng(0)
selected = tournament_select(pop, fit, tournament_size=10, rng=rng)
assert np.array_equal(selected, pop[9])
def test_selection_pressure(self, population_and_fitness):
"""Fitter individuals should be selected more often over many trials."""
pop, fit = population_and_fitness
rng = np.random.default_rng(777)
selection_counts = np.zeros(10)
n_trials = 2000
for _ in range(n_trials):
selected = tournament_select(pop, fit, tournament_size=3, rng=rng)
for idx, ind in enumerate(pop):
if np.array_equal(selected, ind):
selection_counts[idx] += 1
break
assert selection_counts[9] > selection_counts[0]
assert selection_counts[5:].sum() > selection_counts[:5].sum()
def test_does_not_modify_population(self, population_and_fitness, rng):
"""Selection must not alter the original population array."""
pop, fit = population_and_fitness
pop_copy = pop.copy()
tournament_select(pop, fit, tournament_size=3, rng=rng)
np.testing.assert_array_equal(pop, pop_copy)
def test_returns_copy(self, population_and_fitness, rng):
"""Mutating the returned tour must not affect the population."""
pop, fit = population_and_fitness
selected = tournament_select(pop, fit, tournament_size=3, rng=rng)
selected[0] = -999
assert not any(ind[0] == -999 for ind in pop)What do these tests specify?
The tests define a single function tournament_select(population, fitnesses, tournament_size, rng) with these contracts:
- Pick tournament_size random individuals from the population.
- Return the one with the lowest fitness (lower = better in TSP, because shorter tours are better).
- Return a copy, not a view. Modifying the returned array must not affect the population.
- Never modify the original population array.
- Save tests/test_selection.py.
- Confirm pytest discovers the new tests by running:
pytest tests/test_selection.py --collect-onlyYou should see 6 test items collected. They will all fail or error at this point because selection.py has no implementation yet.
Seeing an import error?
If pytest reports an import error for tsp_ga.selection, make sure tsp_ga/selection.py exists in your project directory. It should have been created as a stub in Step 1.
Help me debug why pytest can't import tsp_ga.selection
Implement tournament_select
Tournament selection is conceptually simple. Sample a handful of competitors, let the best one win. The tricky parts are sampling without replacement and returning a copy rather than a view into the population array.
- Open tsp_ga/selection.py and replace pass with this implementation:
import numpy as np
def tournament_select(
population: np.ndarray,
fitnesses: np.ndarray,
tournament_size: int,
rng: np.random.Generator,
) -> np.ndarray:
"""Select one individual via tournament selection (lower fitness = better)."""
# Pick tournament_size random indices without replacement
indices = rng.choice(len(population), size=tournament_size, replace=False)
# Find the index with the lowest (best) fitness among the competitors
winner_idx = indices[np.argmin(fitnesses[indices])]
# Return a copy so mutations to the result don't affect the population
return population[winner_idx].copy()What does this code do?
- rng.choice(len(population), size=tournament_size, replace=False) randomly picks tournament_size unique indices from the population. Using replace=False ensures no individual competes against itself.
- fitnesses[indices] slices out just the fitness values for the competitors. np.argmin finds which competitor has the shortest tour.
- .copy() is critical. Without it, the returned array is a view into the population. Any mutation applied later would corrupt the original population data.
- Save tsp_ga/selection.py.
- Run the selection tests to verify your implementation by running:
pytest tests/test_selection.py -vYou should see all 6 tests passing with green output.
Tests failing?
If test_returns_copy fails, make sure you are calling .copy() on the return value. Numpy array slicing returns a view by default, not an independent copy.
If test_full_tournament_returns_best fails, check that you are selecting by minimum fitness (lowest = best) using np.argmin, not np.argmax.
Help me debug my tournament_select implementation
Why tournament selection over roulette wheel?
Roulette wheel selection assigns reproduction probability proportional to fitness. For TSP, this requires inverting fitness values (shorter tours need higher probability), which is sensitive to the fitness distribution.
Tournament selection has consistent selection pressure regardless of how fitness values are scaled. You control the pressure by adjusting tournament_size. A size of 3 to 5 is the practitioner's default for most problems.
✔️ Awesome, I've got everything!
Great. Double check you've saved both files.
ⓧ I'd like to double check the full code
Here is the full tsp_ga/selection.py:
import numpy as np
def tournament_select(
population: np.ndarray,
fitnesses: np.ndarray,
tournament_size: int,
rng: np.random.Generator,
) -> np.ndarray:
"""Select one individual via tournament selection (lower fitness = better)."""
indices = rng.choice(len(population), size=tournament_size, replace=False)
winner_idx = indices[np.argmin(fitnesses[indices])]
return population[winner_idx].copy()And here is the full tests/test_selection.py:
"""SPECIFICATION: Tournament Selection
=====================================
Tournament selection picks `tournament_size` random individuals from the
population and returns the one with the best (lowest) fitness.
Requirements:
1. The returned individual must be a member of the population (not invented).
2. The returned individual must be a valid tour.
3. With tournament_size == population_size, must always return the best
individual (deterministic extreme case).
4. Over many trials, fitter individuals should be selected more frequently
than less fit ones (selection pressure).
5. Must not modify the original population.
6. Must return a copy, not a view into the population array.
"""
import numpy as np
import pytest
from tsp_ga.chromosome import is_valid_tour
from tsp_ga.selection import tournament_select
class TestTournamentSelect:
"""Tests for tournament selection."""
@pytest.fixture
def population_and_fitness(self):
"""Create a population of 10 tours over 5 cities with known fitnesses."""
rng = np.random.default_rng(99)
pop = np.array([rng.permutation(5) for _ in range(10)])
fitnesses = np.array([10.0, 9.0, 8.0, 7.0, 6.0, 5.0, 4.0, 3.0, 2.0, 1.0])
return pop, fitnesses
def test_returns_valid_tour(self, population_and_fitness, rng):
"""Selected individual must be a valid tour."""
pop, fit = population_and_fitness
selected = tournament_select(pop, fit, tournament_size=3, rng=rng)
assert is_valid_tour(selected, 5)
def test_returns_population_member(self, population_and_fitness, rng):
"""Selected individual must exist in the original population."""
pop, fit = population_and_fitness
selected = tournament_select(pop, fit, tournament_size=3, rng=rng)
assert any(np.array_equal(selected, ind) for ind in pop)
def test_full_tournament_returns_best(self, population_and_fitness):
"""Tournament size == pop size must return the global best."""
pop, fit = population_and_fitness
rng = np.random.default_rng(0)
selected = tournament_select(pop, fit, tournament_size=10, rng=rng)
assert np.array_equal(selected, pop[9])
def test_selection_pressure(self, population_and_fitness):
"""Fitter individuals should be selected more often over many trials."""
pop, fit = population_and_fitness
rng = np.random.default_rng(777)
selection_counts = np.zeros(10)
n_trials = 2000
for _ in range(n_trials):
selected = tournament_select(pop, fit, tournament_size=3, rng=rng)
for idx, ind in enumerate(pop):
if np.array_equal(selected, ind):
selection_counts[idx] += 1
break
assert selection_counts[9] > selection_counts[0]
assert selection_counts[5:].sum() > selection_counts[:5].sum()
def test_does_not_modify_population(self, population_and_fitness, rng):
"""Selection must not alter the original population array."""
pop, fit = population_and_fitness
pop_copy = pop.copy()
tournament_select(pop, fit, tournament_size=3, rng=rng)
np.testing.assert_array_equal(pop, pop_copy)
def test_returns_copy(self, population_and_fitness, rng):
"""Mutating the returned tour must not affect the population."""
pop, fit = population_and_fitness
selected = tournament_select(pop, fit, tournament_size=3, rng=rng)
selected[0] = -999
assert not any(ind[0] == -999 for ind in pop)Selection is done. Your GA can now choose parents based on fitness. Next up, you'll tackle the hardest component: Order Crossover, which combines two parent tours into a valid child tour.
Implement Order Crossover (OX)
Your tournament selection is working. The GA can now pick the fittest parents from a pool. The next challenge is combining two parent tours into a child that inherits good traits from both.
This is where things get tricky. You can't just splice two tours together like strings. Doing so would create duplicates and missing cities, breaking the permutation constraint. Order Crossover (OX) solves this by preserving a segment from one parent and filling the rest using the relative order of the other parent.
In this step, get ready to:
- Add the crossover test specification that defines the exact contract for OX.
- Implement the order_crossover function that passes all 6 tests.
Add the crossover test specification
Order Crossover is the hardest component to implement correctly in this project. The test file defines six contracts that your implementation must satisfy simultaneously: the child must be a valid permutation, it must contain a contiguous segment from parent1, and the remaining cities must follow parent2's relative order.
- Open tests/test_crossover.py in your editor and replace its contents with the following test specification:
"""SPECIFICATION: Order Crossover (OX)
====================================
Order Crossover produces a child from two parent tours while maintaining
the relative order of cities.
Algorithm:
1. Select two random crossover points in the tour.
2. Copy the segment between those points from parent1 into the child
(same positions).
3. Fill the remaining positions with cities from parent2 in the order
they appear in parent2, skipping any city already placed.
Requirements:
1. The child must be a valid tour (permutation of all cities).
2. The segment between crossover points must come from parent1.
3. Remaining cities must appear in the same relative order as in parent2.
4. Must work for any tour size >= 2.
5. Must not modify either parent.
6. Multiple calls with different RNG states should produce variety.
"""
import numpy as np
import pytest
from tsp_ga.chromosome import is_valid_tour
from tsp_ga.crossover import order_crossover
class TestOrderCrossover:
"""Tests for Order Crossover (OX)."""
def test_child_is_valid_tour(self, rng):
"""Child must be a valid permutation of all cities."""
parent1 = np.array([0, 1, 2, 3, 4, 5, 6, 7])
parent2 = np.array([7, 6, 5, 4, 3, 2, 1, 0])
child = order_crossover(parent1, parent2, rng)
assert is_valid_tour(child, 8)
@pytest.mark.parametrize("n_cities", [2, 5, 10, 20, 50])
def test_valid_for_various_sizes(self, n_cities):
"""OX must produce valid tours for any reasonable tour size."""
rng = np.random.default_rng(42)
parent1 = rng.permutation(n_cities)
parent2 = rng.permutation(n_cities)
child = order_crossover(parent1, parent2, rng)
assert is_valid_tour(child, n_cities)
def test_contains_segment_from_parent1(self):
"""The child must contain a contiguous segment from parent1
at the same positions."""
parent1 = np.array([0, 1, 2, 3, 4, 5, 6, 7])
parent2 = np.array([7, 6, 5, 4, 3, 2, 1, 0])
for seed in range(20):
rng = np.random.default_rng(seed)
child = order_crossover(parent1, parent2, rng)
found_segment = False
for start in range(8):
for end in range(start + 2, 9):
if np.array_equal(child[start:end], parent1[start:end]):
found_segment = True
break
if found_segment:
break
assert found_segment, f"No parent1 segment found in child (seed={seed})"
def test_remaining_cities_order_from_parent2(self):
"""Cities outside the copied segment must maintain their relative
order from parent2."""
parent1 = np.array([0, 1, 2, 3, 4, 5, 6, 7])
parent2 = np.array([4, 6, 0, 7, 2, 5, 1, 3])
for seed in range(20):
rng = np.random.default_rng(seed)
child = order_crossover(parent1, parent2, rng)
segment_positions = set()
for start in range(8):
for end in range(start + 2, 9):
if np.array_equal(child[start:end], parent1[start:end]):
segment_positions = set(range(start, end))
break
if segment_positions:
break
remaining_in_child = [
child[i] for i in range(8) if i not in segment_positions
]
segment_cities = set(child[i] for i in segment_positions)
remaining_in_parent2 = [
c for c in parent2 if c not in segment_cities
]
assert remaining_in_child == remaining_in_parent2, (
f"Relative order not preserved (seed={seed})"
)
def test_does_not_modify_parents(self, rng):
"""Crossover must not change either parent."""
parent1 = np.array([0, 1, 2, 3, 4])
parent2 = np.array([4, 3, 2, 1, 0])
p1_copy = parent1.copy()
p2_copy = parent2.copy()
order_crossover(parent1, parent2, rng)
np.testing.assert_array_equal(parent1, p1_copy)
np.testing.assert_array_equal(parent2, p2_copy)
def test_many_crossovers_produce_variety(self):
"""Multiple crossovers with different RNG states should produce
different children."""
parent1 = np.arange(10)
parent2 = np.arange(10)[::-1]
children = set()
for seed in range(50):
rng = np.random.default_rng(seed)
child = order_crossover(parent1, parent2, rng)
children.add(tuple(child))
assert len(children) > 5What do these tests verify?
Read through the docstring at the top of the file first. It lays out the OX algorithm in three steps and lists the six requirements your implementation must meet.
- test_child_is_valid_tour and test_valid_for_various_sizes confirm no cities are lost or duplicated, regardless of tour size.
- test_contains_segment_from_parent1 checks that a contiguous block of genes from parent1 appears at the same positions in the child.
- test_remaining_cities_order_from_parent2 verifies the cities outside the segment follow parent2's relative ordering.
- test_does_not_modify_parents ensures immutability. test_many_crossovers_produce_variety confirms different RNG states produce distinct children.
- Save tests/test_crossover.py.
- Confirm pytest discovers the new tests by running:
pytest tests/test_crossover.py --collect-only- You should see 6 test items collected. They will all fail or error if you run them now because crossover.py has no order_crossover function yet.
Not seeing 6 tests collected?
- Check that you saved the file as tests/test_crossover.py (not test_crossover.py in the project root).
- Verify the from tsp_ga.crossover import order_crossover line is present. An ImportError is expected at this stage, but the tests should still be collected.
- help me debug why pytest isn't finding my crossover tests
✔️ Awesome, I've got everything!
Great. Make sure you've saved tests/test_crossover.py and move on to implement the function.
ⓧ I'd like to double check the full code
"""SPECIFICATION: Order Crossover (OX)
====================================
Order Crossover produces a child from two parent tours while maintaining
the relative order of cities.
Algorithm:
1. Select two random crossover points in the tour.
2. Copy the segment between those points from parent1 into the child
(same positions).
3. Fill the remaining positions with cities from parent2 in the order
they appear in parent2, skipping any city already placed.
Requirements:
1. The child must be a valid tour (permutation of all cities).
2. The segment between crossover points must come from parent1.
3. Remaining cities must appear in the same relative order as in parent2.
4. Must work for any tour size >= 2.
5. Must not modify either parent.
6. Multiple calls with different RNG states should produce variety.
"""
import numpy as np
import pytest
from tsp_ga.chromosome import is_valid_tour
from tsp_ga.crossover import order_crossover
class TestOrderCrossover:
"""Tests for Order Crossover (OX)."""
def test_child_is_valid_tour(self, rng):
"""Child must be a valid permutation of all cities."""
parent1 = np.array([0, 1, 2, 3, 4, 5, 6, 7])
parent2 = np.array([7, 6, 5, 4, 3, 2, 1, 0])
child = order_crossover(parent1, parent2, rng)
assert is_valid_tour(child, 8)
@pytest.mark.parametrize("n_cities", [2, 5, 10, 20, 50])
def test_valid_for_various_sizes(self, n_cities):
"""OX must produce valid tours for any reasonable tour size."""
rng = np.random.default_rng(42)
parent1 = rng.permutation(n_cities)
parent2 = rng.permutation(n_cities)
child = order_crossover(parent1, parent2, rng)
assert is_valid_tour(child, n_cities)
def test_contains_segment_from_parent1(self):
"""The child must contain a contiguous segment from parent1
at the same positions."""
parent1 = np.array([0, 1, 2, 3, 4, 5, 6, 7])
parent2 = np.array([7, 6, 5, 4, 3, 2, 1, 0])
for seed in range(20):
rng = np.random.default_rng(seed)
child = order_crossover(parent1, parent2, rng)
found_segment = False
for start in range(8):
for end in range(start + 2, 9):
if np.array_equal(child[start:end], parent1[start:end]):
found_segment = True
break
if found_segment:
break
assert found_segment, f"No parent1 segment found in child (seed={seed})"
def test_remaining_cities_order_from_parent2(self):
"""Cities outside the copied segment must maintain their relative
order from parent2."""
parent1 = np.array([0, 1, 2, 3, 4, 5, 6, 7])
parent2 = np.array([4, 6, 0, 7, 2, 5, 1, 3])
for seed in range(20):
rng = np.random.default_rng(seed)
child = order_crossover(parent1, parent2, rng)
segment_positions = set()
for start in range(8):
for end in range(start + 2, 9):
if np.array_equal(child[start:end], parent1[start:end]):
segment_positions = set(range(start, end))
break
if segment_positions:
break
remaining_in_child = [
child[i] for i in range(8) if i not in segment_positions
]
segment_cities = set(child[i] for i in segment_positions)
remaining_in_parent2 = [
c for c in parent2 if c not in segment_cities
]
assert remaining_in_child == remaining_in_parent2, (
f"Relative order not preserved (seed={seed})"
)
def test_does_not_modify_parents(self, rng):
"""Crossover must not change either parent."""
parent1 = np.array([0, 1, 2, 3, 4])
parent2 = np.array([4, 3, 2, 1, 0])
p1_copy = parent1.copy()
p2_copy = parent2.copy()
order_crossover(parent1, parent2, rng)
np.testing.assert_array_equal(parent1, p1_copy)
np.testing.assert_array_equal(parent2, p2_copy)
def test_many_crossovers_produce_variety(self):
"""Multiple crossovers with different RNG states should produce
different children."""
parent1 = np.arange(10)
parent2 = np.arange(10)[::-1]
children = set()
for seed in range(50):
rng = np.random.default_rng(seed)
child = order_crossover(parent1, parent2, rng)
children.add(tuple(child))
assert len(children) > 5Implement the order_crossover function
The OX algorithm works in three phases. First, pick two random crossover points and copy the segment between them from parent1 into the child at the same positions. Second, collect all cities from parent2 that are not already in the copied segment, preserving parent2's order. Third, fill the remaining empty positions in the child with those collected cities.
- Open tsp_ga/crossover.py and replace its contents with the following implementation:
import numpy as np
def order_crossover(
parent1: np.ndarray, parent2: np.ndarray, rng: np.random.Generator
) -> np.ndarray:
"""Perform Order Crossover (OX) on two parent tours."""
n = len(parent1)
# Pick two distinct crossover points and sort them
points = sorted(rng.choice(n, size=2, replace=False))
start, end = points[0], points[1]
# Copy the segment from parent1 into the child at the same positions
child = np.full(n, -1, dtype=parent1.dtype)
child[start:end] = parent1[start:end]
# Collect cities from parent2 that are NOT in the copied segment
segment_set = set(child[start:end])
fill_values = [city for city in parent2 if city not in segment_set]
# Fill the remaining empty positions with parent2's cities (in order)
fill_idx = 0
for i in range(n):
if child[i] == -1:
child[i] = fill_values[fill_idx]
fill_idx += 1
return childWhat does this code do?
- rng.choice(n, size=2, replace=False) picks two distinct crossover points. Sorting them guarantees start < end.
- np.full(n, -1) creates a child array filled with -1 as a sentinel value, so you can tell which positions still need filling.
- The segment copy (child[start:end] = parent1[start:end]) preserves exact gene positions from parent1. This is what the segment-preservation test checks.
- Building fill_values by iterating parent2 in order (and skipping cities already placed) guarantees the relative-order property that the fourth test checks.
- Save tsp_ga/crossover.py.
- Run the crossover tests by running:
pytest tests/test_crossover.py -v- You should see 6 passed, 0 failed. Every test name should show PASSED in green.
Seeing test failures?
The segment-preservation and relative-order tests are the ones most people fail on first attempt. Here are the common causes:
- If test_contains_segment_from_parent1 fails, check that your slice uses child[start:end] (not start:end+1). The test expects the segment to match the exact slice boundaries from rng.choice.
- If test_remaining_cities_order_from_parent2 fails, make sure you iterate parent2 in its original order when building fill_values. Using a set lookup on parent2 would lose the ordering.
- If test_does_not_modify_parents fails, verify you are not assigning into parent1 or parent2 anywhere in your function.
- help me debug my Order Crossover implementation
✔️ Awesome, I've got everything!
Great. Double check you've saved tsp_ga/crossover.py with all 6 tests passing.
ⓧ I'd like to double check the full code
import numpy as np
def order_crossover(
parent1: np.ndarray, parent2: np.ndarray, rng: np.random.Generator
) -> np.ndarray:
"""Perform Order Crossover (OX) on two parent tours."""
n = len(parent1)
points = sorted(rng.choice(n, size=2, replace=False))
start, end = points[0], points[1]
child = np.full(n, -1, dtype=parent1.dtype)
child[start:end] = parent1[start:end]
segment_set = set(child[start:end])
fill_values = [city for city in parent2 if city not in segment_set]
fill_idx = 0
for i in range(n):
if child[i] == -1:
child[i] = fill_values[fill_idx]
fill_idx += 1
return childWhy Order Crossover instead of simple splicing?
In a standard genetic algorithm, you can swap gene segments freely between parents. TSP tours are different because every city must appear exactly once. A naive splice would produce duplicates and missing cities.
OX solves this by inheriting a positional block from one parent (exploiting good sub-routes) while preserving the relative city ordering from the other parent (maintaining global structure). This balance of exploitation and exploration is what makes OX the go-to crossover operator for permutation problems.
Your crossover operator is complete. The GA can now combine two parent tours into valid offspring that inherit traits from both. Next up, you'll implement mutation and wire everything into a full evolution loop that converges on near-optimal solutions.
Implement Mutation and the Evolution Loop
You now have working selection and crossover operators. The final two components are mutation (to maintain genetic diversity) and the evolution loop that ties every piece together into a functioning genetic algorithm.
Without mutation, the population can converge prematurely on a local optimum. Swap mutation introduces random variation at a controlled rate. The evolution loop then orchestrates selection, crossover, mutation, and elitism into a generational cycle that provably converges toward near-optimal tours.
In this step, get ready to:
- Add the mutation and evolution test specifications (15 tests total).
- Implement swap mutation and the full generational evolution loop.
- Run the complete test suite and confirm all 44 tests pass.
Add the mutation and evolution test specifications
Following the test-first workflow, you will add both test files before writing any implementation. These tests define the exact contracts for swap_mutate and evolve.
- Replace the contents of tests/test_mutation.py with the following test specification:
"""SPECIFICATION: Swap Mutation
=============================
Swap mutation iterates over each position in the tour. For each position,
with probability `mutation_rate`, it swaps that position with another
randomly chosen position.
Requirements:
1. The mutated tour must always be a valid permutation (no cities lost
or duplicated).
2. With mutation_rate = 0.0, the tour must remain unchanged.
3. With mutation_rate = 1.0, every position will be involved in a swap
(the tour will likely be heavily shuffled).
4. Over many trials with a moderate rate, a reasonable number of swaps
should occur.
5. Must not modify the original tour.
"""
import numpy as np
import pytest
from tsp_ga.chromosome import is_valid_tour
from tsp_ga.mutation import swap_mutate
class TestSwapMutate:
"""Tests for swap mutation."""
def test_always_valid(self, rng):
"""Mutated tour must always be a valid permutation."""
tour = np.arange(20)
for _ in range(100):
mutated = swap_mutate(tour, mutation_rate=0.3, rng=rng)
assert is_valid_tour(mutated, 20)
def test_zero_rate_no_change(self, rng):
"""With mutation_rate=0, the tour must not change."""
tour = np.arange(10)
mutated = swap_mutate(tour, mutation_rate=0.0, rng=rng)
np.testing.assert_array_equal(mutated, tour)
def test_high_rate_causes_changes(self):
"""With mutation_rate=1.0, the tour should differ from the original."""
rng = np.random.default_rng(42)
tour = np.arange(20)
mutated = swap_mutate(tour, mutation_rate=1.0, rng=rng)
assert not np.array_equal(mutated, tour)
def test_statistical_swap_rate(self):
"""Over many trials, the fraction of changed positions should
be in a reasonable range for the given mutation rate."""
rng = np.random.default_rng(123)
tour = np.arange(50)
mutation_rate = 0.2
total_changes = 0
n_trials = 500
for _ in range(n_trials):
mutated = swap_mutate(tour, mutation_rate=mutation_rate, rng=rng)
changes = np.sum(mutated != tour)
total_changes += changes
avg_changes_per_trial = total_changes / n_trials
assert avg_changes_per_trial > 5, "Too few changes"
assert avg_changes_per_trial < 40, "Too many changes"
def test_does_not_modify_original(self, rng):
"""Mutation must not alter the input tour."""
tour = np.arange(10)
original = tour.copy()
swap_mutate(tour, mutation_rate=0.5, rng=rng)
np.testing.assert_array_equal(tour, original)
@pytest.mark.parametrize("n_cities", [2, 5, 10, 50])
def test_various_sizes(self, n_cities):
"""Mutation must work correctly for various tour sizes."""
rng = np.random.default_rng(42)
tour = np.arange(n_cities)
mutated = swap_mutate(tour, mutation_rate=0.15, rng=rng)
assert is_valid_tour(mutated, n_cities)What does this specification require?
The mutation spec defines swap mutation as an operation that iterates every position in the tour. At each position, with probability mutation_rate, it swaps that city with another randomly chosen position.
- Validity is the core invariant: swaps can never lose or duplicate a city.
- A rate of 0.0 means no swaps happen. A rate of 1.0 means every position triggers a swap.
- The statistical test checks that a 20% rate produces a reasonable average number of changed positions across 500 trials.
- Immutability: the original tour array must never be altered.
- Save tests/test_mutation.py.
- Now replace the contents of tests/test_evolution.py with the evolution loop specification:
"""SPECIFICATION: Evolution Loop (Full GA)
========================================
The evolution loop ties all components together into a generational
genetic algorithm with elitism.
Algorithm per generation:
1. Sort population by fitness (lower tour length = better).
2. Copy the top `elite_count` individuals unchanged to the next generation.
3. Fill remaining slots by:
a. Select two parents via tournament selection.
b. Produce a child via Order Crossover (OX).
c. Mutate the child via swap mutation.
4. Evaluate fitness of the new population.
5. Repeat for `n_generations`.
Requirements:
1. Must return a valid tour as the best solution.
2. Must converge: final best fitness <= initial best fitness.
3. History must be monotonically non-increasing (due to elitism).
4. Must find near-optimal solutions for small instances (within 10% of
optimal for 10 cities on a circle).
5. Must be reproducible: same seed = same result.
6. History length must equal n_generations.
7. Returned best_length must match the actual length of best_tour.
"""
import numpy as np
import pytest
from tsp_ga.chromosome import create_distance_matrix, is_valid_tour, tour_length
from tsp_ga.evolution import evolve
class TestEvolve:
"""Tests for the full evolution loop."""
def test_returns_valid_tour(self, square_coords):
"""The best tour returned must be a valid permutation."""
best_tour, best_length, history = evolve(
square_coords, pop_size=20, n_generations=50, seed=42
)
assert is_valid_tour(best_tour, len(square_coords))
def test_converges(self, circle_coords):
"""Final best fitness must be <= initial best fitness."""
_, _, history = evolve(
circle_coords, pop_size=50, n_generations=100, seed=42
)
assert history[-1] <= history[0]
def test_history_monotonic(self, circle_coords):
"""With elitism, best fitness must never worsen across generations."""
_, _, history = evolve(
circle_coords, pop_size=50, n_generations=100, seed=42
)
for i in range(1, len(history)):
assert history[i] <= history[i - 1] + 1e-10, (
f"Fitness worsened at generation {i}: {history[i-1]} -> {history[i]}"
)
def test_near_optimal_circle(self, circle_coords):
"""GA should find a tour within 10% of optimal for 10 cities on a circle.
Optimal tour length for 10 cities on unit circle =
10 * 2 * sin(pi/10) = 6.1803...
"""
optimal = 10 * 2 * np.sin(np.pi / 10)
best_tour, best_length, _ = evolve(
circle_coords,
pop_size=100,
n_generations=300,
tournament_size=5,
mutation_rate=0.1,
elite_count=2,
seed=42,
)
assert best_length < optimal * 1.10, (
f"GA found tour of length {best_length:.4f}, "
f"but optimal is {optimal:.4f} (>10% gap)"
)
def test_finds_optimal_square(self, square_coords):
"""GA should find the optimal tour (length 4.0) for a unit square."""
best_tour, best_length, _ = evolve(
square_coords,
pop_size=30,
n_generations=100,
tournament_size=3,
mutation_rate=0.15,
elite_count=2,
seed=42,
)
assert best_length == pytest.approx(4.0, abs=0.01)
def test_reproducible(self, circle_coords):
"""Same seed must produce identical results."""
_, length1, history1 = evolve(circle_coords, pop_size=50, n_generations=50, seed=99)
_, length2, history2 = evolve(circle_coords, pop_size=50, n_generations=50, seed=99)
assert length1 == length2
assert history1 == history2
def test_different_seeds_different_results(self, circle_coords):
"""Different seeds should produce different results."""
_, length1, _ = evolve(circle_coords, pop_size=50, n_generations=50, seed=1)
_, length2, _ = evolve(circle_coords, pop_size=50, n_generations=50, seed=2)
assert length1 != length2
def test_history_length(self, square_coords):
"""History must contain one entry per generation."""
n_gen = 75
_, _, history = evolve(square_coords, pop_size=20, n_generations=n_gen, seed=42)
assert len(history) == n_gen
def test_best_length_matches_tour(self, circle_coords):
"""The returned best_length must match the actual length of best_tour."""
best_tour, best_length, _ = evolve(
circle_coords, pop_size=50, n_generations=100, seed=42
)
dm = create_distance_matrix(circle_coords)
actual_length = tour_length(best_tour, dm)
assert best_length == pytest.approx(actual_length)What does the evolution specification enforce?
These 9 tests define the full contract for your GA. The most important constraints are:
- Monotonic history: because of elitism, the best fitness can never get worse from one generation to the next.
- Near-optimal convergence: the GA must find a tour within 10% of the theoretical optimum (6.18) for 10 cities on a unit circle.
- Reproducibility: identical seeds must produce identical results, which your deterministic RNG guarantees.
- Consistency: the returned best_length must match the actual computed length of the returned best_tour.
- Save tests/test_evolution.py.
Import errors when running tests?
If you run the tests now, you will see import errors. That is expected. The tsp_ga/mutation.py and tsp_ga/evolution.py files still contain only pass. You will implement them in the next substep.
Help me debug import errors in my test files.
Implement swap_mutate and the evolution loop
Start with swap mutation since it is simpler and the evolution loop depends on it. The mutation function iterates each position in the tour and, with a given probability, swaps it with another random position.
- Replace the contents of tsp_ga/mutation.py with the following implementation:
import numpy as np
def swap_mutate(
tour: np.ndarray, mutation_rate: float, rng: np.random.Generator
) -> np.ndarray:
"""Apply swap mutation to a tour."""
# Copy to avoid modifying the original
tour = tour.copy()
n = len(tour)
# Iterate each position, swap with probability mutation_rate
for i in range(n):
if rng.random() < mutation_rate:
j = rng.integers(0, n)
tour[i], tour[j] = tour[j], tour[i]
return tourWhat does this code do?
- tour.copy() creates a new array so the original tour is never modified (immutability contract).
- The loop visits every position. At each one, rng.random() < mutation_rate decides whether a swap happens.
- rng.integers(0, n) picks a random partner index. Because swaps only rearrange existing elements, the result is always a valid permutation.
- Save tsp_ga/mutation.py.
- Verify the mutation tests pass by running:
pytest tests/test_mutation.py -vYou should see 6 passed, 0 failed.
Seeing failures on the statistical test?
If test_statistical_swap_rate fails, make sure your loop condition uses rng.random() < mutation_rate (strict less-than). Also confirm you are iterating over every position with for i in range(n), not skipping any.
Help me debug my swap_mutate implementation.
Now for the main event. The evolution loop initializes a random population, then runs a generational cycle: sort by fitness, preserve elites, fill the rest with offspring from selection, crossover, and mutation.
- Replace the contents of tsp_ga/evolution.py with the following implementation:
import numpy as np
from tsp_ga.chromosome import (
create_distance_matrix,
create_random_tour,
tour_length,
)
from tsp_ga.crossover import order_crossover
from tsp_ga.mutation import swap_mutate
from tsp_ga.selection import tournament_select
def evolve(
coords: np.ndarray,
pop_size: int = 100,
n_generations: int = 200,
tournament_size: int = 5,
mutation_rate: float = 0.1,
elite_count: int = 2,
seed: int = 42,
) -> tuple[np.ndarray, float, list[float]]:
"""Run the genetic algorithm for TSP."""
rng = np.random.default_rng(seed)
n_cities = len(coords)
dist_matrix = create_distance_matrix(coords)
# Initialize random population and evaluate fitness
population = np.array([create_random_tour(n_cities, rng) for _ in range(pop_size)])
fitnesses = np.array([tour_length(t, dist_matrix) for t in population])
history = []
for gen in range(n_generations):
# Sort population by fitness (lower = better)
order = np.argsort(fitnesses)
population = population[order]
fitnesses = fitnesses[order]
# Record the best fitness this generation
history.append(float(fitnesses[0]))
# Preserve the elite individuals unchanged
new_population = list(population[:elite_count])
# Fill remaining slots with offspring
while len(new_population) < pop_size:
parent1 = tournament_select(population, fitnesses, tournament_size, rng)
parent2 = tournament_select(population, fitnesses, tournament_size, rng)
child = order_crossover(parent1, parent2, rng)
child = swap_mutate(child, mutation_rate, rng)
new_population.append(child)
# Replace population and re-evaluate fitness
population = np.array(new_population[:pop_size])
fitnesses = np.array([tour_length(t, dist_matrix) for t in population])
best_idx = np.argmin(fitnesses)
return population[best_idx], fitnesses[best_idx], historyWhat does this code do?
This is the complete generational GA. Each generation follows 4 phases:
- Sort and record: the population is sorted by tour length, and the best fitness is appended to history.
- Elitism: the top elite_count individuals are copied directly into the next generation. This guarantees the best fitness never worsens.
- Offspring generation: two parents are selected via tournament, crossed over with OX, then mutated. This repeats until the population is full.
- Re-evaluation: the new population's fitnesses are computed fresh for the next generation's sort.
The function returns a tuple of the best tour found, its length, and the full fitness history across generations.
- Save tsp_ga/evolution.py.
- Verify the evolution tests pass by running:
pytest tests/test_evolution.py -vYou should see 9 passed, 0 failed. The test_near_optimal_circle test may take a second or two since it runs 300 generations with a population of 100.
Evolution tests failing on convergence?
If test_near_optimal_circle or test_finds_optimal_square fails, check that elitism is working correctly. The elites must be taken from the sorted population (indices [:elite_count] after the argsort). If you sort the population after recording history, the elites will be wrong.
If test_history_monotonic fails, your elites are being overwritten or you are sorting after the elitism step. Make sure the sort happens before copying elites.
Help me debug my evolution loop.
✔️ Awesome, I've got everything!
Great. Double check you have saved both implementation files before moving on.
ⓧ I'd like to double check the full code
Here is the complete tsp_ga/mutation.py:
import numpy as np
def swap_mutate(
tour: np.ndarray, mutation_rate: float, rng: np.random.Generator
) -> np.ndarray:
"""Apply swap mutation to a tour."""
tour = tour.copy()
n = len(tour)
for i in range(n):
if rng.random() < mutation_rate:
j = rng.integers(0, n)
tour[i], tour[j] = tour[j], tour[i]
return tourAnd here is the complete tsp_ga/evolution.py:
import numpy as np
from tsp_ga.chromosome import (
create_distance_matrix,
create_random_tour,
tour_length,
)
from tsp_ga.crossover import order_crossover
from tsp_ga.mutation import swap_mutate
from tsp_ga.selection import tournament_select
def evolve(
coords: np.ndarray,
pop_size: int = 100,
n_generations: int = 200,
tournament_size: int = 5,
mutation_rate: float = 0.1,
elite_count: int = 2,
seed: int = 42,
) -> tuple[np.ndarray, float, list[float]]:
"""Run the genetic algorithm for TSP."""
rng = np.random.default_rng(seed)
n_cities = len(coords)
dist_matrix = create_distance_matrix(coords)
population = np.array([create_random_tour(n_cities, rng) for _ in range(pop_size)])
fitnesses = np.array([tour_length(t, dist_matrix) for t in population])
history = []
for gen in range(n_generations):
order = np.argsort(fitnesses)
population = population[order]
fitnesses = fitnesses[order]
history.append(float(fitnesses[0]))
new_population = list(population[:elite_count])
while len(new_population) < pop_size:
parent1 = tournament_select(population, fitnesses, tournament_size, rng)
parent2 = tournament_select(population, fitnesses, tournament_size, rng)
child = order_crossover(parent1, parent2, rng)
child = swap_mutate(child, mutation_rate, rng)
new_population.append(child)
population = np.array(new_population[:pop_size])
fitnesses = np.array([tour_length(t, dist_matrix) for t in population])
best_idx = np.argmin(fitnesses)
return population[best_idx], fitnesses[best_idx], historyRun the full test suite
Every module is now implemented. The final check confirms all 44 tests across all 5 modules pass together.
- Run the complete test suite by running:
pytest -vYou should see 44 passed, 0 failed. The output includes tests from all five modules: chromosome (17), selection (6), crossover (6), mutation (6), and evolution (9).
What does the near-optimal result mean?
The test_near_optimal_circle test confirms your GA finds a tour within 10% of the theoretical optimum for 10 cities equally spaced on a unit circle. The optimal tour length for that instance is 6.18 (visiting cities in angular order).
Your GA discovers this near-optimal path through evolution alone. No human told it the angular ordering trick. Selection pressure, crossover, and mutation worked together to find it.
Some tests passing but not all 44?
If individual module tests pass but the full suite has failures, check for import conflicts. Make sure every __init__.py file exists (even if empty) in both tsp_ga/ and tests/.
If you see exactly 44 collected but some fail, read the assertion message carefully. It tells you what value was expected and what your code produced.
Help me get all 44 tests passing.
Secret mission
2-Opt Local Search (Memetic Algorithm)
Your GA finds good tours, but it can't smooth out the small imperfections that remain after evolution converges. What if you could apply a targeted post-processing step that eliminates every crossing edge? Implement 2-opt local search and turn your GA into a memetic algorithm that consistently outperforms the base approach.
Clean Up Your Resources
Clean Up Your Resources
This project runs entirely locally, so there are no ongoing costs. Decide whether to keep your project files, pause your environment, or delete everything.
Resources you used:
- The tsp-ga/ project directory (source code, tests, virtual environment).
- Python packages installed in the virtual environment (numpy, pytest).
Keep everything running
No action needed. Choose this if you plan to keep experimenting with your genetic algorithm or want to extend it further.
- Your project files and virtual environment stay on your Desktop, ready for the next time you open a terminal.
Pause - I'll come back to this later
Deactivate your virtual environment to free up your terminal session. Your files stay on disk.
- If your virtual environment is active, deactivate it by running:
deactivate- When you come back, navigate to your project directory and reactivate the environment with source .venv/bin/activate (macOS/Linux) or .venv\Scripts\activate (Windows).
Delete - I don't want to use this again
Remove all project files and the virtual environment. This cannot be undone.
- If your virtual environment is active, deactivate it first:
deactivate- Navigate to your Desktop and delete the project directory.
- On macOS/Linux, run:
cd ~/Desktop
rm -rf tsp-ga- On Windows, run:
cd ~\Desktop
rmdir /s /q tsp-ga- Confirm the folder is gone by running ls and checking that tsp-ga no longer appears.
Nice Work!
Nice Work!
Nice work! You just built a complete genetic algorithm framework for the Travelling Salesman Problem, entirely test-driven from specification to passing suite.
You've learned how to:
- Build a test-driven algorithmic project by reading tests as specifications, implementing functions to satisfy contracts, and verifying correctness at every step.
- Implement permutation-safe GA operators including tournament selection, Order Crossover (OX), and swap mutation that maintain valid tours throughout the evolutionary process.
- Tie all components into a generational GA with elitism that provably converges on near-optimal solutions for TSP benchmark instances.
- Secret Mission: Extended the base GA into a memetic algorithm by implementing 2-opt local search with efficient delta evaluation.
Ready to quiz yourself?