Python Genetic Algorithm: Traveling Salesman Problem Solver

import random
import math

class Individual:
    def __init__(self, cities):
        self.cities = cities
        self.fitness = 0

    def calculate_fitness(self):
        total_distance = 0
        for i in range(len(self.cities)):
            current_city = self.cities[i]
            next_city = self.cities[(i + 1) % len(self.cities)]
            distance = calculate_distance(current_city, next_city)
            total_distance += distance
        self.fitness = 1 / total_distance

def calculate_distance(city1, city2):
    x1, y1 = city1
    x2, y2 = city2
    distance = math.sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)
    return distance

def create_initial_population(city_list, population_size):
    population = []
    for _ in range(population_size):
        cities = random.sample(city_list, len(city_list))
        individual = Individual(cities)
        individual.calculate_fitness()
        population.append(individual)
    return population

def evolve_population(population, elite_size, mutation_rate):
    elite = select_elite(population, elite_size)
    offspring = crossover_population(elite, population)
    population = mutate_population(offspring, mutation_rate)
    return population

def select_elite(population, elite_size):
    sorted_population = sorted(population, key=lambda individual: individual.fitness, reverse=True)
    return sorted_population[:elite_size]

def crossover_population(elite, population):
    offspring = elite
    non_elite_size = len(population) - len(elite)
    non_elite = random.sample(population, non_elite_size)
    offspring += non_elite
    return offspring

def mutate_population(population, mutation_rate):
    for individual in population:
        if random.random() < mutation_rate:
            index1 = random.randint(0, len(individual.cities) - 1)
            index2 = random.randint(0, len(individual.cities) - 1)
            individual.cities[index1], individual.cities[index2] = individual.cities[index2], individual.cities[index1]
            individual.calculate_fitness()
    return population

# Main genetic algorithm function
def genetic_algorithm(city_list, population_size, elite_size, mutation_rate, generations):
    population = create_initial_population(city_list, population_size)
    print("Initial distance: " + str(1 / max(population, key=lambda individual: individual.fitness).fitness))

    for _ in range(generations):
        population = evolve_population(population, elite_size, mutation_rate)

    best_individual = max(population, key=lambda individual: individual.fitness)
    print("Final distance: " + str(1 / best_individual.fitness))
    return best_individual

# Usage example
city_list = [(x, y) for x in range(10) for y in range(10)]
population_size = 100
elite_size = 20
mutation_rate = 0.01
generations = 100

best_route = genetic_algorithm(city_list, population_size, elite_size, mutation_rate, generations)
print("Best route:", best_route.cities)