genetic_algorithm.travelling_salesman_problem

Use a genetic algorithm to solve the travelling salesman problem (TSP) which asks the following question: “Given a list of cities and the distances between each pair of cities, what is the

shortest possible route that visits each city exactly once and returns to the origin city?”

https://en.wikipedia.org/wiki/Genetic_algorithm https://en.wikipedia.org/wiki/Travelling_salesman_problem

Author: Clark

Attributes

cities

Functions

chose_rws(→ list[list[int]])	A type of selection operator
chose_ts(→ list[list[int]])	A type of selection operator
crossing(→ tuple[list[int], list[int]])	Population crossover
distance(→ float)	Calculate the distance between two coordinate points
fitness(→ tuple[list[float], list[int], float])	Calculate population fitness
init(→ tuple[list[list[int]], list[int]])	Initialization generates initial population
main(→ tuple[list[int], float])	Genetic algorithm main function
mutate(→ list[int])	Population variation: swap two interior cities (endpoints stay at 0).

Module Contents

genetic_algorithm.travelling_salesman_problem.chose_rws(fitness_matrix: list[float], chromosomes: list[list[int]], population_size: int) → list[list[int]]

A type of selection operator Roulette Wheel Selection >>> chose_rws(fitness_matrix=[1], chromosomes=[[0,1,0]], population_size=1) [[0, 1, 0]] >>> chose_rws(fitness_matrix=[1], chromosomes=[0,1,0], population_size=0) [0, 1, 0] >>> chose_rws(fitness_matrix=[], chromosomes=[[0,1,0]], population_size=1) Traceback (most recent call last): … IndexError: list index out of range >>> chose_rws(fitness_matrix=[1], chromosomes=[], population_size=1) Traceback (most recent call last): … IndexError: list index out of range >>> chose_rws(fitness_matrix=[1], chromosomes=[0,1,0], population_size=2) [0, 0, 0]

genetic_algorithm.travelling_salesman_problem.chose_ts(fitness_matrix: list[float], chromosomes: list[list[int]], population_size: int) → list[list[int]]

A type of selection operator Tournament Selection >>> chose_ts(fitness_matrix=[1], chromosomes=[[0,1,0]], population_size=1) [[0, 1, 0]] >>> chose_ts(fitness_matrix=[1], chromosomes=[0,1,0], population_size=0) [] >>> chose_ts(fitness_matrix=[], chromosomes=[[0,1,0]], population_size=1) Traceback (most recent call last): … IndexError: list index out of range >>> chose_ts(fitness_matrix=[1], chromosomes=[], population_size=1) Traceback (most recent call last): … IndexError: list index out of range >>> import random >>> random.seed(0) >>> chose_ts(fitness_matrix=[1], chromosomes=[0, 1, 0], population_size=2) Traceback (most recent call last): … IndexError: list index out of range

genetic_algorithm.travelling_salesman_problem.crossing(chromosome_a: list[int], chromosome_b: list[int], crossover_probability: float, cities_list: list[int]) → tuple[list[int], list[int]]

Population crossover >>> crossing(chromosome_a=[0,1,0], chromosome_b=[0,1,0], … crossover_probability=0,cities_list=[1]) ([0, 1, 0], [0, 1, 0]) >>> crossing(chromosome_a=[0,1,0], chromosome_b=[0,1,0], … crossover_probability=1,cities_list=[1]) ([0, 1, 0], [0, 1, 0]) >>> crossing(chromosome_a=[0,1,0], chromosome_b=[], … crossover_probability=1,cities_list=[1]) Traceback (most recent call last): … IndexError: list index out of range >>> crossing(chromosome_a=[0,1,0], chromosome_b=[0,1,0], … crossover_probability=1,cities_list=[]) ([0, 1, 0], [0, 1, 0])

genetic_algorithm.travelling_salesman_problem.distance(city1: list[int], city2: list[int]) → float

Calculate the distance between two coordinate points >>> distance([0, 0], [3, 4] ) 5.0 >>> distance([0, 0], [-3, 4] ) 5.0 >>> distance([0, 0], [-3, -4] ) 5.0

genetic_algorithm.travelling_salesman_problem.fitness(cities: dict[int, list[int]], chromosomes: list[list[int]], best_path: list[int], best_distance: float) → tuple[list[float], list[int], float]

Calculate population fitness Generate a fitness matrix and obtain the optimal value in the current population >>> fitness(cities={0: [0, 0], 1: [2, 2]},chromosomes=[[0,1,0]], … best_path=[], best_distance=float(“inf”)) ([0.17677669529663687], [0, 1, 0], 5.656854249492381) >>> fitness(cities={0: [0, 0], 1: [2, 2]},chromosomes=[[0,1,0],[0,1,0]], … best_path=[], best_distance=float(“inf”)) ([0.17677669529663687, 0.17677669529663687], [0, 1, 0], 5.656854249492381) >>> fitness(cities={}, chromosomes=[[0,1,0]], … best_path=[], best_distance=float(“inf”)) Traceback (most recent call last): … KeyError: 0 >>> fitness(cities={0: [0, 0], 1: [2, 2]},chromosomes=[], … best_path=[], best_distance=float(“inf”)) ([], [], inf)

genetic_algorithm.travelling_salesman_problem.init(cities: dict[int, list[int]], population_size: int) → tuple[list[list[int]], list[int]]

Initialization generates initial population >>> init(cities={0: [0, 0], 1: [2, 2]}, population_size=2) ([[0, 1, 0], [0, 1, 0]], [1]) >>> init(cities={0: [0, 0], 1: [2, 2]}, population_size=0) ([], [1]) >>> init(cities={},population_size=2) Traceback (most recent call last): … IndexError: list assignment index out of range

genetic_algorithm.travelling_salesman_problem.main(cities: dict[int, list[int]], population_size: int, iterations_num: int, crossover_probability: float, mutation_probability: float) → tuple[list[int], float]

Genetic algorithm main function

The algorithm is stochastic, so seed random and assert invariants of the returned tour rather than one exact ordering (not reproducible across platforms / Python versions).

>>> import random
>>> random.seed(0)
>>> path, best = main(cities=cities, population_size=100, iterations_num=100,
...     crossover_probability=0.6, mutation_probability=0.2)
>>> path[0] == 0 and path[-1] == 0  # starts and ends at the origin city
True
>>> sorted(path[:-1]) == sorted(cities)  # every city visited exactly once
True
>>> 37 <= best < 45  # converges close to the optimal round-trip (~37.9)
True
>>> main(cities={0: [0, 0], 1: [2, 2]}, population_size=10, iterations_num=10,
...     crossover_probability=0.6, mutation_probability=0.2)
([0, 1, 0], 5.656854249492381)
>>> main(cities={},population_size=10,iterations_num=10,
... crossover_probability=0.6,mutation_probability=0.2)
Traceback (most recent call last):
  ...
IndexError: list assignment index out of range

genetic_algorithm.travelling_salesman_problem.mutate(chromosome: list[int], mutation_probability: float) → list[int]

Population variation: swap two interior cities (endpoints stay at 0).

>>> mutate([0, 1, 0], mutation_probability=0)  # no mutation -> unchanged
[0, 1, 0]
>>> import random
>>> random.seed(1)
>>> mutate([0, 1, 2, 3, 0], mutation_probability=1)  # swaps two interior cities
[0, 2, 1, 3, 0]

An empty chromosome has no interior cities to swap; match only the exception type since the exact stdlib message changes across Python versions.

>>> mutate([], mutation_probability=1)
Traceback (most recent call last):
...
ValueError

genetic_algorithm.travelling_salesman_problem.cities