写一个Python实现的遗传算法求解TSP问题的示例代码

以下是一个Python实现的遗传算法求解TSP问题的示例代码：

import random
import math

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

    def distance(self, city):
        x_dist = abs(self.x - city.x)
        y_dist = abs(self.y - city.y)
        distance = math.sqrt((x_dist ** 2) + (y_dist ** 2))
        return distance

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

    def calculate_distance(self):
        tour_distance = 0
        for i in range(len(self.cities)):
            from_city = self.cities[i]
            to_city = None
            if i + 1 < len(self.cities):
                to_city = self.cities[i + 1]
            else:
                to_city = self.cities[0]
            tour_distance += from_city.distance(to_city)
        self.distance = tour_distance
        return tour_distance

    def calculate_fitness(self):
        tour_distance = self.calculate_distance()
        self.fitness = 1 / float(tour_distance)
        return self.fitness

class Population:
    def __init__(self, tour_list, population_size, elitism):
        self.tour_list = tour_list
        self.population_size = population_size
        self.elitism = elitism
        self.population = []

    def create_population(self):
        for i in range(self.population_size):
            tour_order = random.sample(self.tour_list, len(self.tour_list))
            tour = Tour(tour_order)
            self.population.append(tour)

    def get_fittest(self):
        fittest = self.population[0]
        for i in range(1, len(self.population)):
            if fittest.fitness < self.population[i].fitness:
                fittest = self.population[i]
        return fittest

    def get_second_fittest(self):
        fittest = self.population[0]
        second_fittest = self.population[1]
        for i in range(1, len(self.population)):
            if self.population[i].fitness > fittest.fitness:
                second_fittest = fittest
                fittest = self.population[i]
            elif self.population[i].fitness > second_fittest.fitness:
                second_fittest = self.population[i]
        return second_fittest

    def get_least_fittest(self):
        least_fittest = self.population[0]
        for i in range(1, len(self.population)):
            if least_fittest.fitness > self.population[i].fitness:
                least_fittest = self.population[i]
        return least_fittest

    def tournament_selection(self):
        tournament = Population([], len(self.tour_list), 0)
        for i in range(self.elitism):
            tournament.population.append(self.population[i])
        for i in range(self.elitism, self.population_size):
            tournament.population.append(random.choice(self.population))
        return tournament.get_fittest()

    def crossover(self, parent1, parent2):
        child = Tour([None] * len(parent1.cities))
        start_pos = random.randint(0, len(parent1.cities) - 1)
        end_pos = random.randint(0, len(parent1.cities) - 1)
        for i in range(len(child.cities)):
            if start_pos < end_pos and i > start_pos and i < end_pos:
                child.cities[i] = parent1.cities[i]
            elif start_pos > end_pos:
                if not (i < start_pos and i > end_pos):
                    child.cities[i] = parent1.cities[i]
        for i in range(len(parent2.cities)):
            if parent2.cities[i] not in child.cities:
                for j in range(len(child.cities)):
                    if child.cities[j] is None:
                        child.cities[j] = parent2.cities[i]
                        break
        return child

    def mutation(self, tour):
        for i in range(len(tour.cities)):
            if random.random() < 0.01:
                j = random.randint(0, len(tour.cities) - 1)
                tour.cities[i], tour.cities[j] = tour.cities[j], tour.cities[i]

def genetic_algorithm(tour_list, population_size, elitism):
    population = Population(tour_list, population_size, elitism)
    population.create_population()

    generation = 0
    while True:
        fittest = population.get_fittest()
        print("Generation %d: Distance = %f" % (generation, fittest.distance))

        if fittest.distance == 0:
            break

        new_population = Population(tour_list, population_size, elitism)

        new_population.population.append(fittest)

        for i in range(1, population_size):
            parent1 = population.tournament_selection()
            parent2 = population.tournament_selection()
            child = population.crossover(parent1, parent2)
            new_population.population.append(child)

        for i in range(elitism, population_size):
            new_population.mutation(new_population.population[i])

        population = new_population
        generation += 1

    return fittest

使用示例：

city_list = [
    City(60, 200),
    City(180, 200),
    City(80, 180),
    City(140, 180),
    City(20, 160),
    City(100, 160),
    City(200, 160),
    City(140, 140),
    City(40, 120),
    City(100, 120),
    City(180, 100),
    City(60, 80),
    City(120, 80),
    City(180, 60),
    City(20, 40),
    City(100, 40),
    City(200, 40),
    City(20, 20),
    City(60, 20),
    City(160, 20),
]

genetic_algorithm(city_list, 100, 10)