import math
import random
import matplotlib.pyplot as plt

CITY_COORDS = [
    (16.47, 96.1),
    (16.47, 94.44),
    (20.09, 92.54),
    (22.39, 93.37),
    (25.23, 97.24),
    (17.2, 96.29),
    (16.3, 97.38),
    (14.05, 98.12),
    (16.53, 97.38),
    (21.52, 95.59)
]

POPULATION_SIZE = 1000
ELITISM = 0.1
MUTATION_RATE = 0.1
NUM_GENERATIONS = 500


class Individual:
    def __init__(self, chromosome):
        self.chromosome = chromosome
        self.fitness = self.calculate_fitness()

    def calculate_fitness(self):
        total_distance = 0
        for i in range(len(self.chromosome) - 1):
            total_distance += self.get_distance(
                CITY_COORDS[self.chromosome[i]], CITY_COORDS[self.chromosome[i+1]])
        total_distance += self.get_distance(
            CITY_COORDS[self.chromosome[-1]], CITY_COORDS[self.chromosome[0]])
        return 1 / total_distance

    def get_distance(self, city1, city2):
        return math.sqrt((city1[0] - city2[0])**2 + (city1[1] - city2[1])**2)


class Population:
    def __init__(self):
        self.individuals = [Individual(self.generate_chromosome())
                            for i in range(POPULATION_SIZE)]

    def generate_chromosome(self):
        chromosome = list(range(len(CITY_COORDS)))
        random.shuffle(chromosome)
        return chromosome

    def evolve(self):
        next_generation = []
        num_elites = int(POPULATION_SIZE * ELITISM)
        elites = self.select_elites(num_elites)
        next_generation.extend(elites)

        while len(next_generation) < POPULATION_SIZE:
            parent1, parent2 = self.select_parents()
            child1, child2 = self.crossover(parent1, parent2)
            next_generation.extend([child1, child2])

        self.individuals = next_generation

    def select_elites(self, num_elites):
        sorted_individuals = sorted(
            self.individuals, key=lambda i: i.fitness, reverse=True)
        return sorted_individuals[:num_elites]

    def select_parents(self):
        parent1 = self.tournament_selection()
        parent2 = self.tournament_selection()
        return parent1, parent2

    def tournament_selection(self):
        candidates = random.sample(self.individuals, 5)
        return max(candidates, key=lambda i: i.fitness)

    def crossover(self, parent1, parent2):
        point1 = random.randint(0, len(CITY_COORDS) - 2)
        point2 = random.randint(point1, len(CITY_COORDS) - 1)

        child1_chromosome = self.get_child_chromosome(
            parent1.chromosome, parent2.chromosome, point1, point2)
        child2_chromosome = self.get_child_chromosome(
            parent2.chromosome, parent1.chromosome, point1, point2)

        child1 = Individual(child1_chromosome)
        child2 = Individual(child2_chromosome)

        return child1, child2

    def get_child_chromosome(self, parent1_chromosome, parent2_chromosome, point1, point2):
        child_chromosome = [-1] * len(parent1_chromosome)

        for i in range(point1, point2+1):
            child_chromosome[i] = parent1_chromosome[i]

        parent2_index = 0
        for i in range(len(child_chromosome)):
            if child_chromosome[i] == -1:
                while parent2_chromosome[parent2_index] in child_chromosome:
                    parent2_index += 1
                child_chromosome[i] = parent2_chromosome[parent2_index]
                parent2_index += 1

        return child_chromosome

    def mutate(self):
        for individual in self.individuals:
            if random.random() < MUTATION_RATE:
                self.mutate_individual(individual)

    def mutate_individual(self, individual):
        point1 = random.randint(0, len(CITY_COORDS) - 1)
        point2 = random.randint(0, len(CITY_COORDS) - 1)
        individual.chromosome[point1], individual.chromosome[point2] = individual.chromosome[point2], individual.chromosome[point1]


def plot_fitness(fitness_values):
    plt.plot(list(range(len(fitness_values))), fitness_values, 'b-')
    plt.xlabel('Generation')
    plt.ylabel('Fitness')
    plt.show()


def plot_individual(individual):
    plt.clf()
    x_coords = [CITY_COORDS[i][0] for i in individual.chromosome]
    y_coords = [CITY_COORDS[i][1] for i in individual.chromosome]
    x_coords.append(x_coords[0])
    y_coords.append(y_coords[0])
    plt.plot(x_coords, y_coords, 'ro-')
    plt.xlim([min(x_coords) - 1, max(x_coords) + 1])
    plt.ylim([min(y_coords) - 1, max(y_coords) + 1])
    plt.title('Fitness: {}'.format(individual.fitness))
    plt.pause(0.01)


if __name__ == '__main__':
    population = Population()
    fitness_values = []
    for i in range(NUM_GENERATIONS):
        population.evolve()
        population.mutate()
        best_individual = max(population.individuals, key=lambda i: i.fitness)
        fitness_values.append(best_individual.fitness)
        plot_individual(best_individual)
plot_fitness(fitness_values)
以上代码没有输出结果