import math
import numpy as np
import matplotlib.pyplot as plt
from matplotlib.animation import FuncAnimation
from IPython.display import HTML

# 城市坐标
coordinates = [(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)]


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


# 计算城市间距离，构建完整图
num_cities = len(coordinates)
distance_matrix = [[dist(coordinates[i], coordinates[j])
                    for j in range(num_cities)] for i in range(num_cities)]

# 种群大小
POPULATION_SIZE = 100
# 交叉概率
CROSSOVER_RATE = 0.8
# 变异概率
MUTATION_RATE = 0.1
# 繁殖代数
NUM_GENERATIONS = 500


def init_population():
    population = []


for i in range(POPULATION_SIZE):
    path = list(range(num_cities))
    np.random.shuffle(path)
    population.append(path)
return population


def fitness(path):
    length = sum(distance_matrix[path[i]][path[i+1]]
                 for i in range(num_cities-1))
    length += distance_matrix[path[-1]][path[0]]


return 1 / length


def selection(population):
    fits = [fitness(path) for path in population]
    fits_sum = sum(fits)
    prob = [fit / fits_sum for fit in fits]
    index = np.random.choice(POPULATION_SIZE, size=POPULATION_SIZE, p=prob)


return [population[i] for i in index]


def crossover(parent1, parent2):
    if np.random.rand() > CROSSOVER_RATE:
        return parent1
        child = [-1] * num_cities
        indexes = set()


while len(indexes) <= num_cities // 2:
    indexes.add(np.random.randint(num_cities))
for i in indexes:
    child[i] = parent1[i]
    index_parent2 = 0
for i in range(num_cities):
    if child[i] == -1:
        while parent2[index_parent2] in child:
            index_parent2 += 1
            if index_parent2 >= num_cities:
                index_parent2 = 0
                child[i] = parent2[index_parent2]
                index_parent2 += 1
                return child


def mutation(path):

    # “”“变异操作”“”
if np.random.rand() > MUTATION_RATE:
    return path
index1, index2 = np.random.choice(num_cities, size=2, replace=False)
path[index1], path[index2] = path[index2], path[index1]
return path


def genetic_algorithm():

    # “”“遗传算法求解TSP问题”“”
population = init_population()
best_path = None
best_fitness = 0
fitness_list = []
for gen in range(NUM_GENERATIONS):
    offspring = []
for i in range(POPULATION_SIZE // 2):
    parent1, parent2 = np.random.choice(population, size=2, replace=False)
# 交叉
child1 = crossover(parent1, parent2)
child2 = crossover(parent2, parent1)
# 变异
child1 = mutation(child1)
child2 = mutation(child2)
offspring.append(child1)
offspring.append(child2)
# 合并父代和子代，保留最优染色体
population = selection(population + offspring)
fits = [fitness(path) for path in population]
best_index = np.argmax(fits)
if fits[best_index] > best_fitness:
    best_path = population[best_index]
    best_fitness = fits[best_index]
    fitness_list.append(best_fitness)
return best_path, fitness_list

# 求解TSP问题
best_path, fitness_list = genetic_algorithm()

# 绘制适应度函数的进化曲线
plt.plot(fitness_list)
plt.title('Fitness over generations')
plt.xlabel('Generation')
plt.ylabel('Fitness')
plt.show()

# 绘图函数


def plot_path(path):


x = [coordinates[i][0] for i in path]
y = [coordinates[i][1] for i in path]
x.append(x[0])
y.append(y[0])
plt.plot(x, y, '->')
plt.plot(x[0], y[0], 'ro')
plt.title('Path')

# 动态展示路径变化过程
fig, ax = plt.subplots()
def update(i):


ax.clear()
plot_path(best_path[:i+1])
ani = FuncAnimation(fig, update, frames=len(best_path)-1, interval=50)
HTML(ani.to_jshtml())

# 绘制最终路径图
plot_path(best_path)
plt.savefig('yichuan1.png')
plt.show()

给出以上代码正确格式