genetic_algorithm.travelling_salesman_problem ============================================= .. py:module:: genetic_algorithm.travelling_salesman_problem .. autoapi-nested-parse:: 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 ---------- .. autoapisummary:: genetic_algorithm.travelling_salesman_problem.cities Functions --------- .. autoapisummary:: genetic_algorithm.travelling_salesman_problem.chose_rws genetic_algorithm.travelling_salesman_problem.chose_ts genetic_algorithm.travelling_salesman_problem.crossing genetic_algorithm.travelling_salesman_problem.distance genetic_algorithm.travelling_salesman_problem.fitness genetic_algorithm.travelling_salesman_problem.init genetic_algorithm.travelling_salesman_problem.main genetic_algorithm.travelling_salesman_problem.mutate Module Contents --------------- .. py:function:: 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] .. py:function:: 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 .. py:function:: 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]) .. py:function:: 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 .. py:function:: 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) .. py:function:: 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 .. py:function:: 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 .. py:function:: 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) # doctest: +IGNORE_EXCEPTION_DETAIL Traceback (most recent call last): ... ValueError .. py:data:: cities