以下是一个使用Python实现遗传算法进行路径优化（旅行商问题，TSP）的示例代码： ```python import numpy as np import random import matplotlib.pyplot as plt # 城市坐标 cities = np.array([ [60, 200], [180, 200], [80, 180], [140, 180], [20, 160], [100, 160], [200, 160], [140, 140], [40, 120], [100, 120], [180, 100], [60, 80], [120, 80], [180, 60], [20, 40], [100, 40], [200, 40], [20, 20], [60, 20], [160, 20] ]) # 计算路径的总距离 def calculate_distance(path): total_distance = 0 for i in range(len(path) - 1): total_distance += np.linalg.norm(cities[path[i]] - cities[path[i + 1]]) total_distance += np.linalg.norm(cities[path[-1]] - cities[path[0]]) return total_distance # 初始化种群 def initialize_population(population_size, num_cities): population = [] for _ in range(population_size): individual = list(range(num_cities)) random.shuffle(individual) population.append(individual) return population # 选择操作 def selection(population, fitness_scores): total_fitness = sum(fitness_scores) selection_probs = [score / total_fitness for score in fitness_scores] selected_indices = np.random.choice(len(population), size=len(population), p=selection_probs) selected_population = [population[i] for i in selected_indices] return selected_population # 交叉操作 def crossover(parent1, parent2): start, end = sorted(random.sample(range(len(parent1)), 2)) child = [-1] * len(parent1) child[start:end] = parent1[start:end] remaining = [city for city in parent2 if city not in child[start:end]] index = 0 for i in range(len(child)): if child[i] == -1: child[i] = remaining[index] index += 1 return child # 变异操作 def mutation(individual, mutation_rate): if random.random() < mutation_rate: index1, index2 = random.sample(range(len(individual)), 2) individual[index1], individual[index2] = individual[index2], individual[index1] return individual # 遗传算法主函数 def genetic_algorithm(population_size, num_generations, mutation_rate): num_cities = len(cities) population = initialize_population(population_size, num_cities) best_path = None best_distance = float('inf') best_distances = [] for _ in range(num_generations): fitness_scores = [1 / calculate_distance(path) for path in population] selected_population = selection(population, fitness_scores) new_population = [] for i in range(0, population_size, 2): parent1 = selected_population[i] parent2 = selected_population[i + 1] child1 = crossover(parent1, parent2) child2 = crossover(parent2, parent1) child1 = mutation(child1, mutation_rate) child2 = mutation(child2, mutation_rate) new_population.extend([child1, child2]) population = new_population for path in population: distance = calculate_distance(path) if distance < best_distance: best_distance = distance best_path = path best_distances.append(best_distance) return best_path, best_distance, best_distances # 参数设置 population_size = 100 num_generations = 200 mutation_rate = 0.02 # 运行遗传算法 best_path, best_distance, best_distances = genetic_algorithm(population_size, num_generations, mutation_rate) # 输出结果 print("最优路径:", best_path) print("最短距离:", best_distance) # 绘制最优路径 plt.figure(figsize=(10, 5)) plt.subplot(1, 2, 1) plt.scatter(cities[:, 0], cities[:, 1], color='red') for i in range(len(best_path) - 1): plt.plot([cities[best_path[i]][0], cities[best_path[i + 1]][0]], [cities[best_path[i]][1], cities[best_path[i + 1]][1]], 'b-') plt.plot([cities[best_path[-1]][0], cities[best_path[0]][0]], [cities[best_path[-1]][1], cities[best_path[0]][1]], 'b-') plt.title('最优路径') # 绘制距离变化曲线 plt.subplot(1, 2, 2) plt.plot(best_distances) plt.title('每代最优距离变化') plt.xlabel('代数') plt.ylabel('距离') plt.tight_layout() plt.show() ``` 这段代码实现了一个基本的遗传算法来解决旅行商问题（TSP），通过初始化种群、选择、交叉、变异等操作，不断迭代找到最优路径。代码中包含了路径距离的计算、种群的初始化、选择、交叉、变异等核心操作，并最终输出最优路径和最短距离，同时绘制了最优路径和每代最优距离的变化曲线。