Code editing task: genetic_algorithm
Topic: DSA; change kind: corrective
Libraries: numpy

Original code:
import numpy as np
import random
import math

random.seed(100)

class City:

    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __repr__(self):
        return f"({self.x}, {self.y})"

    def __eq__(self, other):
        if isinstance(other, City):
            return self.x == other.x and self.y == other.y
        return False

    def __hash__(self) -> int:
        return self.__repr__().__hash__()

def generate_cities(num_cities):
    cities = []
    for _ in range(num_cities):
        cities.append(City(random.randint(0, 10), random.randint(0, 10)))
    return cities
    
def distance(this, that):
    return np.sqrt((this.x - that.x)**2 + (this.y - that.y)**2)
    
def calculate_fitness(route):
    d = 0
    for i in range(len(route)):
        if i + 1 == len(route):
            d += distance(route[i], route[0])
        else:
            d += distance(route[i], route[i + 1])
    return 1 / d

def generate_population(cities, population_size):
    routes = []
    for _ in range(population_size):
        routes.append(random.sample(cities, len(cities)))
    return routes

def tournament_selection(population, tournament_size=3):
    indices = random.sample(range(len(population)), tournament_size)
    fitnesses = [calculate_fitness(population[i]) for i in indices]
    best_index = indices[fitnesses.index(max(fitnesses))]
    return population[best_index]

def mutate(route, mutation_rate=0.1):
    if (random.random() < mutation_rate):
        i1 = random.randint(0, len(route) - 1)
        i2 = random.randint(0, len(route) - 1)
        route[i1], route[i2] = route[i2], route[i1]
    return route

def get_crossing_point(parent1):
    return random.randint(1, len(parent1) - 1)

def crossover(parent1, parent2):
    crossover_point = get_crossing_point(parent1)
    child = parent1[:crossover_point] + parent2[crossover_point:]
    return child

def next_generation(population, crossover_rate, mutation_rate):

    next_pop = []

    cross = math.floor(len(population) * crossover_rate)
    normal = len(population) - cross

    for _ in range(normal):
        next_pop.append(random.choice(population))

    for _ in range(cross):
        parent1 = tournament_selection(population)
        parent2 = tournament_selection(population)
        next_pop.append(crossover(parent1, parent2))

    next_pop = [mutate(p, mutation_rate) for p in next_pop]

    return next_pop

Instruction (descriptive):
Edit the genetic algorithm to not generate any routes with repeating cities when calling `next_generation`.

Instruction (lazy):
Edit the code to not generate any routes with repeating cities in any generation.

Edited code:
import numpy as np
import random
import math

random.seed(100)

class City:

    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __repr__(self):
        return f"({self.x}, {self.y})"
    
    def __eq__(self, other):
        if isinstance(other, City):
            return self.x == other.x and self.y == other.y
        return False
    
    def __hash__(self) -> int:
        return self.__repr__().__hash__()

def generate_cities(num_cities):
    cities = []
    for _ in range(num_cities):
        cities.append(City(random.randint(0, 10), random.randint(0, 10)))
    return cities
    
def distance(this, that):
    return np.sqrt((this.x - that.x)**2 + (this.y - that.y)**2)
    
def calculate_fitness(route):
    d = 0
    for i in range(len(route)):
        if i + 1 == len(route):
            d += distance(route[i], route[0])
        else:
            d += distance(route[i], route[i + 1])
    return 1 / d

def generate_population(cities, population_size):
    routes = []
    for _ in range(population_size):
        routes.append(random.sample(cities, len(cities)))
    return routes

def tournament_selection(population, tournament_size=3):
    indices = random.sample(range(len(population)), tournament_size)
    fitnesses = [calculate_fitness(population[i]) for i in indices]
    best_index = indices[fitnesses.index(max(fitnesses))]
    return population[best_index]

def mutate(route, mutation_rate=0.1):
    if (random.random() < mutation_rate):
        i1 = random.randint(0, len(route) - 1)
        i2 = random.randint(0, len(route) - 1)
        route[i1], route[i2] = route[i2], route[i1]
    return route

def get_crossing_point(parent1):
    return random.randint(1, len(parent1) - 1)

def crossover(parent1, parent2):
    crossover_point = get_crossing_point(parent1)
    child = parent1[:crossover_point]
    for city in parent2:
        if city not in child:
            child.append(city)
    return child

def next_generation(population, crossover_rate, mutation_rate):

    next_pop = []

    cross = math.floor(len(population) * crossover_rate)
    normal = len(population) - cross

    for _ in range(normal):
        next_pop.append(random.choice(population))

    for _ in range(cross):
        parent1 = tournament_selection(population)
        parent2 = tournament_selection(population)
        next_pop.append(crossover(parent1, parent2))

    next_pop = [mutate(p, mutation_rate) for p in next_pop]

    return next_pop

Tests:
### START TESTS ###
if True:  # pragma: no cover
    # checking that nothing that shouldn't change has changed

    cities = generate_cities(10)

    assert cities == [City(2, 7), City(7, 2), City(6, 5), City(6, 8), City(1, 8), City(1, 1), City(7, 4), City(0, 10), City(10, 3), City(5, 3)]

    assert distance(cities[0], cities[1]) == distance(cities[1], cities[0])
    assert distance(cities[0], City(2, 0)) == 7
    assert distance(cities[9], City(8, 7)) == 5

    population = generate_population(cities, 5)
    assert population[1] == [City(x, y) for x, y in [(7, 4), (0, 10), (1, 8), (5, 3), (6, 8), (7, 2), (2, 7), (1, 1), (6, 5), (10, 3)]]
    assert population[4] == [City(x, y) for x, y in [(10, 3), (1, 1), (0, 10), (6, 8), (2, 7), (5, 3), (6, 5), (7, 4), (7, 2), (1, 8)]]

    p1 = tournament_selection(population)
    p2 = tournament_selection(population)

    assert p1 == [City(x, y) for x, y in [(7, 4), (0, 10), (1, 8), (5, 3), (6, 8), (7, 2), (2, 7), (1, 1), (6, 5), (10, 3)]]
    assert p2 == [City(x, y) for x, y in [(1, 8), (6, 8), (6, 5), (7, 2), (7, 4), (0, 10), (5, 3), (10, 3), (1, 1), (2, 7)]]

    afterpop1 = [City(x, y) for x, y in [(7, 4), (0, 10), (1, 8), (5, 3), (6, 8), (10, 3), (2, 7), (1, 1), (6, 5), (7, 2)]]
    assert mutate(population[1]) == afterpop1

    afterp2 = [City(x, y) for x, y in [(1, 8), (6, 8), (6, 5), (7, 2), (7, 4), (0, 10), (5, 3), (10, 3), (1, 1), (2, 7)]]
    assert mutate(p2) == afterp2

    afterp1 = [City(x, y) for x, y in [(10, 3), (1, 1), (0, 10), (6, 8), (2, 7), (5, 3), (6, 5), (7, 4), (7, 2), (1, 8)]]
    assert mutate(population[4]) == afterp1

    assert get_crossing_point(p1) == 2
    assert get_crossing_point(afterp1) == 1

    # checking crossover and next_generation, check no repeat cities in children

    next_gen = next_generation(population, 0.8, 0.2)
    city_set = set(cities)

    for individual in next_gen:
        assert set(individual) == city_set

    city = City(1, 1)
    assert city == City(1, 1)
    assert city != City(1, 2)
    assert city != City(2, 1)
    assert city != 4