首先，旅行商问题可以转化为图论中的TSP问题，我们将城市之间的距离计算出来，构建完整图。

代码如下：

import math

# 城市坐标
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)]

接下来，我们可以使用遗传算法求解旅行商问题。我们将每个可能的路线视为一个染色体，每个城市为基因，采用交叉和变异操作进行进化。同时，我们选择路径长度的倒数作为染色体的适应度函数进行选择，使得越短的路径被选择的概率越大。

代码如下：

import numpy as np

# 种群大小
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()

最后，我们可以绘制适应度函数的进化曲线、线路的动态变化过程及最终的线路图。

代码如下：

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

# 绘制适应度函数的进化曲线
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.show()

完整代码如下：