### 使用Python求解TSP问题 #### 遗传算法求解TSP问题 遗传算法是一种模拟自然选择过程的全局优化技术，适合处理复杂的组合优化问题。通过编码、交叉、变异等操作逐步进化种群中的个体，最终收敛到较优解。 ```python import random import numpy as np from deap import base, creator, tools, algorithms def create_individual(cities): individual = list(range(len(cities))) random.shuffle(individual) return individual def evaluate_tour(tour, distance_matrix): total_distance = sum(distance_matrix[tour[i]][tour[(i+1)%len(tour)]] for i in range(len(tour))) return (total_distance,) creator.create("FitnessMin", base.Fitness, weights=(-1.0,)) creator.create("Individual", list, fitness=creator.FitnessMin) toolbox = base.Toolbox() cities = [...] # 城市坐标数据 distance_matrix = [[np.linalg.norm(np.array(a)-np.array(b)) for b in cities] for a in cities] toolbox.register("individual", tools.initIterate, creator.Individual, lambda: create_individual(cities)) toolbox.register("population", tools.initRepeat, list, toolbox.individual) toolbox.register("mate", tools.cxPartialyMatched) toolbox.register("mutate", tools.mutShuffleIndexes, indpb=0.05) toolbox.register("select", tools.selTournament, tournsize=3) toolbox.register("evaluate", evaluate_tour, distance_matrix=distance_matrix) pop = toolbox.population(n=300) hof = tools.HallOfFame(1) stats = tools.Statistics(lambda ind: ind.fitness.values) stats.register("avg", np.mean) stats.register("std", np.std) stats.register("min", np.min) stats.register("max", np.max) result, logbook = algorithms.eaSimple(pop, toolbox, cxpb=0.7, mutpb=0.2, ngen=400, stats=stats, halloffame=hof, verbose=True)[^1] ``` #### 最小生成树近似方法求解TSP问题 最小生成树(MST)近似算法虽然无法保证获得最优解，但对于大多数实际情况来说已经足够好，并且计算效率较高。 ```python import networkx as nx import matplotlib.pyplot as plt G = nx.Graph() for edge in edges: G.add_edge(edge[0], edge[1], weight=edge[2]) mst = nx.minimum_spanning_tree(G) path = [] visited = set() def dfs(node): visited.add(node) path.append(node) neighbors = sorted((n for n in mst.neighbors(node) if n not in visited), key=lambda x:mst[node][x]['weight']) for neighbor in neighbors: dfs(neighbor) start_node = next(iter(mst.nodes())) dfs(start_node) if len(path)<len(list(G.nodes())): remaining_nodes=set(G.nodes())-set(path) closest_remaining=min([(node,min([nx.shortest_path_length(G,node,to_node,'weight') for to_node in path])) for node in remaining_nodes], key=lambda item:item[1])[0] insertion_point=np.argmin([nx.shortest_path_length(G,path[i],closest_remaining,'weight')+\ nx.shortest_path_length(G,closest_remaining,path[(i+1)%len(path)],'weight')- nx.shortest_path_length(G,path[i],path[(i+1)%len(path)],'weight') for i in range(len(path))]) path.insert(insertion_point+1,closest_remaining) while True: try: cycle_start=path.index(min(path,key=path.count)) del path[cycle_start:path.index(min(path[key=path.count]),cycle_start+1)] except ValueError: break plt.figure(figsize=(8,6)) pos=nx.spring_layout(G,k=0.9) nx.draw_networkx_labels(G,pos,font_size=10,font_family='sans-serif') nx.draw_networkx_edges(G,pos,alpha=0.4,width=0.5) nx.draw_networkx_edges(nx.subgraph(G,path+[path[0]]), pos=pos, edgelist=[(path[i],path[(i+1)%len(path)]) for i in range(len(path))], width=1.5, alpha=0.8, color='r', ) plt.show()[^2] ``` #### 近邻算法求解TSP问题 最近邻算法作为最简单的贪婪策略之一，在每一步都选取当前节点距离最近且未访问过的下一个节点加入路径中直到遍历完所有节点形成回路。 ```python def nearest_neighbor_algorithm(points): unvisited = points.copy() current_city = unvisited.pop(random.randint(0,len(unvisited)-1)) tour = [current_city] while unvisited: last_city = tour[-1] distances = {city : ((last_city[0]-city[0])**2+(last_city[1]-city[1])**2)**0.5 for city in unvisited} nearest_city = min(distances.items(),key=lambda kv:(kv[1],random.random()))[0] tour.append(nearest_city) unvisited.remove(nearest_city) cost=sum((((tour[i][0]-tour[j][0])**2+(tour[i][1]-tour[j][1])**2)**0.5) for i,j in zip(range(-1,len(tour)),range(len(tour)))) return {'Tour':tour,'Cost':cost}[^3]