Code editing task: genetic_algorithm_2
Topic: DSA; change kind: perfective
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):
    mutated = route.copy()
    if (random.random() < mutation_rate):
        i1 = random.randint(0, len(route) - 1)
        i2 = random.randint(0, len(route) - 1)
        mutated[i1], mutated[i2] = route[i2], route[i1]
    return mutated

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

Instruction (descriptive):
Edit the genetic algorithm to guarantee that two random Cities in the list are swapped if the generated number between 0 and 1 is below the stated threshold specified in the `mutation` method.

Instruction (lazy):
Edit the genetic algorithm to guarantee mutation if the generated number is below the stated threshhold.

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):
    mutated = route.copy()
    if (random.random() < mutation_rate):
        i1 = random.randint(0, len(route) - 1)
        i2 = random.randint(0, len(route) - 1)
        while i2 == i1:
            i2 = random.randint(0, len(route) - 1)
        mutated[i1], mutated[i2] = route[i2], route[i1]
    return mutated

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
    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)]]

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

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

    # checking that mutation at 100% chance will always produce a mutation

    mutation_cities = generate_cities(5)
    mutation_test = generate_population(mutation_cities, 1)[0]

    for i in range(10000):
        diff = mutate(mutation_test, 1)
        assert diff != mutation_test

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